9.13集训

考试 第一题是个走迷宫

注意：判断有没有走过，别打tag标记，就用最简朴的vis数组来判断

坑点：开始为0与1

第二个是个类似选择数字的题目

\(f[i] = min(f[i], f[i - 1] + abs(a[j] - a[i]))\)

\(O(n^2)\)可做70分，但是用权值线段树可以优化到100分

第三个是一个字符串问题

裸字符串可以30分

考虑优化：树剖

用类似倍增的思想，跳过一些不必要的串，在查询的时候特判id到底是不是大于n

不大于n说明不需要拼接，大于n的话需要拼接，就一直跳while

第四个是个原题

同花顺

考虑排序方式：先按花色，花色相同的按照点数来排序，然后考虑每一张牌作为结尾需要更换多少张牌

显然一定这副牌有n张

for (i = 1; i <= cnt; ++ i)
{
   now = 0;
   for (j = 1; j < (int)v[i].size(); ++ j)
   {
      while(v[i][now] < v[i][j] - n + 1) ++ now;
      res = max(res, j - now + 1);
   }
}
cout << n - res;

然后通过上面的代码我们可以发现一个精妙绝伦地方：题目要求最小值，我们求出满足某张牌为结尾的，最多可以满足的牌数，让总数n减去这些最多可以满足的，剩下的就是最少需要更换的

其中now是左端点，j是右端点，j-now+1是区间长度

因为保证同花顺是递增的，所以\(while(v[i][now] < v[i][j] - n + 1) ++ now\)，now就是在找，最多可以到哪里，就是now之前的都不合题意，now之后的，j之前的，满足v[i][j]作为结尾的牌