NOIP 2016 题解

发表于 | 更新于

新课学完了，回到微机室开始OI生活。首先当然要把NOIP的题目都A掉。 做完之后才感觉到，这一届NOIP虽然槽点很多，但是题目的质量还是很不错的，解法优美，没有码农题。

Toy

膜拟。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<algorithm>
#include<cstring>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::max;
using std::min;
const int MAXN=1e5+10;
int stat[MAXN];//0 内 1  外 
char nam[MAXN][20];
int main()
{
	int n,m;red(n),red(m);
	for(int i=1;i<=n;i++)
	{
		red(stat[i]);
		scanf("%s",nam[i]);
	}
	int cur=1,opt,cnt;
	for(int i=1;i<=m;i++)//opt==0 left opt==1 right
	{
		red(opt),red(cnt);
		opt^=stat[cur];
		if(opt==0) cnt*=-1;
		(((cur+=cnt)%=n)+=n)%=n;
		//cur+=cnt;if(cur<=0) cur+=n;
		if(!cur) cur=n;
	}
	printf("%s\n",nam[cur]);
	return 0;
}

Running

对于链，很容易想到使用双指针，扫一遍统计。 想想使用双指针的原因，无非是因为一些runner虽然到某个点ii的距离是wiw_i，但是在此之前就已经走到了终点，要排除这些runner的影响。 由此可以想到，一个runner能起作用的区间只是这个runner的起点到终点，由此可以看出差分的影子。这样，又得出一个不用双指针的在链上的做法：在区间l处+1,r+1处-1，就可以直接统计了。 做法搬到树上，基本差不多。从lca拆成两条链，这样深度是连续的，可以套用链的做法。 一点trick是，统计子树的答案，只需要统计出子树和进子树的答案差。这个还是第一次见。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T>
inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T>
inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::swap;
using std::make_pair;
using std::pair;
const int MAXN=3e5;
template <class T> struct List
{
	List<T> *pre;
	T val;
	List(List<T> *_pre,T _val):pre(_pre),val(_val){}
};
template <class T> inline void Add(List<T> *&cur,T val)
{
	cur=new List<T>(cur,val);
}
inline void *operator new(size_t sz)
{
	static const size_t SIZE=536870912;
	static char *ME=(char *)malloc(SIZE),*cur;
	return cur=ME,ME+=sz,(void *)cur;
}
inline void operator delete(void *p){}

List<int> *G[MAXN];
List<pair<int,int> > *mrk1[MAXN],*mrk2[MAXN],*query[MAXN];
struct FUS
{
	int fa[MAXN];
	int Root(int x){return fa[x]?fa[x]=Root(fa[x]):x;}
	void Union(int x,int y)//x为父节点
	{
		x=Root(x),y=Root(y);
		fa[y]=x;
	}
}S;
int qlca[MAXN],dep[MAXN],w[MAXN];
void DFS(int pos)
{
	for(List<int> *it=G[pos];it;it=it->pre)
	{	
		int u=it->val;if(dep[u]) continue;
		dep[u]=dep[pos]+1;
		DFS(u);
		S.Union(pos,u);
	}
	for(List<pair<int,int> > *it=query[pos];it;it=it->pre)
	{
		int u=it->val.first;
		if(dep[u]) qlca[it->val.second]=S.Root(u);
	}
}
int cnt1[MAXN<<1],__cnt2[MAXN<<1],*cnt2=__cnt2+MAXN,ANS[MAXN];
bool ud[MAXN];
void Calc(int pos)
{
	ud[pos]=1;
	ANS[pos]-=cnt1[w[pos]+dep[pos]]+cnt2[w[pos]-dep[pos]];
	for(List<pair<int,int> > *it=mrk1[pos];it;it=it->pre)
		cnt1[it->val.first]+=it->val.second;
	for(List<pair<int,int> > *it=mrk2[pos];it;it=it->pre)
		cnt2[it->val.first]+=it->val.second;
	for(List<int> *it=G[pos];it;it=it->pre)	
		if(!ud[it->val]) Calc(it->val);	
	ANS[pos]+=cnt1[w[pos]+dep[pos]]+cnt2[w[pos]-dep[pos]];
}
int main()
{
	static struct Opt{int s,t;}opt[MAXN];
	int n,Q,t1,t2;red(n),red(Q);
	for(int i=1;i<=n-1;i++)
	{
		red(t1),red(t2);
		Add(G[t1],t2);Add(G[t2],t1);
	}
	for(int i=1;i<=n;i++)
		red(w[i]);
	for(int i=1;i<=Q;i++)
	{
		red(opt[i].s),red(opt[i].t);
		Add(query[opt[i].s],make_pair(opt[i].t,i));
		Add(query[opt[i].t],make_pair(opt[i].s,i));
	}
	dep[1]=1;DFS(1);
	for(int i=1;i<=Q;i++)
	{
		int lca=qlca[i],s=opt[i].s,t=opt[i].t;
		Add(mrk1[lca],make_pair(t1=dep[s],-1));
		Add(mrk1[s],make_pair(t1,1));
		Add(mrk2[lca],make_pair(t1=dep[s]-dep[lca]*2,-1));
		Add(mrk2[t],make_pair(t1,1));
		if(dep[s]-dep[lca]==w[lca]) ANS[lca]++;
	}
	Calc(1);
	for(int i=1;i<=n;i++)
		printf("%d%s",ANS[i],i==n?"\n":" ");
	return 0;
}

Classroom

在考场上想到的就是正解。但是因为不熟悉期望的性质怕有问题不敢写。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define dred(x) scanf("%lf",&x)
#define ldred(x) scanf("%Lf",&x)
template <class T>
inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T>
inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long double ld;
using std::min;
using std::max;
const int MAXC=2000+1,MAXN=300+1,INF=522133279;
inline ld E(ld rate,ld v1,ld v2){return rate*v1+(1-rate)*v2;}
int main()
{
	static int loc[MAXC][2],sp[MAXN][MAXN];
	static ld rate[MAXC],f[MAXC][MAXC][2];
	//freopen("input","r",stdin);
	memset(sp,31,sizeof(sp));
	int cac,lim,n,m;red(cac),red(lim),red(n),red(m);
	for(int i=1;i<=cac;i++) red(loc[i][0]);
	for(int i=1;i<=cac;i++) red(loc[i][1]);
	for(int i=1;i<=cac;i++) ldred(rate[i]);
	for(int i=1;i<=n;i++) sp[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int a,b,w;
		red(a),red(b),red(w);
		chkmn(sp[a][b],w);
		chkmn(sp[b][a],w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
					chkmn(sp[i][j],sp[i][k]+sp[k][j]);
	//f[i][j][0/1] 前i个教室，申请j个，第i间教室申请/不申请的最小期望
	for(int i=1;i<=cac;i++)
			for(int j=0;j<=lim;j++)
				for(int k=0;k<=1;k++)
					f[i][j][k]=INF;
	f[1][0][0]=f[1][1][1]=0;
	for(int i=2;i<=cac;i++)
		for(int j=0;j<=lim;j++)
		{
			f[i][j][0]=min(f[i-1][j][0]+sp[loc[i-1][0]][loc[i][0]],
						   f[i-1][j][1]+E(rate[i-1],sp[loc[i-1][1]][loc[i][0]],sp[loc[i-1][0]][loc[i][0]]));
			if(j==0) continue;
			f[i][j][1]=min(f[i-1][j-1][0]+E(rate[i],sp[loc[i-1][0]][loc[i][1]],sp[loc[i-1][0]][loc[i][0]]),
						   f[i-1][j-1][1]+rate[i-1]*rate[i]*sp[loc[i-1][1]][loc[i][1]]
									   +rate[i-1]*(1-rate[i])*sp[loc[i-1][1]][loc[i][0]]
									   +(1-rate[i-1])*rate[i]*sp[loc[i-1][0]][loc[i][1]]
									   +(1-rate[i-1])*(1-rate[i])*sp[loc[i-1][0]][loc[i][0]]);
		}
	ld ANS=INF;
	for(int i=0;i<=lim;i++) chkmn(ANS,min(f[cac][i][0],f[cac][i][1]));
	printf("%.2Lf\n",ANS);
	return 0;
}

Problem

成了今年决定1=的题目了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#define red(x) scanf("%d",&x)
using std::max;
using std::min;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
typedef unsigned long long ULL;
const int N=2000,MAXN=N+100;
int f[MAXN][MAXN];
int Prep(int K)
{
	f[0][0]=f[1][0]=f[1][1]=1%K;
	for(int i=2;i<=N;i++)
	{
		f[i][0]=f[i][i]=1%K;
		for(int j=1;j<i;j++)
			f[i][j]=(f[i-1][j-1]+f[i-1][j])%K;
	}
	f[0][0]=(f[0][0]==0);
	for(int i=1;i<=N;i++)
		for(int j=0;j<=i;j++)
			f[i][j]=f[i-1][j]+(f[i][j]==0);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=i;j++)
			f[i][j]+=f[i][j-1];
}
int main()
{
	int T,K,n,m;red(T),red(K);
	Prep(K);
	while(T--)
	{
		red(n),red(m);chkmn(m,n);
		printf("%d\n",f[n][m]);
	}
	return 0;
}

Worm

在考场上思路的方向错了

因为⌊mt⌋\lfloor \frac mt\rfloor是1e5级别的，认为时间复杂度应该是个T(mt)T(\frac mt)的。然后毫无头绪。 q=0，每次拿出的长度单调不升，则切出来的长的一段和短的一段也分别单调不上升。维护三个队列：原序列，切出的长的一段，切出的短的一段，则可以直接取得最大值。

q>0，每次除了切的那个，其它的都长了q。即使它们不长q，切出的两端也要短，更别提它们都长了q，而切去的没有长

这个思路难吗？不难。但是这种分析的方式是迫切需要学习的。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T>
inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T>
inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+7e6+1;
using std::sort;
using std::for_each;
using std::greater;
struct queue
{
	int a[MAXN],head,tail;
	queue(){head=1,tail=0;}
	void push(int x){a[++tail]=x;}
	void pop(){head++;}
	int& front(){return a[head];}
	bool empty(){return head>tail;}
}Q[3];
int Pop()
{
	int res=-1;
	for(int i=0;i<=2;i++)
		if(!Q[i].empty() && (res==-1 || Q[res].front()<Q[i].front()))
			res=i;
	int ans=Q[res].front();Q[res].pop();
	return ans;
}
int main()
{
	static int a[MAXN],outs[MAXN],*op=outs;	
	int n,m,q,u,v,t;
	red(n),red(m),red(q),red(u),red(v),red(t);
	for(int i=1;i<=n;i++) red(a[i]);
	sort(a+1,a+1+n,greater<int>());
	for(int i=1;i<=n;i++) Q[0].push(a[i]);
	int delta=0;
	for(int i=1;i<=m;i++)
	{
		int x=Pop()+delta,px=(int)((long double)u*x/v);
		delta+=q;
		Q[1].push(px-delta);Q[2].push(x-px-delta);
		if(i%t==0) *++op=x;
	}
	for(int *it=outs+1;it<=op;++it)
		printf("%d%s",*it,it==op?"":" ");
	puts("");
	op=outs;
	for(int i=1;i<=n+m;i++)
	{
		int x=Pop()+delta;
		if(i%t==0) *++op=x;
	}
	for(int *it=outs+1;it<=op;++it)
		printf("%d%s",*it,it==op?"":" ");
	puts("");
	return 0;
}

AngryBirds

DFS，状压剪个枝。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
using std::max;
using std::min;
using std::sort;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=20,INF=522133279;
typedef long double ld;
const ld eps=1e-10;
inline int fcmp(const ld &x)
{
	if(-eps<=x && x<=eps) return 0;
	return x<0?-1:1;
}
struct Point
{
	ld x,y;
	bool operator <(const Point &a) const
	{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
}p[MAXN];
int ANS,cur,n;
struct Line
{
	ld a,b;
	Line(){a=b=0;}
	ld f(ld x){return a*x*x+b*x;}
	bool On(Point po)
	{
		return fcmp(f(po.x)-po.y)==0;
	}
};
Line equ(Point a,Point b)//a.x !=b.x
{
	Line res;
	ld C1=a.y,A1=a.x*a.x,B1=a.x;
	ld C2=b.y,A2=b.x*b.x,B2=b.x;
	ld a1=A1,a2=A2;
	C1*=a2,A1*=a2,B1*=a2,C2*=a1,A2*=a1,B2*=a1;
	res.b=(C1-C2)/(B1-B2);
	res.a=(C1-res.b*B1)/A1;
	return res;
}
inline int Count(int x)
{
	int res=0;
	while(x) x>>=1,res++;
	return --res;
}
const int SZE=2097152+10;
int rec[SZE],us[SZE],rT;
void DFS(int step)
{
	if(us[cur]!=rT)
	{
		us[cur]=rT;
		rec[cur]=INF;
	}
	if(!cur)
	{
		chkmn(ANS,step);
		return;
	}
	else if(step>ANS)
		return;
	else if(!chkmn(rec[cur],step)) 
		return;
	int bac=cur,pres=Count(cur & -cur);Line eq;
	cur^=(1<<pres);DFS(step+1);cur=bac;
	for(int i=pres+1;i<=n;i++)
	{
		if(p[pres].x!=p[i].x)
		{
			eq=equ(p[pres],p[i]);
			if(fcmp(eq.a)<0)
			{
				for(int j=pres;j<=n;j++)
				{
					if(eq.On(p[j]) && (cur & (1<<j)))
						cur^=(1<<j);
				}
				DFS(step+1);
				cur=bac;
			}
		}
	}
}
int main()
{
	//freopen("input","r",stdin);
	int T,m;red(T);
	while(T--)
	{
		rT++;
		red(n),red(m);
		cur=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%Lf%Lf",&p[i].x,&p[i].y);
			cur|=(1<<i);
		}
		sort(p+1,p+1+n);
		ANS=n;
		if(m==1) ANS=(int)(1.0*n/3+2);
		DFS(0);
		printf("%d\n",ANS);
	}
	
	return 0;
}

对了，Worm和AngryBirds一开始在uoj上都etf了，都是精度问题。 所以，用的起long double，绝不用double