先喷一句,没有大样例,差评。
再喷一句,数据水,好评。

预计 80′ ,实际 110′ 。

我真是个奇葩实际分比预计分高。。。

Day0-

省选前三天教练每天给我们推一道题,都是主席树应用(教练曰“线段树模板”)。
都是看了题解的思路才做出来的,自己想就找不到用主席树维护的地方。

不知道为什么这三天效率都挺高,这三天我 A 的题目估计有我平常一个星期的 A 题数。。。

然而还没来得及复习每个知识点,省选就来了。

Day1

预计 70′ ,实际 40′ 。

fish

我看到这题的时候就意识到我只能打暴力了。
计算几何?我对这块一片空白。
好吧,硬要说思路我大概想得到枚举线段,按斜率搞个什么数据结构?
然后真的不会,敲暴力滚粗。

预计 20′ ,实际 20′ 。

jojo

前缀和后缀相同?求 KMP 的 fail 数组嘛。
暴力求,一次加几个字符就求几次 fail, 全加起来就是答案。
可持久化?版本树像个 AC 自动机,但是没管这么多,无脑写了个可持久化数组。
因为是把每个字符暴力求的,只能过前 50′ 。
结果我后面 30′ tm TLE 了? $ O(n log(n)) $ 的时空复杂度跑 1e5 要 6 秒?

预计 50′ ,实际 20′ 。

polygon

什么鬼畜题啊,简化一波题意。
把线段看做一个区间,除 (x, x + 1) 外每个区间一定可以划分成两个子区间。
然后把每个区间看做一个点,相当于有了一个满二叉树。
然后旋转操作就相当于把一个点 blablabla 换一下位置。
旋转次数可以贪心,方案数不会,大概要 DP ?
然后想着就求旋转次数吧,看看数据范围。。。
沃日 90% 的数据都要求方案数?小 W 的心情得多差啊。。。
当时我还没打其他题,感觉比较亏,就先做前面的题了,结果最后都没打。

预计 0′ ,实际 0′ 。

Watering

下午直接去机房颓废,死神 vs 火影真好玩。
还有被 lyy 安利太阳系争夺战,画风清新,内容硬核。

Day2

emm, 我是来测数据湿度的。。。
结果真被我水过去了。。。

预计 10′ ,实际 70′ 。

所以说有想法就要实现 不然就没事干了 2333 。

tour

u = v 或者 s[u] = s[v] 且 u, v 相邻的时候 (u, v) 一定是可行的。
其他点对 (u, v) 可行当且仅当 s[u] = s[v] 且存在 u -> u2, v -> v2 且 (u2, v2) 可行。
DP ?有环。
然后就只能把一个点对看做一个点,对于新的点建图,如果从初始的可行点能跑到 (u, v) 则 (u, v) 可行。
点数 $ O(n^2) $ ,边数 $ O(m^2) $ ,复杂度 $ O(n^2 + m^2 + q) $ 。
然而第一档暴力 m 就有 1e4 , 纯随机数据开O2 本地测了一下跑 5s, 真棒。

预计 0′ ,实际 30′ 。

dance

好迷啊,看了看 n = 1 有 40′ ,就去想 n = 1 怎么做,
推了推就是个式子: $ ans_i = \sum_{j=0} C_L^{i+j k} W^{i+j k} $ 。
把每个 $ C_L^x W^x $ 算一遍,快速幂复杂度 $ O(L log(L)) $ ,
然而 L 有 1e8 。。。
线性都跑不过去吧这,但我实在没别的思路,就想试试线性。
做法就是预处理,预处理 L 以内的逆元和 $ W_i $ ,再线性求一排的组合数。
时空复杂度都是 $ O(L) $ , 开 O2 本地测试 17s, 就算不 TLE 都得 MLE 。

预计 0′ ,实际 30′ (考完后再放本地测可以水 40′ woc)。

看了看实际的 L 只有 1e7 到 2e7 左右,真棒。
至于空间,我还算有点脑子搞了波动态开空间,不然直接开 1e8 的数组肯定得炸。

sequence

b 是整数的话还能枚举枚举。分数?没救了感觉。
于是只打了 10′ 的整数 DP 。

预计 10′ ,实际 10′ 。

Watering

下午本来打算去黄兴街打游戏的,先去麦克唐纳德吃中饭,吃完后发现就已经 3 点多了没什么时间。
于是放弃了 xbox 又回到机房颓废,死神 vs 火影昨天已经玩熟练了,打起来比较轻松。

Day3+

省选完了,结果并不想想象的那样,即使运气眷顾了我还是 wei 的一批。
实力不够啊,说啥都是扯淡。

常规欠下的帐也该还了,滚回去学文化课啦,接受作业的洗礼。

分类: 竞赛

1 条评论

ld_liaomo · 2019年4月13日 下午8:10

道理我都懂,可是死神 vs 火影是真的颓。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: