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

我好无语呀场上怎么没人做

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <queue>
  6 using namespace std;
  7 const int maxnode = 1111111, sigma_size = 27;
  8 char s[maxnode];
  9 int len[maxnode];
 10 
 11 // ACA
 12 struct Ac_auto
 13 {
 14     int Next[maxnode][sigma_size];
 15     int fail[maxnode];
 16     int val[maxnode];
 17     int sz;
 18 
 19     Ac_auto(){sz = 1; memset(Next[0], 0, sizeof(Next[0]));}
 20     void init(){sz = 1; memset(Next[0], 0, sizeof(Next[0]));}
 21 
 22     int idx(char c)
 23     {
 24         if(c >= 'a' && c <= 'z') return c - 'a';
 25         if(c >= 'A' && c <= 'Z') return c - 'A';
 26         return 26;
 27     }
 28 
 29     void Insert(char * s)
 30     {
 31         int u = 0, n = strlen(s);
 32         for(int i = 0; i < n; i++)
 33         {
 34             int c = idx(s[i]);
 35             if(!Next[u][c])
 36             {
 37                 memset(Next[sz], 0, sizeof(Next[sz]));
 38                 val[sz] = 0;
 39                 Next[u][c] = sz++;
 40             }
 41             u = Next[u][c];
 42         }
 43         val[u] = n;
 44     }
 45 
 46     void Build()
 47     {
 48         queue<int> q;
 49         fail[0] = 0;
 50         for(int i = 0; i < sigma_size; i++) if(Next[0][i])
 51         {
 52             fail[Next[0][i]] = 0;
 53             q.push(Next[0][i]);
 54         }
 55         while(!q.empty())
 56         {
 57             int pos = q.front(); q.pop();
 58             for(int i = 0; i < sigma_size; i++)
 59             {
 60                 if(!Next[pos][i]) Next[pos][i] = Next[fail[pos]][i];
 61                 else
 62                 {
 63                     fail[Next[pos][i]] = Next[fail[pos]][i];
 64                     q.push(Next[pos][i]);
 65                 }
 66             }
 67         }
 68     }
 69 
 70     void Solve(char * s)
 71     {
 72         int u = 0, n = strlen(s + 1);
 73         for(int i = 1; i <= n; i++)
 74         {
 75             int c = idx(s[i]);
 76             u = Next[u][c];
 77             int tmp = u, M = 0;
 78             while(tmp)
 79             {
 80                 M = max(M, val[tmp]);
 81                 tmp = fail[tmp];
 82             }
 83             len[i-M+1] += 1, len[i+1] -= 1;
 84         }
 85     }
 86 
 87 } ACA;
 88 
 89 int main(void)
 90 {
 91     int T;
 92     scanf("%d", &T);
 93     while(T--)
 94     {
 95         ACA.init();
 96         int N;
 97         scanf("%d", &N);
 98         for(int i = 1; i <= N; i++)
 99         {
100             scanf("%s", s);
101             ACA.Insert(s);
102         }
103         ACA.Build();
104         getchar();
105         gets(s + 1);
106         // scanf("%s", s + 1);
107         memset(len, 0, sizeof(len));
108         ACA.Solve(s);
109         int n = strlen(s + 1);
110         for(int i = 1; i <= n; i++)
111         {
112             len[i] += len[i-1];
113             if(len[i] > 0) s[i] = '*';
114         }
115         puts(s + 1);
116     }
117     return 0;
118 }

Aguin

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
", 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
", 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
", Dinic(1, N));
171     }
172     return 0;
173 }

Aguin

1012 Eighty seven

这题不补好像对不起学魔……

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 typedef vector<int> vi;
 6 vi dp[11][111], ans[22222], ban[22222];
 7 int N, a[111];
 8 
 9 vi DP(vi b)
10 {
11     for(int j = 0; j <= 10; j++)
12         for(int k = 0; k <= 87; k++)
13             dp[j][k].clear();
14     for(int i = 1; i <= N; i++)
15     {
16         int ok = 1;
17         for(int j = 0; j < b.size(); j++)
18             if(i == b[j]) ok = 0;
19         if(!ok) continue;
20         for(int j = 9; j >= 0; j--)
21         for(int k = 87 - a[i]; k >= 0; k--)
22         {
23             if((j || k) && dp[j][k].empty()) continue;
24             vector<int> tmp = dp[j][k];
25             tmp.push_back(i);
26             dp[j+1][k+a[i]] = tmp;
27         }
28     }
29     return dp[10][87];
30 }
31 
32 void dfs(int x, int dep)
33 {
34     if(!x) ban[x].clear();
35     else
36     {
37         ban[x] = ban[x/11];
38         ban[x].push_back(ans[x/11][x%11-1]);
39     }
40     ans[x] = DP(ban[x]);
41     if(!ans[x].empty() && dep < 3)
42         for(int i = 0; i < ans[x].size(); i++)
43             dfs(11 * x + i + 1, dep + 1);
44 }
45 
46 int main(void)
47 {
48     int T;
49     scanf("%d", &T);
50     while(T--)
51     {
52         scanf("%d", &N);
53         for(int i = 1; i <= N; i++) scanf("%d", a + i);
54         dfs(0, 0);
55         int Q;
56         scanf("%d", &Q);
57         while(Q--)
58         {
59             int a[3], now = 0;
60             for(int i = 0; i < 3; i++) scanf("%d", a + i);
61             for(int i = 0; i < 3; i++)
62             for(int j = 0; j < 3; j++)
63             for(int k = 0; k < ans[now].size(); k++)
64                 if(ans[now][k] == a[j]) {now = now * 11 + k + 1; break;}
65             puts(ans[now].empty() ? "No" : "Yes");
66         }
67     }
68     return 0;
69 }

Aguin

1013 String