首页 > 代码库 > 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 }
Aguin

 

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 }
Aguin

 

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 }
Aguin

 

1012 Eighty seven

 

1013 String

 

2016 ACM/ICPC Asia Regional Qingdao Online