提答练习

orz hhw posted @ 2015年12月08日 13:58 in 算法学习 with tags 做题记录 提交答案 , 3535 阅读

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)

题意:找一条最长路
1-2:数据很小,直接暴力即可
3:暴力4分
4:暴力6分
5:发现1~75构成一个联通块,但是76所在联通块更大,在这个联通块上暴力可以得到81的答案
6:发现1~256是一个联通块,257~512是另一个联通块,但是257~512的联通块稠密一些,选择257~512的联通块前向星暴力就可以了
7:发现是200个大小为5的完全图,完全图当中有一条链联通,那么按照分层图的方法一层一层走就可以了
8:暴力3分
9-10:是一颗树,直接暴力即可
实在没有办法看题解了。。剩下的分要用随机化构树的方法,随机尽量小的度数扩展,就可以拿到满分啦
【NOI2004】毕业生(90/100)
题意:给你一些图形,可以旋转,用一个最小的矩形把这些图形覆盖
先写个暴力,直接暴力地选一个使得当前代价最小的点扩展,而且只能向下扩展,就可以拿到68分。。
然后再随机放入顺序,取最优的,可以拿到81分
最后一个点有特殊性,是400个相同的图形,手玩就可以拿满

 

答案

暴力

暴力+随机化

1

36

36

10

36

10

2

81

81

10

81

10

3

36

46

8

36

10

4

252

266

9

266

9

5

2178

3168

7

2736

8

6

1600

2960

5

1600

10

7

10000

20130

5

19912

5

8

10000

19068

5

11000

9

9

10000

11400

8

10680

9

10

14400

186500

1

/

1

 

68

81

【NOI2005】小H的聚会(93/115)

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

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

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

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

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

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

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

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

测试点

标准答案

傻逼暴力

傻逼随机化

1

90

90

10

90

10

2

35047

35047

10

35047

10

3

462121

462121

10

462121

10

4

9949536

9949454

0

9949614

15

5

1992993

1992929

0

1993029

15

6

8773794

8773786

0

8773789

0

7

64034

非法

0

62634

6

8

570138

548470

4

566240

9

9

1021302

非法

0

1020081

9

10

1041394

非法

0

1040449

9

总分

 

34

93

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

【NOI2010】成长快乐(87/100)

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

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

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

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

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

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

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

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

NO.

标准答案

傻逼暴力

傻逼随机化(5S)

傻逼贪心(1次)

 

最佳

1

20

20

10

20

10

20

10

 

 

10

2

73

73

10

73

10

63

3

 

 

10

3

1073741823

1073741823

10

1073741823

10

536870911

5

 

 

10

4

25905712

超时

0

25169858

6

25905712

10

 

 

10

5

34258154

超时

0

362351

2

32479435

7

 

 

7

6

34189691

超时

0

323718

2

32340431

6

 

 

6

7

56452

超时

0

30982

5

53932

8

 

 

8

8

174773389722037

超时

0

110563840

4

174773389670330

7

 

 

7

9

16667039

超时

0

14628214

6

16667039

10

 

 

10

10

21848713

超时

0

1354698

3

21841546

9

 

 

9

总分

 

30

55

75

 

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

NO.

标准答案

暴力+傻逼贪心

傻逼随机化

最佳

1

32387.574718

32387.574718

10

32387.574718

10

10

2

39687.553857

39687.553857

10

39687.553857

10

10

3

44519.286202

19081.11988396

5

42386.33801641

9

10

4

30674.100812

9874.55992867

1

30041.82036444

8

8

5

36062.011601

6439.41875777

1

36062.01160145

10

10

6

1000000

122950

1

192812.5

1

10

7

1664000

193946.3125

1

297219.40775055

1

10

8

134170.9573121

134170.9573121

10

134170.9573121

10

10

9

134170.9573121

134170.9573121

10

134170.9573121

10

10

10

50349113.20665

9709779.089883

1

47918456.34218650

6

6

总分

 

50

75

94

然后发现智商太低了人类智慧题码了个暴力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分。。

  • 无匹配