A
题意
Sakurako和Kosute用数轴上一个点玩游戏，Sakurako把点往x轴负方向走，Kosute把点往x轴正方向走，两人依次走1，3，5，7....单位长度，从原点开始，Sakurako先手。现在给出点只能到达的范围\([-n, n]\)，求最后一个移动的人。
题解
点从原点依次移动-1，3，-5，7...
那么每一次移动后点所在的坐标应该是-1，2，-3，4...那么一个人移动后恰好到达的坐标的绝对值等于\(n\)时，下一个人一定是最后一个移动的，因为下一个人会移动到\(-n\)，然后停止移动。所以根据\(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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
if (n & 1) {
cout << "Kosuke" << "\n";
} else {
cout << "Sakurako" << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
B
题意
给定一个矩阵，每次可以选定一条主对角线，把上面的所有数都+1，求进行至少多少次操作可以把矩阵里面的数字均变为非负的。
题解
显然我们找到每一条主对角线最小的负数相加即可。注意主对角线的性质：\((i,j)\)和\((i+1,j+1)\)在同一条主对角线，那么\(i-j\)应该为定值。
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<vector<int>> m(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> m[i][j];
}
}
map<int, int> mp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mp[j - i] = min(mp[j - i], m[i][j]);
}
}
int ans = 0;
for (int i = 1 - n; i <= n - 1; i++) {
ans -= mp[i];
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
C
题意
给定一个长度为\(n\)数组\(a_i\)，定义学生的干扰度为满足\(a_i =
a_{i+1}\)的元素个数。现在可以交换处于对称位置的两个元素任意次数，求干扰度的最小值。
题解
我们钦定每一组数如果进行交换只考虑已经进行交换过的部分，而不需要考虑别的部分。这样做的理由是如果每一组数都按照这样的规则，那么最优的方案是可以从部分拓展到全部的，即：第二组数交换时考虑第一组数，第三组数交换时考虑第一组数......直到所有数都遍历完，而第一组数交换与否是不会影响结果的，因为每一组数都交换其实和每一组数都不交换是等价的，因为结果数量不会变化，只是顺序反了。因此我们贪心地从外侧遍历到内侧，执行最优策略即可。
注意：不要同时考虑相邻的未交换的部分和已交换的部分，这样做的话如果下一组需要交换，上一组的答案就不对了，因为它考虑的是下一组不交换的情况。
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i < n / 2; i++) {
int cnt = 0, cnt2 = 0;
int j = n - i - 1;
if (i - 1 >= 0 && a[i - 1] == a[i]) {
cnt++;
}
if (j + 1 < n && a[j + 1] == a[j]) {
cnt++;
}
if (i - 1 >= 0 && a[i - 1] == a[j]) {
cnt2++;
}
if (j + 1 < n && a[j + 1] == a[i]) {
cnt2++;
}
if (cnt > cnt2) {
swap(a[i], a[j]);
}
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
if (a[i] == a[i + 1]) {
ans++;
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
D
题意
给定一个数组，将这个数组划分为若干子数组（每个数只能出现在一个子数组里）给出这个数组里和为0的子数组的最大数量。
题解
显然需要统计区间和，我们可以通过前缀和处理，假设区间\([l,r]\)满足和为0，\(pre_i\)表示加到\(i\)位置的前缀和，那么有\(pre_r - pre_{l-1} = 0\)即\(pre_r =
pre_{l-1}\)，所以我们可以通过哈希表记录下从左到右遍历出现的每个前缀和的出现次数，每次求出一个前缀和，若之前出现过同样大小的前缀和，说明这个区间是可以作为一个答案的。
需要注意的是我们每次求出一个答案，这个区间里面的数是不能再用的，因此需要清空哈希表。同时，如果某个位置的前缀和就是0，它可以单独作为一个答案，因此每次清空哈希表后都要把0的出现次数设为1进行特判。这样又会出现一个问题，考虑这样的情况：所有数的和恰好为0，且前面已经有一个和为0的子数组，那么把整个数组看作一个答案是不行的，因此我们在统计出一个答案时把当前的前缀和也设为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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int ans = 0;
int n;
cin >> n;
vector<int> a(n);
map<int, int> mp;
mp[0] = 1;
int preSum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
preSum += a[i];
if (mp[preSum]) {
ans++;
mp.clear();
mp[0] = 1;
preSum = 0;
} else {
mp[preSum]++;
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
E
题意
给定一个大小为\(n\)的数组\(p_i\)，里面的数是\(n\)的一个排列，可以任选数组中的两个数交换位置任意多次，要求最后的数组满足\(p_i = i\)或\(p_{p_i} = i\)，求最少交换次数。
题解
如果数组中位置\(i\)向\(p_i\)连一条边，我们知道会形成多个环，而题目中的条件等价于每个环都是自环或大小为2的环，因此，我们可以把大小大于2的环拆分成自环和大小为2的环。有这样一个事实：边是从一个位置\(i\)连向位置\(p_i\)的，交换位置\(i,j\)，应该有它们连向的位置不变，而起点改变。
考虑一个三元环，由于三个位置相互连接形成环，因此我们任意交换其中两个数，例如把位置1连向的数和连向位置1的数交换位置，这样就会形成一个二元环和一个自环。
考虑一个四元环，按照同样的方法，把位置1连向的数和连向位置1的数交换位置，这样就会形成两个二元环。
同理，五元环经过一次交换就可以变成三元环的情况，六元环经过一次交换会变为四元环的情况。
因此，每个环需要的交换次数就是\(\lfloor(size-1)/2\rfloor\)。我们可以\(O(n)\)的复杂度通过vis数组找环，最后在计算答案。
时间复杂度：\(O(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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
vector<bool> vis(n);
int cnt = -1;
for (int i = 0; i < n; i++) {
int j = i;
cnt += (vis[j] == 0);
while (!vis[j]) {
vis[j] = 1;
c[cnt]++;
b[j] = cnt;
j = a[j];
}
}
int ans = 0;
for (int i = 0; i <= cnt; i++) {
ans += (c[i] - 1) / 2;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
F
题意
给定\(n,k\)，求第\(n\)个被\(k\)整除的斐波那契数列的位置。初始时\(fib[1] = 1, fib[2] = 1\)。
\(1\le n \le 10^{18}\)
题解
考虑到\(n\)的范围很大，只有$\(级别的复杂度才能通过，由于是被\)k\(整除的数，我们不妨在模\)k$意义下计算斐波那契数列，这样为0的项就是符合条件的。
一个可以通过打表或证明的结论是：斐波那契数列是存在周期的。
我们设\(F_i\)为第\(i\)项斐波那契数列的值，\(G_i \equiv F_i (\mod k)\)，那么\(G_i\in
{0,1,2,...k-1}\)，因此对于相邻的两个数\((G_i,G_{i+1})\)，它们的取值是有限的，因为他们的组合不超过\(k^2\)种。也就是说，对于至少\(k^2+1\)个连续的\(G_i\)，一定存在两个数对\((G_i,G_{i+1}),(G_j,G_{j+1})\)满足\(G_i=G_j,G_{i+1}=G_{j+1}\)，又因为斐波那契数列的定义，这个数列是存在循环节的。
实际上还有皮萨诺定理：在模\(k\)的情况下斐波那契数列的周期不超过\(6k\)，证略。
事实上，我们最终的答案就是第一个被\(k\)整除的数的位置乘\(n\)，这是因为模\(k\)意义下，数列是从1开始的，大致为：1，1，2，3，......，0。因为这是一个周期数列，我们还可以往前写：......，0，1，1，2，3，......，0（省略号之中不存在0）。我们发现出现0这个数后，它的后一个数必为1。因此，我们从第一个数开始，已知寻找到被\(k\)整除的数，随后这段数列就会重复出现，答案易得。
防止内存不够，我们可以通过滚动数组优化，由于所有样例之和的\(k\)不超过\(10^6\)，因此时间复杂度为\(O(k)\)
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(3);
a[0] = 1;
a[1] = 1;
int idx = 0;
const int mod = 1e9 + 7;
for (int i = 0;; i++) {
if (i >= 2) {
a[i % 3] = (a[(i - 1) % 3] + a[(i - 2) % 3]) % k;
}
if (a[i % 3] % k == 0) {
idx = i;
break;
}
}
cout << (idx + 1) % mod * (n % mod) % mod << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
G
题意
给定一棵树，和\(q\)次询问，每次询问给定一个节点和一个体力\(k\)，规定一个节点向叶子节点移动不消耗体力，向根节点移动消耗一个单位的体力，求能移动到的位置到出发点的最长距离。
题解
我们考虑能够作为答案的位置。叶子节点显然是可以作为答案的，我们可以通过一次DFS来得到每个节点到叶子节点的距离（即高度）。然后考虑向根节点移动的情况，假设从\(v\)节点移动到\(u\)节点，考虑两种情况：如果\(u\)到叶子节点的最长距离恰好经过\(v\)，那么我们选择\(u\)到另一个叶子节点的次长距离一定是最优的，因为一定比\(u\)到\(v\)的距离长；否则，那么我们选择\(u\)到叶子节点的最长距离就是答案。
我们通过一次DFS处理出每个节点到叶子节点的最长、次长距离，同时通过倍增的方式处理出每个节点的祖先节点，那么求解答案也可以通过倍增的方式求最大值。
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n);
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
x--, y--;
e[x].push_back(y);
e[y].push_back(x);
}
int logn = log2(n);
vector<vector<int>> p(n, vector<int>(logn + 1, -1));
vector<vector<int>> g(n, vector<int>(logn + 1));
vector<int> dep(n), h(n);
auto dfs = [&](auto self, int u) -> void {
int f[2]{};
for (auto v : e[u]) {
if (v == p[u][0]) {
continue;
}
dep[v] = dep[u] + 1;
p[v][0] = u;
self(self, v);
int val = h[v] + 1;
if (val > f[0]) {
f[1] = f[0];
f[0] = val;
} else if (val > f[1]) {
f[1] = val;
}
}
h[u] = f[0];
for (auto v : e[u]) {
if (v == p[u][0]) {
continue;
}
g[v][0] = f[f[0] == 1 + h[v]] + 1;
}
};
dfs(dfs, 0);
for (int i = 0; i < logn; i++) {
for (int j = 0; j < n; j++) {
if ((2 << i) <= dep[j]) {
p[j][i + 1] = p[p[j][i]][i];
g[j][i + 1] = max(g[j][i], g[p[j][i]][i] + (1 << i));
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int v, k;
cin >> v >> k;
v--;
int ans = h[v];
k = min(k, dep[v]);
int len = 0;
for (int j = logn; j >= 0; j--) {
if ((k >> j) & 1) {
ans = max(ans, g[v][j] + len);
v = p[v][j];
len += (1 << j);
}
}
cout << ans << " \n"[i == q - 1];
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|