2017ACM萧山训练第1场(NEERC 2016)
A.[Neerc2016]Abbreviation
字符串模拟
E.[Neerc2016]Expect to Wait
如果对于等待的人数维护一个关于时间的前缀和
那么我们就得到了一个很长的前缀和序列，我们注意到初始车辆为 x，实际上就是询问这个序列大于 x 的前缀和的和
那么对于时间离散化以后，就是询问大于 x 的段的加权和
对所有的段从小到大排序，依次处理
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mp(a, b) make_pair(a, b) #define inf 1000000000 #define mod 1000000007 #define ll long long #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, m; int opt[100005], t[100005], k[100005]; ll sum[100005], ans[100005]; ll Asum[100005], Tsum[100005]; pair<int, int>p[100005], q[100005]; int main() { n = read(); m = read(); char ch[2]; for(int i = 1; i <= n; i++) { scanf("%s", ch); t[i] = read(); k[i] = read(); if(ch[0] == '+')k[i] = -k[i]; sum[i] = sum[i - 1] + k[i]; } for(int i = 1; i <= m; i++) { int x = read(); q[i] = make_pair(x, i); } for(int i = 1; i < n; i++) p[i] = make_pair(sum[i], t[i + 1] - t[i]); sort(p + 1, p + n); sort(q + 1, q + m + 1); for(int i = n - 1; i > 0; i--) { Tsum[i] = Tsum[i + 1] + p[i].second; Asum[i] = Asum[i + 1] + (ll)p[i].first * p[i].second; } for(int i = 1, t = 1; i <= m; i++) { int Q = q[i].first; if(Q < sum[n]) { ans[q[i].second] = -1; continue; } while(t < n && Q >= p[t].first)t++; ans[q[i].second] = Asum[t] - Tsum[t] * Q; } for(int i = 1; i <= m; i++) if(ans[i] == -1)puts("INFINITY"); else printf("%lld\n", ans[i]); return 0; } |
G.[Neerc2016]Game on Graph
第二个人先手的状态的一个后继被确定不是平局，则这个状态不是平局
第一个人先手的某个状态的所有后继都不是平局，则这个状态不是平局
从出度为0的点开始拓扑排序，剩下的点都是平局状态
类似地，确定不是平局的所有状态的胜负
剩下无法确定的点一定是第一个人必胜，第二个人必败，因为第二个人宁愿输也不平局
H.[Neerc2016]Hard Refactoring
模拟
J:Jenga Boom
对于每一层，维护一下最两侧的木块，以及本层木块的数量与重心
每次移除一块积木时，从上往下考虑每一层 x
对于比 x 更高的那些层，若奇偶性与 x 相同，则第 i 块木块重心在 i，否则设其重心在（n + 1) / 2
计算这些层的重心是否在 (mn_x – 0.5, mx_x + 0.5)这个范围内
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define eps 1e-12 #define mp(a, b) make_pair(a, b) #define inf 1000000000 #define mod 1000000007 #define ll long long #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, w, h, m; int l[5005], k[5005]; int del[5005][10005]; int mx[5005], mn[5005]; double tot[5005], cnt[5005]; bool solve(int l, int k) { tot[l] -= 2 * k; cnt[l]--; if(!cnt[l] && cnt[l + 1])return 1; del[l][k] = 1; for(int i = 1; i <= n; i++) if(!del[l][i]){mn[l] = i; break;} for(int i = n; i; i--) if(!del[l][i]){mx[l] = i; break;} double sw1 = 0, sc1 = 0, sw2 = 0, sc2 = 0; for(int i = h; i; i--) { if(sc1 || sc2) { double t = 0; if(i % 2 == 0)t = (sw2 + sc1 * (n + 1)); else t = (sw1 + sc2 * (n + 1)); if(t <= (2 * mn[i] - 1) * (sc1 + sc2) || t >= (2 * mx[i] + 1) * (sc1 + sc2))return 1; } if(i % 2 == 0) sc2 += cnt[i], sw2 += tot[i]; else sc1 += cnt[i], sw1 += tot[i]; } return 0; } int main() { n = read(); w = read(); h = read(); m = read(); for(int i = 1; i <= m; i++) l[i] = read(), k[i] = read(); for(int i = 1; i <= h; i++) { mx[i] = n, mn[i] = 1; tot[i] = n * (n + 1); cnt[i] = n ; } for(int i = 1; i <= m; i++) if(solve(l[i], k[i])) { puts("yes"); printf("%d\n", i); return 0; } puts("no"); return 0; } |
L:List of Primes
发现用到的质数不会太多，质数和小于1500时总长4*10^18
M.Mole Tunnels
在一棵满二叉树上模拟费用流
维护每个子树内离根最近的可流出的结点，每次流入量加一时，依次查询它的所有祖先，找到一个离它最近的结点，然后把整条路径的所有信息暴力更新一下
维护的时候要记录每条边两个方向的退流
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<map> #include<set> #include<cmath> #include<stack> #include<deque> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mp(a, b) make_pair(a, b) #define inf 1000000000 #define mod 1000000007 #define ll long long #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ANS; int n, m; int c[100005], p[100005], f[100005], g[100005], uop[100005], dop[100005]; void update(int x) { int l = x << 1, r = x << 1 | 1; int ld = 1, rd = 1; if(dop[l])ld = -1; if(dop[r])rd = -1; if(l > n)l = 0; if(r > n)r = 0; if(f[l] + ld < f[r] + rd) f[x] = f[l] + ld, g[x] = g[l]; else f[x] = f[r] + rd, g[x] = g[r]; if(c[x])f[x] = 0, g[x] = x; } void updatepath(int p, int q, int lca) { c[q]--; for(int i = p; i != lca; i >>= 1) { if(uop[i])ANS--, uop[i]--; else ANS++, dop[i]++; update(i); } for(int i = q; i != lca; i >>= 1) { if(dop[i])ANS--, dop[i]--; else ANS++, uop[i]++; update(i); } for(int i = lca; i; i >>= 1) update(i); } void query(int x) { int ans = x, mn = inf; for(int i = x, dis = 0; i >= 1; i >>= 1) { if(dis + f[i] < mn)mn = dis + f[i], ans = i; if(uop[i])dis--; else dis++; } updatepath(x, g[ans], ans); } int main() { n = read(); m = read(); for(int i = 1; i <= n; i++)c[i] = read(); for(int i = 1; i <= m; i++)p[i] = read(); f[0] = inf; for(int i = n; i >= 1; i--) update(i); for(int i = 1; i <= m; i++) { query(p[i]); printf("%d", ANS); if(i == m)printf("\n"); else printf(" "); } return 0; } |
Subscribe
计数器 9774122
OI 课件=>
OI 课件=>