NOIP2021游记

Farewell

Day 0

中午去拿快递不果。有点生气。下午才得知系统错误,然后我手机号错了一位??错的还刚好是后四位,无语了。

但手办还是到了,开心。

对文化课没有热情的我不想晚修,于是在就去了机房。

第一次看到wxc的冬冷夏热的小窝,想到他的“卧薪尝胆”,有点好笑,也有点感慨。

六点半到,看到机房都没几个人,在的也不知道在干什么。

聊了会天打开电脑配置了一下网络什么的已经七点了。

如计划的,打开了csp的题。

点开了感觉思路非常简单的“回文”。一顿操作之后终于过了样例。交上去竟发现CE。原来是luogu炸了。。

这时候已经过了45分钟。

然后点开了括号序列。

知道要分类。但感觉越做越乱。原地踏步了好久好久,真的在机房挠头挠了两个多小时(要分清怎么尽量少的分类然后不重真的太难了,对于我来说),终于才过了这题。。

还是贴贴代码吧,应该是比较简洁的实现。

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int n,k;
typedef long long ll;
const int N = 602;
char s[N];
int is[N][N],wh[N],xs[N];
ll a[N][N],b[N][N],as[N][N];
inline bool pd(int l,int r)
{
	return l>r||is[l][r];
}
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)wh[i]=wh[i-1]+(s[i]=='?'),xs[i]=xs[i-1]+(s[i]=='*');
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)if(wh[j]-wh[i-1]+xs[j]-xs[i-1]==j-i+1&&j-i+1<=k)
			is[i][j] = 1;
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)if(pd(k+1,j))as[i][j]=(as[i][j]+(a[i][k]+b[i][k]))%mod;
			if((s[i]!='('&&s[i]!='?')||(s[j]!=')'&&s[j]!='?'))continue;
			a[i][j]=(pd(i+1,j-1)+b[i+1][j-1]+a[i+1][j-1])%mod;
			for(int k=i+1;k<j-1;k++)if(pd(i+1,k))
				a[i][j]=(a[i][j]+b[k+1][j-1]+a[k+1][j-1])%mod;
			for(int k=j-1;k>i+1;k--)if(pd(k,j-1))
				a[i][j]=(a[i][j]+b[i+1][k-1]+a[i+1][k-1])%mod;
			for(int k=i;k<j;k++)
				b[i][j]=(b[i][j]+(b[i][k]+a[i][k])*a[k+1][j])%mod;
			for(int l=i+2;l<=j;l++)
					b[i][j]=(b[i][j]+(as[i][l-1])*a[l][j])%mod;
//			printf("%d %d %lld %lld %lld\n",i,j,a[i][j],b[i][j],as[i][j]);
		}	
	}	
	ll ans = (a[1][n]+b[1][n])%mod;
	printf("%lld\n",ans);
}
/*
6 2
(?)(?)

*/

这时候10点,我欢呼雀跃,感觉过年了,(比双休还开心!)

然后随便打开了一场ARC的A,叫make ten。

分别给\(n_2,n_3,n_4\)根长度为2、3、4的棍子,问最多能拼成多少根10。。

简单分析,就这?3只能两个一起用,肯定要334先,然后剩下的和2就可以了嘛!

然后过了样例交上去却一个点也过不了。。。叫来cp援助。

虽然他没怎么看题,但他说诶,你这个连把2转成4都没有,肯定错的。

什么垃圾思路。刚想证明给他看并不需要(实际也确实不需要)那样做,然后发现错了。。

发现只考虑了442,少考虑了多了一个4,然后222的情况。

交上去还是错。。心态爆炸,调到快40分,最终滚了。

在回宿舍的路上和宿舍脑海里一直想自己的思路有没有问题,想了好久好久,上床还在想,最终只能得出结论,肯定是我打错了。

Day 1

6:20就起床了。(发现昨天订的闹钟订到下午6:30了,笑死了。。。)

高三上一次这么早起还是上一次这么早起的时候。

走向饭堂的路还挺暗的,晚秋的太阳睡得也比我多。

太困了就想着买点咖啡,第一次喝瓶装的星巴克(果不其然不喜欢)。

6:50就提前到了集合的地方。不出我所料的大把人迟到,cmb还生气了。

但还是顺利的非常早到达了广大附。

在车上不知道干什么,拿手机盯昨天的代码。。!!终于找到了,原来是\(n_3/2*2\)写成了\(n_3\)。大屑。。

然后就是听歌。。。

先是符合情境的Farewell Song,然后是最近很喜欢听的未来へ,充满活力的Daisy。。。。

到啦!困死了。。

相互鼓励了一下就进场了。今年8点就能进场了,只不过还是不能动鼠标键盘,进去坐牢。

密码是IronHeart。

进场随便看了看,感觉1、2、3都很模板(指题目较短,而且感觉是见过的东西),4就像题目所说:是个缝合怪,有点长,看着也没这么简单。

t1越看越蠢,直接15分钟切了。

t2是个计数题。看到那个\(n\)这么小就知道是那个压位的套路,但是可能因为脑抽还想了很久其他做法(比如将相邻的合并上去,然后背包什么的,然后发现计不了每个数分别取多少个。。)然后发现直接跑dp就能做,45分钟也切了。。。

t3我一看就知道那种变换就是对数组变换一下就会变的很简单。就是差分数组调换嘛。。。

然后推了一个小时方差与差分数组的关系。

只记得推出来个这个玩意:

\[ans = \sum_i i(n-i)\Delta^2_i+\sum_i i\Delta_i\sum_{j>i} (n-j)\Delta_j \]

(可能不等号那里有错)

考场觉得一点用都没有。只能看出来小的放中间(这个我早就看出来了。。)

(就在我写这段文字的时候,突然发现事实上按着上面这个式子\(dp\)一下不就好了,我在干什么。。。真是个÷生啊。。。

复杂度\(O(n^2a_i)\),也是非常合理,考场就只觉得\(n\)的范围很奇怪,。。。太菜了)

然后打了个运气暴力,随便排排,然后\(O(n^3)\)枚举哪两个交换会变得更优就换。。

然后改了很多都过不了第四个样例,就算了。。

做了好久t3,放弃的时候可能已经12点了。

看了t4,发现部分分满地,最后只来得及打个\(nmq\)。。嘛差不多了都。。

估分\(100+100+50+24=274\)。

出去发现dby和我基本一样。。还和csp300分的厉害的高一学弟讨论了一下t3,发现他很强。

政和川好像摆烂了,我也不知道。。

cdr只会做前2。

在车上感觉人都要散架了,累死了,看看时间也不早了,决定咕掉语文考试,直接回家。

本来还想和cdr出去吃个饭的,然后我爸到得太早了。。

Day 2

就是你现在看到的这样。

从四年前2017的a*b-a-b。

到两年前2019的Emiya家今天的饭。

到现在2021的看了Emiya家今天的饭。

从OIer到一个破看动画的。

NOIP2021游记

NOIP2021游记

NOIP2021游记

这段时间听的很多很多很多的春之逝

その日々は夢のように
那些时光就像是一场梦

上一篇:vue中html导出到word


下一篇:NOIP2021游记