• 周四. 6月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

NOI 2021

admin

11月 28, 2021

目前进度:d1t1,d1t2

D1T3 : 缩点以后会变成一颗树。暴力加边判断子树范围。

D2T1 : 把每个串砍成 16 段,一定有一段相同。。然后去暴力找,由于字典是随机的所以是对的。

D2T2 :

D2T3 :

首先每个操作序列可以看做 ( exttt{0R1RrevRsameR…}) ,也就是说被经过的非空格子会 一定变为 0 ,一定变为 1 ,取反,不变 四种状态。

由于对于有多个相同的开始位置 (p)((X,Y)) 需要只统计一次,考虑容斥。

统计有 (ge 1) 个位置 (p) 满足条件的个数 ,再减掉有 (ge 2) 个位置 (p) 满足条件的个数,再加上有 (ge 3) 个位置 (p) 满足条件的个数…

考虑 R 的个数小于 16 的情况。

此时考虑从头往后,一位一位的填 [每位是否作为开始的位 (p)] 的状态。

并且只需要状压前面的 16 位是否作为开始的位,再往前的影响不到了。

观察到如果 R 的个数 (ge 16) ,那这条纸要么全空着(不会爆炸),要么初始位置只能是前 16 位,状态数反而少了。

感觉会极其难写…

$$Huge ext{Goodbye OI}$$

发表评论

您的电子邮箱地址不会被公开。