D. Balanced Round
双指针，贪心
题意：
给出\(n\)个数，我们可以删去其中若干个数，使得删完后的数重新排列任意相邻的数之差绝对值不超过\(k\)，输出最小删去数的个数
思路：
很明显可以先将给出的数组进行排序。对于排序后的数组，我们可以将其分为若干个相邻差绝对值不超过\(k\)的子数组，对于每个子数组，很明显我们只能留下其中一个。考虑贪心选取其中长度最大的，若长度为\(len\)，则答案为\(n - len\)。
void QAQ(){
int n, k;
cin >> n >> k;
vector<int> num(n + 1);
for(int i = 1; i <= n; i ++){
cin >> num[i];
}
sort(num.begin() + 1, num.end());
int ans = 1, l = 1, r = 1;
for(int i = 2; i <= n; i ++){
if(abs(num[i] - num[i - 1]) <= k) r ++;
else{
ans = max(ans, r - l + 1);
l = r + 1;
r = l;
}
}
ans = max(ans, r - l + 1);
cout << n - ans << endl;
}
E. Cardboard for Pictures
题意：
有\(n\)幅照片，每幅图片都裱在一块正方形硬纸板上，这样每幅图片的四边都有 \(w\)厘米的硬纸板边框。他总共用了\(c\)平方厘米的硬纸板。已知图片尺寸和数值\(c\)，求出恰好满足要求的\(w\)
思路：
二分查找答案。
数据范围大要开__int128
void QAQ(){
ll n, c;
cin >> n >> c;
vector<ll> num(n + 1);
for(int i = 1; i <= n; i ++){
cin >> num[i];
}
int l = 0, r = 1e9 + 10;
auto check =[&] (int x) -> bool {
int cnt = 0;
for(int i = 1; i <= n; i ++){
cnt += (num[i] + x * 2) * (num[i] + x * 2);
if(cnt >= c) return false;
}
return true;
};
while(l + 1 < r){
int mid = l + r >> 1;
if(check(mid)) l = mid;
else r = mid;
}
cout << (ll)r << endl;
}
F. We Were Both Children
题意：
有\(n\)只青蛙，第\(i\)只青蛙每次跳\(a_i\)距离，我们可以挑选一个位置放置陷阱，使其能捕捉到的青蛙个数最多
思路：
直接暴力统计每个青蛙会跳过的位置，取max即可，注意去重否则会t掉
void QAQ(){
int n;
cin >> n;
vector<int> num(n + 1);
map<int, int> mp;
int ans = 0;
for(int i = 1; i <= n; i ++){
cin >> num[i];
}
sort(num.begin(), num.end());
int k = 1;
while(k <= n){
int cnt = 1;
while(k < n && num[k] == num[k + 1]){
k ++;
cnt ++;
}
for(int j = num[k]; j <= n; j += num[k]){
if(j <= n){
mp[j] += cnt;
ans = max(ans, mp[j]);
}
}
k ++;
}
cout << ans << endl;
}
G. The Morning Star
题意：
有\(n\)个指针，放在不同位置，可以指向上下左右，左上，左下，右上，右下，问能找出多少对指针互相指向彼此
思路：
分别用多个map记录x，y，x + y，x - y（分别代表上下，左右，左上右下，左下右上），对每个点记录求和即可。
void QAQ(){
int n;
cin >> n;
map<int, int> dia, inv, xx, yy;
vector<pll> s;
for(int i = 1; i <= n; i ++){
int a, b;
cin >> a >> b;
s.push_back({a, b});
xx[a] ++;
yy[b] ++;
dia[a - b] ++;
inv[a + b] ++;
}
int ans = 0;
for(auto it : s){
int x, y;
tie(x, y) = it;
ans += xx[x] - 1;
ans += yy[y] - 1;
ans += dia[x - y] - 1;
ans += inv[x + y] - 1;
}
cout << ans << endl;
}
H. The Third Letter
题意：
共有\(n\)个人，给出\(m\)组距离关系，\(a_i,b_i,d_i\)，若\(d_i\)大于\(0\)代表\(a_i\)在\(b_i\)前\(d_i\)距离的位置，小于\(0\)同理，问是否所有关系都能被满足。
思路：
有两种不同思路，一种是利用带权并查集记录两点间的关系，在线查询和合并；第二种是建图，对每个连通块dfs查看是否存在距离冲突。
带权并查集
void QAQ(){
int n, m;
cin >> n >> m;
vector<int> fa(n + 1), dis(n + 1);
iota(fa.begin(), fa.end(), 0);
//===========================================================================
auto find = [&] (auto find, int x) -> int{
// cerr << x << " " << fa[x] << endl;
if(fa[x] != x){
int t = find(find, fa[x]);
dis[x] = dis[fa[x]] + dis[x];
fa[x] = t;
}
return fa[x];
};
auto add = [&] (int u, int v, int c) -> void {
int uu = find(find, u), vv = find(find, v);
fa[uu] = vv;
dis[uu] = dis[v] - dis[u] - c;
};
//===========================================================================
bool flag = true;
for(int i = 1; i <= m; i ++){
int u, v, c;
cin >> v >> u >> c;
int uu = find(find, u), vv = find(find, v);
if(uu == vv){
if(dis[v] - dis[u] != c){
flag = false;
}
}
else{
add(u, v, c);
}
}
if(flag){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
}
建图dfs
void QAQ(){
int n, m;
cin >> n >> m;
vector<int> vis(n + 1), dis(n + 1);
//===========================================================================
struct type{
int nxt, to, w;
};
vector<type> e(m * 2 + 1);
vector<int> h(n + 1);
int idx = 0;
auto add = [&] (int u, int v, int w) -> void {
idx ++;
e[idx].to = v;
e[idx].w = w;
e[idx].nxt = h[u];
h[u] = idx;
};
for(int i = 1; i <= m; i ++){
int u, v, w;
cin >> v >> u >> w;
add(u, v, w);
add(v, u, -w);
}
//===========================================================================
bool flag = true;
auto dfs = [&](auto dfs, int u) -> void {
vis[u] = true;
for(int i = h[u]; i; i = e[i].nxt){
int v = e[i].to, w = e[i].w;
if(vis[v]){
if(dis[u] + w != dis[v]) flag = false;
}
else{
dis[v] = dis[u] + w;
dfs(dfs, v);
}
}
};
for(int i = 1; i <= n; i ++){
if(!vis[i]){
dfs(dfs, i);
}
if(!flag) break;
}
//===========================================================================
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}