WC 2016
ZJOI 2016 day 2

ZJOI 2016 Day 1

RXDoi posted @ 2016年3月20日 09:20 in 酱油记 , 339 阅读

[Upd 3.25] 滚粗不谈

[Upd 3.26~3.27] 写了下游记和简要题解。

Day 0:

前几天写了个国际象棋AI,暴搜5步估价,对付一些业余初级选手还是绰绰有余的。上午没事干,先去大战网上的AI,在调了好几次参之后打爆了高级电脑。然后拿去跟QQ游戏上面的人下,1胜2负。

打了下VK cup资格赛第二场,sb题写错了一发,D题扔给叶队然后弃疗了。

下午到了学军,住在浙外里面的某宾馆。感觉学军伙食还不错啊……?

晚上在lnj大爷的教育下打一个奇怪的塔防小隔膜。

Day 1:

洲哥的课只听懂了本来就会的部分。下午不知道在干嘛。晚上围观某高一小哥推gal。

Day 2:

早上听说讲量子计算机,去了发现讲整形浮点什么的,第一次下课的时候大爷们突然集体退场,我想了想也回宾馆了。回去写了道模板题,去吃饭的路上撞见老大,慌。

下午顺便也翘了。在宾馆睡了2个小时,然后继续打隔膜。试机感觉不错。回去随便看了看板子什么的,然后继续在lnj大爷指导下打那个小隔膜。打到11点终于通关了。

Day 3:

早上感觉精神很好,早饭吃得有点饱。到处被人立flag。

进考场,看了第一题感觉是个乱搞题,看了第二题第一眼以为是对偶图什么的,看了第三题发现是个数数题,心里一惊。

然后想了一会儿第二题感觉不会,开始搞第三题。

考场上智商下线,3^n*...的暴力都没想到……二三两题想了3个小时,啥都没搞出来,不知道在想什么。

第二题中途想到了分治,但是以为扭一下的情况不能做,就没再想下去。

3个小时的时候觉得滚粗了,准备写暴力,乱搞了下第一题,一开始只想拿个20分,没想到乱判了下准确率不错。但是我不会造4的数据,完全忘了prufer序列这种东西,就对着样例观察4的参数,乱搞了下。

后来样例错1个,把4000组当成了400组,心想极限数据错10个,稳得要死,就不管他了……噗……

然后写了下第三题的40分,第二题的20分,试图写第二题的50分,没写出来,就结束了。

出考场听说了敦爷灿爷耀峰叶队都A题了的消息,GT和Jabby感觉和我考得差不多。

然后得知了爆蛋的消息……GT第三题从说好的40分变成了90分,Jabby第一题实力78,只有我该爆蛋的都爆了。你们这群骗子……

然后就成为了学校第8……被3个初三小哥吊着打。

一出考场就觉得三道都是sb题了……考场上智商都去哪里了……

赛后觉得考场上随便搞哪道题都能搞出很多分啊……我怎么就一道都没搞出呢……

二试怎么这么早……要抓紧时间提高姿势水平啊……

 

简要题解:

T1:选直径、度数方差、度数为2的点数、度数排序后第450个值、∑每条边两边size的乘积……之类的乱七八糟搞搞,注意到每种树1000个,最高分jsb大爷的方法是对每种参数设个权值求和排序,每1000个分一段,实测这样比较靠谱,但是标程是直接判的……我判来判去效果还是很差……弃疗了。

T2:分治,从中间一行/列向所有点跑最短路来更新答案。每次割长边,复杂度T(n)=2T(n/2)+O(nsqrt(n)log(n)),T(n)=O(nsqrt(n)log(n)),UOJ上要卡卡常数。

T3:暴力的想法是枚举每棵子树对应的点集,然后子集卷积。O(3^nn^3)。注意到最后只要算全集那么一个点的值,会成为答案的一定是1的个数=size的那些东西,所以可以改成或卷积,用FWT做到O(2^nn^3)。常数方面,注意到FWT的transform对向量加法和点积具有分配率(?),可以中途一直用“点值”计算,但是这样常数还是有点大,可以小范围暴力子集卷积,大范围FWT。

标算:考虑给每个树上点一个1~n标号,标号可以重复,这样子算方案直接O(n^3)搞下就行了。考虑它实际映射到的点集,能算的东西是要算的东西的莫比乌斯变换。那么容斥一下就行了。O(2^nn^3)。


登录 *


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