51Nod B 小明与回转寿司V2

传送门

题目

小明来到一家新开的日料店品尝回转寿司。
料理师傅共准备了26种不同的寿司，记为a~z。每次他都会选出每种寿司各一枚，按照一定顺序（如mildreabcfghjknopqstuvwxyz）放到传送带上，记为一轮。之后每轮，师傅都会按照同样的顺序将寿司放上传送带。
由于店内客人较多，寿司到达小明面前时已经所剩无几。小明记录了一段时间内经过自己面前的每一枚寿司的种类，现在他想知道，这期间至少有多少轮寿司经过了自己面前？

题解

比较摆烂，随便写写。
状压， 一开始每个字符单独一轮，考虑dp长度为20的那个字符串，加入第一个字母，假如是a，那么所有出现的a都可以把它后面的那个字母并入自己，同理，每加入一个字符，这个字符每次出现的位置，如果它后面的字符在原始字符串中也在它后面，那就并入；
预处理一个数组，\(pre_{a,b}\)表示a和b相邻，且a在b前面出现的次数。

这题大有可以研究的地方，诸如复用，无效信息等等，很神奇的是答案之和pre数组有关。
今日摆烂，下次一定

实现

#include 
#include 
#include 
using namespace std;

int read(){
    int num=0, flag=1; char c=getchar();
    while(!isdigit(c) && c!='-') c=getchar();
    if(c == '-') c=getchar(), flag=-1;
    while(isdigit(c)) num=num*10+c-'0', c=getchar();
    return num*flag;
}


const int N = 1e5+100;
const int Z = 2e6;
const int M = 21;
const int S = 26;
int vis[S], tab[S],cnt=0, s[N], n, pre[M][M];
vector zt[M];
int f[Z];

void reads(){
    char c=getchar();
    while(c>='a' && c<='z') s[++n] = c-'a', c=getchar();
}

void dfs(int lzt, int x, int num){
    if(x >= cnt){
        zt[num].push_back(lzt);
        return ;
    }
    dfs(lzt, x+1, num);
    dfs(lzt+(1<