 补题笔记（A-E）)
A. Lever
预计难度：红。
考察：语法。
对于所有满足 \(a_i>b_i\) 的下标 \(i\)，累计 \(a_i-b_i\) 再加上 \(1\) 就是结果。因为忽略操作 \(1\) 时还迭代了一次所以要加 \(1\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 12;
int t, n, a[N], b[N];
void Solve() {cin >> n; for(int i = 1; i <= n; i++) {cin >> a[i]; } for(int i = 1; i <= n; i++) {cin >> b[i]; } int ans = 0; for(int i = 1; i <= n; i++) {if(a[i] > b[i]) ans += a[i] - b[i]; }cout << ans + 1 << '\n'; return;
}
int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t--) Solve(); return 0;
}
B. Alternating Series
预计难度：橙。
考察：贪心、构造。
手玩样例发现奇数位得是负数，偶数位得是正数才行，否则不优。然后找规律发现如果偶数位除非是最后都填 \(3\)，最后的话填 \(2\)，奇数位全填 \(-1\) 即可。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 12;
int t, n, a[N], b[N];
void Solve() {cin >> n; if(n % 2 == 0) {for(int i = 1; i <= n - 1; i++) {if(i & 1) cout << -1 << ' '; else cout << 3 << ' '; }cout << 2 << '\n'; }else {for(int i = 1; i <= n; i++) {if(i & 1) cout << -1 << ' '; else cout << 3 << ' '; }cout << '\n'; }return;
}
int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t--) Solve(); return 0;
}
C. Make it Equal
预计难度：橙。
考察：数学-同余。
容易发现，如果一个数 \(y\) 能由 \(x\) 通过操作得到，那么令 \(a=x \bmod k\)，\(b=k-a\)，则 \(y\) 一定能表示成 \(a+xm\) 或 \(b+xm\) 的形式（\(m\) 为非负整数），即必须满足条件 \(y \equiv a\pmod x\) 或 \(y \equiv b\pmod x\)。那么，我们只要储存集合 \(S\) 中的每个数对应的 \(a,b\)，然后判断 \(T\) 中的每个数能否用这有限个 \(a,b\) 全部得到即可。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int t, n, k, a[N], b[N];
map<int, int> mp;
void Solve() {cin >> n >> k; for(int i = 1; i <= n; i++) {cin >> a[i]; } for(int i = 1; i <= n; i++) {cin >> b[i]; } for(int i = 1; i <= n; i++) {int c = a[i] % k; mp[c]++;mp[(k - c) % k]++; }bool ok = 0; for(int i = 1; i <= n; i++) {int c = b[i] % k; if(!mp[c]) {ok = 1; break; }mp[c]--, mp[(k - c) % k]--; }for(int i = 1; i <= n; i++) {int c = a[i] % k; mp[c] = 0; mp[(k - c) % k] = 0; }if(!ok) cout << "YES\n"; else cout << "NO\n"; return;
}
int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t--) Solve(); return 0;
}
D. Arboris Contractio
预计难度：黄。
考察：贪心、树的直径。
容易发现，当点数大于 \(2\) 时，树操作后能得到的最小直径必然为 \(2\)，我们需要思考怎么把它的直径快速变成 \(2\)。
容易发现选取某一个点为起点后，不仅到终点的路径上的点无需再操作一次，其他与其相邻的点也不需要再操作了。那我们每次操作贪心地选取当前拥有深度大于 \(1\) 的叶节点最多的节点就能保证操作次数最少了。下面是示意图。
如图，先选 \(1\) 为起点，再选 \(5\)，最后选 \(9\) 即可。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int t, n;
vector<int> g[N];
void solve(){cin >> n; for (int i = 1; i <= n; i++) g[i].clear(); for (int i = 1, u, v; i < n; i++) {cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }int ans = 0, maxx = 0;for (int i = 1; i <= n; i++) {if((int)g[i].size() > 1) {int tmp = 0; for(int v : g[i]) {tmp += ((int)g[v].size() == 1); } maxx = max(tmp, maxx); ans += tmp; }} cout << ans - maxx << endl; return;
}
int main(){cin >> t; while(t--) solve(); return 0;
}
E. Adjacent XOR
预计难度：黄。
考察：位运算、贪心。
题意简述
给你一个长度为 \(n\) 的数组 \(a\)，对于每个 \(1 \le i< n\)，最多可以执行一次下面的操作：
- \(a_i = a_i \oplus a_{i+1}\)。
给定另一个长度为 \(n\) 的数组 \(b\)，判断是否可以将 \(a\) 转换为 \(b\)。
解题报告
除去 \(i=n\) 的情况，如果 \(a_i\) 可以变成 \(b_i\)，那么可以是 \(a_{i+1}\) 在修改之前被其用来修改，也可以是 \(a_{i+1}\) 修改成 \(b_{i+1}\) 之后被 \(a_i\) 用来修改，还有一种情况是本来就 \(a_i=b_i\)。判断通过这两个操作之一能否变成 \(b_i\) 就好。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int t, n;
int a[N], b[N], c[N], d[N]; void Solve() {cin >> n; for(int i = 1; i <= n; i++) {cin >> a[i]; } for(int i = 1; i <= n; i++) {cin >> b[i]; } if(a[n] != b[n]) {cout << "NO\n"; return; } for(int i = 1; i <= n - 1; i++) {int c1 = (a[i] ^ a[i + 1]), c2 = (a[i] ^ b[i + 1]);if(c1 == b[i] || c2 == b[i] || a[i] == b[i]) continue; else {cout << "NO\n"; return; }}cout << "YES\n"; return;
}
int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t--) Solve(); return 0;
}