D
题目大意：Kagari 正准备对一棵树进行归档，她知道归档的成本取决于树的直径 ¹。为了降低成本，她的目标是首先尽可能缩小直径。她可以对树执行以下操作： - 选择两个顶点 $s$ 和 $t$。设从 $s$ 到 $t$ 的简单路径 ² 上的顶点序列为 $v_{0},v_{1},…,v_{k}$，其中 $v_{0} = s,v_{k} = t$。移除路径上的所有边。即移除边 $(v_{0},v_{1}),(v_{1},v_{2}),…,(v_{k-1},v_{k})$。- 将顶点 $v_{1},v_{2},…,v_{k}$ 直接连接到 $v_{0}$。即添加边 $(v_{0},v_{1}),(v_{0},v_{2}),…,(v_{0},v_{k})$。
数据范围：$\sum n \le 2⋅10^5$。
思路：
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
| using i128 = __int128_t;
void solve() {
ll n, x, y;
cin >> n;
vvl ma(n);
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
if (n == 2) {
cout << 0 << endl;
return;
}
ll ans = 0;
rep(i, 0, n - 1) {
if (sz(ma[i]) == 1) ans++;
}
ll ans2 = LLONG_MAX;
rep(i, 0, n - 1) {
ll tem = 0;
for (auto& p : ma[i]) {
tem += (sz(ma[p]) == 1);
}
ans2 = min(ans2, ans - tem);
}
cout << ans2 << endl;
return;
}
|
E
题目大意：你有一个长度为 $n$ 的数组 $a$，对于每个满足 $1 \le i < n$ 的索引 $i$，你只能执行以下操作最多一次： - 令 $a_i := a_i \oplus a_{i+1}$，其中 $\oplus$ 表示按位异或运算。你可以按任意顺序选择这些索引并执行操作。给定另一个数组 $b$，判断 $a$ 能否通过这些操作转换为 $b$。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$0 \le a_i < 2^{30}$，$0 \le b_i < 2^{30}$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n), b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
if (a[n - 1] != b[n - 1]) {
cout << "NO" << endl;
return;
}
frep(i, n - 2, 0) {
if (a[i] == b[i] || ((a[i] ^ a[i + 1]) == b[i]) || ((a[i] ^ b[i + 1]) == b[i])) continue;
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
return;
}
|
F
题目大意：Yuri 有两个长度为 $n$ 的 01 字符串 $a$ 和 $b$，这两个字符串可以定义一个 $n \times n$ 的网格。记 $(i, j)$ 为第 $i$ 行第 $j$ 列的单元格。单元格 $(i, j)$ 的值为 $a_i \oplus b_j$，其中 $\oplus$ 表示按位异或运算。Yuri 的旅途永远从单元格 $(1, 1)$ 开始。从单元格 $(i, j)$ 出发，她只能向下移动到单元格 $(i+1, j)$ 或者向右移动到单元格 $(i, j+1)$。当且仅当路径上所有单元格——包括起始单元格 $(1, 1)$——的值均为 $0$ 时，她才能沿着这条路径移动。在她出发之前，她可以进行任意次下列操作。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
string s, t;
cin >> s >> t;
vl pre(n);
pre[0] = (t[0] == '0' ? -1 : 1);
rep(i, 1, n - 1) { pre[i] = pre[i - 1] + (t[i] == '0' ? -1 : 1); }
ranges::sort(pre);
vl pre2(n);
pre2[0] = pre[0];
rep(i, 1, n - 1) pre2[i] = pre2[i - 1] + pre[i];
ll ans = 0;
ll tem = 0;
rep(i, 0, n - 1) {
tem += (s[i] == '0' ? 1 : -1);
ll tem2 = ranges::lower_bound(pre, tem) - pre.begin();
ans += tem * tem2 - (tem2 > 0 ? pre2[tem2 - 1] : 0);
ans += (tem2 > 0 ? pre2[n - 1] - pre2[tem2 - 1] : pre2[n - 1]) - (n - tem2) * tem;
}
cout << (n * n * (n + 1) - ans) / 2 << endl;
return;
}
|
G
题目大意：为了帮助 Kudryavka 提高数学能力，她得到了一个包含 $n$ 个互不相同正整数的集合 $S$。初始时，她的得分为 $1$。只要集合不为空，她可以对集合执行任意次数如下操作： 1. 设 $S$ 的最小值为 $m$。2. 将她的得分乘以 $m$。3. 从 $S$ 中移除 $m$。4. 对于每个满足 $1 \le i < m$ 的整数 $i$，将 $i$ 加入集合 $S$。可以证明在此步骤中不会添加重复元素。她沉迷于执行这些操作，但在进行了 $k$ 次操作后，她忘记了自己的得分。需要帮她计算她的得分，结果对 $10^9+7$ 取模。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^9$，$1 \le s_i \le 10^9$，$\sum n \le 2 \times 10^5$。
思路：
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
| using i128 = __int128_t;
constexpr int MOD = 1e9 + 7;
constexpr int MX = 1e5 + 1;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
ll res = 1;
for (; n; n >>= 1) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD; // 预处理阶乘
INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
} // 预处理逆元
return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
ll l[31];
ll val[31];
auto init2 = [] {
l[0] = 0, val[0] = 1;
rep(i, 1, 30) {
l[i] = l[i - 1] * 2 + 1;
val[i] = mul(mul(val[i - 1], val[i - 1]), i);
}
return 0;
}();
void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
ll ans = 1;
rep(i, 0, n - 1) {
if (k == 0) break;
ll tem = (a[i] > 31 ? LLONG_MAX : (1LL << (a[i] - 1)));
if (tem <= k) {
ans = mul(ans, a[i]);
ans = mul(ans, val[a[i] - 1]);
k -= tem;
} else {
ans = mul(ans, a[i]);
k--;
ll tem2 = (a[i] - 1 >= 31 ? 30 : a[i] - 1);
while (k > 0 && tem2 > 0) {
if (k <= l[tem2 - 1]) {
tem2--;
continue;
}
ans = mul(ans, val[tem2 - 1]);
k -= l[tem2 - 1];
if (k == 0) break;
ans = mul(ans, tem2);
k--;
if (k == 0) break;
tem2--;
}
}
}
cout << ans << endl;
return;
}
|
H
题目大意：羽未有一个数组 $a$，包含了 $n$ 个介于 $1$ 和 $m$ 之间的整数。她非常喜欢互质的数，想从找出四个不同的索引 $p,q,r,s$（$1 \le p,q,r,s \le n$）使得 $\gcd(a_p,a_q)=1$ 并且 $\gcd(a_r,a_s)=1$，其中 $\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公因数。如果有多个答案，你可以输出其中任意一组。
数据范围：$1 \le t \le 10^4$，$4 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^6$，$1 \le a_i \le m$，$\sum n \le 2 \cdot 10^5$，$\sum m \le 10^6$。
思路：
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
| using i128 = __int128_t;
constexpr int MX = 1e6 + 5;
vector<int> divisors[MX];
vector<int> fac[MX];
auto init = [] {
rep(i, 1, MX - 1) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
rep(i, 2, MX - 1) {
if (fac[i].empty()) {
for (int j = i; j < MX; j += i) {
fac[j].push_back(i);
}
}
}
return 0;
}();
void solve() {
ll n, m;
cin >> n >> m;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll maxx = *max_element(all(a));
vl cnt(maxx + 1);
vl cnt2(maxx + 1);
rep(i, 0, n - 1) {
for (auto& p : divisors[a[i]]) {
cnt[p]++;
}
}
rep(i, 1, maxx) {
if (!cnt[i]) continue;
int tem = sz(fac[i]);
ll tot = 0;
rep(j, 1, (1 << tem) - 1) {
ll tem2 = 1;
rep(v, 0, tem - 1) {
if (j >> v & 1) {
tem2 *= fac[i][v];
}
}
if (popcount((unsigned)j) % 2 == 1)
tot += cnt[tem2];
else
tot -= cnt[tem2];
}
cnt2[i] = tot;
}
vl deg(n);
rep(i, 0, n - 1) { deg[i] = n - cnt2[a[i]] - (a[i] == 1); }
int idx1 = -1, idx2 = -1;
rep(i, 0, n - 1) {
if (!deg[i]) continue;
rep(j, 0, n - 1) {
if (i == j) continue;
if (__gcd(a[i], a[j]) == 1) {
idx1 = i, idx2 = j;
break;
}
}
if (idx1 != -1) break;
}
if (idx1 == -1) {
cout << 0 << endl;
return;
}
rep(i, 0, n - 1) {
if (i == idx1 || i == idx2) continue;
ll tem = deg[i];
if (__gcd(a[i], a[idx1]) == 1) tem--;
if (__gcd(a[i], a[idx2]) == 1) tem--;
if (tem == 0) continue;
rep(j, 0, n - 1) {
if (j == i || j == idx1 || j == idx2) continue;
if (__gcd(a[i], a[j]) == 1) {
cout << i + 1 << ' ' << j + 1 << ' ' << idx1 + 1 << ' ' << idx2 + 1 << endl;
return;
}
}
}
vl idx3, idx4;
rep(i, 0, n - 1) {
if (i == idx1 || i == idx2) continue;
if (__gcd(a[i], a[idx1]) == 1 && sz(idx3) < 2) idx3.push_back(i);
if (__gcd(a[i], a[idx2]) == 1 && sz(idx4) < 2) idx4.push_back(i);
}
for (auto& p : idx3) {
for (auto& q : idx4) {
if (p != q) {
cout << p + 1 << ' ' << idx1 + 1 << ' ' << q + 1 << ' ' << idx2 + 1 << endl;
return;
}
}
}
cout << 0 << endl;
return;
}
|
