T1： P14023 [ICPC 2024 Nanjing R] 社交媒体
solution
我会暴力！
提前计算好每个好友的贡献，枚举选取哪两个好友，计算结果。
注意：map 不要在循环内开，否则会被卡到30pts！
时间复杂度 \(O(n ^ 2)\)
我做过P8817 [CSP-S 2022] 假期计划 ！
考虑优化掉其中一个点。
枚举一个好友，更新其他好友的贡献，这样就可以贪心了。
注意计算对已经是好友的点的贡献
虽然我做过这道题但是考场上出现神秘错误，属于是运气不行了
code：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int QWQ = 2e5 + 5;
map<int, int> g[QWQ];
void solve()
{int n, m, k, a[QWQ], f[QWQ], vis[QWQ], in[QWQ], U[QWQ], V[QWQ];int ans = 0;for(int i = 1;i <= k;i ++) g[i].clear();memset(vis, 0, sizeof(vis));memset(in, 0, sizeof(in));cin >> n >> m >> k;for(int i = 1;i <= n;i ++){cin >> f[i];vis[f[i]] = 1;}for(int i = 1;i <= m;i ++){cin >> U[i] >> V[i];int u = U[i], v = V[i];if(u == v && !vis[u]){in[u] ++;}g[u][v] ++, g[v][u] ++;if(vis[u] && !vis[v]){in[v] ++;}if(vis[v] && !vis[u]){in[u] ++;}if(vis[v] && vis[u]){ans ++;}}int res = 0, fi = 0, se = 0;for(int i = 1;i <= k;i ++){if(in[i] >= fi){se = fi;fi = in[i];}else if(in[i] >= se){se = in[i];}}res = max(res, fi + se);for(int i = 1;i <= m;i ++){int u = U[i], v = V[i];if(u != v && !vis[u] && !vis[v]){res = max(res, in[u] + in[v] + g[u][v]);}}cout << ans + res << endl;
}
signed main()
{int T;cin >> T;while(T --) solve();
}
T2：
小明和机器人一共会进行 \(T\) 轮游戏。
每轮游戏中，机器人会给小明一个长度为 \(N\) 的数列 \(a_1,\ a_2,\ ...,\ a_N\)。
小明需要将这个数列转化为一棵大小为 \(N\) 的树，每条边的长度均为 \(1\)。，使得树上的任意节点 \(i\)，到距离它最远的点的距离都是对应的 \(a_i\)。
solution
考虑树的直径。
肯定是要把最大的点放在直径两端的，最小的点放在树的重心上，如果不能构造出这样的数，那么直接判无解。
然后把树拆成一条链，每次插入一个距离就尝试加入一个叶子节点。
构造不出来就输出无解
code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int QWQ = 1e5 + 5;
void solve()
{int n, a[QWQ], qwq[QWQ], sum;memset(qwq, 0, sizeof(qwq));cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];qwq[a[i]]++;}sort(a + 1, a + n + 1);if (a[1] < (a[n] + 1) / 2){cout << "No" << endl;return;}for (int i = a[n]; i >= (a[n] + 1) / 2; i--){int w = 2;if (i == a[n] / 2){w = 1;}if (qwq[i] < w){cout << "No" << endl;return ;}qwq[i] -= w;}if (qwq[(a[n] + 1) / 2]){cout << "No" << endl;}else{cout << "Yes" << endl;}
}
signed main()
{int T;cin >> T;while (T--)solve();
}
T3：P14015 [ICPC 2024 Nanjing R] 生日礼物
题意
给你一个序列，你可以执行任意次操作。每次可以执行以下三种操作之一：
- 将任意一个 \(2\) 改为 \(0\) 或 \(1\)。
- 选择两个相邻的 \(0\)，删除它们，并将剩下的部分连接起来。
- 选择两个相邻的 \(1\)，删除它们，并将剩下的部分连接起来。
求能得到的最短序列的长度。
solution
神秘trick
将奇数位的 \(0\) 给替换成 \(1\)，\(1\) 替换成 \(0\)，那么每次消除就是消除序列中的 \(01\) 或 \(10\)。
当序列中不存在 \(2\) 时，记序列中 \(0\) 的个数为 \(cnt_0\)，\(1\) 的个数为 \(cnt_1\)，那么答案就是 \(|cnt_0 - cnt_1|\)。
发现最后剩下的序列中要么全是 \(0\)，要么全是 \(1\)。
考虑序列中存在 \(2\) 的情况，尝试将 \(2\) 替换成 \(0\) 和 \(1\) 中数量最少的那个，这样可以使答案达到最小。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve() {string s;int cnt0 = 0, cnt1 = 0;cin >> s;for(int i = 1;i < s.size();i += 2) {if(s[i] == '0') s[i] = '1';else if(s[i] == '1') s[i] = '0';}for(int i = 0;i < s.size();i ++) {if(s[i] == '0') cnt0 ++;if(s[i] == '1') cnt1 ++;}for(int i = 0;i < s.size();i ++) {if(s[i] != '2') continue;if(cnt0 < cnt1) cnt0 ++;else cnt1 ++;}cout << abs(cnt0 - cnt1) << endl;
}
signed main() {int T;cin >> T;while(T --) solve();
}