2020 KAIST 10th ICPC Mock Contest (XXI Open Cup. Grand Prix of Korea. Division 2) 补题

ICPC Mock Contest (XXI Open Cup. Grand Prix of Korea. Division 2) 补题"/>

2020 KAIST 10th ICPC Mock Contest (XXI Open Cup. Grand Prix of Korea. Division 2) 补题

2021.2.10 校队训练纪念戳
诶诶诶怎么大年二十九还训练啊qwq
不得不说 感觉这套题好难读题啊qwq 因为我英语太差了qwq？？
慢速补题中qwq

A- Advertisement Matching

B- Bombs In My Deck

比较签到的一个题，直接用一个搜索就完事了。
但是注意30的阶乘是大于long long范围的！
实测：20!还在long long范围内，但是21!就超过了qwq

#include<bits/stdc++.h>
using namespace std;
double ans1, ans2;
inline void solve(double x, int a, int b, int c){if(a <= 0) return;double cur_ans = x * b / a;if(b > 0) {if(c <= 5) ans1 += cur_ans;else solve(cur_ans, a - 1, b - 1, c - 5);}return;
}
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifint a, b, c;scanf("%d%d%d", &a, &b, &c);ans2 = 1.0;for(int i = 2; i <= a; i++) ans2 *= i; solve(ans2, a, b, c);printf("%.7lf\n", (ans2 - ans1) / ans2);return 0;
}

C- Economic One-way Roads

D- Fix Wiring

题目大意：有n个点，连一张完全图。现在有n*(n-1)/2个值，你需要由某种策略给每条边赋上这些值，使得建立一个最小生成树的费用最小 和 最大（两问），求最小值和最大值是多少。
最小值显然就是选前n-1条最小的边。
最大值就是我们需要使得小的边尽可能没用。那么我们假设最小生成树应当是从点1连点2，点2连点3…点n-1连点n，我们每次按次序往里面加一个点。
我们可以发现，每次加入一个点的时候，总要向前n-1个点连边。而此时，举个例子来说，如果点i连上了通往点1的边，那么点1到点i这条中间按着顺序直接连的i-1条边中有可能就有一条边不再是最小生成树上的边。
那么我们就有做题策略了，将边从小到大排序之后进行使用。按照次序加点，每次点i向前连边，一直连到通往点1的边（这样是保证i到i-1的边是最小边以使其一定在最小生成树上）。

#include<bits/stdc++.h>
#define MAXN 200010
using namespace std;
int n, m;
int a[MAXN];
long long ans1, ans2;
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifscanf("%d", &n);m = n * (n - 1) / 2;for(int i = 1; i <= m; i++) scanf("%d", &a[i]);sort(&a[1], &a[m + 1]);for(int i = 1; i <= n - 1; i++) ans1 += a[i];int cnt = 0;for(int i = 2; i <= n; i++){for(int j = i - 1; j >= 1; j--){cnt++;if(i == j + 1) ans2 += a[cnt];}} printf("%lld %lld\n", ans1, ans2);return 0;
} 

E- Min-hashing

每个点的l都是不同的，所以在每一个联通块里都是最小值尽可能多的往外传。
如果当前联通块最小值ai在i点，那么对于一个点j来说，它第一次变成ai是在第dis(i,j)次，在这一次之后再传偶数次可以保证它的值还是ai，但是奇数次就不一定是。
所以在k次之后，如果原图是一个二分图的话，就会分成两类，一类是奇数次能够传到，一类是偶数次能被传到。我们对于两类分别计数。
如果不是的话，那么就有至少一条边可以做到奇偶互换，所以无数多次之后整个联通块都会变成一样的最小值。我们对联通块内所有节点进行计数。

#include<bits/stdc++.h>
#define MAXN 300010
#define MAXM 500010
using namespace std;int n, m, t;
int a[MAXN], head[MAXN], color[MAXN];
long long ans;
long long cnt[3];struct Edge{int nxt, to;}edge[MAXM << 1];inline void add(int from, int to){edge[++t].nxt = head[from], edge[t].to = to;head[from] = t;
}inline bool solve(int x, int tmp){bool flag = true;color[x] = tmp;cnt[tmp]++;for(int i = head[x]; i; i = edge[i].nxt){int v = edge[i].to;if(!color[v]){bool cur_flag;cur_flag = solve(v, 3 - tmp);if(cur_flag == false) flag = false;}if(color[v] == color[x]) flag = false;}return flag;
}
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifscanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);}int u, v;for(int i = 1; i <= m; i++){scanf("%d%d", &u, &v);add(u, v);add(v, u);}for(int i = 1; i <= n ; i++){if(color[i]) continue;cnt[1] = cnt[2] = 0;if(solve(i, 1) == true){ans += cnt[1] * (cnt[1] - 1) / 2;ans += cnt[2] * (cnt[2] - 1) / 2;}else{ans += (cnt[1] + cnt[2]) * (cnt[1] + cnt[2] - 1) / 2;}}printf("%lld\n", ans);return 0;
}

F- Square, Not Rectangle

二分答案+ST表

#include<bits/stdc++.h>
#define MAXN 300010
using namespace std;
int n;
int st[MAXN][21], f[MAXN];
inline void pre_solve(){f[1] = 0;for(int i = 2; i <= n; i++) f[i] = f[i >> 1] + 1; for(int i = 1; i <= 20 && (1 << i) <= n; i++){for(int j = 1; j <= n && j + (1 << (i - 1)) <= n; j++){st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);}}return;
}
inline int query(int l, int r){int len = r - l + 1;int flen = f[len];int ans = min(st[l][flen], st[r - (1 << flen) + 1][flen]);return ans;
}
inline bool check(int len){for(int i = 1; i <= n; i++){int l = i, r = i + len - 1;if(r > n) break;if(query(l, r) >= len) return true;}return false;
}
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifscanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &st[i][0]);}pre_solve();int l = 1, r = n, ans = 1;while(l <= r){int mid = (l + r) >> 1;if(check(mid)){if(mid > ans) ans = mid;l = mid + 1;}else r = mid - 1;}printf("%d\n", ans);return 0;
}

G- LCS 8

H- Mock Competition Marketing

这道题大意是这样的。一共有6种广告，有一个你现在拥有的钱数。每种广告有它投放需要的费用，然后有一个广告投放序列。预先决定出来一个种类的集合，然后扫一遍广告投放序列，只有当剩下的钱大于等于投放需要的费用而且这个广告种类在预先决定的集合里面，进行投放（这时候必须投放，不能选择不投）。问最多投放几个广告？
那思路很清晰了呀，6种广告，直接枚举预先决定的集合，然后验证求最大值就好啦qwq~

#include<bits/stdc++.h>
#define MAXN 200010
using namespace std;
int n, cnt, ans_cnt;
long long k, ans;
int b[7];
struct Node{int id, val;}node[MAXN];
inline bool cmp(struct Node x, struct Node y){return x.val < y.val;}
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifscanf("%d%lld", &n, &k);for(int i = 1; i <= 6; i++) scanf("%d", &b[i]);for(int i = 1; i <= n; i++){scanf("%d", &node[i].id);node[i].val = b[node[i].id];node[i].id--; }for(int j = 1; j < (1 << 6); j++){ans = 0, cnt = 0;for(int i = 1; i <= n; i++){if(((1 << node[i].id) & j) == 0) continue;if(ans + node[i].val > k) break;ans += node[i].val;cnt++;}ans_cnt = max(ans_cnt, cnt);}printf("%d\n", ans_cnt);return 0;
}

I- Query On A Tree 17

J- Remote Control

移动不了车，我们就移动墙（相对运动）。相当于每次墙向车移动相反的方向移动。
如果墙撞到了车，就将这个格子上的所有车向墙移动的方向移动一步。
但是如果一个格子上的车很多怎么办？一个一个改会炸时间复杂度。
我们可以给每个格子编一个号，一个格子上的所有车都是一个集合，假设编号为 s i s_i si​。如果从格子a移动到了b，就将格子a和b指定的集合编号进行改变。
接下来我们可以发现，需要维护一个汽车编号的数据结构——set，为了保证最坏情况下每个汽车合并的次数依然不超过logn次，要使用启发式合并qwq。
最后我们将墙移动回原点，那么相应的也可以算出来车的位置了。
PS.这道题其实我还有一个想法，但是好像不太好实现。就是我们知道移动序列，显然如果不撞墙的话我们可以O（1）知道每个车的最终位移，那么我们只要设定一个校正值(a,b)，每次撞墙就是 a + m x [ i ] = 0 , b + m y [ i ] = 0 a+m_x[i]=0,b+m_y[i] = 0 a+mx​[i]=0,b+my​[i]=0,我们在map里面寻找 − a , − b -a,-b −a,−b即可。但是这样需要map映射一个vector???好像做不了？？？qwq

#include<bits/stdc++.h>
#define MAXN 600010
#define base 300000
using namespace std;
int n, q, cnt;
char pre[MAXN];
struct Node{int x, y;}node[MAXN];
map<long long, int>m;
set<int>s[MAXN];
inline long long get_id(int x, int y){return 1ll * x * (base * 2 + 1) + y;}
inline int get_x(long long x){return x / (base * 2 + 1);}
inline int get_y(long long x){return x % (base * 2 + 1);}
inline void mixx(long long id, long long new_id){if(!m[new_id]) m[new_id] = m[id], m[id] = 0;else{if(s[m[new_id]].size() > s[m[id]].size()){s[m[new_id]].insert(s[m[id]].begin(), s[m[id]].end());	m[id] = 0;}else{s[m[id]].insert(s[m[new_id]].begin(), s[m[new_id]].end());m[new_id] = m[id];m[id] = 0;}}return;
}
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifscanf("%d", &n);scanf("%s", pre + 1);scanf("%d", &q);for(int i = 1; i <= q; i++){scanf("%d%d", &node[i].x, &node[i].y);node[i].x += base;node[i].y += base;long long id = get_id(node[i].x, node[i].y);if(!m[id]){m[id] = ++cnt;s[cnt].insert(i);}else s[m[id]].insert(i);}int now_x = 0 + base, now_y = 0 + base;for(int i = 1; i <= n; i++){if(pre[i] == 'L') now_x += 1;if(pre[i] == 'R') now_x -= 1;if(pre[i] == 'U') now_y -= 1;if(pre[i] == 'D') now_y += 1;long long id = get_id(now_x, now_y), new_id;if(m[id]){if(pre[i] == 'L') new_id = get_id(now_x + 1, now_y);if(pre[i] == 'R') new_id = get_id(now_x - 1, now_y);if(pre[i] == 'U') new_id = get_id(now_x, now_y - 1);if(pre[i] == 'D') new_id = get_id(now_x, now_y + 1); mixx(id, new_id);}}for(map<long long, int>::iterator it = m.begin(); it != m.end(); it++){int id = it->second;if(id == 0) continue;for(set<int>::iterator it2 = s[id].begin(); it2 != s[id].end(); it2++){node[*it2].x = get_x(it->first) - now_x;node[*it2].y = get_y(it->first) - now_y;} }for(int i = 1; i <= q; i++) printf("%d %d\n", node[i].x, node[i].y);return 0;
}

K- Sewing Graph

构造题？（雾）
按照x坐标为第一关键字，y坐标为第二关键字排序，然后依次连（一次正面一次背面交替来）就可以了。

#include<bits/stdc++.h>
#define MAXN 10010
using namespace std;
int n;
struct Node{int x, y, id;friend bool operator < (struct Node a, struct Node b){if(a.x != b.x) return a.x < b.x;else return a.y < b.y;}
}node[MAXN];
int main(){#ifndef ONLINE_JUDGEfreopen("ce.in", "r", stdin);#endifscanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d%d", &node[i].x, &node[i].y);node[i].id = i;}sort(&node[1], &node[n + 1]);printf("%d\n", n * 2 - 1);for(int i = 1; i <= n; i++){printf("%d ", node[i].id);}for(int i = n - 1; i >= 1; i--){printf("%d ", node[i].id);}puts("");return 0;
}

L- Steel Slicing 2