NOI Online2021第一场游记

0 准备

2021年3月27日，一个美妙的早上，我从我温暖的被子里滚了出来，走向了襄阳五中的大门，内心踌躇：这可能是我最后一次参加NOI Online了，但是不慌，因为此时学校俨然已经被封锁起来，变成了公务员考试的考场。我从旁边的宁静湖穿过，走了比平时多了大约一倍的路程直达我的竞赛场地——大成楼，有诗云：

大成楼里集大成，大成楼旁小成生，小小大大大小成，小小大大状元名

好不费力，我从一层的电梯起步坐到五层，然后从五层的楼梯爬到六层，这里就是我所在的机房了——只有我一个人的机房。

拿出钥匙，我将钥匙插进门锁中，前后倒腾了几下，门开了，里面散发出一股灰尘的味道，我知道，是我上周月考，没有进去，已经布满灰尘了。进门之后向右转，打开电闸，快到墙的时候，又及时来了一个急转弯，走到倒数第二排的电脑面前，放下书包，踱到窗旁，打开窗户，迎接这一天的新鲜空气。

电脑缓缓地开了，滴滴的声音和窗外公务员考试的广播声加大了比赛的真实感觉，让我身临其境，

时间一分一秒地过去，终于到了8：30这个时间，题目发下来了

1 提高组

T1 愤怒的小N

鸽

T2 积木小赛

这道题目开始看的时候没有思路，以为是动态规划，但是怎么找状态转移方程就是找不到。

下来之后，参考了别人的题解之后，这道题用hash最方便！

然而我没学

接下来来介绍一下哈希

Hash算法可以将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点，就是很难找到逆向规律。

Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。

Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。

——摘自《百度百科》

我们常见情况下我们可以使用一种简单的方法做哈希，就是对于一个数据，我们可以对它的某一位进行一个误差非常大的处理，然后使这个值与相距很近的数的差值非常大，以区分开，这样哈希也是比较好理解的

对于这道题目，n≤3005n\leq 3005，我们需要一个O(n3)O(n^3)以内的算法

观察字符串s，t，实际上就是：

对于所有的s的子序列，t的子串，求他们子序列和子串相同的个数

对于s的子序列，我们有2n−12^n-1种情况，但是对于t的子串，我们的情况就少了许多，所以我们从t开始下手

我们可以枚举一个t为i到ji到j的子串，然后查找s串是否具有相同的子序列，如果具有的话，就可以将这个子串变成一个数存进去，作为一个hash值

最后，运用C++中的函数unique统计一下不同元素的个数，就是本道题的答案了

PS：不同元素的个数=unique(a+1,a+1+n)-(a+1);

参考自：syksykCCC

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const int HASH=52717;
const long long M=2004090320050915;
int n;
char s[3005],t[3005];
long long hash[3005*3005],tot;
int main()
{
	cin>>n;
	scanf("%s%s",s+1,t+1);
	for(int i=1;i<=n;i++)
	{
		long long v=0;
		int p=1;
		for(int j=i;j<=n;j++)
		{
			while(p<=n&&s[p]!=t[j])
			p++;
			if(p>n)
			break;
			p++;
			v=(1LL*v*HASH+t[j]-'a'+1)%M;
			hash[++tot]=v;
		}
	}
	sort(hash+1,hash+tot+1);
	cout<<(long long)(unique(hash+1,hash+tot+1)-(hash+1))<<endl;
	return 0;
}/

T3 岛屿探险

鸽

2 停顿

提高组的考试考完了，我收拾了一下东西就去食堂吃饭了。由于公务员考试的原因，学生都放假了，食堂自然没有很多的菜品。去食堂的路上，来公务员考试的考生们都在坐在树荫下，坐在台阶上，自己复习自己的东西，还有一些人在食堂里学习，所有人都是如此努力，所有人都是那么精神，所有人都是充满激情。

鲁迅说过：“人类的悲欢并不相通。”我走进食堂，看见其他学科竞赛的同学们已经坐在那里了，我赶忙打了饭，然后坐了过去，讨论着月考的事情，你一言我一语地说着，我开始抱怨自己在月考中的生物，我只考了65分，但是对着答案我却不止，我错误地将考差的原因归咎于批卷老师了，后来我才想通，最主要是自己的问题，导致了总排名的落后。

吃完饭，我们回到了寝室，有几个人说要玩狼人杀，我就在看着，但是他们许久没玩，看着手表，已经来到了12：35分，他们快要静校了，我也赶紧回到了机房。机房还是那个味道，我一通熟练操作，拿起了电脑上的耳机放入耳朵，然后从我最喜欢的音乐《Luv Letter》开始播放起来，音乐忽然刺痛到我心灵的某个地方。却说不出来，又一曲《风吹过的街》，唤起了我内心中美好的回忆，却现在已然悄然逝去。

听着听着，看着看着电脑，打着打着模板，时间很快就到了14:30，是考入门组试题的时间了，我照例下载了试题，打开了试题。

3 入门组

T1 切蛋糕

这道题开始的时候一看，没有思路，阿这，这不是入门组的题目吗，我已经菜到这个程度了吗，我仔细一看，原来是找规律的题目，蛋糕最多切，不可能超过三下，但是怎么分类呢？我们可以看一下样例数据。

输入样例

1
2
3
4
5
6
7
6
0 0 8
0 5 3
9 9 0
6 2 4
1 7 4
5 8 5

输出样例

1
2
3
4
5
6
0
2
1
2
3
2

首先分析一个人的情况

从第一组数据，同时我们根据一个数据的特殊性质

30%的数据满足a=b=0a=b=0

也就是第一组数据，因为其他两个人是0，所以只有一个人，自然也就不需要切分蛋糕了，所以特殊判断一下，如果三个人中有两个人是0，就直接输出0

接下来我们来分析两个人的情况

从第二组和第三组数据，同时我们根据数据的另一个特殊性质

60%的数据满足a=0a=0

也就是说，只有两个人参与分蛋糕，这肯定好分啊，不就切一下就好了吗？

不不不，不要着急，这里还需要分为两种情况：

第一种情况：两个人的不同

如果两个人的不同的话，我们肯定不能只切一次，所以切两次就一定可以成功了，因为第二次我们可以把蛋糕切成任意比例的二分，所以当两个人的不同的话，就直接输出2

如果两个人的相同的话，那就更好办了，只用输出1

接下来我们来分析三个人的情况

根据三、四、五组数据，我们发现：

1.如果其中两个加起来等于第三个的话，我们就可以只用先切一下，再切一下，因为实际上就是将蛋糕二分之后，再分一次，这样的情况，我们可以直接输出2

2.如果其中两个相同的话，也只用切两次，第一次将蛋糕分成两个部分，第二次再切的时候，我们无论怎么切（除了重复切一个地方），总是可以在四块蛋糕中找到两份相同的蛋糕，然后另外的部分就可以随意控制大小了

3.最后，如果这个数据没有以上的所有性质的话，也就是说，我们切两次已经不能完成了（想一想，为什么），切完两次之后，再切一次，就可以把蛋糕分成任意的三比形式了

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int T;
int main()
{
	//freopen("cake.in","r",stdin);
	//freopen("cake.out","w",stdout);
	cin>>T;
	while(T--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(a==0&&b==0||b==0&&c==0||a==0&&c==0)
		cout<<0<<endl;
		else if(a==0)
		{
			if(b==c)
			cout<<1<<endl;
			else
			cout<<2<<endl;
		}
		else if(b==0)
		{
			if(a==c)
			cout<<1<<endl;
			else
			cout<<2<<endl; 
		}
		else if(c==0)
		{
			if(a==b)
			cout<<1<<endl;
			else
			cout<<2<<endl;
		}
		else if(a+b==c||a+c==b||b+c==a)
		{
			cout<<2<<endl;
		}
		else if(a==b||a==c||b==c)
		{
			cout<<2<<endl;
		}
		else
		{
			cout<<3<<endl;
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

T2 吃豆人

这道题目实际上跟T1很类似，也有一些找规律的问题和数据范围的查看

数据范围n≤1000n\leq 1000，我们可以想到O(n3)O(n^3)就可以解决这道题目了，因为电脑一秒钟可以计算大约10910^9的数量级

我们所要做的就是从两个点开始，他们所经过的路径权值最大和，我们经过试验可以发现，无论选取左上，左下，右上还是右下无论哪一个方向，只要在某一个矩形上，这个矩形永远就是那个矩形，这个矩形的权值也永远不会变，所以我们设置一个数cic_i，表示从第一行的第i个出发，所经过矩阵的权值和

如何计算cic_i呢，我们可以建立两个方向数组，dx，dy，分别储存方向，这个在二维的方向问题上非常好用，然后按照游戏的规则，设立边界，如果大于边界就反弹，也就是说，横坐标和纵坐标分别满足$x\in [0,n) ,,y\in [0,n)$,所以，我们遇到了边界，方向标志dir就加一，这样就可以做到反弹的效果了

将经过的每个点aija_{ij}加起来，这样就是c所对应矩形的权值和.

算出来矩形对应的权值和之后有什么作用呢，这样我们就可以枚举啦，枚举两个点所对应的矩阵，我们将他们的权值和加起来，再把他们重复的减去，这样就可以通过设立一个答案变量ansans来记录枚举的最大值。但是重复的怎么办呢？

我们通过尝试以及找规律，我们可以找到如下结果：

1.当j−ij-i为奇数的时候，,这个时候两个矩形不会有公共的交点，ans=ci+cjans=c_i+c_j

2.当j−ij-i为偶数的时候

（1）i=1且j=ni=1且j=n时,两个矩形是线，正好是对角线的交叉，公共交点在矩阵的中心，此时ans=ci+cj−an+12n+12ans=c_i+c_j-a_{\frac{n+1}{2}\frac{n+1}{2}}

(2)当且仅当i=1或j=ni=1或j=n时，一个矩形是线，另一个是矩形，这个时候ans=ci+cj−a1+j−i2i+j2−an−j−i2,n−i+j2+1ans=c_i+c_j-a_{1+\frac{j-i}{2}\frac{i+j}{2}}-a_{n-\frac{j-i}{2},n-\frac{i+j}{2}+1}

(3)i不等于1且j不等于1i不等于1且j不等于1时，是两个矩形，此时

ans=ci+cj−a1+j−i2i+j2−an−j−i2,n−i+j2+1−ai+j2,1+j−i2−an−i+j2+1,n−j−i2ans=c_i+c_j-a_{1+\frac{j-i}{2}\frac{i+j}{2}}-a_{n-\frac{j-i}{2},n-\frac{i+j}{2}+1}-a_{\frac{i+j}{2},1+\frac{j-i}{2}}-a_{n-\frac{i+j}{2}+1,n-\frac{j-i}{2}}

PS：以上参考自@水の殤璃

这样我们所有的情况都讨论完毕了

预处理一个c，然后枚举一下，时间复杂度O(n2)O(n^2)

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n;
int a[1005][1005];
int c[1005];
int dx[]={1,1,-1,-1},dy[]={-1,1,1,-1};
bool v[1005][1005];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	{
		c[1]+=a[i][i];
		c[n]+=a[i][n-i+1];
	}
	for(int i=2;i<n;i++)
	{
		int x=1,y=i;
		int dir=0,sum=0;
		bool flag=false;
		while(1)
		{
			if(x==1&&y==i&&flag)
			{
				c[i]=sum;
				break;
			}
			sum+=a[x][y];
			flag=true;
			if(x+dx[dir]<=0||x+dx[dir]>n||y+dy[dir]<=0||y+dy[dir]>n)
			dir++;
			x+=dx[dir],y+=dy[dir];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
			continue;
			int maxn=max(i,j),minn=min(i,j);
			if((maxn-minn)%2==1)
			ans=max(ans,c[i]+c[j]);
			else if(minn==1&&maxn==n)
			ans=max(ans,c[i]+c[j]-a[(i+j)>>1][(i+j)>>1]);
			else
			{
				int t=c[i]+c[j];
				t-=a[1+(maxn-minn)/2][(i+j)/2];
				t-=a[n-(maxn-minn)/2][n-(i+j)/2+1];
				if(minn==1||maxn==n)
				ans=max(ans,t);
				else
				{
					t-=a[(i+j)/2][1+(maxn-minn)/2];
					t-=a[n-(i+j)/2+1][n-(maxn-minn)/2];
					ans=max(ans,t);
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

T3 重力球

鸽

4 尾声

题目终于考完了，简直就是头脑风暴，大脑简直累死了，只会打暴力的我默默地留下了眼泪，看着一无所有的代码，看着一无所有的电脑，看着一无所有的月考成绩，一切似乎都变得昏暗起来。所以我学信息学竞赛的意义在哪里，为什么要学呢，如果不会的话，如果没有天赋的话，学它又有什么意义？

看着代码，看是倒计时走到零，我不禁想起了我的小学同学，是他将我带入了学习计算机的这一条道路，想起了我的小学计算机老师，这是我的计算机启蒙老师，她非常耐心，认为我也非常有天赋，也是她的教学给了我对于信息学的极大兴趣，一路上我参加了YNIT，北京海淀区的知识技能竞赛，北京海淀区的“世纪杯”竞赛，全国青少年计算机表演赛，均获得了很好的成绩。但是在这里，我的天赋似乎被压抑，所有的成绩在这里似乎变得不值一提，也许信息学竞赛和之前的竞赛完全不是一个难度吧，值得肯定的是，我这么去做了，我也努力去做了。

总是有人问我，“你为什么要学习信息学啊”，“为什么不学习其他的竞赛呢”，“信息学竞赛是不是只是玩电脑就可以了”，从广义上说，信息学竞赛对于有兴趣的人来说，的确是一种娱乐，而且使人沉迷其中，无法自拔，同时增长人的知识。为什么不学其他的竞赛啊，因为我喜欢信息学啊，喜欢是没有理由的。

“一旦选择了这条道路。就算哭着走，也要自己走下去。”没错，这次我要走到底。从小时候开始，我似乎都不是一个非常有毅力的人：学前班的时候，我跟着学前班兴趣班的围棋老师学习围棋，没学多久，我便展现出我的天赋，很快就考过了围棋十段，父母老师也觉得我很有天赋，于是准备继续学下去，但是我却在一次又一次与高手对决中，在老师的讲解非常难的情况下退缩了，以自己不想学结束了围棋的学习；又是小学一年级，我在小学报名了奥数兴趣班，我在一次“巨人杯”比赛中拿到了不错的成绩，于是就在某巨人学校的数学尖子班学习奥数，开始的时候父母跟着我学，每次也催促我完成作业，到后来，我就在和爷爷一起去巨人学校学习，没有父母的催促，我也渐渐怠惰了下来，每次去上兴趣班唯一的目的便是去吃楼下飘香的手抓饼——每次加很多鸡蛋，很多火腿肠。渐渐地，我和一位父亲的朋友的孩子渐行渐远，我们原本在一个尖子班，我进入时考试成绩比他高，但是最后我却没有留在尖子班。那天晚上，听着父母的谈话，“没有必要，这些什么数列都是高中的知识，现在学太早了”，在这样的话语中，我在四年级的时候结束了奥数的学习，那位尖子班的孩子通过自己在各个竞赛中的优异成绩进入了清华附中的，而我通过这三年的学习却一无所得。

这是我的问题吗，是的，在某种意义上，也不是我的问题，因为我那时候小，不懂事。但是从二年级开始，我的朋友带着我走的路——信息之路，我却坚持到了现在，既然往事历历已经年，已经快8年了，还在坚持，我又有什么理由放弃呢？

站在人生的交界处，面对越考越差的月考，面对一无所获的竞赛，却有了一个更加屡败屡战的我，这是我的幸运吗，通过NOI Online，也算是成长了一步啊。

公务员考试考完了，同学们从各自的家回到学校，学校又恢复了生机。我背起书包，收拾东西回到教室。路上，每个同学都洋溢着笑容，既然如此，何必每天愁眉苦脸呢？我抬了一下书包，拍拍身上的灰尘，加快了脚步，望向久违的明德楼，望向那个梦想中的远方。