本文主要是介绍Codeforces Round #804 (Div. 2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Codeforces Round #804 (Div. 2)

这场题感觉都挺有意思的。

A

题意

找到一组解 \((a,b,c)\) 使得 \((a \oplus b) + (b \oplus c) + (a \oplus c) = n\)

没有输出 -1

思路

先看偶数，很容易看出 \((n/2,n/2,0)\) 是合法解

对于奇数。考虑 \(n=1\) 。无解，这是可以枚举的。这等于说最低位上的 \(1\) 是无法构造合法解的，也就是奇数无解。

给出官方题解上的一个证明，用到了加法和异或的关系。

我们知道 \(a+b = a \oplus b + 2 * (a \& b)\) 。通过它可以看出 \(a+b\) 和 \(a \oplus b\) 具有相同的奇偶性。只看奇偶性的话 \((a \oplus b) + (b \oplus c) + (a \oplus c)\) 等价于 $ a+b+b+c+a+c$ 。因此 \(n\) 一定是偶数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int n; cin >> n;
    if(n & 1) {
        cout << -1 << endl;
        return ;
    }
    cout << n / 2 << " " << n / 2 << " " << 0 << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

B

题意

给 \(n *m\) 的网格染色，使得每一个格子有且仅有 \(2\) 个邻居和它不同色

思路

构造题，就挺看眼缘的。。。我们可以先构造出 \(2 * m\) 的情况，接下来每行翻转复制即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;
void solve()
{    
    int n,m; cin >> n >> m;
    int a[2][3][3];
    rep(i,1,2) rep(j,1,2) {
        if(i == j) a[0][i][j] = 1;
        else a[0][i][j] = 0;
    }
    rep(i,1,2) rep(j,1,2) {
        if(i == j) a[1][i][j] = 0;
        else a[1][i][j] = 1;
    }

    vector<vector<int>> ans(n + 1,vector<int>(m + 1));
    int op = 0;
    for(int i = 1;i <= 1;i += 2){
        for(int j = 1;j <= m;j += 2) {
            for(int k = 0;k < 2;k ++)
                for(int p = 0;p < 2;p ++) 
                    ans[i + k][j + p] = a[op][k + 1][p + 1];
            op ^= 1;
        }
    }
    
    for(int i = 1;i <= n;i += 2) {
        if((i + 1) / 2 % 2 == 0) {
            rep(j,1,2) rep(k,1,m) cout << ans[j][k] << " \n"[k == m];
        }else {
            per(j,2,1) rep(k,1,m) cout << ans[j][k] << " \n"[k == m];
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

C

题意

给一个排列 \(p\) ，求满足下列条件的排列 \(q\) 的方案数。

• \(q,p\) 的任意子段的 \(mex\) 相等。

思路

赛后看大佬一个比一个短的代码有点怀疑人生（。

先分析最小子段，有一个显然的观察，\(0\) 的位置一定不会变。

那么我们试着从这个不动点从小到大考虑。考虑一段区间覆盖 \([0,i]\) ，我们求此区间的 \(mex\) 我们发现，所有比这个 \(mex\) 小的元素不能离开这个区间，否则就会改变 \(mex\) 。我们考虑此时区间中还未安排的位置为 \(sz\) ，比 \(mex\) 小的元素为 \(cnt\) 个。安排它们对答案的贡献就是 \(A_{sz}^{cnt}\) 。需要注意的是如果遇到比 \(mex\) 大的元素要先将其存起来，当之后扩展到新的区间再继续考虑它们。

之后继续扩展区间即可求得答案。

在实现方面可以开两个 \(set\) 。一个放已被使用的元素，一个放比 \(mex\) 大的元素。因为每个集合中的元素最多被插入一次，删除一次，且每个元素在扩展区间时仅会被访问一次，时间复杂度是 \(O(nlogn)\) 的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;
int fac[MAXN],invfac[MAXN],inv[MAXN];
void init() {
    inv[1] = invfac[1] = invfac[0] = fac[1] = fac[0] = 1;
    for(int i = 2;i < MAXN;i ++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        fac[i] = fac[i - 1] * i % mod;
        invfac[i] = invfac[i - 1] * inv[i] % mod;
    }
}
int C(int n,int m) {
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int A(int n,int m) {
    return fac[n] * invfac[n - m] % mod;
}
void solve()
{    
    int n; cin >> n;
    vector<int> a(n);
    rep(i,0,n - 1) cin >> a[i];
    vector<int> id(n);
    rep(i,0,n - 1) id[a[i]] = i;
    int l = id[0],r = id[0];
    int mex = 0;
    vector<bool> st(n);
    set<int> s, big;
    s.insert(a[0]);
    st[0] = 1;
    int ans = 1;
    int sz = 0;
    rep(i,1,n - 1) {
        int t = id[i]; 
        if(t < l){
            // [l,r] -> [t,r]   [t,l - 1]
            rep(j,t,l - 1) {
                sz ++;
                int x = a[j];
                st[a[j]] = 1;
                while(st[mex]) mex ++;
            }
            int cnt = 0;
            s.insert(a[t]);
            sz --;
            rep(j,t,l - 1) {
                if(a[j] < mex && s.count(a[j]) == 0) 
                    cnt ++, s.insert(a[j]);
                else if(s.count(a[j]) == 0 && a[j] > mex)
                    big.insert(a[j]), s.insert(a[j]);
            }
            vector<int> v;
            for(auto x : big) {
                if(x > mex) break;
                if(x < mex) {
                    cnt ++;
                    v.push_back(x);
                }
            }
            for(auto x : v) big.erase(x);

            ans = (ans * A(sz,cnt)) % mod;
            sz -= cnt;
            l = t;
        } else if(t > r){ 
            rep(j,r + 1,t) {
                sz ++;
                st[a[j]] = 1;
                while(st[mex]) mex ++;
            }
            int cnt = 0;
            s.insert(a[t]);
            sz --;
            rep(j,r + 1,t) {
                if(a[j] < mex && s.count(a[j]) == 0) 
                    cnt ++, s.insert(a[j]);
                else if(s.count(a[j]) == 0 && a[j] > mex)
                    big.insert(a[j]), s.insert(a[j]);
            }
            vector<int> v;
            for(auto x : big) {
                if(x > mex) break;
                if(x < mex) {
                    cnt ++;
                    v.push_back(x);
                }
            }
            for(auto x : v) big.erase(x);

            ans = (ans * A(sz,cnt)) % mod;
            sz -= cnt;
            r = t;
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

D

题意

给一个序列 \(a\)，若 $a_i \neq a_{i + 1} $ 就可以删除它们。现在要求把序列删到所有值都相等，问最后剩下的最长长度。

思路

手玩了一下样例，感觉有点括号序列的意思，找左右括号看是否匹配，然后在歪路上越走越远···

正解应该是考虑dp。因为这是一个子序列删除问题，感觉还是很常见的。

我们定义 \(dp[i]\) 表示考虑前 \(i\) 个元素，且保留第 \(i\) 位元素的保留长度最大值

那么最后答案就是 \(max\{dp[i]\},当[i+1,n]所有元素都可删除时i可取到\) 。

考虑转移，如果前驱状态到现态中间所有元素都可以删除，那么可以有 \(dp[i] = dp[j]+1\) 的转移。

现在就需要考虑这样一个子问题：什么时候可以将一段区间中所有元素删除。

结论是当出现次数最多的元素不多于 \(\frac{len}{2}\) 且 \(len\) 为偶数时可删除。

给出如下证明：

对必要性，显然

对充分性。我们设当前出现最多数字的数量为 \(c\) ，当前长度为 \(len\) 。\((c\le len/2)\)

引入一个结论：当 \(c < len\)时， 出现最多的元素总可以找到一个和它不同的元素进行删除。（反证法）

那么我们就可以有如下的删除策略。

1. 删除出现最多的元素和一个其他元素
2. 检查新序列最大元素，删除它和其他元素
3. 重复12直到无法删除

在第2步中，查出的新的最多元素数量 \(x < c < len\) 根据引入结论，删除总是可行的。

预处理出可以可全删除的区间，之后正常做dp即可。另外需要注意的是dp数组初始化，对于 \([1,i-1]\) 全部可删，初始为 \(1\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '\n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;

void solve()
{    
    int n; cin >> n;
    vector<int> a(n + 1);
    rep(i,1,n) cin >> a[i];
    int ans = 0;
    vector<vector<int>> f(n + 1,vector<int>(n + 1));
    rep(i,1,n) {
        vector<int> cnt(n + 1);
        int mx = 0;
        rep(j,i,n) {
            mx = max(mx , ++ cnt[a[j]]);
            if((j - i + 1) % 2 == 0 && 2 * mx <= j - i + 1)
                f[i][j] = 1;
        }
    }
    vector<int> dp(n + 1,-linf);

    // dp[i] = max dp[j] + 1   dp[0] ?
    dp[0] = 0;
    dp[1] = 1;
    rep(i,2,n) if(f[1][i - 1]) dp[i] = 1;
    rep(i,1,n) {
        rep(j,1,i - 1) {
            if(a[i] == a[j] && (f[j + 1][i - 1] || j + 1 > i - 1)){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    rep(i,1,n - 1) if(f[i + 1][n]) ans = max(ans, dp[i]);
    cout << max(ans, dp[n]) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

这篇关于Codeforces Round #804 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！