吐槽：
群O的不是很舒服 不知道自己应该干嘛 怎样才能在团队中充分发挥自己价值
一点都不想写题 理想中的情况是想题丢给别人写 但明显滞后 一道题拖沓很久 中途出岔子又返回来搞
最放心的是微软微软妹可以随便丢 有几个小盆友也比较靠谱 还有几个小盆友一开始有点担心 后来都做的挺棒
写题的选择上很尴尬 会写的别人也会 要么队内都不会 结果大概是写了一些板子题
感觉到了比较艰难的阶段 有些题是要我学着去写的 不会写没有突破
1001 I Count Two Three
AC by ctr
指数不会很大，枚举指数打个表，排个序后每组询问在表里二分它。
cb好像一开始也在搞这个 似乎出现了什么问题 后来ctr先写完交就1A了
1002 Cure
AC by nps
平方调和收敛于pi ^ 2 / 6，数小的时候预处理，大于阈值直接出答案。
数的范围很大，读串。
把几个数值弄出来后 给nps稍微一讲就明白了 写也比较快
1003 Family View
我好无语呀 场上怎么没人做
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxnode = , sigma_size = ;
char s[maxnode];
int len[maxnode]; // ACA
struct Ac_auto
{
int Next[maxnode][sigma_size];
int fail[maxnode];
int val[maxnode];
int sz; Ac_auto(){sz = ; memset(Next[], , sizeof(Next[]));}
void init(){sz = ; memset(Next[], , sizeof(Next[]));} int idx(char c)
{
if(c >= 'a' && c <= 'z') return c - 'a';
if(c >= 'A' && c <= 'Z') return c - 'A';
return ;
} void Insert(char * s)
{
int u = , n = strlen(s);
for(int i = ; i < n; i++)
{
int c = idx(s[i]);
if(!Next[u][c])
{
memset(Next[sz], , sizeof(Next[sz]));
val[sz] = ;
Next[u][c] = sz++;
}
u = Next[u][c];
}
val[u] = n;
} void Build()
{
queue<int> q;
fail[] = ;
for(int i = ; i < sigma_size; i++) if(Next[][i])
{
fail[Next[][i]] = ;
q.push(Next[][i]);
}
while(!q.empty())
{
int pos = q.front(); q.pop();
for(int i = ; i < sigma_size; i++)
{
if(!Next[pos][i]) Next[pos][i] = Next[fail[pos]][i];
else
{
fail[Next[pos][i]] = Next[fail[pos]][i];
q.push(Next[pos][i]);
}
}
}
} void Solve(char * s)
{
int u = , n = strlen(s + );
for(int i = ; i <= n; i++)
{
int c = idx(s[i]);
u = Next[u][c];
int tmp = u, M = ;
while(tmp)
{
M = max(M, val[tmp]);
tmp = fail[tmp];
}
len[i-M+] += , len[i+] -= ;
}
} } ACA; int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
ACA.init();
int N;
scanf("%d", &N);
for(int i = ; i <= N; i++)
{
scanf("%s", s);
ACA.Insert(s);
}
ACA.Build();
getchar();
gets(s + );
// scanf("%s", s + 1);
memset(len, , sizeof(len));
ACA.Solve(s);
int n = strlen(s + );
for(int i = ; i <= n; i++)
{
len[i] += len[i-];
if(len[i] > ) s[i] = '*';
}
puts(s + );
}
return ;
}
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改下就过了
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + ;
int a[maxn];
queue<LL> q1, q2; int main(void)
{
int t0;
scanf("%d", &t0);
while(t0--)
{
int N, T;
scanf("%d %d", &N, &T);
for(int i = ; i <= N; i++) scanf("%d", a + i);
sort(a + , a + + N);
int l = , r = N, mid;
while(l < r)
{
mid = l + (r - l) / ; while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
for(int i = ; i <= N; i++) q1.push(a[i]); int num = (N - ) / (mid - ) + ((N - ) % (mid - ) ? : ); LL ans = ;
for(int i = ; i < num; i++)
{
int nn = (N - ) % (mid - );
if(!i && nn)
{
LL tmp = ;
for(int j = ; j <= nn; j++)
{
if(!q1.empty() && !q2.empty())
{
if(q1.front() < q2.front())
{
tmp += q1.front();
q1.pop();
}
else
{
tmp += q2.front();
q2.pop();
}
}
else if(!q1.empty())
{
tmp += q1.front();
q1.pop();
}
else
{
tmp += q2.front();
q2.pop();
}
}
ans += tmp;
q2.push(tmp);
}
else
{
LL tmp = ;
for(int j = ; j < mid; j++)
{
if(!q1.empty() && !q2.empty())
{
if(q1.front() < q2.front())
{
tmp += q1.front();
q1.pop();
}
else
{
tmp += q2.front();
q2.pop();
}
}
else if(!q1.empty())
{
tmp += q1.front();
q1.pop();
}
else
{
tmp += q2.front();
q2.pop();
}
}
ans += tmp;
q2.push(tmp);
}
}
if(ans <= T) r = mid;
else l = mid + ;
}
printf("%d\n", r);
}
return ;
}
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就没写出来过 细节多 大概是需要克服的一个方面
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + ;
typedef long long LL; // edge
int cnt, h[maxn];
struct edge
{
int to, pre, w;
} e[maxn<<];
void init()
{
cnt = ;
memset(h, , sizeof(h));
}
void add(int from, int to, int w)
{
cnt++;
e[cnt].pre = h[from];
e[cnt].to = to;
e[cnt].w = w;
h[from] = cnt;
} // dp
LL fir[maxn], id1[maxn], sec[maxn], id2[maxn], thi[maxn], dp2[maxn];
void dfs1(int x, int f)
{
fir[x] = sec[x] = thi[x] = id1[x] = id2[x] = dp2[x] = ;
for(int i = h[x]; i; i = e[i].pre)
{
int to = e[i].to, w = e[i].w;
if(to == f) continue;
dfs1(to, x);
if(fir[to] + w >= fir[x])
{
thi[x] = sec[x]; sec[x] = fir[x];
id2[x] = id1[x]; fir[x] = fir[to] + w;
id1[x] = to;
}
else if(fir[to] + w >= sec[x])
{
thi[x] = sec[x]; sec[x] = fir[to] + w;
id2[x] = to;
}
else if(fir[to] + w > thi[x]) thi[x] = fir[to] + w;
dp2[x] = max(dp2[x], dp2[to]);
}
dp2[x] = max(dp2[x], fir[x] + sec[x]);
} LL f1[maxn], f2[maxn];
void dfs2(int x, int f, int wf)
{
if(!f) f1[x] = f2[x] = ;
for(int i = h[x]; i; i = e[i].pre)
{
int to = e[i].to, w = e[i].w;
if(to == f) continue; if(to == id1[x])
{
f1[to] = max(f1[x] + wf, sec[x]);
f2[to] = f1[x] + wf + sec[x] + thi[x] - min(f1[x] + wf, thi[x]);
}
else if(to == id2[x])
{
f1[to] = max(f1[x] + wf, fir[x]);
f2[to] = f1[x] + wf + fir[x] + thi[x] - min(f1[x] + wf, thi[x]);
}
else
{
f1[to] = max(f1[x] + wf, fir[x]);
f2[to] = f1[x] + wf + fir[x] + sec[x] - min(f1[x] + wf, sec[x]);
} dfs2(to, x, w);
}
} LL fa[maxn];
LL L[maxn], R[maxn];
void dfs3(int x, int f)
{
if(!f) fa[x] = ; int tot = ;
for(int i = h[x]; i; i = e[i].pre)
{
int to = e[i].to, w = e[i].w;
if(to == f) continue;
tot++;
} int cnt = ;
for(int i = h[x]; i; i = e[i].pre)
{
int to = e[i].to, w = e[i].w;
if(to == f) continue;
cnt++;
L[cnt] = R[cnt] = dp2[to];
}
for(int i = ; i <= tot; i++) L[i] = max(L[i], L[i-]);
for(int i = tot - ; i >= ; i--) R[i] = max(R[i], R[i+]); L[] = R[tot+] = cnt = ;
for(int i = h[x]; i; i = e[i].pre)
{
int to = e[i].to, w = e[i].w;
if(to == f) continue;
cnt++;
fa[to] = max(f2[to], fa[x]);
fa[to] = max(fa[to], max(L[cnt-], R[cnt+]));
} for(int i = h[x]; i; i = e[i].pre)
{
int to = e[i].to, w = e[i].w;
if(to == f) continue;
dfs3(to, x);
}
} int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
int N;
scanf("%d", &N);
init();
for(int i = ; i < N; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add(u, v, w), add(v, u, w);
} dfs1(, );
dfs2(, , );
dfs3(, ); LL ans = ;
for(int i = ; i <= N; i++) ans += max(dp2[i], fa[i]);
printf("%I64d\n", ans);
}
return ;
}
Aguin
1010 Herbs Gathering
1011 Barricade
BFS把最短路图抠出来，裸最小割最大流。
一开始担心网络流T都没敢写 后来写了真T了 其实是BFS写挫 如果直接最短路可能还没问题
ctr 和 wzm也尝试了一下 但好像对这块都不是很熟悉
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 1e9;
const int maxn = 2e4 + ;
int lv[], it[];
int cnt, h[]; struct edge
{
int to, pre, cap;
} e[maxn<<]; void init()
{
memset(h, -, sizeof(h));
cnt = ;
} void add(int from, int to, int cap)
{
e[cnt].pre = h[from];
e[cnt].to = to;
e[cnt].cap = cap;
h[from] = cnt;
cnt++;
} void ad(int from, int to, int cap)
{
add(from, to, cap);
add(to, from, );
} void bfs(int s)
{
memset(lv, -, sizeof(lv));
queue<int> q;
lv[s] = ;
q.push(s);
while(!q.empty())
{
int v = q.front(); q.pop();
for(int i = h[v]; i >= ; i = e[i].pre)
{
int cap = e[i].cap, to = e[i].to;
if(cap > && lv[to] < )
{
lv[to] = lv[v] + ;
q.push(to);
}
}
}
} int dfs(int v, int t, int f)
{
if(v == t) return f;
for(int &i = it[v]; i >= ; i = e[i].pre)
{
int &cap = e[i].cap, to = e[i].to;
if(cap > && lv[v] < lv[to])
{
int d = dfs(to, t, min(f, cap));
if(d > )
{
cap -= d;
e[i^].cap += d;
return d;
}
}
}
return ;
} int Dinic(int s, int t)
{
int flow = ;
while()
{
bfs(s);
if(lv[t] < ) return flow;
memcpy(it, h, sizeof(it));
int f;
while((f = dfs(s, t, INF)) > ) flow += f;
}
} // edge
int cn, he[];
edge ee[maxn<<];
void init_e()
{
memset(he, -, sizeof(he));
cn = ;
}
void add_e(int from, int to, int cap)
{
ee[cn].pre = he[from];
ee[cn].to = to;
ee[cn].cap = cap;
he[from] = cn;
cn++;
} int vis[], dist[];
void bfs1()
{
queue<int> q;
memset(vis, , sizeof(vis));
memset(dist, , sizeof(dist));
dist[] = ;
vis[] = ;
q.push();
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = he[u]; i != -; i = ee[i].pre)
{
int to = ee[i].to;
if(vis[to]) continue;
vis[to] = , dist[to] = dist[u] + ;
q.push(to);
}
}
} void bfs2(int N)
{
init();
queue<int> q;
q.push(N);
memset(vis, , sizeof(vis));
vis[N] = ;
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = he[u]; i != -; i = ee[i].pre)
{
int to = ee[i].to;
if(dist[u] - dist[to] == )
{
ad(to, u, ee[i].cap);
if(!vis[to]) vis[to] = , q.push(to);
}
}
}
} int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
int N, M;
scanf("%d %d", &N, &M);
init_e();
for(int i = ; i <= M; i++)
{
int a, b, w;
scanf("%d %d %d", &a, &b, &w);
add_e(a, b, w), add_e(b, a, w);
}
bfs1();
bfs2(N);
printf("%d\n", Dinic(, N));
}
return ;
}
Aguin
1012 Eighty seven
这题不补好像对不起学魔……
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> vi;
vi dp[][], ans[], ban[];
int N, a[]; vi DP(vi b)
{
for(int j = ; j <= ; j++)
for(int k = ; k <= ; k++)
dp[j][k].clear();
for(int i = ; i <= N; i++)
{
int ok = ;
for(int j = ; j < b.size(); j++)
if(i == b[j]) ok = ;
if(!ok) continue;
for(int j = ; j >= ; j--)
for(int k = - a[i]; k >= ; k--)
{
if((j || k) && dp[j][k].empty()) continue;
vector<int> tmp = dp[j][k];
tmp.push_back(i);
dp[j+][k+a[i]] = tmp;
}
}
return dp[][];
} void dfs(int x, int dep)
{
if(!x) ban[x].clear();
else
{
ban[x] = ban[x/];
ban[x].push_back(ans[x/][x%-]);
}
ans[x] = DP(ban[x]);
if(!ans[x].empty() && dep < )
for(int i = ; i < ans[x].size(); i++)
dfs( * x + i + , dep + );
} int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &N);
for(int i = ; i <= N; i++) scanf("%d", a + i);
dfs(, );
int Q;
scanf("%d", &Q);
while(Q--)
{
int a[], now = ;
for(int i = ; i < ; i++) scanf("%d", a + i);
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
for(int k = ; k < ans[now].size(); k++)
if(ans[now][k] == a[j]) {now = now * + k + ; break;}
puts(ans[now].empty() ? "No" : "Yes");
}
}
return ;
}
Aguin
1013 String