Day -1

参加了热身赛。

热身赛

T1

第一题叫你猜东北大学几月份建的，实际上在参赛手册上，但是显然我们没看，很抽象，猜 1212 个月，猜了十次才过。好在可做，勉强算签到题。

T2 L. Random Permutation

第二题是说，生成一个序列，每个数字在 ii 位置上生成的概率是 1n\frac{1}{n} 问你期望他大于多少个排列。

显然的，我们考虑 f(x)f(x) 为只放进了前 xx 的数的排列方案数，有

f(x)=x∗f(x−1)∗n−x+1nf(x)=x*f(x-1)*\frac{n-x+1}{n}

换句话说 f(x)=n!∗n!nnf(x)=\frac{n!*n!}{n^n}

T3 B. The Great Wall

第三题才有意思，告诉你一个长度为 nn 的序列，希望你找到将这个序列分成 nn 个区间后最大值减去最小值的和的最大值

我们不妨令 fi,j,1/2/3f_{i,j,{1/2/3}} 表示前 ii 个数中已经分出来 jj 个区间，并且现在找到新的区间的 (最小值，什么都没找到，最大值) 的答案。

fi,j,2=max⁡(fi−1,j−1,2,fi−1,j,2,fi−1,j−1,3−ai,fi−1,j−1,1+ai)f_{i,j,2}=\max(f_{i-1,j-1,2},f_{i-1,j,2,f_{i-1,j-1,3}-a_i,f_{i-1,j-1,1}+a_i})

fi,j,3=max⁡(fi−1,j,3,fi−1,j−1,2+ai)f_{i,j,3}=\max(f_{i-1,j,3},f_{i-1,j-1,2}+a_i)

fi,j,1=max⁡(fi−1,j,1,fi−1,j−1,2−ai)f_{i,j,1}=\max(f_{i-1,j,1},f_{i-1,j-1,2}-a_i)

特别的，我们需要维护 fi,0,1/2/3f_{i,0,1/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
#include<bits/stdc++.h>

using namespace std;

const int maxn=10010;

int f[2][maxn][5];
int a[maxn],n;

int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	memset(f,-0x3f,sizeof(f));
	f[1][0][1]=-a[1];
	f[1][0][3]=a[1];
	f[1][1][2]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=i;j++) f[i&1][j][1]=f[i&1][j][2]=f[i&1][j][3]=-0x3f3f3f3f;
		f[i&1][0][1]=max(f[(i-1)&1][0][1],-a[i]);
		f[i&1][0][3]=max(f[(i-1)&1][0][3],a[i]);
		f[i&1][i][2]=0;
		for(int j=1;j<i;j++)
		{
			f[i&1][j][2]=max(max(f[(i-1)&1][j-1][1]+a[i],max(f[(i-1)&1][j-1][2],f[(i-1)&1][j][2])),f[(i-1)&1][j-1][3]-a[i]);
			f[i&1][j][1]=max(f[(i-1)&1][j][1],f[(i-1)&1][j][2]-a[i]);
			f[i&1][j][3]=max(f[(i-1)&1][j][3],f[(i-1)&1][j][2]+a[i]);
		}
	}
	for(int i=1;i<=n;i++) cout<<f[n&1][i][2]<<endl;
	return 0;
}

T4 A Bite of Teyvat

出得很好，下次不要再出了

Day 0

早上好。

中午好

美好的早上从中午开始，十点起床是我对比赛的恩赐，但是起得早并没有改善我的精神。

神仙 October 告诉我别演他，于是自己不敢乱口胡了。

拿到题了，神仙说第一题和最后一题中有一个很可能是签到题，发现不怎么能签到，然后看看榜。我超有人十五秒就过题了？然后秒了 D

然后开始 bfs\text{bfs} 式看题，不会就遍历下一题，感觉 GG 很可做，就是找俩直径然后用个数据结构维护？然后看到了 CC ,猜了个很假的结论是 l,rl,r 有一个一定是 aia_i 跑暴力就可以了，然后龙巨也卡题了，回来看 CC

“我有一个很假的做法。”我说

神说：“那你再想想。”

然后用一个很诡异的图论方法证明了这个正确性。过了 CC

组内一致认为 FF 可做，然而我没有思路，于是看了下 GG ,又看了看自己的离线版博客，发现有题和这个很像，感觉是真的？但是这题没 ACAC 所以也没开。

然后龙巨去开了 LL ，得益于他的优秀阅读能力，写了个一个代码过了。

全组开 FF ,然后看题顺序也从 $\text{bfs} $ 变成了随机。

最后四十分钟我突然想到了一个构造，构造出上下两排没法相互影响的，这样在 n=3n=3 中得到的是

111000111\begin{matrix} 1& 1& 1\\0&0&0\\1&1&1 \end{matrix}

但是 nn 更大就没法推广了，然后过了二十分钟龙巨推导出 n=4n=4 的做法

1111000011111111\begin{matrix} 1& 1& 1&1\\0&0&0&0\\1&1&1&1\\1&1&1&1 \end{matrix}

然后猜想是不是让某些行全填 00 某些行全 11 就可以了，打了个表，发现确实可以这么弄，而且和答案做法很像。

可惜最后也没调过来，充满遗憾，好在前三题过得快，混了个铜尾巴。

后记

看到自己两年前写的博客

$ de~Brujin $环:有2n2^n个长度为n的二进制字符串，有方法使得以循环顺序防止2n2^n个二进制数字使得其中2n2^n个连续数字的字符串彼此不同（这里咕一下）

感慨万千，这不就是这次没人 A\text{A} 的 B\text{B} 考的吗，现在的自己还远远不如高中的自己，也许自己有高中的一半实力，沈阳也能混个银不成？

区域赛铜似乎确实没什么用，但是有总比没有好，萌新发现任重而道远，同时也不得不把自己走过的路再走一遍，也许四年的 ACM\text{ACM} 会一场空，我也不敢说我会不会中途放弃。希望自己能坚持下去吧。

冲动消费买了个 GPW2\text{GPW2} ，果然游戏才是最快乐的。