10月做题记录

✩ trick
✯ 会大部分，要\(tj\)提示
✬ 会小部分/完全没想到，看了\(tj\)才会
◈ 脑电波
✡ 有某一算法的神秘通用性质
⊗ 待补

• 10月做题记录
  • CF2018F Speedbreaker Counting ✬✩

CF2018F Speedbreaker Counting ✬✩

非常牛题目，就是学\(whk\)学傻了，乘法过后的取模写掉了，调了两个多小时/ll

首先，这道题是CF2019D Speedbreaker的进化版（？），那么CF2019D Speedbreaker的策略应该有用吧？诶，实际上没用，太邪恶了出题人！

如果你CF2019D Speedbreaker就用了这道题要用的那个很牛的性质当我没说（

这道题要用一个很重要的性质，设区间\(I=[\max i-a_i+1,\min i+a_i-1]\)，那么对于序列\(\{a_i\}\)，要么能作为起始城市的集合就是\(I\)，要么就没有可以作为起始城市的城市

还有一个很重要的策略，对于当前走到的区间\([l,r]\)，那么下一步要往右走当且仅当右边存在一个点\(i\)，使得\(i-l+1=a_i\)，否则就往左边走

可以发现，每个\(\{a_i\}\)对应了唯一一种走法

用这个策略证明该性质：

设\(I=[l,r]\)，假设从\([t,t]\)开始（\(t\in[l,r]\)），因为有\(l=\max i-a_i+1\)，所以可能向右走的第一步一定是一直向左走到达\(l\)之后，假设在\(p\)处向右走，那么现在的区间为\([p,t]\)，那么向右走到的点如果还在\([l,r]\)中，可以继续归类为\([p,t]\)，那么现在向右走的点\(q>r\)，现在有区间\([p,q]\)，显然之后的步骤都一样了，且对于中途，如果有一个\(t\)不能合法的走了，那么所有的\(t\)都无法合法的走，那么得证

下面排除\(I\)中都不合法的情况，即\(I\)就是\(\{a_i\}\)的起始城市的集合

来考虑能不能求出\(I=[l,r]\)的\(\{a_i\}\)，直接求等于肯定不太好弄，变为求\([l,r]\in I\)的\(\{a_i\}\)，枚举出\(l\)和\(r\)，考虑\(dp[i][j][0/1]\)，表示\([i,j]\)区间中的方案数，其中\(0\)表示下一步不强制向右走，\(1\)表示强制向右走，那么如果从\([i+1,j]\)转移到\([i,j]\)，\(a_i\geq\max(i-l+1,r-i+1,j-i+1)\)，从\([i,j-1]\)转移到\([i,j]\)同理有\(a_j\geq\max(j-l+1,r-j+1,j-i+1)\)，如果向右走停在\(j\)，那么\(a_j=j-i+1\)

这样得到\(O(N^4)\)的解法

明显有很大的优化空间，考虑优化成\(O(N^3)\)的

发现其实\(l\)和\(r\)的具体值不重要，只需要知道它们的相对大小以及\(i\)和\(j\)和它们的相对大小即可

那么现在来处理一个\(2n\)的\(dp\)数组，固定\(r=n\)，枚举\(l\)，然后\(dp\)，显然取对应的\(dp[i][j][0/1]\)即可得到答案

感觉这个算个\(trick\)，似乎没咋见过，但是好像又见过，如见（

再来考虑\(O(N^2)\)的做法

我们直接以\(r\)为起始城市来算答案，发现有这样的性质：

• \(i\in[l,\lceil\frac{l+r}2\rceil-1]\)，\(a_i\geq r-i+1\)
• \(i\in[\lceil\frac{l+r}2\rceil,r]\)，\(a_i\geq i-l+1\)
• \(i\in[1,l)\)，\(a_i\geq j-i+1\)
• \(j\in(r,n]\)，\(a_j\geq j-i+1\)

且可以知道，从\(r\)会一直走到\(l\)，此时才可能会向右走，那么整个过程可以分为两个部分，\(r\rightarrow l\)和之后的步骤

那么\(r\rightarrow l\)间的方案是简单的

考虑之后的步骤，发现与\(l\)和\(r\)无关，于是直接用\(dp[i][j][0/1]\)来算，然后倒着从\(dp[1][n][0]=1\)开始倒着\(dp\)即可

那么对于从\(r\)走到\(l\)后会向右走的\(\{a_i\}\)，向右走的第一步就确保了\(l\)的取值就是\(l\)，而对于\(r\)走到\(l\)后不向右走的，说明确保\(l\)取到\(l\)的只存在\([l,r]\)内，且可知只能是\([\lceil\frac{l+r}2\rceil,r]\)来确保的，那么分别算出对应的\(a_{[l,r]}\)的方案数，乘上\(dp[l][r][0]/dp[l][r][1]\)即可，记\([l,r]\)的方案数为\(g[l][r]\)

但是可以发现我们只确保了\(l\)，没确保\(r\)，也就意味着，\(g[l][r]\)记录的实际是\([l,\geq r]\)，那么只需要在记录答案的时候变成\(ans[r-l+1]+=g[l][r]-g[l][r+1]\)即可

https://codeforces.com/contest/2018/submission/283997789

似乎还看到了\(O(N)\)的做法，有时间再去学一下

感觉这道题咋越写越像\(dp\)用一堆\(trick\)来优化的题（