Virtual NOIP II Day 1 总结
Sweetlemon
2018-10-31 15:12:27
### T1 String Master
这道题是最长公共子串问题的一个变形，允许修改$k$次。
严格$\text{O}(n^3)$的$\text{dp}$方法（学傻了的方法）：
设$f[i][j][k]$为`a`串从$i$开始，`b`串从$j$开始，且修改了$k$次后的最长公共子串长度。那么如果`a[i]==b[j]`，$f[i][j][k]=f[i+1][j+1][k]+1$；否则$f[i][j][k]=f[i+1][j+1][k-1]+1$。从后往前递推计算即可。
注意不要重复使用变量$k$。
请注意，`int f[305][305][305]`占空间约为$108\text{MB}$。
不严格$\text{O}(n^3)$的暴力法（`std`）：
枚举子串在`a`和`b`中开始的位置（即上述$i$和$j$），从这个位置开始，修改最多$k$次，计算得到的公共子串的长度，更新答案即可。
标准的$\text{O}(n^2)$方法：
在上面的暴力法中，我们实际多次匹配了两个字符是否相等，如当$i=1,j=1;i=2,j=2;i=3,j=3$时，我们都要比较$a[3]$和$b[3]$是否相等，这显然浪费了时间。
两个长度为$n$的字符串，他们的位置对应关系只有$\text{O}(n^2)$种。我们能否通过枚举位置对应关系来求解呢？
我们设字符串`a`在`b`的左边，且字符串`a`的第一个字符`a[0]`对应字符串`b`中的`b[i]`。在这种对应模式下，我们记$f[k]$表示两字符串重合部分的第`k`个字符是否相等，相等则为$0$，不相等则为$1$。于是问题转化为求$f$数组中最长的、和不超过$k$的一段。
可以对$f$数组求前缀和（当然不求也可以），枚举区间右端点，此时左端点是否可行是单调的，且随着右端点的右移，左端点不会左移。这是[尺取法](https://www.luogu.org/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie)的一种应用，尺取法在处理区间单调性的问题上比二分少一个$\log$。
算法基本过程如下：枚举字符串$a$和$b$的位置对应关系（即`a`在`b`的左边，且$a[0]$对应$b[i]$；或`b`在`a`的左边，且$b[0]$对应$a[i]$；见下图），计算$f$数组，求最长区间。
最后附上$\text{O}(n^2)$的代码，可以用来解决经典问题：最长公共子串。
```cpp
#include <cstdio>
#include <cctype>
#define MAXIOLOG 25
#define MAXN 5005
using namespace std;
int io_temp[MAXIOLOG];
char stra[MAXN];
char strb[MAXN];
int f[MAXN];
//Start at i/j, changed k times, max length
int max(int a,int b);
typedef int io_t;
io_t uread(void);
void uwrite(io_t x,char spliter='\n');
void uread_str(char *str);
int main(void){
int n,kkk; //kkk表示题面中的k
int ans=0;
n=uread(),kkk=uread();
uread_str(stra);
uread_str(strb);
int ubound=n-1;
for (int i=ubound;i>=0;i--){
//Common:[i,n-1](stra),[0,n-i-1](strb)
int al,ar,bl,br;
al=i,ar=n-1,bl=0,br=n-i-1;
for (int j=i,k=0;j<=ar;j++,k++)
f[k+1]=(stra[j]!=strb[k]);
//上面+1是因为，前缀和要用到0下标，因此下标要从1开始
f[0]=0;
for (int k=1;k<=br+1;k++)
f[k]+=f[k-1];
//j(l point),k(r point)
for (int j=0,k=1;k<=br+1;k++){
int target=f[k]-kkk;
while (f[j]<target)
j++;
ans=max(ans,k-j);
}
}
for (int i=1;i<=ubound;i++){
//Common:[0,n-i-1](stra),[i,n-1](strb)
int al,ar,bl,br;
al=0,ar=n-i-1,bl=i,br=n-1;
for (int j=0,k=i;j<=ar;j++,k++)
f[j+1]=(stra[j]!=strb[k]);
f[0]=0;
for (int j=1;j<=ar+1;j++)
f[j]+=f[j-1];
//j(l point),k(r point)
for (int j=0,k=1;k<=ar+1;k++){
int target=f[k]-kkk;
while (f[j]<target)
j++;
ans=max(ans,k-j);
}
}
uwrite(ans);
return 0;
}
inline int max(int a,int b){
return a>b?a:b;
}
io_t uread(void){
io_t ans=0;
int symbol=0;
char ch;
ch=getchar();
while (!isdigit(ch)){
if (ch=='-')
symbol=1;
ch=getchar();
}
while (isdigit(ch)){
ans=ans*10+(ch-'0');
ch=getchar();
}
return symbol?(-ans):(ans);
}
void uwrite(io_t x,char spliter){
if (!x){
putchar('0');
putchar(spliter);
return;
}
if (x<0){
putchar('-');
x=-x;
}
int len=0;
while (x){
io_temp[len++]=x%10;
x/=10;
}
while (len){
len--;
putchar(io_temp[len]+'0');
}
putchar(spliter);
}
void uread_str(char *str){
char ch;
ch=getchar();
while (!islower(ch))
ch=getchar();
while (islower(ch)){
(*str)=ch;
str++;
ch=getchar();
}
(*str)='\0';
}
```
### T2 Tourist Attractions
给定一张$n$个点的无向图，统计有多少条简单路径恰好经过了$4$个点。
$40$分：枚举路径的起点，直接$\text{dfs }4$层即可。$\text{O}(n^4)$。
$70$分：考虑路径$a \rightarrow b \rightarrow c \rightarrow d$，我们如果枚举中间的$b\rightarrow c$边，再计算出有多少组$a,d$满足条件（$a,b$连通，$c,d$连通，$a\neq d$），记录即可。
对于某一组$b,c$（有序对），有多少合法的路径呢？实际上，若设$b$的邻集为$B$，$c$的邻集为$C$，答案就是$\left(\left|B\right|-1\right) \left(\left|C\right|-1\right) - \left|B\cap C\right|$。
现在的问题就是，如何求出$\left|B\cap C\right|$呢？
我们采用的方法是，直接暴力枚举$b,c$，再枚举$x$，统计$\left|B\cap C\right|$，再计算答案即可。$\text{O}(n^3)$。
$100$分：上面的枚举方法效率略低，如何加速呢？
这里用到一个简单的技巧：`bitset`加速。`bitset::count()`可以返回`bitset`中$1$的个数，因此我们只需计算每个点邻集的`bitset`二进制表示，再用`bitset`求交和计算交集元素个数即可。$\text{O}(\frac{n^3}{64})$。
### T3 Walk
给定一张有$n$个点的有向图，点$i$的权值为$val_i$，若$val_i \& val_j = val_j$，则$i$向$j$连边。
另外再给定$m$条有向边，假设边权都是$1$，求$1$到每个点的最短路。
$40$分：暴力建图，再$\text{bfs}$求出最短路即可。
$60$分：玄学做法，复杂度不正确。
采用$\text{bfs}$，首先将源点加入队列。对队列中的每个元素$i$，枚举$val_i$的子集并松弛，再枚举$val_i$的出边松弛。如果某个元素是由枚举子集松弛而来的，就无需对它枚举子集松弛。
$70$分：暴力建图边数过多，且对每个$val_i$枚举子集复杂度无法接受。我们考虑增加辅助点（参见[车站分级](https://sweetlemon.blog.luogu.org/Note-day3)）。
我们添加辅助点$val$（共有$2^{20}$个），这些点中，由超集向子集连权值为$0$的边，由原图中点$i$向$val_i$连权值为$0$的边，由$val_i$向$i$连权值为$1$的边。如此重新建图后再$\text{bfs}$跑最短路即可。
$100$分：考虑上面建的图，$1111$向$111,11,1$等都连有边，整个图中边数很多。如何优化呢？
我们考虑由某个$val$向它二进制表示中去掉某一位的所有点连边，即$1111$向$111,1011,1101,1110$连边，这样也可以涵盖所有子集，且边数大大减少，解决了问题。
### 总结
这套题难度其实不是特别大，但是我在写题策略上出了一点问题。T3我没有及时写暴力，到最后对拍时才发现优化方法可能有误，把急急忙忙写出来的暴力交了上去，导致$\text{WA}$了本应得分的$2$个点。因此今后写题**一定要先写暴力**（尤其是对优化方法的正确性不确定的时候）！
另外，我的玄学优化程序的枚举子集部分写错了。枚举子集的代码应该这么写：
```cpp
for (int status=full_set;status;status=(status-1)&full_set){
//Do something
}
//Do something with the empty set
```