Day1
T1 toy
本题考查你会不会编程。
//toy//by Cydiater//2016.11.19#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <iomanip>#include <bitset>#include <set>using namespace std;#define ll long long#define up(i,j,n)for(int i=j;i<=n;i++)#define down(i,j,n)for(int i=j;i>=n;i--)#define cmax(a,b)a=max(a,b)#define cmin(a,b)a=min(a,b)#define FILE "toy"const int MAXN=1e5+5;const int oo=0x3f3f3f3f;inline int read(){char ch=getchar();int x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int N,M,Step,F,now=0;struct Data{char s[25];int pos,f,len;}a[MAXN];namespace solution{void init(){N=read();M=read();up(i,0,N-1){a[i].f=read();scanf("%s",a[i].s+1);a[i].len=strlen(a[i].s+1);a[i].pos=i;}}void slove(){while(M--){F=read();Step=read();if(F==a[now].f)F=-1;else F=1;now=((now+N+F*Step)%N+N)%N;}}void output(){up(i,1,a[now].len)printf("%c",a[now].s[i]);puts("");}}int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);using namespace solution;init();slove();output();return 0;}
T2 running
这道题其实放在T2并不合适，相比去年的D1T2要难太多。
首先如果忽略观测时间的话，这就是个很简单的树上差分问题。同样，这道题也需要用树上差分解决。对于一颗树，从$x$到$y$的路径可以拆分成两个部分：$x \rightarrow lca$和$lca \rightarrow y$。那么，我们就可以把整条路径拆成这两个部分单独考虑。即所有路径拆分过后只有两种形式：从深度浅的指向深度深的,和从深度深的指向深度浅的。接下来考虑题目要求。设$v_i$表示第$i$点的值，$dep_i$表示第$i$个点的深度，有一条$x \rightarrow y(dep_x < dep_y)$的路径,那么对于每个符合要求的点，必有$dep_i-v_i=dep_x$，即$dep_i-v_i$是一个定值，同样的，从下指上的，$dep_i+v_i$是一个定值。
这样问题就转化成了给定一条深度递增/递减的路径，把路径上的点$dep_i \pm v_i$为某一值的点加1。
考虑使用树上差分解决。对于一条$x \rightarrow y(dep_x<dep_y)$这样的路径，要将其中$dep_i-v_i=dep_x$的点全部加一，在$fa_x$上插入$(dep_x,-1)$这样的状态（用pair+vector维护），在$y$上插入$(dep_x,1)$这样的状态。另外的情况同理。
这样的话用Tarjan在$O(N+M)$的时间内求出所有的lca,然后每个询问在$O(1)$的时间内打个标记就行了。
但是问题是，最后的统计似乎并不是很好处理。
首先，搞出DFS序。对于每个点我们很好搞出其对应的区间。再次利用离线和差分的思想，把所有需要操作的区间存下来。搞两个数组$cnt_1$和$cnt_2$分别记录$dep_i \pm v_i$的答案，然后遍历DFS序，每次访问到一个节点，先更新其对$cnt_1$和$cnt_2$的贡献，最后更新其对应区间的答案。（看代码比较直观
//NOIP2016D1T2//by Cydiater//2016.11.26#include <iostream>#include <cmath>#include <cstdlib>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <bitset>#include <cstdio>#include <set>#include <iomanip>#include <vector>using namespace std;#define ll long long#define pii pair<int,int>#define up(i,j,n)for(int i=j;i<=n;i++)#define down(i,j,n)for(int i=j;i>=n;i--)#define cmax(a,b)a=max(a,b)#define cmin(a,b)a=min(a,b)#define Auto(i,node)for(int i=LINK[node];i;i=e[i].next)#define FILE "running"const int MAXN=3e5+5;const int oo=0x3f3f3f3f;inline int read(){char ch=getchar();int x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int N,M,LINK[MAXN],len=0,lable[MAXN],G[MAXN],fa[MAXN],dep[MAXN],dfn[MAXN],Pos[MAXN],dfs_clock,siz[MAXN],cnt1[MAXN<<2],cnt2[MAXN<<2],ans[MAXN];bool vis[MAXN];struct edge{int y,next;}e[MAXN<<1];struct PATH{int x,y,lca;}Path[MAXN];vector<pii> fri[MAXN],tag1[MAXN],tag2[MAXN],LR[MAXN];namespace solution{inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}inline void Insert(int x,int y){insert(x,y);insert(y,x);}int getf(int k){if(G[k]==k)return k;G[k]=getf(G[k]);return G[k];}void init(){N=read();M=read();up(i,2,N){int x=read(),y=read();Insert(x,y);}up(i,1,N)lable[i]=read();up(i,1,M){int x=read(),y=read();Path[i].x=x;Path[i].y=y;fri[x].push_back(make_pair(i,y));fri[y].push_back(make_pair(i,x));}}void Tarjan(int node){G[node]=node;vis[node]=1;dfn[node]=++dfs_clock;Pos[dfs_clock]=node;siz[node]=1;Auto(i,node)if(!vis[e[i].y]){dep[e[i].y]=dep[node]+1;Tarjan(e[i].y);G[e[i].y]=node;fa[e[i].y]=node;siz[node]+=siz[e[i].y];}up(i,0,(int)(fri[node].size()-1))if(vis[fri[node][i].second])Path[fri[node][i].first].lca=getf(fri[node][i].second);}void make_tag(int x,int y,int st,bool flag=false){if(dep[x]<=dep[y]){int fx=fa[x];if(fx)tag1[fx].push_back(make_pair(st-dep[x],-1));tag1[y].push_back(make_pair(st-dep[x],1));}else{int fy=fa[y];if(flag)tag2[y].push_back(make_pair(st+dep[x],-1));else if(fy)tag2[fy].push_back(make_pair(st+dep[x],-1));tag2[x].push_back(make_pair(st+dep[x],1));}}void slove(){Tarjan(1);//O(N+M) LCA and some opup(i,1,M){int x=Path[i].x,y=Path[i].y,lca=Path[i].lca;if(lca==x||lca==y)make_tag(x,y,0);else{make_tag(x,lca,0,true);make_tag(lca,y,dep[x]-dep[lca]);}}up(i,1,N){LR[dfn[i]-1].push_back(make_pair(i,-1));LR[dfn[i]+siz[i]-1].push_back(make_pair(i,1));}int Delta=N<<1;up(i,1,N){int node=Pos[i];up(j,0,(int)(tag1[node].size()-1))cnt1[tag1[node][j].first+Delta]+=tag1[node][j].second;up(j,0,(int)(tag2[node].size()-1))cnt2[tag2[node][j].first+Delta]+=tag2[node][j].second;up(j,0,(int)(LR[i].size()-1)){pii tmp=LR[i][j];ans[tmp.first]+=cnt1[lable[tmp.first]-dep[tmp.first]+Delta]*tmp.second;ans[tmp.first]+=cnt2[lable[tmp.first]+dep[tmp.first]+Delta]*tmp.second;}}}void output(){up(i,1,N)printf("%d ",ans[i]);puts("");}}int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);using namespace solution;init();slove();output();return 0;}
T3 classroom
制杖DP，但是赛场上被T2搞懵了，没有认真分析这道题。
首先，肯定要用Floyd搞出$g_ij$表示任意两点的最短路径。然后设$f[i][j][0/1]$表示第$i$个课程，申请了$j$次，这一次是否申请的最小答案。
然后很好得到以下转移方程。
$f[i][j][0]=min(f[i-1][j][0]+g[c[i-1]][c[i]],f[i-1][j][1]+g[d[i-1]][c[i]] \times P[i-1]+g[c[i-1]][c[i]] \times (1-P[i-1]))$
$f[i][j][1]=min(f[i-1][j-1][0]+g[c[i-1]][d[i]]\times P[i]+g[c[i-1]][c[i]]\times (1-P[i]),(f[i-1][j-1][1]+g[d[i-1]][d[i]]) \times P[i-1] \times P[i]+(f[i-1][j-1][1]+g[d[i-1]][c[i]]) \times P[i-1] \times (1-P[i])+(f[i-1][j-1][1]+g[c[i-1]][d[i]]) \times (1-P[i-1]) \times P[i]+(f[i-1][j-1][1]+g[c[i-1]][c[i]]) \times (1-P[i-1]) \times (1-P[i]))$
//NOIP2106D1T3//Cydiater//2016.11.25#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstdlib>#include <iomanip>#include <bitset>#include <set>using namespace std;#define ll long long#define db double#define up(i,j,n)for(int i=j;i<=n;i++)#define down(i,j,n)for(int i=j;i>=n;i--)#define cmax(a,b)a=max(a,b)#define cmin(a,b)a=min(a,b)#define FILE "classroom"const int MAXN=2005;const int MAXX=305;const db oo=1e20;inline int read(){char ch=getchar();int x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int N,M,V,E,c[MAXN],d[MAXN],g[MAXX][MAXX];db P[MAXN],f[MAXN][MAXN][2],ans=oo;namespace solution{void init(){N=read();M=read();V=read();E=read();if(N==1){puts("0.00");exit(0);}memset(g,10,sizeof(g));up(i,1,N)c[i]=read();up(i,1,N)d[i]=read();up(i,1,N)scanf("%lf",&P[i]);up(i,1,V)g[i][i]=0;up(i,1,E){int x=read(),y=read(),v=read();cmin(g[x][y],v);cmin(g[y][x],v);}}void slove(){up(i,0,MAXN-1)up(j,0,MAXN-1)up(k,0,1)f[i][j][k]=oo;up(k,1,V)up(i,1,V)up(j,1,V)cmin(g[i][j],g[i][k]+g[k][j]);f[1][0][0]=f[1][1][1]=0;up(i,2,N){f[i][0][0]=f[i-1][0][0]+g[c[i-1]][c[i]];up(j,1,min(M,i)){f[i][j][0]=min(f[i-1][j][0]+g[c[i-1]][c[i]],f[i-1][j][1]+g[d[i-1]][c[i]]*P[i-1]+g[c[i-1]][c[i]]*(1-P[i-1]));f[i][j][1]=f[i-1][j-1][0]+g[c[i-1]][d[i]]*P[i]+g[c[i-1]][c[i]]*(1-P[i]);db part1=(f[i-1][j-1][1]+g[d[i-1]][d[i]])*P[i-1]*P[i];//both applies passeddb part2=(f[i-1][j-1][1]+g[d[i-1]][c[i]])*P[i-1]*(1-P[i]);//second apply not passeddb part3=(f[i-1][j-1][1]+g[c[i-1]][d[i]])*(1-P[i-1])*P[i];//first apply not passeddb part4=(f[i-1][j-1][1]+g[c[i-1]][c[i]])*(1-P[i-1])*(1-P[i]);//both applies passedcmin(f[i][j][1],part1+part2+part3+part4);if(i==N)cmin(ans,min(f[i][j][0],f[i][j][1]));}if(i==N)cmin(ans,f[i][0][0]);}printf("%.2lf\n",ans);}}int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);using namespace solution;init();slove();return 0;}
Day1小结
Day1的题目水平相当高，特别是T2坑住了一堆弱如我这般赛场上暴力写挂又想不出正解的制杖。但是难度分配确实不合理蛙，T2和T3应该调换一下顺序这场比赛才比较好..
//CCF公开膜吃枣药丸
Day2
T1 problem
题目好评，对初学者不太友好。
首先组合数的递推公式：$C_i^j=C_{i-1}^j+C_{i-1}^{j-1}$。这个要知道，然后在递推时对$k$取个余，最后统计一下矩阵就行了。（不是很懂质因数分解那一套
//problem//by Cydiater//2016.11.20#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <algorithm>#include <iomanip>#include <ctime>#include <cmath>#include <queue>#include <map>#include <bitset>#include <set>using namespace std;#define ll long long#define up(i,j,n)for(int i=j;i<=n;i++)#define down(i,j,n)for(int i=j;i>=n;i--)#define cmax(a,b)a=max(a,b)#define cmin(a,b)a=min(a,b)#define FILE "problem"const ll MAXN=2000+5;const ll LIM=2000;const ll oo=0x3f3f3f3f;inline ll read(){char ch=getchar();ll x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}ll C[MAXN][MAXN],T,K,ans[MAXN][MAXN];namespace solution{void slove(){T=read();K=read();memset(C,0,sizeof(C));memset(ans,0,sizeof(ans));up(i,0,LIM)C[i][0]=1;up(i,1,LIM)up(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%K;up(i,1,LIM)up(j,i+1,LIM)C[i][j]=-1;up(i,1,LIM){up(j,1,LIM){if(C[i][j]==0)ans[i][j]++;ans[i][j]+=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];}}while(T--){ll x=read(),y=read();printf("%lld\n",ans[x][y]);}}}int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);using namespace solution;slove();return 0;}
T2 earthworm
很容易看出来就是个堆，但是显然想AC需要线性算法。通过打表我们可以发现蚯蚓每次切割的长度是单调递增的，而每次被切成两段的总是单调递减的。于是我们就可以用三个单调队列来维护没被切断的，切断的短的那一段，切断的长的那一段，每次取个max即可。
//NOIP2016 D2T2//by Cydiater//2016.11.24#include <iostream>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstdlib>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <iomanip>#include <bitset>#include <set>using namespace std;#define ll long long#define up(i,j,n)for(int i=j;i<=n;i++)#define down(i,j,n)for(int i=j;i>=n;i--)#define cmax(a,b)a=max(a,b)#define cmin(a,b)a=min(a,b)#define FILE "earthworm"const ll MAXN=1e7+5;const ll oo=1LL<<55;inline ll read(){char ch=getchar();ll x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}ll N,M,Q,U,V,T,_old[MAXN],_short[MAXN],_long[MAXN],t1=0,t2=1,t3=1,top2=0,top3=0,cnt=0,delta=0;namespace solution{void init(){N=read();M=read();Q=read();U=read();V=read();T=read();up(i,1,N)_old[++t1]=read();sort(_old+1,_old+t1+1);_old[0]=_short[0]=_long[0]=-oo;}void slove(){while(M--){ll now=max(_old[t1],max(_short[t2],_long[t3]));if(now==_old[t1])t1--;else if(now==_short[t2])t2++;else if(now==_long[t3])t3++;now+=delta;if(!(++cnt%T))printf("%d ",now);ll __short=now*U/V,__long=now-__short;delta+=Q;_short[++top2]=__short-delta;_long[++top3]=__long-delta;}cnt=0;puts("");M=t1+top2+top3-t2-t3+2;while(M--){ll now=max(_old[t1],max(_short[t2],_long[t3]));if(now==_old[t1]&&t1>0)t1--;else if(now==_short[t2]&&t2<=top2)t2++;else if(now==_long[t3]&&t3<=top3)t3++;if(t2>top2)_short[t2]=-oo;if(t3>top3)_long[t3]=-oo;if(!(++cnt%T))printf("%lld ",now+delta);}}}int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);using namespace solution;init();slove();return 0;}
T3 angrybirds
状压DP一眼题。但是一眼的复杂度是$O(2^N N^2)$的，会被卡掉。
考虑优化掉一个$N$。其实每次转移时只需要处理第一个没被攻击的猪就好了，这样的话复杂度降低到$O(2^N N)$可以顺利通过。
//angrybirds//by Cydiater//2016.11.20#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <algorithm>#include <iomanip>#include <ctime>#include <cmath>#include <queue>#include <map>#include <bitset>#include <set>using namespace std;#define ll long long#define up(i,j,n)for(ll i=j;i<=n;i++)#define down(i,j,n)for(ll i=j;i>=n;i--)#define cmax(a,b)a=max(a,b)#define cmin(a,b)a=min(a,b)#define FILE "angrybirds"#define eps 1e-6const int MAXN=25;const int MAXX=1<<18+5;inline int read(){char ch=getchar();int x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int N,M,S[MAXN][MAXN],f[MAXX],T,top[MAXN];struct XY{double x,y;}xy[MAXN];namespace solution{void init(){N=read();M=read();memset(top,0,sizeof(top));memset(f,10,sizeof(f));f[0]=0;up(i,0,N-1)scanf("%lf %lf",&xy[i].x,&xy[i].y);up(i,0,N-1){xy[i].x*=100;xy[i].y*=100;}}inline bool OK(double a,double b,XY t){double x=t.x,y=t.y;if(abs(y-(x*x*a+b*x))<=eps)return 1;return 0;}void slove(){up(i,0,N-1){S[i][++top[i]]=(1<<i);up(j,i+1,N-1){double x=xy[i].x,y=xy[i].y,_x=xy[j].x,_y=xy[j].y;if(x*_x==0||x-_x==0)continue;double a=y/(x*(x-_x))-_y/(_x*(x-_x)),b=y/x-a*x;if(a+eps>=0)continue;int ss=0;up(k,0,N-1)if(OK(a,b,xy[k]))ss|=(1<<k);S[i][++top[i]]=ss;}}up(i,0,(1<<N)-1)up(j,0,N-1)if(((1<<j)&(i))!=(1<<j)){up(k,1,top[j])cmin(f[(i|S[j][k])],f[i]+1);break;}}void output(){printf("%d\n",f[(1<<N)-1]);}}int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);using namespace solution;T=read();while(T--){init();if(N==1){puts("1");continue;}slove();output();}return 0;}
Day2小结
Day2的题目比较良心，没什么好说的，略水。
