【游记】ZROI 21秋季noip10连 day8

比赛链接（正睿）

	T1	T2	T3	T4
得分	0	10	40	0
估分	0	10	40	10

本场比赛共有四道题，分别为《题》《目》《不》《难》，但实际上难度都很高。

开始比赛后先看的是T1。T1是一道期望$\text{dp}$题，题面很复杂，花了大约$20$分钟读懂了题意，发现暴力非常困难，于是跳过。

T2是给出若干约束，求满足的字符串数量。首先想到搜索枚举所有可能，迅速写出了暴力方法。之后开始朝乘法原理、容斥的方向想，但由于选取的方法受上一个选择方法的影响，没有推出来，后来看题解发现这个思路是错的，应该是子集状压$\text{dp}$。

T3是在一个无穷大的平面上，给定$n$个特殊点，最开始没有移动方式，路过这些点能以一定代价获取一些移动方式。以第一个特殊点为起点，求最后移动到$(0,0)$需要的最小代价。

写了一个玄学$\text{DFS}$。当记录前节点的所有的，逐个尝移动方法试。但这样会无限递归下去，于是根据数据范围估了一个边界，实际上是有几率被卡的。

T4是给定一个序列和一些操作，称一个序列河大当且仅当每次删除序列中所有与序列长度相等的数，最后可以将序列删完。问每次操作后还要修改几个数才能让序列合法。难点在于怎么计算最小修改个数。考试时我构造了一个优先队列的方法，不断取堆顶直到堆顶不等于长度，可惜假了。正确的结论是$n-[1,n]$中被所有$[i-cnt_i+1,i]$覆盖的整数个数。