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

题意

思路

代码

랜덤 게시물