首页 > 代码库 > 2016 ACM/ICPC Asia Regional Qingdao Online
2016 ACM/ICPC Asia Regional Qingdao Online
吐槽：
群O的不是很舒服 不知道自己应该干嘛 怎样才能在团队中充分发挥自己价值
一点都不想写题 理想中的情况是想题丢给别人写 但明显滞后 一道题拖沓很久 中途出岔子又返回来搞
最放心的是微软微软妹可以随便丢 有几个小盆友也比较靠谱 还有几个小盆友一开始有点担心 后来都做的挺棒
写题的选择上很尴尬 会写的别人也会 要么队内都不会 结果大概是写了一些板子题
感觉到了比较艰难的阶段 有些题是要我学着去写的 不会写没有突破
1001 I Count Two Three
AC by ctr
指数不会很大，枚举指数打个表，排个序后每组询问在表里二分它。
cb好像一开始也在搞这个 似乎出现了什么问题 后来ctr先写完交就1A了
1002 Cure
AC by nps
平方调和收敛于pi ^ 2 / 6，数小的时候预处理，大于阈值直接出答案。
数的范围很大，读串。
把几个数值弄出来后 给nps稍微一讲就明白了 写也比较快
1003 Family View
1004 Tea
AC by 高老师
先倒下界的一半，然后一点一点倒，大概要注意一下最后能剩一点。
高老师智能找水题 但是讨论上折腾了一会 出了这题前期就不是太紧张
1005 Balanced Game
AC by lpf
奇偶一判。
高老师智能找水题 然后lpf一写就过了
1006 The Best Path
AC by lpf
先判连通性以及是否构成欧拉路/回路，如果是欧拉路，数下每个点的度，贡献都是唯一的。
如果是回路，枚举一下起点，找下最大的即可。
懒洋洋先发现是个欧拉路 但是我不懂这套 好像判下奇偶就可以了
然后在没太想清楚的情况下和他们瞎比比 然后他们按我bb的写全wa了
微软微软妹指出了孤立点处理连通性时的问题 懒洋洋指出了环路枚举起点的问题
然后lpf就A了 由于我的bb浪费了不少时间在这
1007 Sort
二分k，第一次合并可能少于k，之后都合并k个。
先把所有排个序，放在一个队列里，合并出来的放在一个新的队列里，这样两个队列都是单增的，每次两个队首挑小的出来就好。
一开始铖霸在搞这个 他写了pq T掉了 我写multiset也T掉了 软妹打算手写pq了
可能对我们来说合并果子的pq做法太深入人心了吧 突然想到可以少个log改下就过了
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int maxn = 1e5 + 10; 8 int a[maxn]; 9 queue<LL> q1, q2; 10 11 int main(void) 12 { 13 int t0; 14 scanf("%d", &t0); 15 while(t0--) 16 { 17 int N, T; 18 scanf("%d %d", &N, &T); 19 for(int i = 1; i <= N; i++) scanf("%d", a + i); 20 sort(a + 1, a + 1 + N); 21 int l = 2, r = N, mid; 22 while(l < r) 23 { 24 mid = l + (r - l) / 2; 25 26 while(!q1.empty()) q1.pop(); 27 while(!q2.empty()) q2.pop(); 28 for(int i = 1; i <= N; i++) q1.push(a[i]); 29 30 int num = (N - 1) / (mid - 1) + ((N - 1) % (mid - 1) ? 1 : 0); 31 32 LL ans = 0; 33 for(int i = 0; i < num; i++) 34 { 35 int nn = (N - 1) % (mid - 1); 36 if(!i && nn) 37 { 38 LL tmp = 0; 39 for(int j = 0; j <= nn; j++) 40 { 41 if(!q1.empty() && !q2.empty()) 42 { 43 if(q1.front() < q2.front()) 44 { 45 tmp += q1.front(); 46 q1.pop(); 47 } 48 else 49 { 50 tmp += q2.front(); 51 q2.pop(); 52 } 53 } 54 else if(!q1.empty()) 55 { 56 tmp += q1.front(); 57 q1.pop(); 58 } 59 else 60 { 61 tmp += q2.front(); 62 q2.pop(); 63 } 64 } 65 ans += tmp; 66 q2.push(tmp); 67 } 68 else 69 { 70 LL tmp = 0; 71 for(int j = 0; j < mid; j++) 72 { 73 if(!q1.empty() && !q2.empty()) 74 { 75 if(q1.front() < q2.front()) 76 { 77 tmp += q1.front(); 78 q1.pop(); 79 } 80 else 81 { 82 tmp += q2.front(); 83 q2.pop(); 84 } 85 } 86 else if(!q1.empty()) 87 { 88 tmp += q1.front(); 89 q1.pop(); 90 } 91 else 92 { 93 tmp += q2.front(); 94 q2.pop(); 95 } 96 } 97 ans += tmp; 98 q2.push(tmp); 99 }100 }101 if(ans <= T) r = mid;102 else l = mid + 1;103 }104 printf("%d\n", r);105 }106 return 0;107 }
1008 XM Reserves
1009 Tower Defence
简单点就是先找直径，端点做两次dp最长路，讨论一下切的边在不在直径上。
直接dp不好写。
大概需要先做一遍dp1[x]表示通过x往子树的最长单链，dp2[x]子树x中的最长链，然后为了后面还要多做个第二、三大。
父亲方向，先做f1[x]表示经过x的父亲不过x的最长单链，f2[x]表示经过x父亲不经过x的最长链，讨论x是不是最大、次大才能搞出fa[x]表示父亲方向答案。
中间可能还要一些预处理孩子们的dp2[son]的最大值。
赛场上树dp就没写出来过 细节多 大概是需要克服的一个方面
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 1e5 + 10; 7 typedef long long LL; 8 9 // edge 10 int cnt, h[maxn]; 11 struct edge 12 { 13 int to, pre, w; 14 } e[maxn<<1]; 15 void init() 16 { 17 cnt = 0; 18 memset(h, 0, sizeof(h)); 19 } 20 void add(int from, int to, int w) 21 { 22 cnt++; 23 e[cnt].pre = h[from]; 24 e[cnt].to = to; 25 e[cnt].w = w; 26 h[from] = cnt; 27 } 28 29 // dp 30 LL fir[maxn], id1[maxn], sec[maxn], id2[maxn], thi[maxn], dp2[maxn]; 31 void dfs1(int x, int f) 32 { 33 fir[x] = sec[x] = thi[x] = id1[x] = id2[x] = dp2[x] = 0; 34 for(int i = h[x]; i; i = e[i].pre) 35 { 36 int to = e[i].to, w = e[i].w; 37 if(to == f) continue; 38 dfs1(to, x); 39 if(fir[to] + w >= fir[x]) 40 { 41 thi[x] = sec[x]; 42 43 sec[x] = fir[x]; 44 id2[x] = id1[x]; 45 46 fir[x] = fir[to] + w; 47 id1[x] = to; 48 } 49 else if(fir[to] + w >= sec[x]) 50 { 51 thi[x] = sec[x]; 52 53 sec[x] = fir[to] + w; 54 id2[x] = to; 55 } 56 else if(fir[to] + w > thi[x]) thi[x] = fir[to] + w; 57 dp2[x] = max(dp2[x], dp2[to]); 58 } 59 dp2[x] = max(dp2[x], fir[x] + sec[x]); 60 } 61 62 LL f1[maxn], f2[maxn]; 63 void dfs2(int x, int f, int wf) 64 { 65 if(!f) f1[x] = f2[x] = 0; 66 for(int i = h[x]; i; i = e[i].pre) 67 { 68 int to = e[i].to, w = e[i].w; 69 if(to == f) continue; 70 71 if(to == id1[x]) 72 { 73 f1[to] = max(f1[x] + wf, sec[x]); 74 f2[to] = f1[x] + wf + sec[x] + thi[x] - min(f1[x] + wf, thi[x]); 75 } 76 else if(to == id2[x]) 77 { 78 f1[to] = max(f1[x] + wf, fir[x]); 79 f2[to] = f1[x] + wf + fir[x] + thi[x] - min(f1[x] + wf, thi[x]); 80 } 81 else 82 { 83 f1[to] = max(f1[x] + wf, fir[x]); 84 f2[to] = f1[x] + wf + fir[x] + sec[x] - min(f1[x] + wf, sec[x]); 85 } 86 87 dfs2(to, x, w); 88 } 89 } 90 91 LL fa[maxn]; 92 LL L[maxn], R[maxn]; 93 void dfs3(int x, int f) 94 { 95 if(!f) fa[x] = 0; 96 97 int tot = 0; 98 for(int i = h[x]; i; i = e[i].pre) 99 {100 int to = e[i].to, w = e[i].w;101 if(to == f) continue;102 tot++;103 }104 105 int cnt = 0;106 for(int i = h[x]; i; i = e[i].pre)107 {108 int to = e[i].to, w = e[i].w;109 if(to == f) continue;110 cnt++;111 L[cnt] = R[cnt] = dp2[to];112 }113 for(int i = 2; i <= tot; i++) L[i] = max(L[i], L[i-1]);114 for(int i = tot - 1; i >= 0; i--) R[i] = max(R[i], R[i+1]);115 116 L[0] = R[tot+1] = cnt = 0;117 for(int i = h[x]; i; i = e[i].pre)118 {119 int to = e[i].to, w = e[i].w;120 if(to == f) continue;121 cnt++;122 fa[to] = max(f2[to], fa[x]);123 fa[to] = max(fa[to], max(L[cnt-1], R[cnt+1]));124 }125 126 for(int i = h[x]; i; i = e[i].pre)127 {128 int to = e[i].to, w = e[i].w;129 if(to == f) continue;130 dfs3(to, x);131 }132 }133 134 int main(void)135 {136 int T;137 scanf("%d", &T);138 while(T--)139 {140 int N;141 scanf("%d", &N);142 init();143 for(int i = 1; i < N; i++)144 {145 int u, v, w;146 scanf("%d %d %d", &u, &v, &w);147 add(u, v, w), add(v, u, w);148 }149 150 dfs1(1, 0);151 dfs2(1, 0, 0);152 dfs3(1, 0);153 154 LL ans = 0;155 for(int i = 2; i <= N; i++) ans += max(dp2[i], fa[i]);156 printf("%I64d\n", ans);157 }158 return 0;159 }
1010 Herbs Gathering
1011 Barricade
BFS把最短路图抠出来，裸最小割最大流。
一开始担心网络流T都没敢写 后来写了真T了 其实是BFS写挫 如果直接最短路可能还没问题
ctr 和 wzm也尝试了一下 但好像对这块都不是很熟悉
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 const int INF = 1e9; 8 const int maxn = 2e4 + 10; 9 int lv[11111], it[11111]; 10 int cnt, h[11111]; 11 12 struct edge 13 { 14 int to, pre, cap; 15 } e[maxn<<1]; 16 17 void init() 18 { 19 memset(h, -1, sizeof(h)); 20 cnt = 0; 21 } 22 23 void add(int from, int to, int cap) 24 { 25 e[cnt].pre = h[from]; 26 e[cnt].to = to; 27 e[cnt].cap = cap; 28 h[from] = cnt; 29 cnt++; 30 } 31 32 void ad(int from, int to, int cap) 33 { 34 add(from, to, cap); 35 add(to, from, 0); 36 } 37 38 void bfs(int s) 39 { 40 memset(lv, -1, sizeof(lv)); 41 queue<int> q; 42 lv[s] = 0; 43 q.push(s); 44 while(!q.empty()) 45 { 46 int v = q.front(); q.pop(); 47 for(int i = h[v]; i >= 0; i = e[i].pre) 48 { 49 int cap = e[i].cap, to = e[i].to; 50 if(cap > 0 && lv[to] < 0) 51 { 52 lv[to] = lv[v] + 1; 53 q.push(to); 54 } 55 } 56 } 57 } 58 59 int dfs(int v, int t, int f) 60 { 61 if(v == t) return f; 62 for(int &i = it[v]; i >= 0; i = e[i].pre) 63 { 64 int &cap = e[i].cap, to = e[i].to; 65 if(cap > 0 && lv[v] < lv[to]) 66 { 67 int d = dfs(to, t, min(f, cap)); 68 if(d > 0) 69 { 70 cap -= d; 71 e[i^1].cap += d; 72 return d; 73 } 74 } 75 } 76 return 0; 77 } 78 79 int Dinic(int s, int t) 80 { 81 int flow = 0; 82 while(1) 83 { 84 bfs(s); 85 if(lv[t] < 0) return flow; 86 memcpy(it, h, sizeof(it)); 87 int f; 88 while((f = dfs(s, t, INF)) > 0) flow += f; 89 } 90 } 91 92 // edge 93 int cn, he[11111]; 94 edge ee[maxn<<1]; 95 void init_e() 96 { 97 memset(he, -1, sizeof(he)); 98 cn = 0; 99 }100 void add_e(int from, int to, int cap)101 {102 ee[cn].pre = he[from];103 ee[cn].to = to;104 ee[cn].cap = cap;105 he[from] = cn;106 cn++;107 }108 109 int vis[11111], dist[11111];110 void bfs1()111 {112 queue<int> q;113 memset(vis, 0, sizeof(vis));114 memset(dist, 0, sizeof(dist));115 dist[1] = 0;116 vis[1] = 1;117 q.push(1);118 while(!q.empty())119 {120 int u = q.front(); q.pop();121 for(int i = he[u]; i != -1; i = ee[i].pre)122 {123 int to = ee[i].to;124 if(vis[to]) continue;125 vis[to] = 1, dist[to] = dist[u] + 1;126 q.push(to);127 }128 }129 }130 131 void bfs2(int N)132 {133 init();134 queue<int> q;135 q.push(N);136 memset(vis, 0, sizeof(vis));137 vis[N] = 1;138 while(!q.empty())139 {140 int u = q.front(); q.pop();141 for(int i = he[u]; i != -1; i = ee[i].pre)142 {143 int to = ee[i].to;144 if(dist[u] - dist[to] == 1)145 {146 ad(to, u, ee[i].cap);147 if(!vis[to]) vis[to] = 1, q.push(to);148 }149 }150 }151 }152 153 int main(void)154 {155 int T;156 scanf("%d", &T);157 while(T--)158 {159 int N, M;160 scanf("%d %d", &N, &M);161 init_e();162 for(int i = 1; i <= M; i++)163 {164 int a, b, w;165 scanf("%d %d %d", &a, &b, &w);166 add_e(a, b, w), add_e(b, a, w);167 }168 bfs1();169 bfs2(N);170 printf("%d\n", Dinic(1, N));171 }172 return 0;173 }
1012 Eighty seven
1013 String
2016 ACM/ICPC Asia Regional Qingdao Online
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。