A. 买爱心气球（博弈）
输入
3
3 1
3 3
5 2
输出
Alice
Alice
Bob
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"using namespace std;const int N = 2e5 + 10;int n, m, f;void solve()
{cin >> n >> m;if(n % 3 == m) cout << "Bob\n";else cout << "Alice\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
B. 亚托莉 -我挚爱的时光-(大模拟)
输入1
4
sudo pacman -S genshinimpact
1 genshinimpact
pacman -R genshinimpact
1 genshinimpact
输出1
yes
no
说明
第一行安装了某软件，然后询问了某软件，回答yes,表示安装上了，之后卸载了某软件，问是否还有这款软件，回答no,表示没有这款软件。
输入2
6
sudo pacman -S genshinimpact
pacman -R genshinimpact
2 genshinimpact
sudo pacman -S genshinimpact
pacman -Rscn genshinimpact
2 genshinimpact
输出2
yes
no
说明
前两个指令先安装了某软件，并且卸载了某软件，但是个人数据却没有删除掉，问是否有这款软件的数据，回答yes,之后又安装上了这款软件，又将软件和个人数据一并卸载掉，所以问是否有这款软件的个人数据，回答no。
输入3
5
1 genshinimpact
sudo pacman -S genshinimpact
sudo rm -rf /*
2 genshinimpact
1 genshinimpact
输出3
no
wuwuwu
说明
第三条命令导致输出wuwuwu，所以之后的命令不用回答，直接退出。
点击查看代码
#include<bits/stdc++.h>
#define endl "\n"using namespace std;string s[5];
string t[10] = {"sudo", "pacman", "-S", "-R", "rm", "-Rscn"};
map<string, int> mp;void solve()
{int n, f = 1;cin >> n;while(n --){cin >> s[0] >> s[1];if(s[0] == "1"&&f){if(mp[s[1]] == 2) cout << "yes\n";else cout << "no\n";}else if(s[0] == "2"&&f){if(mp[s[1]]) cout << "yes\n";else cout << "no\n";}else if(s[0] == "sudo"){if(s[1] == "pacman"){cin >> s[2] >> s[3];if(s[2] == "-S")mp[s[3]] = 2;}else{cin >> s[2] >> s[3];cout << "wuwuwu\n";f = 0;
// break;}}else if(s[0] == "pacman"){cin >> s[2];if(s[1] == "-R")mp[s[2]] = 1;else mp[s[2]] = 0;}}}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;
// cin >> T;while(T --)solve();return T ^ T;
}
D. 01分数规划（扫描遍历）
输入
5
5
01110
1
0
4
01??
3
110
3
1??
输出
3
1
3
2
3
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"using namespace std;const int N = 2e5 + 10;int n, m, ans, mx1, mx0;
int a[N], f, t, ss;
string s;void solve()
{cin >> n >> s;mx0 = mx1 = t = 0;for(auto x : s){if(x == '0'||x == '?')t ++;else mx0 = max(mx0, t), t = 0;}mx0 = max(mx0, t);t = 0;for(auto x : s){if(x == '1'||x == '?')t ++;else mx1 = max(mx1, t), t = 0;}mx1 = max(mx1, t);cout << max(mx0, mx1) << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
E. 换根DP（并查集）
输入
5
1 2 2
2 3 2
1 4 1
4 5 2
输出
5
说明
以节点4作根时f(4)=w(4,1)+w(4,2)+w(4,3)+w(4,5)=gcd(1,2)+gcd(1,2,2)+1+2=1+1+1+2=5 可以证明，没有比上述情况更小的价值。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
// DSU with Size
struct DSU{ //并查集板子 vector<int> p, sz; //p 表示集合 ， se表示集合个数DSU(int n) : p(n + 1,0), sz(n + 1, 1){ //初始化 iota(p.begin(), p.end(), 0); // iota(sz.begin(), sz.end(), 1); }int find(int x){ //寻找根节点return p[x] == x ? x : p[x] = find(p[x]);}bool same(int x, int y) { //判断是否相同，根节点 return find(x) == find(y); }bool merge(int x, int y){ //合并集合 x = find(x), y = find(y);if (x == y) return false;if (sz[x] < sz[y]) swap(x, y);sz[x] += sz[y];p[y] = x;return true;}int size(int x) { //输出集合点数return sz[find(x)];}
};
int main()
{ios::sync_with_stdio(0);cin.tie(0);int n,m;cin>>n;DSU dsu(n+1);int x,y,w;for(int i=1;i<n;i++){cin>>x>>y>>w;if(w==2){dsu.merge(x,y);}}int ans=n;for(int i=1;i<=n;i++){ans=min(ans,dsu.size(i)-1);}cout<<ans+n-1<<"\n";return 0;
}G. Kruskal（二进制枚举）
输入
1
3
输出
1
说明
对于n=3的完全图，生成树的方式有如下三种：
- 1↔2,1↔3，生成树的权值之和为0+1=1
- 1↔3,2↔3，生成树的权值之和为1+2=3
- 1↔2,2↔3，生成树的权值之和为0+2=2
选择第一种连接方式最优，因此最小生成树的权值之和为1。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"using namespace std;const int N = 2e5 + 10, M = N * 2;int n, m, ans, s, ss;
int a[N], f[N];void solve()
{cin >> n;s = 0, ss = 0;m = n;while(n){if(n & 1) ss ++;n >>= 1;}while(m)s ++, m >>= 1;
// cout << s << ' ' << ss << ' ';if(s == ss) ans = 1;else ans = 0;cout << ans << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
I. 双指针（map）
输入
2
5
3 2 2 2 3
3 1 2 4 2
5
2 1 1 1 3
4 2 4 3 1
输出
2
1
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"using namespace std;const int N = 2e5 + 10;int n, m, ans, mx1, mx0;
int a[N], b[N], t;int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}void solve()
{cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 1; i <= n; i ++)cin >> b[i];map<pair<int, int>, int> mp;ans = 0;for(int i = 1; i <= n; i ++){int t = gcd(a[i], b[i]);a[i] /= t, b[i] /= t;auto s = mp[{a[i], b[i]}];ans += s;mp[{b[i], a[i]}] ++;
// cout << ans << ' ';}cout << ans << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
J. 树上DP（树上dp+贪心）
输入
5
2
1 2
9 8
4
1 2
2 3
2 4
6 6 5 7
8
1 2
1 3
1 5
2 4
4 7
5 6
5 8
8 10 9 7 3 6 9 8
5
1 2
1 3
1 4
4 5
2 3 5 9 9
2
1 2
7 4
输出
26
56
163
63
18
说明
对于第二个样例
4
1 2
2 3
2 4
6 6 5 7
可以先交换节点2,3上的权值， 再交换节点1,2上的权值
此时的美丽值最大
该树的美丽值计算过程为：以1为根的子树权值和+以2为根的子树权值和+以3为根的子树权值和+以4为根的子树权值和=24+19+6+7=56
点击查看代码
#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 2e5 + 10, M = N * 2;int n, m, cnt, ans, ss;
int a[N], f[N], depth[N], q[N], s[N], t[N];
int h[N], e[M], ne[M], idx;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void init()
{int tt = -1, hh = 0;depth[1] = 1;q[++ tt] = 1;while(hh <= tt){int t = q[hh ++];for(int i = h[t]; ~i; i = ne[i]){int j = e[i];if(depth[j] == 0){depth[j] = depth[t] + 1;q[++ tt] = j;}}}
}void solve()
{cin >> n;for(int i = 1; i <= n; i ++)h[i] = -1;cnt = ans = 0;for(int i = 1; i < n; i ++){int a, b;cin >> a >> b;add(a, b), add(b, a);}init();ss = 0;for(int i = 1; i <= n; i ++)s[depth[i]] ++, ss = max(ss, depth[i]);for(int i = 1; i <= ss; i ++)if(s[i])t[++ cnt] = s[i];for(int i = 1; i <= n; i ++)cin >> a[i];
// sort(t, t + cnt);sort(a + 1, a + n + 1);
// for(int i = 0; t[i]; i ++)
// cout << t[i] << ' ';
// cout << "\n";
// for(int i = 1; i <= n; i ++)
// cout << a[i] << ' ';
// cout << cnt << "\n";for(int i = n; i >= 1; i --){ans += a[i] * cnt;
// cout << a[i] << ' ' << cnt << "\n";t[cnt] --;if(t[cnt] == 0) cnt --;}cout << ans << "\n";idx = 0;for(int i = 0; i <= n; i ++)depth[i] = 0;for(int i = 0; i <= ss; i ++)s[i] = t[i] = 0;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --)solve();return T ^ T;
}
