Solution - Codeforces Round 1046 (Div. 2)

Posted on Edited on

Codeforces Round 1046 (Div. 2)

A. In the Dream

Solution

分成两个半场，每个半场得分小的为bb，大的为aa，则⌈a2⌉≤b+1\lceil\frac{a}{2}\rceil \leq b + 1即可。

复杂度O(1)O(1)。

Code

Show Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
inline bool judge(int a, int b) {
    if (a < 0 || b < 0) return false;
    if (a < b) swap(a, b);
    return ((a + 1) >> 1) <= b + 1;
}
signed main() {
    int t; cin >> t;
    while (t--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << (judge(a, b) && judge(c - a, d - b) ? "Yes" : "No") << endl;
    }
    return 0;
}

B. Like the Bitset

Solution

首先可以发现，如果有11位置的数大于00位置的数的情况，交换两个数后情况不会更差，所以把最小的若干个数放到11位置。这样相当于知道了一部分数放11，一部分数放00。

对于放11的数，我们从大到小放，则相当于放完一个就变成00，所以只要满足一开始有地方放，也就是**不存在连续kk个11**即可。所以最后就是分两种数，都随便放就行。

复杂度O(n)O(n)。

Code

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
inline bool get() {
    char ch = getchar();
    while (ch != '0' && ch != '1') ch = getchar();
    return ch == '1';
}
bool s[N];
signed main() {
    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        int maxk = 0;
        for (int i = 1, pre0 = 0; i <= n; ++i) {
            s[i] = get();
            if (s[i]) {
                maxk = max(maxk, i - pre0);
            } else {
                pre0 = i;
            }
        }
        if (maxk >= k) {
            puts("NO");
            continue;
        }
        puts("YES");
        for (int i = 1, min_n = 1, max_n = n; i <= n; ++i) {
            if (s[i] == 0) {
                printf("%d ", max_n--);
            } else {
                printf("%d ", min_n++);
            }
        }
        puts("");
    }
}

C. Against the Difference

Solution

令f(i)f(i)表示前ii个数中任意选的最大值。

则f(0)=0f(0)=0，对于i≥1i\geq 1，f(i)=max⁡{f(i−1),f(pre i)+i}f(i) = \max\{f(i - 1), f(\mathrm{pre} \ i) + i\}，其中pre i\mathrm{pre}\ i表示从ii位置往小方向数第i+1i+1个ii数字的位置。这个可以用一个vector维护。

复杂度O(n)O(n)。

Code

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int f[N], n, a[N];
vector<int> pre[N];
signed main() {
    int t; cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) f[i] = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; ++i) {
            pre[i].clear();
        }
        for (int i = 1; i <= n; ++i) {
            pre[a[i]].push_back(i);
            f[i] = f[i - 1];
            if (pre[a[i]].size() >= a[i]) {
                int j = pre[a[i]][pre[a[i]].size() - a[i]];
                f[i] = max(f[i], f[j - 1] + a[i]);
            }
        }
        cout << f[n] << endl;
    }
}

D. For the Champion

Solution

我认为全场最难想的题。

由于套了两个绝对值非常难处理，我们可以通过在两个维度上都平移2×1092\times 10^9的距离（总计四次操作）来消除绝对值。令V=109V = 10^9。

假设先向第四象限平移，则此时获得的答案是min⁡i{∣xi−(X−2V)∣+∣yi−(Y−2V)∣}=min⁡i{xi+yi−X−Y+4V}=min⁡i{xi+yi}−X−Y+4V\min_i\{\left| x_i - (X - 2V)\right| + \left| y_i - (Y - 2V)\right|\} = \min_i\{x_i + y_i - X - Y + 4V\} = \min_i\{x_i + y_i\} - X - Y + 4V。所以根据答案可以算出X+YX+Y的值。

此时再向上平移4×1094\times 10^9，则获得的答案变为min⁡i{xi−yi}−X+Y+4V\min_i\{x_i - y_i\} - X + Y + 4V，可以算出X−YX-Y的值。

两式加减就可以得到XX和YY。

Code

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 1e9, N = 101;
int n;
int min_X_plus_Y = INF * 2, min_X_minus_Y = INF * 2;
int X_plus_Y, X_minus_Y;
signed main() {
    int t; cin >> t;
    while (t--) {
        min_X_plus_Y = INF * 2, min_X_minus_Y = INF * 2;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int x, y; cin >> x >> y;
            min_X_plus_Y = min(min_X_plus_Y, x + y);
            min_X_minus_Y = min(min_X_minus_Y, x - y);
        }
        LL output;
        cout << "? D " << INF << endl; cout.flush(); cin >> output;
        cout << "? D " << INF << endl; cout.flush(); cin >> output;
        cout << "? L " << INF << endl; cout.flush(); cin >> output;
        cout << "? L " << INF << endl; cout.flush(); cin >> output;
        X_plus_Y = -(output - LL(INF) * 4 - min_X_plus_Y);
        cout << "? U " << INF << endl; cout.flush(); cin >> output;
        cout << "? U " << INF << endl; cout.flush(); cin >> output;
        cout << "? U " << INF << endl; cout.flush(); cin >> output;
        cout << "? U " << INF << endl; cout.flush(); cin >> output;
        X_minus_Y = -(output - LL(INF) * 4 - min_X_minus_Y);
        cout << "! " << (LL(X_plus_Y) + X_minus_Y) / 2 << " " << (LL(X_plus_Y) - X_minus_Y) / 2 << endl;
        cout.flush();
    }
}

E. By the Assignment

Solution

首先发现题目限制是不影响树的，于是我们先来研究一个简单环的情况。

先考虑环上相邻两点的路径。相邻两点的两条路径异或和相同，所以任意相邻两点的异或值等于整个环的异或值，也就是说任意相邻两点异或值相同，所以任意两点值相同。

同时，如果这是一个奇环，那么奇数个点的异或和为00，则可以得出环上任意一个点的值为00。偶环则没有这个限制，只需全部相同。

现在考虑一个双连通分量。一个双连通分量内如果不存在奇环，则这个双连通分量中的节点可以是任意一个相同值（除非里面有已知值或者矛盾值），否则这个双连通分量中的节点必须全部为00。

先Tarjan缩边双，然后对于每个边双内用染色法判断是否为二分图（是否有奇环），然后再将每一个边双内的方案数乘起来，即可得到答案。

复杂度O(n)O(n)。

Code

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1, MOD = 998244353;
vector<int> G[N];
int dfn[N], low[N], idx;
int st[N], top;
int col[N], cl;
int n, m, V;
int val[N];
bool vis[N];
bool dfsed[N];
bool color[N];
int number[N];
void Tarjan(int u, int fa) {
    dfn[u] = low[u] = ++idx; st[++top] = u;
    for (const auto& v : G[u]) {
        if (v == fa) continue;
        if (dfn[v]) {
            low[u] = min(low[u], dfn[v]);
        } else {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++cl;
        while (u != st[top]) {
            col[st[top--]] = cl;
        }
        col[st[top--]] = cl;
    }
    
}
inline int comp(int val1, int val2) {
    if (val1 == -1) {
        return val2;
    }
    if (val2 == -1) {
        return val1;
    }
    return val1 == val2 ? val1 : -2;
}
int Dfs(int u, int c) {
    dfsed[u] = true;
    int num = val[u];
    for (const auto& v : G[u]) {
        if (col[v] != c) continue;
        int nt;
        if (!dfsed[v]) {
            color[v] = !color[u];
            nt = Dfs(v, c);
        } else {
            if (color[u] == color[v]) {
                nt = comp(val[v], 0);
            } else {
                nt = val[v];
            }
        }
        num = comp(num, nt);
    }
    return val[u] = num;
}
signed main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> m >> V;
        for (int i = 1; i <= n; ++i) {
            dfn[i] = low[i] = col[i] = vis[i] = dfsed[i] = color[i] = number[i] = 0;
            G[i].clear();
        }
        cl = idx = top = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> val[i];
        }
        for (int i = 1; i <= m; ++i) {
            int x, y; cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        for (int i = 1; i <= n; ++i) {
            if (!dfn[i]) Tarjan(i, 0);
        }
        for (int i = 1; i <= n; ++i) {
            int c = col[i];
            if (!vis[c]) {
                vis[c] = true;
                color[c] = 0;
                int num = Dfs(i, c);
                // printf("num %d = %d\n", c, num);
                number[c] = num;
            }
        }
        int ans = 1;
        for (int i = 1; i <= cl; ++i) {
            if (number[i] == -2) {
                ans = 0;
            } else if (number[i] == -1) {
                ans = LL(ans) * V % MOD;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

F1. From the Unknown (Easy Version)

Solution

由于要求两次就能猜出来，我们尽可能每次获得更多的信息而不爆00。

最简单的想法是先来10510^5个11，可以测出WW的范围在[105l,105l−1)[\frac{10^5}{l}, \frac{10^5}{l - 1})内。由于l=1l=1时知道答案为10510^5，所以l≥2l\geq 2，此时我们发现WW的上下界不会差到两倍。利用这个性质，我最先的想法是：假设下界为mm，上界为MM，则我们如果问x,m,mx, m, m为一组，xx为从11到M−mM-m变化的整数，则每一组的有效长度是22或者33，且具有单调性（从某一个开始都是33），根据总长度ll，我们可以知道答案是M−(l−(M−m)∗2)M - (l - (M - m) * 2)。但是这样可能会爆10510^5个。

为了进一步优化，尽可能调大第一次猜的总长度。我们第一次如果问10510^5个33，则WW的范围进一步缩小到[105l,105l−1+2)[\frac{10^5}{l}, \frac{10^5}{l - 1} + 2)，其中l≥3l\geq 3（等于33直接输出）。如果第一次猜爆00，就可以猜全22或者全11，通过排除法做出。

运用这个方法，可以通过本题。

Code

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
signed main() {
    int t; cin >> t;
    while (t--) {
        string prompt = "? " + to_string(N);
        int res;
        for (int i = 1; i <=N; ++i) {
            prompt += " 3";
        }
        cout << prompt << endl; cout.flush(); cin >> res;
        if (res == 0) {
            prompt = "? " + to_string(N);
            for (int i = 1; i <=N; ++i) {
                prompt += " 2";
            }
            cout << prompt << endl; cout.flush(); cin >> res;
            if (res == 0) {
                cout << "! " << 1 << endl; cout.flush();
            } else {
                cout << "! " << 2 << endl; cout.flush();
            }
        } else {
            prompt = "? ";
            int minn = ceil(float(3 * N) / res);
            int maxn = ceil(float(3 * N) / (res - 1)) + 2;
            if (maxn == minn) {
                cout << "! " << minn << endl; cout.flush();
            } else {
                prompt += to_string((maxn - minn) * 3);
                for (int i = minn + 1; i <= maxn; ++i) {
                    prompt += " " + to_string(i - minn);
                    prompt += " " + to_string(minn);
                    prompt += " " + to_string(minn);
                }
                cout << prompt << endl; cout.flush();
                cin >> res;
                cout << "! " << maxn - (res - (maxn - minn) * 2) << endl; cout.flush();
            }
        }
    }
    return 0;
}

F2. From the Unknown (Hard Version)

Solution

顺着F1的思路走，其实第一次爆0的影响可以再次缩小。我们如果第一次猜1000010000个100100，则爆0之后只需要再问1000010000个11，由于⌈10000i⌉\lceil \frac{10000}{i}\rceil在i∈[1,100]i\in[1, 100]时各不相同，所以可以得出答案。

这样的话可以进一步缩小WW的范围，但是并不能将总次数卡进2.5e42.5e4的范围内。这时候可以发现，如果没有爆0的情况下的输出其实有优化的空间。我们可以把x,m,mx, m, m组合改成m,xm, x组合，不仅更加稳定而且省次数。最后再进行一些细节上的调整（进一步精确化WW的范围，略微增加第一次问的大小）即可通过。

Code

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int N = 10000, M = 125, K = 15000;
int mp[M + 1];
signed main() {
    int t; cin >> t;
    for (int i = 1; i <= M; ++i) {
        mp[i] = ceil(float(K) / i);
        assert(mp[i] != mp[i - 1]);
    }
    while (t--) {
        string prompt = "? " + to_string(N);
        int res;
        for (int i = 1; i <= N; ++i) {
            prompt += " " + to_string(M);
        }
        cout << prompt << endl; cout.flush(); cin >> res;
        if (res == 0) {
            prompt = "? " + to_string(K);
            for (int i = 1; i <= K; ++i) {
                prompt += " 1";
            }
            cout << prompt << endl; cout.flush(); cin >> res;
            for (int i = 1; i <= M; ++i) {
                if (mp[i] == res) {
                    cout << "! " + to_string(i) << endl; cout.flush();
                }
            }
        } else {
            prompt = "? ";
            int minn = ceil(float(M * N) / res);
            int maxn = floor(float(M * N) / (res - 1)) + M - 1;
            maxn = min(maxn, 100000);
            if (maxn == minn) {
                cout << "! " << minn << endl; cout.flush();
            } else {
                prompt += to_string((maxn - minn) * 2);
                for (int i = minn + 1; i <= maxn; ++i) {
                    prompt += " " + to_string(minn);
                    prompt += " " + to_string(i - minn);
                }
                cout << prompt << endl; cout.flush();
                // cout << (maxn - minn) * 2 << endl; //
                cin >> res;
                cout << "! " << maxn - (res - (maxn - minn)) << endl; cout.flush();
            }
        }
    }
    return 0;
}