很不幸,我违反了之前自己定下的 “不再在此博客更新 XCPC 相关” 的约定,但是感觉想要记录点什么,纸上总感觉差了点什么,不仔细记录又感觉自己每次写题解会敷衍了事,所以在这里开一个吧。

退役之后我会将该博文删除。

第一要务是收心,不要去在意杂事,不担心以后,最后几个月专心做竞赛,不留下遗憾。

8.25~8.26 Codeforces Round #767 (Div. 1)

1628A Meximum Array

对每个位置分别选。要使得字典序最大,那么第一要务是保证当前选的 $MEX$ 尽可能大。然后,相同值之中,我们选最左的那个,以此来保证在选取 $MEX$ 相同的条件下,整个 $b$ 的长度尽可能长。

于是我们可以用一个队列按顺序存各个数出现的位置,模拟一下保证这两个条件。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
int a[maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, queue<int>> pos;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pos[a[i]].push(i);
}
vector<int> b;
for (int i = 1; i <= n; ++i) {
int st = i;
int mex = -1;
// 寻找 mex+1,直到没有.
while (!pos[mex + 1].empty()) {
if (pos[mex + 1].front() < st) {
pos[mex + 1].pop();
continue;
}
if (pos[mex + 1].front() <= i) {
while (!pos[mex + 1].empty() && pos[mex + 1].front() <= i) {
pos[mex + 1].pop();
}
mex++;
continue;
}
i = pos[mex + 1].front();
pos[mex + 1].pop();
mex++;
}
b.push_back(mex + 1);
}
cout << b.size() << endl;
for (int i = 0; i < b.size(); ++i) {
cout << b[i] << " ";
}
cout << endl;
}
return 0;
}

1628B Peculiar Movie Preferences

水题,每个字符串的长度都小于等于 3,首先单一个字符串自己组成回文的情况先处理掉,然后剩下的情况字符串数量都 $\geq2$.

假设我们能够造出一个使用的字符串数量为 $x\geq2$ 的回文串,那么最左边和最右边是一定可以构造成一个回文串的。如果最左边最右边长度相等,那么他们拼起来肯定是回文;如果长度不等,一个是 2,一个是 3,那么最前面两个和最后面两个肯定也相等,总长度 5,还是可以构成回文。

所以只需要对每个串看前面存不存在与他构成回文的串就行啦,字符串哈希或者 map 即可过。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
// 17576 - 780.
// 规模最多为 2???

int n;
cin >> n;
map<string, int> mp;
map<string, int> mp32;
bool flag = 0;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
if (flag) continue;
mp[s]++;
if (s.size() == 1) {
flag = 1;
}
else if (s.size() == 2 && s[0] == s[1]) {
flag = 1;
}
else if (s.size() == 2) {
reverse(s.begin(), s.end());
if (mp.count(s) || mp32.count(s)) {
flag = 1;
}
}
else if (s.size() == 3) {
string tmp;
tmp += s[1];
tmp += s[2];
reverse(tmp.begin(), tmp.end());
if (mp.count(tmp)) {
flag = 1;
continue;
}
tmp.clear(); tmp += s[0], tmp += s[1];
mp32[tmp]++;
reverse(s.begin(), s.end());
if (mp.count(s)) {
flag = 1;
}
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}

1628C Grid Xor

纯构造题…尝试了构造各个位置异或次数为奇数的方法,和不同的组合来容斥求答案的思路,越弄越复杂,但是其实很简单就能够造出每个位置被异或一次的方法……

按各个位置的奇偶性分别去手画几下即可(国际象棋棋盘染色),奇偶性不同的位置是互不影响的。具体可以参考洛谷上的题解。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1005;
int a[maxn][maxn];
int f1[maxn][maxn];
int f2[maxn][maxn];
bool v[maxn][maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= 1000; ++i) {
for (int j = 1; j <= 1000; ++j) {
if ((i + j) & 1) {
f1[i][j] = 1, f2[i][j] = 0;
}
else f2[i][j] = 1, f1[i][j] = 0;
}
}
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
v[i][j] = 0;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (!f1[i][j]) continue;
if (i > 1 && v[i - 1][j]) continue;
if (j > 1 && v[i][j - 1]) continue;
if (i < n && v[i + 1][j]) continue;
if (j < n && v[i][j + 1]) continue;
v[i - 1][j] = v[i][j - 1] = v[i + 1][j] = v[i][j + 1] = 1;
ans ^= a[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (!f2[i][j]) continue;
if (i > 1 && v[i - 1][j]) continue;
if (j > 1 && v[i][j - 1]) continue;
if (i < n && v[i + 1][j]) continue;
if (j < n && v[i][j + 1]) continue;
v[i - 1][j] = v[i][j - 1] = v[i + 1][j] = v[i][j + 1] = 1;
ans ^= a[i][j];
}
}
cout << ans << endl;
}
return 0;
}

1628D1 Game on Sum (Easy Version)

由 $2000$ 数据范围很容易想到需要构造一个 $dp$ 状态。设 $dp_{i,j}$ 表示已经选择了 $i$ 个数字,其中 $j$ 次相加的答案。

但因为存在二元博弈,这个 $dp$ 既不是最大值也不是最小值。考虑单独的每一步:
如果 Alice 给的数较大,那么 Bob 将会选择减。但若 Alice 给的数小,那么 Bob 在次数还没加够时可以选择加。因为 Bob 是在 Alice 给数之后选的,他会将答案最小化。

所以有

那么 Alice 现在可以决定 $x$,她会使得答案尽可能大。在和不变的条件下让二者最小值最大,因为显然有 $dp_{i-1,j}\geq dp_{i-1,j-1}$,且差值一定不大于 $k$,所以我们可以选择一个值使得 $dp_{i-1,j}-x=dp_{i-1,j-1}+x=avr$,这样就是最优的选择。

所以转移方程为

但要注意有个边界条件是不同的,即 $i=j$ 时,因为 Bob 只能选择加,所以 Alice 会最大化答案为 $ik$.

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 2005;
const int mod = 1e9 + 7;
int dp[maxn][maxn];
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = (ans * x) % mod;
}
x = (x * x) % mod;
k >>= 1;
}
return ans;
}
int inv(int x) {
return fpow(x, mod - 2);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
int i2 = inv(2);
while (t--) {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i <= n; ++i) {
dp[i][i] = i * k % mod;
}
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i == j) continue;
dp[i][j] = ((dp[i - 1][j] + dp[i - 1][j - 1]) * i2) % mod;
}
}
cout << dp[n][m] << endl;
}
return 0;
}

1628D2 Game on Sum (Hard Version)

范围扩大,由 D1 解法可知答案只与 $k$ 有关,故我们应该时可以找到一个公式的。

考虑各个 $dp$ 值对 $dp_{n,m}$ 的贡献,每个 $dp$ 值理应包括:

若干个 $dp_{1,1}$ 及其 $\frac{1}{2^x}$ 倍,若干个 $dp_{2,2}$ 及其 $\frac{1}{2^x}$ 倍……所有的 $dp$ 值都可以只通过 $dp_{i,i}$ 的贡献推出来。

那么 $dp_{i,i}$ 对 $dp_{n,m}$ 的贡献,每个来自 $dp_{i,i}$ 的分贡献一定是走的不同的路径,从 $dp_{i,i}$ 走到 $dp_{n,m}$,路径不同,长度相同,所以最后的分贡献值都一样。这是经典的走楼梯组合问题,走法为 $C_{n-i-1}^{m-i}$,每次都贡献了 $\frac{dp_{i,i}}{2^{n-i}}$. 全部求和即可。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int f[maxn];
int pi[maxn];
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = (ans * x) % mod;
}
x = (x * x) % mod;
k >>= 1;
}
return ans;
}
int inv(int x) {
return fpow(x, mod - 2);
}
void pre(int n) {
pi[0] = pi[1] = 1;
for (int i = 1; i <= n; ++i) {
pi[i] = (pi[i - 1] * i) % mod;
}
}
int C(int n ,int m) {
return ((pi[n] * inv(pi[m]) % mod) * inv(pi[n - m])) % mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
pre(maxn - 5);
int t = 1;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
if (m == 1) {
cout << (inv(fpow(2, n - 1)) * k) % mod << endl;
continue;
}
else if (n == m) {
cout << m * k % mod << endl;
continue;
}
else if (m == 0) {
cout << 0 << endl;
continue;
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
int x = C(n - i - 1, m - i);
int y = fpow(inv(2), n - i);
ans = (ans + (i * ((x * y) % mod)) % mod) % mod;
}
cout << ans * k % mod << endl;
}
return 0;
}

8.27~8.28 吉林省赛复现

四天三个训练赛,多补补题吧。

The 15th Jilin Provincial Collegiate Programming Contest I. Nim Game

复习 Nim 博弈,其条件是集合各数异或和为 0 即必败,否则必胜。

那么嘉然小姐想要赢,必定是集合中存在一个子集,其异或和为 0.

我们可以用线性基来判断。每次将一个数加入线性基,如果加入时更新了 $a_0$,说明现在有异或和为 0 且非空的子集了。又因为位数不会超过 $32$,所以当至少有 $32$ 个数时,线性基一定会更新到 $a_0$,一定存在一个异或和为 0 的子集,不用判断。小于 $32$ 的暴力判断即可。

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
#include <bits/stdc++.h>
#define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#pragma GCC optimize(3)
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
struct node {
int l, r, sum, tag;
}a[maxn << 2];
int num[maxn];
void pushup(int k) {
a[k].sum = a[lson].sum + a[rson].sum;
}
void build(int k, int l, int r) {
a[k].l = l, a[k].r = r;
if (l == r) {
a[k].l = l, a[k].r = r;
a[k].sum = num[l];
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(k);
}
void pushdown(int k) {
if (!a[k].tag) return;
a[lson].sum += a[k].tag * (a[lson].r - a[lson].l + 1);
a[lson].tag += a[k].tag;
a[rson].sum += a[k].tag * (a[rson].r - a[rson].l + 1);
a[rson].tag += a[k].tag;
a[k].tag = 0;
}
void add(int k, int l, int r, int x) {
if (a[k].l > r || a[k].r < l) return;
if (a[k].l >= l && a[k].r <= r) {
a[k].sum += x * (a[k].r - a[k].l + 1);
a[k].tag += x;
return;
}
pushdown(k);
add(lson, l, r, x);
add(rson, l, r, x);
}
int b[33];
int insert(int x) {
for (int i = 32; i >= 0; --i) {
if (!(x & (1 << i))) continue;
if (!b[i]) {
b[i] = x;
break;
}
x ^= b[i];
}
return x;
}
int query(int k, int x) {
if (a[k].l > x || a[k].r < x) return 0;
if (a[k].l == a[k].r && a[k].l == x) return a[k].sum;
pushdown(k);
return query(lson, x) + query(rson, x);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> num[i];
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int op, l, r, x;
cin >> op >> l >> r;
if (op == 1) {
cin >> x;
add(1, l, r, x);
}
else {
if (r - l + 1 >= 33) {
cout << "Yes" << endl;
continue;
}
else {
bool flag = 1;
memset(b, 0, sizeof(b));
for (int i = l; i <= r; ++i) {
int y = query(1, i);
y = insert(y);
if (!y) {
flag = 0;
break;
}
}
cout << (flag ? "No" : "Yes") << endl;
}
}
}
return 0;
}

8.29~8.30 Educational Codeforces Round 134

1721D Maximum AND

贪心,优先保证高位能异或为 1.

为了 $a,b$ 异或为1,我们将 $a,b$ 分组。假设现在考虑到了第 $i$ 位,那么 $a$ 中第 $i$ 位为 1 的和 $b$ 中第 $i$ 位为 0 的分一组,反之亦然。如果分完组后,$a_i=1$ 和 $b_i=0$ 的数个数是相同的,说明这个分组是有效的,不会出现多余的数,于是我们分组继续下去就可以。如果出现了分不齐的情况,就说明在保证某几个高位能够达到 $1$ 的条件下,我们是无法保证这一位为 1 的,所以不进行分组,直接判断下一位。

(场上没有注意将大小为 0 的分组剔除,导致 vector 爆了,还不知道错在哪)

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
#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
int xx;
struct pvv {
vector<int> a, b;
};
vector<pvv> v, tmp;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
xx = 0x7fffffff;
int n;
cin >> n;
vector<int> a, b;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
a.push_back(x);
}
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
b.push_back(x);
}
v.push_back({a, b});
for (int j = 30; j >= 0; --j) {
tmp.clear();
bool flag = 1;
for (int i = 0; i < v.size(); ++i) {
pvv a0b1, a1b0;
for (int k = 0; k < v[i].a.size(); ++k) {
if (v[i].a[k] & (1 << j)) a1b0.a.push_back(v[i].a[k]);
else a0b1.a.push_back(v[i].a[k]);
}
for (int k = 0; k < v[i].b.size(); ++k) {
if (v[i].b[k] & (1 << j)) a0b1.b.push_back(v[i].b[k]);
else a1b0.b.push_back(v[i].b[k]);
}
if (a0b1.a.size() == a0b1.b.size()) {
if (!a0b1.a.empty()) {
tmp.push_back(a0b1);
}
if (!a1b0.a.empty()) {
tmp.push_back(a1b0);
}
}
else {
xx -= (1 << j);
flag = 0;
break;
}
}
if (flag)
v = tmp;
}
cout << xx << endl;
v.clear();
}
return 0;
}

8.31~9.1 Codeforces Round #698 (Div. 1)

A. Nezzar and Board

把所有的数放在数轴上,可以发现任取两个数,通过不断地往集合中加 $2x-y$,最后得到的数的间隔不会大于 $|x-y|$.

所以通过这两个数能构造出所有以 $x$ 或者 $y$ 为某项,公差为 $\gcd(x,y)$ 的等差数列。

扩展到所有元素可知,所有元素构造出来的应该是以某个 $a_i$ 为首项,公差为 $\gcd(a_1,a_2,…,a_n)$ 的等差数列。

先求出 $g=\gcd(a_1,a_2,…,a_n)$,然后枚举各个 $a_i$,看是否 $(k-a_i)\%g=0$.

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
#include <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
// k = 2x - y
// 2(x1a1 + x2a2 + ... + xnan) - (y1a1 + y2a2 + ...)
// = (2x1 - y1)a1 + (2x2 - y2)a2 + ...
// x + d = k --> d = m * |x - y|.
// k - x = d = m * |x - y|
// (k - x) % |x - y| = 0
// x, y 从集合中任取。
// 存在整数列使得 k - ax = x1(a1 - a2) + x2(a2 - a3) + ... + x_{n-1}(a_{n-1} - an)
// xi \in integer
// 存在互质的数时一定yes... --> gcd = 1
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int g = a[2] - a[1];
for (int i = 3; i <= n; ++i) {
g = __gcd(a[i] - a[i - 1], g);
}
bool flag = 0;
for (int i = 1; i <= n; ++i) {
if ((k - a[i]) % g == 0) {
flag = 1;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}

B. Nezzar and Binary String

意外的简单题,但是卡壳了一会。

只要逆向考虑就能发现,因为每次操作都是要求 strictly less than half of the characters,所以其实倒过来的修改是固定,没有选择的。一开始没注意严格更少,还想了一会二者相等的情况。。

所以逆向考虑,操作用线段树维护即可,遇到数量相等的情况直接 break 输出 $NO$,最后 $n\log n$ 判断一下最终得到的字符串,再比较一下。

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
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int ql[maxn], qr[maxn];
struct node {
int l, r;
int cnt0, cnt1;
int tag;
}a[maxn << 2];
string s, f;
void pushup(int k) {
a[k].cnt0 = a[lson].cnt0 +a[rson].cnt0;
a[k].cnt1 = a[lson].cnt1 + a[rson].cnt1;
}
void build(int k, int l, int r) {
a[k].l = l, a[k].r = r;
a[k].tag = -1;
if (l == r) {
if (f[l] == '0') a[k].cnt0 = 1, a[k].cnt1 = 0;
else a[k].cnt1 = 1, a[k].cnt0 = 0;
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(k);
}
void pushdown(int k) {
if (a[k].tag == -1) return;
a[lson].cnt0 = (a[lson].r - a[lson].l + 1) * (!a[k].tag);
a[rson].cnt0 = (a[rson].r - a[rson].l + 1) * (!a[k].tag);
a[lson].cnt1 = (a[lson].r - a[lson].l + 1) * a[k].tag;
a[rson].cnt1 = (a[rson].r - a[rson].l + 1) * a[k].tag;
a[lson].tag = a[rson].tag = a[k].tag;
a[k].tag = -1;
}
void change(int k, int l, int r, int x) {
if (a[k].l > r || a[k].r < l) return;
if (a[k].l >= l && a[k].r <= r) {
if (x) {
a[k].tag = 1;
a[k].cnt1 = a[k].r - a[k].l + 1;
a[k].cnt0 = 0;
}
else {
a[k].tag = 0;
a[k].cnt0 = a[k].r - a[k].l + 1;
a[k].cnt1 = 0;
}
return;
}
pushdown(k);
change(lson, l, r, x);
change(rson, l, r, x);
pushup(k);
}
int query0(int k, int l, int r) {
if (a[k].l > r || a[k].r < l) return 0;
if (a[k].l >= l && a[k].r <= r) return a[k].cnt0;
pushdown(k);
return query0(lson, l, r) + query0(rson, l, r);
}
int query1(int k, int l, int r) {
if (a[k].l > r || a[k].r < l) return 0;
if (a[k].l >= l && a[k].r <= r) return a[k].cnt1;
pushdown(k);
return query1(lson, l, r) + query1(rson, l, r);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
cin >> s >> f;
s = 'X' + s, f = 'X' + f;
for (int i = 1; i <= q; ++i) {
cin >> ql[i] >> qr[i];
}
build(1, 1, n);
bool flag = 1;
for (int i = q; i >= 1; --i) {
int cnt0 = query0(1, ql[i], qr[i]);
int cnt1 = query1(1, ql[i], qr[i]);
if (cnt0 == 0 || cnt1 == 0) continue;
if (cnt0 == cnt1) {
flag = 0;
break;
}
else if (cnt0 < cnt1) {
change(1, ql[i], qr[i], 1);
}
else change(1, ql[i], qr[i], 0);
}
string x;
x += "X";
for (int i = 1; i <= n; ++i) {
int c = query0(1, i, i);
if (c) x += "0";
else x += "1";
}
if (x != s) flag = 0;
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}

C. Nezzar and Nice Beatmap

我还手画有没有不可能的情况呢,一直画不出来。

结果题解给了一个非常简洁优雅的方法:每次选取未加入点中距离最远的点连起来。

于是就保证每个角都是锐角……太强了。

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
#include <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct point {
int x, y;
int id;
};
int dis(point p1, point p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
vector<point> v1, v2;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while (t--) {
int n;
cin >> n;
v1.clear();
v1.resize(n);
for (int i = 0; i < n; ++i) {
cin >> v1[i].x >> v1[i].y;
v1[i].id = i + 1;
}
while (1) {
cout << v1[0].id << " ";
v2 = v1;
int mxi = 1, mxd = 0;
if (v1.size() == 1) break;
for (int i = 1; i < v2.size(); ++i) {
int d = dis(v2[0], v2[i]);
if (d > mxd) {
mxi = i, mxd = d;
}
}
v1.clear();
v1.push_back(v2[mxi]);
for (int i = 1; i < v2.size(); ++i) {
if (i == mxi) continue;
v1.push_back(v2[i]);
}
}
cout << endl;
}
return 0;
}

2022“杭电杯”中国大学生算法设计超级联赛(9)1008 Shortest Path in GCD Graph

  1. 任何两点间的距离都不大于 $2$,因为 $\gcd(1,i)=1$. 故答案只能是 $1$ 或者 $2$.

  2. 对于 $a,b$ 的距离,若 $\gcd(a,b)>1$,问题等价于找到满足 $\gcd(a,i)=1,\gcd(b,j)=1$ 的 $i,j$ 数量。

  3. 对于 $n\leq10^7$ 条件,任何数的素因子数量都不会超过 $15$ 个(大概 $12$ 个左右)。可以先筛出 $a$ 和 $b$ 的所有素因子,然后计算它们在 $[1,n]$ 内整除的数,再用总数减去即可。
  4. 要求 $a,b$ 的素因子在 $[1,n]$ 内整除的数。假设素因子是 $\{x_1,x_2,…,x_m\}$,例如 $x_1$ 在范围内的倍数有 $\lfloor \frac{n}{x_1} \rfloor$ 个,然后再算 $x_2,x_3,…$ 的,这里 $x_1,x_2$ 的倍数肯定有重合的部分,发现这是一个容斥模型,于是可以二进制枚举容斥,这样单次询问复杂度上限就是 $O(2^{12})$.

std 的容斥模板是好的(

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
#include <bits/stdc++.h>
#pragma GCC optimize(3)
// #define endl '\n'
using namespace std;
// #define int long long
const int mod = 998244353;
const int maxn = 1e7 + 10;
int st[maxn], primes[maxn / 10], f[maxn];
int n, q;
int cnt;
void ola(int n) {
for (int i = 2; i <= n; ++i) {
if (st[i] == 0) primes[++cnt] = i, f[i] = i;
for (int j = 1; primes[j] <= n / i; ++j) {
st[primes[j] * i] = 1;
f[primes[j] * i] = primes[j];
if (i % primes[j] == 0) break;
}
}
}
set<int> myset;
vector<int> vec;
void add(int x) {
while (x > 1) {
int y = f[x];
myset.insert(y);
while (x % y == 0) x /= y;
}
}
int ans = 0;
void dfs(int x, int s, int o) {
if (s > n) return;
if (x == vec.size()) {
ans += o * (n / s);
// ans = (ans + mod) % mod;
return;
}
dfs(x + 1, s, o);

// 不可写成乘法. 因为取个数就是要向下取整,不能不舍去.
if (s <= n / vec[x]) dfs(x + 1, s * vec[x], -o);
}
void solve(int x, int y) {
myset.clear(); vec.clear();
add(x), add(y);
for (auto &xx : myset) vec.push_back(xx);
ans = 0;
dfs(0, 1, 1);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("1008.in", "r", stdin);
// freopen("1008.out", "w", stdout);
int t;
// cin >> t;
t = 1;
while (t--) {
cin >> n >> q;
ola(n + 1);
for (int i = 1; i <= q; ++i) {
int u, v;
cin >> u >> v;
if (__gcd(u, v) == 1) {
cout << "1 1" << endl;
continue;
}
solve(u, v);
if (__gcd(u, v) == 2) ans++;
cout << 2 << " " << ans << endl;
}
}
return 0;
}