Codeforces Round (2022-07-04)

Codeforces Round #804 (Div. 2)

A. The Third Three Number Problem

题目链接

题意

给定 $n$ ，找三个非负整数 $a,b,c$ ，使 $(a\oplus b)+(b\oplus c)+(a\oplus c)=n$ 。找不到就输出 -1。

思路

看二进制的同一位，三个数要么全相同，三个异或结果在这一位都是 0；要么有一个不同，就会出现两个 1。所以总和一定是偶数，奇数直接无解。

偶数时取 $a=b=0,c=n/2$ ，三个异或结果就是 $0,n/2,n/2$ ，加起来正好是 $n$ 。

代码

#include <bits/stdc++.h>
using namespace std;

int n;

int main() {
    cin >> n;
    while(n--) {
        int x;
        cin >> x;
        if(x & 1) cout << "-1" << endl;
        else {
            cout << "0 0 " << (x >> 1) << endl;
        }
    }
    return 0;
}

B. Almost Ternary Matrix

题目链接

题意

给定偶数行、偶数列的网格，填入 0 和 1。要求每个格子恰好有两个相邻格子的值与它不同，只算上下左右。

思路

按 $2\times2$ 分块，每块里面交错填 0 和 1。这样每个格子在自己块里就有两个不同的邻居。

相邻块的朝向再翻一下，让跨块边界两侧相等，就不会多出第三个不同的邻居。代码里根据左边或上面的值决定当前块的左上角，其余三个位置跟着填就行。

代码

#include <bits/stdc++.h>
using namespace std;

int T, n, m;
int a[100][100];

void w(int o, int i, int j) {
    a[i][j] = a[i + 1][j + 1] = o;
    a[i + 1][j] = a[i][j + 1] = (1 - o);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i += 2) {
            for(int j = 1; j <= m; j += 2) {
                if(j == 1) w(a[i - 1][j], i, j);
                else w(a[i][j - 1], i, j);
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) printf("%d%c", a[i][j], " \n"[j == m]);
        }
    }
    return 0;
}

C. The Third Problem

题目链接

题意

给定一个 $0$ 到 $n-1$ 的排列 $a$ 。求有多少个排列 $b$ ，使任意相同下标区间在两个排列里的 MEX 都相同，答案模 $10^9+7$ 。MEX 就是区间里没有出现的最小非负整数。

思路

从小到大放数，维护前面这些数覆盖的最小区间 $[l,r]$ 。当前数 $i$ 如果在区间外，它的位置就必须固定，否则某个区间的 MEX 会变。

如果它在区间里面，包含前面所有小数的区间也一定包含它，所以可以放在 $[l,r]$ 内任何还空着的位置。把空位数乘进答案，再标记当前位置、更新左右边界。

这里用树状数组数已经放了多少个数，时间是 $O(n\log n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 17;
int T, n, ans, l, r;
int a[maxn], p[maxn], t[maxn];
const int mod = 1e9 + 7;

void add(int x) {
    for(; x <= n; x += (x & -x)) t[x]++;
}

int cal(int x) {
    int res = 0;
    for(; x; x -= (x & -x)) res += t[x];
    return res;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            p[a[i]] = i;
        }
        ans = 1, l = n + 1, r = 0;
        for(int i = 0; i < n; i++) {
            if(p[i] > l && p[i] < r) {
                ans = 1ll * ans * (r - l - (cal(r) - cal(l))) % mod;
                // cout <<r << " " << l << " " <<  i<< " " << ans << endl;
            }
            add(p[i]);
            l = min(l, p[i]);
            r = max(r, p[i]);
        }
        printf("%d\n", ans);
        for(int i = 0; i <= n; i++) t[i] = 0;
    }
    return 0;
}

D. Almost Triple Deletions

题目链接

题意

每次可以删掉一对相邻且不同的数，剩余两边会接起来。求最后只剩一种数时，数组最多能有多长，也可以删成空数组。

思路

还是看最后要保留哪些相同的数。它们之间的间隔，以及首尾剩下的部分，都得能完全删空；不能把每一小段的代价直接相加，因为中间某个同值元素也可能需要一起删掉。

一段能删空，当且仅当长度是偶数，而且出现最多的数不超过一半。否则最多的那种数找不到足够的其他数配对；满足条件时，每次拿一个最多的数和不同的邻居配对，就能继续删下去。

f[i] 表示保留 $a_i$ 作为最后一个数时，前缀最多能留下多少个同值元素。枚举下一个保留位置 $j$ ，只有 $a_i=a_j$ 且中间能删空时才能接上。首个保留位置前面也要能删空，最后再检查后缀。

枚举间隔时顺手维护长度和最大出现次数，不用真的执行删除，总时间 $O(n^2)$ ，额外空间 $O(n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 17;
int T, n, ans;
int a[maxn], cnt[maxn], f[maxn];

int main() {
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            f[i] = -1;
        }
        f[0] = 0;
        for(int i = 0; i <= n; i++) {
            if(f[i] < 0) continue;
            for(int j = 1; j <= n; j++) cnt[j] = 0;
            int mx = 0;
            for(int j = i + 1; j <= n; j++) {
                int len = j - i - 1;
                if(!(len & 1) && mx * 2 <= len && (i == 0 || a[i] == a[j])) {
                    f[j] = max(f[j], f[i] + 1);
                }
                mx = max(mx, ++cnt[a[j]]);
            }
            int len = n - i;
            if(!(len & 1) && mx * 2 <= len) ans = max(ans, f[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

A. The Third Three Number Problem

题意

思路

代码

B. Almost Ternary Matrix

题意

思路

代码

C. The Third Problem

题意

思路

代码

D. Almost Triple Deletions

题意

思路

代码

随机文章