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 \leftarrow 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 op		up(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]])*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 passed				db part2=(f[i-1][j-1][1]+g[d[i-1]][c[i]])*P[i-1]*(1-P[i]);//second apply not passed				db part3=(f[i-1][j-1][1]+g[c[i-1]][d[i]])*(1-P[i-1])*P[i];//first apply not passed				db part4=(f[i-1][j-1][1]+g[c[i-1]][c[i]])*(1-P[i-1])*(1-P[i]);//both applies passed				cmin(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的题目比较良心，没什么好说的，略水。

NOIp2016 Day1&Day2 解题报告