NOIP2021 – 赛前集训

10/25 – 21noip赛前20天 day8

T1构造题,T2线代,T3是树上问题,T4字符串。

选择先做T2,首先一眼有 $50$ 分的做法,直接暴力枚举三元组,放到一个矩阵里,求三阶行列式,若行列式不为 $0$,则三个向量是线性无关的。

后面又想到去把 $n$ 个向量都扔到一个矩阵里,每次枚举前两个,快速找到第三个,但并不会快速找到第三个的方法,只能是一些常数级别的优化。赛时发布通知,说 T1 为了防止被错误做法卡过去,把数据加强了。就去看 T1 了。

先自己手算了前 $20$ 的,发现方案不唯一,于是就都列出来,然后找有没有统一的构造方法。

先发现对于偶数 $x=2\cdot y$,可以递归到子问题 $y$,然后把每个数都 $\times 2$ ,一定合法。

然后就开始找奇数的规律。发现要想不和递归后的问题重复,就每次减去 $3$ 的最高次幂,然后再递归子问题。

不确定对不对,因为 $100$ 分要高精度,先写了个 $70$ 分数据范围的验证正确性。

构造题验证正确性要自己写 $\rm{checker}$,考场上写错了,调了半天 $\rm{checker}$,差点以为是自己解法错了。

时间也不是很多了,就没去写高精度,先去看了看后面的题。大概花了半个小时,得到了自己暴力都不会的结论。

最后还剩二十分钟去写高精度,没调出来。

估分 $70+50+0+0$,得分 $0+50+0+0$。

第一题输出格式错了,后面因为不舒服就没检查,改完上去就有 $70$ 分,加个高精就是 $100$ 分。

排名:$92/156$。

10/26 – 21noip赛前20天 day9

按题目编号顺序开题。

T1又是奇怪的结论题,手造数据试了试,猜了一个:$\operatorname{Ans}=\max($白色连通块个数,黑色连通块个数$)$.

试了好几组自己造的数据,都是对的,就交上去了,去看了 T2。耗时 $\rm{30min}$.

观察数据范围发现,因为取模的特殊性,打暴力都要写高精度,肯定是直接找到策略贪心地选。

思考一下发现,对于每个数而言,一定先做操作三,其次是连续的操作二,最后做操作一。想到这,就感觉快做出来了。

想到赋值操作只保留最大的那次,转化为加法操作。对一次加法操作,转化为乘上 $\frac{a}{b}$,然而并不知道连续的加法操作如何处理,就没继续往这个方向想了。

赛后才知道,距离正解只差一步了,因为加法一定是先加大的数,再加小的数,所以排序后,加上的是连续段。把每个加法操作转化为:作用在前一次加法操作后的数上的乘法操作即可。然后直接全局找最大的 $m$ 次乘法操作即可计算。

又想了一会还是不会(因为正确的方向已经被自己否定掉了),写了 $30$ 部分分,在 1h30min 的时候回到了T1。因为是猜的结论,想拿对拍验证一下,结果WA on Test #1.

看了一下,确实是个反例,而且直接随机数据就很容易出反例。开始重新想 T1。

模拟了一下过程,如果把连通块缩成一个点,构成的新树一定是:一层黑,一层白,一层黑,一层白这样交替下去的。然而还是不会,就在新树上找规律。

想在新树上DP,想了个状态+转移方程写出来了,对拍能找到反例。于是就循环在找反例、改DP上 1h 左右,最后终于找到一组反例,设定的状态完全无法解决。突然想到把上面两种错误做法合到一起,取最优解,交上去,赛后发现也可以获得 $70$ 分的高分。

但毕竟没有正确性,只能再重新想。在还剩30min的时候猜出:答案为缩点后的树的直径,写完之后拍不出来反例。感觉很神奇,就把前面的删掉,只保留了树的直径。

T3T4没时间了。

估分 $100+30+0+0$,得分 $100+35+0+0$.

T1对拍假做法花了太长时间,导致没看后面的题。不过T3T4没几个人拿到部分分。

所以在对拍出错解之后,应该先检查一下正确性再继续调代码,不然如果最后发现做法假了,就会浪费很多时间。

排名:$91/158$。

10/31 – 21秋季noip10连 day8

先看了T1。30min之后连样例都看不懂,还和期望有关,估计不会,就直接跳了。

T2,首先注意到数据范围中 $1\leq Q\leq 15$,想要容斥处理。手推了一下只会处理两个区间的交集,三个往上就不行了。先写了个10分暴力,1.5h的时候写完。

观察了一下榜,发现T4有不少提交,把T3和T4题意看完之后,先去尝试做了T4。对没有修改的情况,又是结论题。试了几组数据完全找不到规律,暴力也不知道每次该怎么修改,2h时去写C。

看完题感觉和数论相关,但我并不会快速判断能否到达源点,也想不到什么把状态转化的方法。对暴力的部分,想了一个分层图的做法,要分 $2^n$ 层,时间复杂度不是很好,估计也写不出来,就继续回去推T2了。

$\rm{sub2}$ 中 $1\leq Q\leq 8$。想到了一个方法是按区间端点离散化,枚举每段内模 $9$ 的余数,再判断是否合法,复杂度分析上是 $10^{2Q}\cdot \log Q$ 的,但如果在 DFS 的同时判断当前区间是否合法,并且区间端点有重合的话,也许有 $30$ 分。

3.5h时通过特别水的大样例。

再回来看T3,发现打暴力的 $40$ 分并不需要分层图,只需要在 DFS 时加一维:当前所学习到的移动方式即可,用二进制压缩的方式存到一个数里面。这样 DFS 状态数最多是 $(2|x_i|)^2\times 2^n=400\times 400\times 32=5120000$.

打标记的时候习惯性的加了个回溯,找了半天才发现不需要回溯。删掉之后在本地跑样例会爆栈,终端报 segmentation fault.

segmentation fault

这时候就剩五分钟了,静态查错也看不出来啥问题。突然想到可能是Mac的本地栈空间比较小,在OJ上交了一下,确实能正常运行样例。

最后两分钟发现 T3 无解的情况要输出 $-1$ 而不是最大值,补了个特判交上去。

估分:$0+(10\sim 30)+40+0$,得分 $0+10+50+0$.

T2有 subtask 绑定,$30$ 分的部分超时了一个点。T3没有 subtask 绑定,输出的 $-1$ 多拿到了 $10$ 分。

排名:$39/168$,大部分人总分都没上 $100$。

11/07 – 21秋季noip10连 day9

按顺序开题,第一题看懂之后就能有一些思路。

先想到的是预处理出 $f_{i, j}$,表示对于第 $i$ 种狗子,选其的任意一个子集,子集的智力和 $\bmod m$ 为 $j$ 的方案数。

对于前 $60\rm{pts}$ 的数据, $a_i\leq 10$,$f$ 可以用组合数直接算。1h左右想到这里。

之后,每种狗子只能选一种 $\bmod m$ 的取值,于是就变成分组背包。耗时1.5h,估分 $60$。

然后想满分做法,当 $a_i$ 增大时,复杂度瓶颈在预处理部分,想了好久不知道咋弄, 就去看 T2 了。

T2题面里说是字符串,读了一遍就知道,这题和字符串的算法没关系。

先手模了一下数据范围里的特殊性质,发现和奇偶性有关。大概是先倒着隔一个选一个,再正着也来一遍。

又想到在 $ai$ 和 $a{i+1}$ 之间的这段,一定是整体正或者负,所以就每段只留 $2$ 个数,写了个大一点的数据手模。

发现规律还是类似的,倒着的时候字符串内部为正序,正着的时候字符串内部为倒序。就直接模拟,线性复杂度,估分 $100$,还剩 1.5h。

去看了一遍T3,没什么思路,先跳到T4了。

看懂题之后 $n^2$ 的暴力很显然,有 $30$ 分。还有 $10$ 分的特殊性质,用前缀和优化一下就好了。估分 $40$,写完还剩1h.

T3还是不会,返回去看T1。往组合上面想,不可避免的要枚举子集大小,复杂度里直接带着 $10^9$。还剩 20min 的时候终于想到能利用周期性质的做法了。因为只需要考虑一个周期与前面已经处理好的连续周期之间的合并,每次转移的方法一定是相同的,考虑矩阵快速幂。

复杂度是 $\mathcal{O}(m^3\log_2 a_i)$,往里面带数值的时候把 $m, n$ 弄混了,导致 $20^3\rightarrow 100^3$,没看错也写不完了。

赛后证明这种矩阵快速幂做法可行,但不必要这么麻烦。存在只用矩阵快速幂、不用分组背包的做法,也有都不用的做法。

估分 $60+100+0+40$,得分 $60+100+0+40$,排名 $77/168$.

T1一大堆人过,赛时思路卡在一个方向上的时间太久了。

11/08 – 21noip赛前20天 day15

先读了每道题。做T1,拿到之后只想到 $\mathcal{O}(n^2m)$ 的暴力,空间复杂度也要 $\mathcal{O}(n^2)$,能拿到 $30$ 分。看完题+写完这部分花了1h.

继续想正解,题目最下面说:

附:需要用 __builtin_popcountll() 来计算 64 位整数的 popcount,而不是 __builtin_popcount()

等于 $64$ 的是 $m$,是操作的次数。想的过于复杂导致没做出来,过了30min去看T2。

T2,最大化每段平均值的最小值,想到二分答案。想如何 $\rm{check}$ 的过程中先想到了DP做法,就去往DP方向上想了。能找到好多种状态表示,与序列前 $i$ 位,已经分出 $j$ 段,最小的平均值为 $k$ 中的一些有关。

在 2h 的时候确定了一种时间复杂度为 $\mathcal{O}(n^2k)$,空间复杂度为 $\mathcal{O}(nk)$ 的 DP,$k\leq n\leq 500$ 可以过,$40$ 分。

继续看怎么优化这个DP,对着转移顺序看了一会,没发现可以用数据结构维护或者和可以利用的单调性。

再想二分答案的 $\rm{check}$ 过程,整体减掉 $x$,就等价于要把序列分成 $k$ 段,每段元素和 $\geq 0$。又想DP处理这个,不会。

还剩1h,去看了一眼 T3 和 T4,只有 T4 的暴力可做,有 $20$ 分,先没写,回去看 T1。

又发现 $n\leq 2\times 10^4$, 感觉题意就是可以 $\mathcal{O}(n^2)$ 加小常数通过。

想到对每个点对单独计算贡献,把每个点在 $m$ 次操作中处于的点集压到 unsigned long long 里面存。

具体地,$v_1[i]$ 拆成二进制位之后,$v_1[i][j]=1$ 当且仅当 $i$ 在第 $j$ 轮的时候处于点集 $x$,$v_2[i]$ 同理。

这样可以通过简单位运算得知,每个点对之间在哪些轮次时会被翻转,用题目给到的 __builtin_popcountll() 计算 popcount 即可。

调完还剩 15min,去写 T4 的暴力。写完只花了不到 $10$ 分钟,但过不了样例。

到最后也没看出来是因为 $i,j$ 写混,丢掉 $20$ 分。

估分 $100+40+0+0$,得分 $100+50+0+0$,排名 $101/147$.

11/10 – 21noip赛前20天 day17

T1 看上去和博弈论相关,两人在过程中都按照最优策略去选,暴力都没法打。

对着大样例模拟了一个多小时,发现对于每个环,只有两种情况。第一种是先手获得 $4$,后手获得 $a_i-4$;第二种是先手获得 $0$,后手获得 $a_i$,并交换先后手的顺序。

如果对每个点搜索所属情况复杂度是 $\mathcal{O}(2^n)$,能拿到 $60$ 分,可以接受。

但赛后发现这样是不正确的。

对于选取的顺序问题,在想到上面的两种情况之前,感觉上应当升序或者降序去取,模拟大样例的时候也是按照升序去做的。

写代码的时候没加 sort,发现也能通过大样例,于是就忽略了顺序问题。考试最后几分钟发现了这个问题,因为其实并没有想清楚排序有没有必要,就没有加上去。

由于数据点绑定 $\rm{subtask}$,$60\to 0$。

写完 T1 还剩 2h,去做 T2。

T2 看懂题面就去打暴力了,用并查集维护是否在同一个连通块内,每次判断需要合并的两点是否已经属于一个连通块。

写了一下,能过大样例也就没想太多,直接交上去了。

然而这样并不是正确的。在连通块中,是允许存在偶环的,只是不允许存在奇环。所以更准确的,应当判断合并后是否仍然是一张二分图,我暴力的方法是不正确的。

于是这题也 $0$ 分了。

去看 T3&4 还剩 1h。

想了半个小时的 T3,发现拿分都比较困难,就去写 T4 的暴力。

首先有 $10$ 分暴力直接枚举,后面还有个 $20$ 分的部分,感觉需要在线段树上操作,比较麻烦,想清楚的时候只剩 10 分钟了,也没去写。

赛后发现后面的 $20$ 分有不需要线段树的做法。时间复杂度虽然没有保障,但在随机数据下跑的很快,也可以拿到这 $20$ 分。

估分 $60+30+0+10$,得分 $0+0+0+10$。

在处理这种需要找性质的题的时候,没什么思路。经常是想到了差不多的地方,但是细节想不清楚,也证明不出。

多刷 CF 可能有用?

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();