BZOJ的第500题不知道做什么好了，就来做做几乎不太会的提答吧。。

【NOI2014】消除游戏（95/100）

题意：给一个N*M的数字矩阵，每次找一个长度为l的数，将获得l^c1+l^c2的得分，c1为质数得分，c2为回文数得分，要获得尽量高的分

1：数据很小，手玩就可以了

2：数据比较小，用机器模拟+手玩就可以了

3、4：100*100的方格找500个18位素数，暴力找用Miller-Rabin判素数，很快就可以出解

5：10*10的方格找最多8位素数，先暴力找，然后最后几步手玩多试一下就可以了

6、7：1000*1000的方格，只有至多3种数，要找一条1000的回文路，直接在中心找一个暴力扩展到1000步就可以了

8：999*100的方格，大多数是5和6交叉，中间有几个其它的数，要找一条回文路，原来想和T9一样绕过去，但发现有些点绕不过去，就拿5分GG了。。

9：129*128的方格，要求找一条回文路，发现左右几乎对称，但是有几个点不对称，小心地绕过这些点就行了

10：3*999的方格，要求找一条回文路，一开始发现第一行是回文，但是第2、3行不回文，仔细看发现是33*9个3*3的循环节，先两边对称走，中间一个特判一下走就可以了

【NOI2006】聪明的导游（83+17/100）

【NOI2005】小H的聚会（93/115）

题意：求一颗每个点有度数限制的最小生成树

1-3：度数限制为n-1，直接最小生成树

4-6：只有一个点有度数限制，没有部分分，可以用度限制最小生成树的算法，可是我不会QAQ

7-10：每个点都有度数限制的数据

先用一个傻逼的方法，从大到小排序后合法就加，不合法就不加，可是这样除了送的30分拿不了多少分

那么在排序后再加一个随机化，每次随机调整相邻位置的，再用傻逼的方法进行判断

每组数据随机几百万次，取最好的一次，这样就可以拿到挺多分了，只有第6个点0分，第7个点6分

据说4~6是度限制最小生成树的做法TAT

可见这个出题人十分邪恶，看上去最正确的做法根本拿不到分，随便搞搞却可以拿很多分

【NOI2010】成长快乐（87/100）

题目大意：有一只鱼要去吃虾，只能吃比他小的虾，虾按一个固定方向走，鱼有最大速度，求在一定时间内鱼最多增重

第1~3个测试点比较小，可以直接暴力，算时间的话解一个一元二次方程就可以了

剩下的点比较大了，先多随机化几遍试试看，但是增加的分并不对

那么试一下贪心，每次选增重/t^2最大的虾去吃

随机化贪心有点难写啊，先贪一次试试看。。

前几个点不太理想，但是后面几个测试点却拿了很多分。。

这样把多种傻逼方法综合一下就可以拿到87分

估计随机化贪心可以再多拿点蛤

【NOI2008】赛程安排（94/100）

题意：安排淘汰赛赛程，使得1号选手获得最大奖金

先写了个暴力，只给了两个点，剩下的点先傻逼贪心，只按和1的关系排序，这样就骗了50分

然后觉得退火找不到范围啊，只好乱写了个随机化。。

就是每次随机选择调整两个位置互换，如果答案更优就换，这样就骗到了75分

6、7两个明显是特殊数据，发现6只有1.0和0.5，那么肯定是要让1和100%的胜率的对手打，那么用堆安排一种方案就行了

用同样的方法做7发现不合法，发现还有0.6、0.7、0.8，一开始眼瞎了只看到0.7，结果还是不合法，改了一下也没加特判，把0.6、0.7、0.8当1看，结果就跑出最优解了。。

如此傻逼的做法就拿了93分，真是醉了。。感觉3、4两个点是人类智慧233。。

第三个点人类智慧一下，手动安排前4个排列，剩下的暴力，就可以得到最优解啦

第四个点人类智慧就GG啦QAQ

然后发现智商太低了人类智慧题码了个暴力GG了。。

【WC2015】未来程序（62/100）

1（10）：送分点，快速加就可以了

2（10）：发现有循环节，直接取膜模拟就可以了

3（10）：数列题，求出数列通项公式就可以了

4（10）：第一个问题是求出白点总数*（白点总数-1），第二问是找出离每个黑点曼哈顿最近的白点，BFS即可

5（10）：求有多少个矩形，暴力n^3 1小时就跑出了，不用写n^2

6（3）：求f^n(x),f(x)=(ax^2+b),不会做，发现有一些点有循环节，骗了3分

7（3）：搜索一个16*16数独的方案，暴力只跑出了3分。。

8（6）：排列组合大集合，只做出6道，剩下几道挺难算的。。

9：后来在线破解了下 10：QAQ

前5个点大约花了一个小时，还是很划算的，后面几个点花了一个多小时，不过在WC上似乎也不亏。。

【WC2013】小Q运动季（63/100）

1（10）：送分点，找出符合最多等式的数就可以了

2（5）：50个m=1的式子，需要CRT+高精度，太烦人了，用了第一个测试点的方法拿5分走人

3（10）：模质数的高斯消元

4（10）：发现是有规律的，从下往上暴力得到可能的解，并对解进行判断，取符合等式最多的解即可

5（2）：模2*3*5*...*23的高斯消元，加了个CRT，可是只能符合30个等式GG了

6（2）：模不一样的数的高斯消元，要CRT+高精，可我+CRT就炸了，GG了

7（10）：发现是有规律的，但有50个数直接暴力就GG了，可以用dp[i][S]表示前i个数模数为S是否可行，就可以出解啦

8（2）：同6

9（10）：送分点，找出出现次数最多的数就可以了

10（2）：GG

【WC2014】非确定机（68/100）

1（10）：送分点，按输出连边就可以了

2（10）：给出一个最短路答案，构造方案，边权不超过20000，从小到大连起来就可以了

3（10）：大概是BFS之类的，只要把所有1的连起来就可以了

4（10）：从1号点开始到每个点求出最少经过一个环的最短路，边权不超过20000，发现最小的答案也比20000大，不科学啊。。想了好久，发现可以连自环，然后从小到大连起来就可以了

5（10）：给出tarjan后情况，构造方案，写个vector把边连起来就可以了

6（2）：只有4个数，实在是找不到规律QAQ

7（2）：和6差不多GG

8（10）：试了几下，发现只要把61*100的矩阵填满就可以啦

9（2）：不知道是干嘛的

10（2）：不知道是干嘛的

最近三年WC的提答都是NOIP十合一，发现一般来说30~40分可以30min玩出，要拿到60需要2小时多，然后花更多的时间的收获就不会太多了..

【ZJOI2014】2048（50/100）

一开始写了个纯随机化，发现还不如手玩TAT。。

然后试了下暴搜几步取块数最小的，只能合出1024,0分。。

然后改一下估价，块数相等取角落最大的，可以合出4096了，10分。。

然后再改一下估价，为取任意一个角为起点，其它格子到角的距离*权值和，竟然跑过了8192，跑过了16384，吓死了。。

#include<bits/stdc++.h>
using namespace std;bool ff;int T,X,i,j,o=0,w,t,U,V,now,nn,XX,b[22][5][5],a[5][5],A[5][5],q[1111111],ST[22],st[22];
int G(int &X){return (X=(X*8221)+(X>>16))&15;}
int GJ(){
	int A=0,B=0,C=0,D=0,i,j,k;
	for(i=1;i<=4;i++)for(j=1;j<=4;j++)A+=(i+j-2)*b[11][i][j];
	if(b[11][1][2]>b[11][2][1]){
		if(!b[11][1][4])A++;
	}else if(!b[11][4][1])A++;
	for(i=1;i<=4;i++)for(j=1;j<=4;j++)B+=(4-i+j-1)*b[11][i][j];
	if(b[11][3][1]>b[11][4][2]){
		if(!b[11][1][1])B++;
	}else if(!b[11][4][4])B++;
	for(i=1;i<=4;i++)for(j=1;j<=4;j++)C+=(i-1+4-j)*b[11][i][j];
	if(b[11][1][3]>b[11][2][4]){
		if(!b[11][1][1])C++;
	}else if(!b[11][4][4])C++;
	for(i=1;i<=4;i++)for(j=1;j<=4;j++)D+=(4-i+4-j)*b[11][i][j];
	if(b[11][3][4]>b[11][4][3]){
		if(!b[11][1][4])D++;
	}else if(!b[11][4][1])D++;
	return min(min(A,B),min(C,D));
}
bool mdf(int o){
	int i,j,k;bool ff=0;
	if(!o){//U
		for(k=1;k<4;k++)for(j=1;j<=4;j++)for(i=1;i<4;i++)
			if(!a[i][j]&&a[i+1][j])swap(a[i][j],a[i+1][j]),ff=1;
		for(j=1;j<=4;j++)
			if(a[1][j]==a[2][j]){
				ff|=a[2][j];a[1][j]*=2,a[2][j]=a[3][j],a[3][j]=a[4][j],a[4][j]=0;
				if(a[2][j]==a[3][j])a[2][j]*=2,a[3][j]=0;
			}else if(a[2][j]==a[3][j])ff|=a[3][j],a[2][j]*=2,a[3][j]=a[4][j],a[4][j]=0;
			else if(a[3][j]==a[4][j])ff|=a[4][j],a[3][j]*=2,a[4][j]=0;
	}else if(o==1){//D
		for(k=1;k<4;k++)for(j=1;j<=4;j++)for(i=1;i<4;i++)
			if(a[i][j]&&!a[i+1][j])swap(a[i][j],a[i+1][j]),ff=1;
		for(j=1;j<=4;j++)
			if(a[3][j]==a[4][j]){
				ff|=a[4][j],a[4][j]*=2,a[3][j]=a[2][j],a[2][j]=a[1][j],a[1][j]=0;
				if(a[2][j]==a[3][j])a[3][j]*=2,a[2][j]=0;
			}else if(a[2][j]==a[3][j])ff|=a[3][j],a[3][j]*=2,a[2][j]=a[1][j],a[1][j]=0;
			else if(a[1][j]==a[2][j])ff|=a[2][j],a[2][j]*=2,a[1][j]=0;
	}else if(o==2){//L
		for(k=1;k<4;k++)for(i=1;i<=4;i++)for(j=1;j<4;j++)
			if(!a[i][j]&&a[i][j+1])swap(a[i][j],a[i][j+1]),ff=1;
		for(i=1;i<=4;i++)
			if(a[i][1]==a[i][2]){
				ff|=a[i][1],a[i][1]*=2,a[i][2]=a[i][3],a[i][3]=a[i][4],a[i][4]=0;
				if(a[i][2]==a[i][3])a[i][2]*=2,a[i][3]=0;
			}else if(a[i][2]==a[i][3])ff|=a[i][2],a[i][2]*=2,a[i][3]=a[i][4],a[i][4]=0;
			else if(a[i][3]==a[i][4])ff|=a[i][3],a[i][3]*=2,a[i][4]=0;
	}else if(o==3){//R
		for(k=1;k<4;k++)for(i=1;i<=4;i++)for(j=1;j<4;j++)
			if(a[i][j]&&!a[i][j+1])swap(a[i][j],a[i][j+1]),ff=1;
		for(i=1;i<=4;i++)
			if(a[i][3]==a[i][4]){
				ff|=a[i][4],a[i][4]*=2,a[i][3]=a[i][2],a[i][2]=a[i][1],a[i][1]=0;
				if(a[i][2]==a[i][3])a[i][3]*=2,a[i][2]=0;
			}else if(a[i][2]==a[i][3])ff|=a[i][3],a[i][3]*=2,a[i][2]=a[i][1],a[i][1]=0;
			else if(a[i][1]==a[i][2])ff|=a[i][2],a[i][2]*=2,a[i][1]=0;
	}
	return ff;
}
void find(int X,int x){
	int w;
	if(x==11){
		int o=0;
		for(int i=1;i<=4;i++)
		for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)if(b[x][i][j])o++;
		//if(o<now||o==now&&max(max(b[x][1][1],b[x][1][4]),max(b[x][4][1],b[x][4][1]))<nn)now=o,XX=X,nn=max(max(b[x][1][1],b[x][1][4]),max(b[x][4][1],b[x][4][1])),memcpy(A,b[x],sizeof b[x]),memcpy(ST,st,sizeof st);
		if(GJ()<nn||GJ()==nn&&o<now)XX=X,now=o,nn=GJ(),memcpy(A,b[x],sizeof b[x]),memcpy(ST,st,sizeof st);
		return;
	}
	for(w=G(X);b[x][w/4+1][w%4+1];w=G(X));b[x][w/4+1][w%4+1]=2;
	for(int o=0;o<4;o++){
		memcpy(a,b[x],sizeof b[x]);
		if(mdf(o)){
			st[x]=o;
			memcpy(b[x+1],a,sizeof a);
			find(X,x+1);
		}
	}
}
int main(){
	//freopen("20482.out","w",stdout);
	puts("14");
	srand(time(0));
	scanf("%d",&X);
	for(w=G(X);a[w/4+1][w%4+1];w=G(X));a[w/4+1][w%4+1]=2;
	for(T=100000;T;T--){
		for(i=1;i<=4;i++,puts(""))
			for(j=1;j<=4;j++)if(a[i][j])printf("%5d",a[i][j]);else printf("    .");
		for(i=1;i<=4;i++)for(j=1;j<=4;j++)if(a[i][j]==32768){
			for(int k=1;k<=t;k++)if(!q[k])putchar('U');else if(q[k]==1)putchar('D');else if(q[k]==2)putchar('L');else if(q[k]==3)putchar('R');
			fclose(stdout);
			return 0;
		}
		for(i=1;i<=4;i++)for(j=1;j<=4;j++)b[1][i][j]=a[i][j];
		now=1e9;nn=1e9;
		find(X,1);X=XX;
		memcpy(a,A,sizeof A);
		for(i=1;i<=10;i++)q[++t]=ST[i];
		/*for(V=0,ff=0;!ff;){
			V++;U=(rand())%4;
			if(V>=100)break;
			ff=mdf(U);
		}
		if(V>=100)break;
		//printf("%d\n",U);
		q[++t]=U;*/
	}
	for(i=1;i<=4;i++,puts(""))
		for(j=1;j<=4;j++)if(a[i][j])printf("%5d",a[i][j]);else printf("    .");
	for(i=1;i<=t;i++)if(!q[i])putchar('U');else if(q[i]==1)putchar('D');else if(q[i]==2)putchar('L');else if(q[i]==3)putchar('R');

}

【UR #9】包子晚宴（85/100）

1（10）：送分点

2（10）：在一个2*2的方格上走，某些时刻某些点有子弹，一段时间不接触子弹获得一定奖励。f[i][j][k]表示在i时刻，位置在j，连续k时间没接触子弹的最大代价，就可以得到最优答案了。

3（10）：16行的数字三角形，走30步使得价值最大。发现最下面一行最好吃，肯定要尽量吃最多最后一行，就吃掉最后一行右边一半，并带走一个最大的倒数第二行的就得到最优解了。

4（8）：60行的数字三角形，从(i,j)到(i+1,j+1)和(i+1,j)都要17步，从(i,j)到(i,j+1)要16步。可以用DP得到最优解，不过不太好写。CHEAT了一下最后一行取两个能得到8分。

5（10）：走迷宫，在特定时刻走到特定的地方。不妨打印出迷宫，然后手玩就可以了，才700多步，还有指示的迷宫，10分钟左右就可以玩出来了。

6（8）：一个树形结构的迷宫，要求经过所有点，并在一个特定时刻经过一个点，并在最后时刻回来。由于迷宫要走4K多步，直接手玩的话估计得一个小时。由于迷宫是树形结构，可以找到最短路后剩下的都DFS一遍，然后可以背包得解了。不过还是不太好写。发现有两块比较大的，DFS一下加进去，能得到较优解，有8分。

7（10）：直接走到子弹发射点就可以得到全部的擦弹分数了。

8（8）：一群子弹乱飞，且速度一般来说比你大。用了个傻逼DP，f[T][i][j]表示在T时刻，坐标(i,j)能获得的最大价值，卡出了8分。

9（7）：子弹从一条线上射出，竖直速度相同且为整数，且速度比你快。可以在一条线上DP，f[T][i]表示在T时刻在w时刻获得的最大值，可以得到7分。

10（4）：一堆圆，要你从左边走到右边，再走回来。不能碰到圆。。太难了，直接CHEAT了4分。。

• 相关文章推荐
• 全局相关文章