3
21
2016
4

ZJOI2016 酱油记

这个坑先开好

因为我太懒了前几天都没有写

DAY0:

早上各路神犇各种开开开,我比较弱所以就和lnj一起口胡主席树。最后两个不会主席树的人会了主席树,可喜可贺可喜可贺。

中午去买了一大坨烧烤土豆和小当家,感觉可以吃4天实际上2天就吃完了

学军宣传册不是去年的不开心,看不到东方cos了。

晚上吃鸡颓人生记

DAY1:

上午洲爷讲课,一开始感觉很可听的样子,然后就作了很多笔记,大概9:30开始杜教筛,我发现这个东西我好像会的,然后就开始掉线睡觉。睡到10:30发现重连不回来了...人弱有什么办法

胖子烧饼还是原来的味道

下午去得迟了,然后就只能陪初三爷和JPY坐在二楼。

刚开始看到讲动态规划基础的时候然后等课件弄下来看了一下果断决定掉线。

围观JPY下午缘之空TKK。

5:30在宾馆里发现自己笔记本包不见了...

我:我记得很清楚,我上楼梯的时候拿着包的!!!所以一定在房间里

lnj:我劝你不要相信自己的记忆

好吧lnj说对了,回到学军找到包,完成任务,RP++

晚上吃鸡推人生记

DAY2:

上午不知道是谁讲什么奇怪的数据类型的东西,各路神犇表示这些东西太傻了,早会了,所以果断回宾馆。

我虽然不会看了一下课件发现里面一个汉字都没有决定紧跟神犇的脚步。

回来路上问lnj才发现这个东西只有我不会...

上午炼哥好像拉肚子了(好像是我一不小心开空调的缘故),然后我就推人生记。

中午另外一家烧饼店,感觉没有胖子烧饼好吃。

下午问各路神犇要不要去,大半都不去,本着队友不动我不动的原则,果断人生记。

后来听说讲的是分块以及量子计算机,还好没有去

晚上吃鸡+人生记所以说我推了5/3天人生记

9:10和JPY还有炼哥去吃麻辣烫。JPY发现自己带的钱不够然后就请了他3块钱

然而萎比JPY并没有能吃完13块的麻辣烫。

然后继续人生记,本来想10:30睡得,结果一不小心0:00了_(:зゝ∠)_

DAY3:

早饭没有前两天的小笼,吃得不是很爽。

考场外互奶。

初三大爷一号:只要不出现不可理喻的低级失误,R爷绝不会爆蛋

R爷:找阿

初三大爷一号:就算R爷3小时AK,也要坐满5小时

R爷:你找阿

进考场发现今年没有压缩包大吃一惊(我记得去年有不知道是不是我记错了)

先看题面。

T1感觉是个乱搞题,好像很可做

T2感觉是个裸题,但我不会做

T3感觉是个不可做题

淦怎么突然8:40了我TM什么都没干啊。

回去搞T1,感觉是什么期望度数,然后方差弄一弄。

写好试一下样例错了一半。

回去改了一下改成不开方的。

写好试一下样例错了三分之二。弃疗。

写T2暴力,这已经不知道我第几次算floyd复杂度少算1个0了。最后出场的时候我都还没发现。

然后东看看西看看,卵都没看出来。

9:40还是个0分选手。

然后开始看数据范围。看T1数据范围不明所以,看T2数据范围感觉是若干个Log或者若干个根号

看T3数据范围。诶好像是指数级别的。诶好像可以状压啊。诶好像可以树形DP啊。然后写的时候超级爽,键盘打得超响。

打完随便调了一下就过了样例,然后开始写O(n!*n^2)的暴力对拍,写的时候还是超爽,然后键盘打得超响。

写好对拍一拍就拍起来了,超爽。然后去上了个厕所。

回来想了一下发现我复杂度不会算。然后试了一下17,136的数据,等了10s没出来。。。我的内心是崩溃的。

然后试了一下14,还好秒出,然后试16,大概要3s,17链的大概要4s左右。

然后走上了卡常的不归路。

改之前

 

for(int I=Head[j];I;I=E[I].next){
	int V=E[I].to;
	for(int K=1;K<=s[size[root]][0];K++){
		int b=s[size[root]][K];
		if(a&b==0)dp[root][V][a^b]+=dp[v][j][a]*dp[root][V][b];
	}
}

改之后

for(int I=Head[j];I;I=E[I].next){
	int V=E[I].to;
	if(s[size[root]][0]<s[size[root]+size[v]][0]){
		for(int K=1;K<=s[size[root]][0];K++){
			int b=s[size[root]][K];
			if(dp[root][V][b])if((a&b)==0)dp[root][V][a^b]+=dp[v][j][a]*dp[root][V][b];
		}
	}else{
		for(int K=1;K<=s[size[v]+size[root]][0];K++){
			int b=s[size[v]+size[root]][K];
			if(dp[root][V][b^a])if((a&b)==a)dp[root][V][b]+=dp[v][j][a]*dp[root][V][a^b];
		}
	}
}

然后成功把16卡到1.2秒,17链卡到1.4秒。

然后还试了各种各样的优化,比如说假如对应的那个点度数小于这个点直接剪枝(并没有什么卵用主要是考虑到出题人的毒瘤心理一定会把m设得很大)、直接枚举一个n-size[v]的二进制数然后再O(n)把它和a并起来就可以减少K的枚举(成功从1.2秒变成2.6秒)

然后我就绝望了。

然后我开始东看看西看看。

发现所有都开O2的,然后开O2试了一下。

16、120的数据0.6秒,17、136链的数据0.75秒。感觉人生又有了希望。

然后开始弃疗,各种乱搞第一题还是卵都没搞出来,T2感觉是平面图然而我不会平面图。

出考场发现T3有大样例我没注意_(:зゝ∠)_不过拍了2个小时应该没事吧

T2O(1000*1000*1000)暴力感觉要挂_(:зゝ∠)_

下午orz各路神犇上台领奖RP++

其他的那啥那啥还有那啥:

1、身份证和饭卡都不知道是忘在考场还是食堂了到处丢东西_(:зゝ∠)_

2、本来以为饭票能换钱的,我想多了_(:зゝ∠)_

3、回来之后发现上次什么优秀学生事迹已经被挂在外面了,但是因为我比较弱所以我没有,orz RXD LNJ FF AKY XYP WYX

4、T1不知道为什么拿了18分_(:зゝ∠)_T380还是稳的,T2floyd炸成0分论作死的技巧_(:зゝ∠)_

5、后来据说T3M不是满的,MDZZ

6、叶队:前15绍一9个,为什么绍一不开一个分校

Category: 游记 | Tags: 游记 | Read Count: 8138
Avatar_small
hzq84621 说:
2016年3月25日 07:23

@rxd: orz进队大爷

Avatar_small
繁星 说:
2016年3月29日 09:28

跪跪跪话说为什么我又被黑了...


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com