【游记】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]\)覆盖的整数个数。