训练日志捏

牛客第7场J题
果然DP还是弱项

题意：给定n，k，t三个整数，定义：一段区间的和能够被k整除这段区间产生一点价值。要求找出满足以下条件的数组共有多少个，个数对998244353取模。

1.长度为n
2.数组定义域是0到k-1
3.价值为t（也就是说有t个区间取模k为0）

考察：逆元，组合数，前缀和，数学，DP

思路：
根据题意，我们要找出的区间满足的性质为区间和取模于k为0常见套路是1.两个前缀和取模于k相等则此段区间的区间和取模于k为0。2.由于数组取值是0到k-1所以取前缀和模于k则可以唯一确定原数组。

这样就转变为，构造一个前缀和数组，如果相等的非零元素个数为x个，那么一定产生的价值就是组合数（2,x）原因可以参考上面的第一个常见套路所说的。

设DP[i][j][k]为[0,k-1]的前i个数构成了长度为j的序列产生了k点价值

那么转移方程其实就显而易见了
我们将i-1拓展到i，对应的构造出j+len长度数组，产生的贡献自然是dp[i-1][j][k]*组合数(2，len)

转移方程有了之后还要注意一点，就是0的情况需要特别注意，因为他不需要和别人配对自身就能判断出一个被k整除的区间。

最后还要注意，这题的转移方程需要剪枝，而且由于用到了大量的组合数，所以必须预处理出组合数。

#include 
#define int long long
using namespace std;
const int mod= 998244353;
int dp[70][70][70*70];//0到k-1的前i个数使用了j个，产生了k点贡献
int fac[200],c[200][200];
int fastpow(int n,int a)
{
    int res=1;
    while(n)
    {
        if(n&1)
            res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res%mod;
}
int C(int n,int m)
{
    if(n<m||n<0||m<0)
        return 0;
    return fac[n]%mod*fastpow(mod-2,fac[m])%mod*fastpow(mod-2,fac[n-m])%mod;
}
signed main()
{
    int n,k,t;
    cin>>n>>k>>t;
    fac[0]=1;
    for(int i=1;i<=65;i++)
        fac[i]=fac[i-1]*i%mod;
      dp[0][0][0] = 1;
    for(int i=0;i<=65;i++)
        for(int j=0;j<=65;j++)
            c[i][j]=C(i,j);
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int v=0;v<=t;v++)
            {
                if(!dp[i-1][j][v])
                    continue;
                for(int num=0;num+j<=n;num++)
                {
                    if(i==1)
                        dp[i][j+num][c[num+1][2]+v]=(dp[i][j+num][c[num+1][2]+v]+dp[i-1][j][v]*c[j+num][num])%mod;
                    else
                        dp[i][j+num][c[num][2]+v]=(dp[i][j+num][c[num][2]+v]+dp[i-1][j][v]*c[j+num][num])%mod;
                }
            }
        }
    }
    cout<<dp[k][n][t]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

力扣2370

一个序列DP

题意：给定一个只有小写字母的字符串s，定义完美串是相邻字母在字典序行差的绝对值小于等于k，请你求出s的最长完美子序列

思路：序列DP，定义DP[i][j]是以j为结尾的长度为i的最长完美子序列

那么每一次找到符合完美定义的DP[i-1][j]+1和DP[i][j]取最大值即可

再想想将其空间优化，优化到一维，利用滚动数组的思想即可。

#include 
using namespace std;
const int N = 1e5+100;
int maxx=0,k;//前i个字符里以j号字符为结尾的理想子序列长度
int dp[26];
int main()
{
    string s;
    cin>>s>>k;
    for(int i=0;i<(int)s.length();i++)
    {
        int c=s[i]-'a',maxx=0;
        for(int j=max(0,c-k);j<=min(25,c+k);j++)
             maxx=max(maxx,dp[j]);
        dp[c]=maxx+1;
    }
    for(int i=0;i<=25;i++)
        maxx=max(dp[i],maxx);
    cout<<maxx<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

但是二维DP的答案就绝对没用吗？
不是的，二维DP空间在限制内，时间和一维dp差不多，然而二维dp可以记录下题目中的答案字符串是什么。

关于SAM的DFS
emmmm，今天在做SAM的时候，想起之前做的求第k小子串。
想起之前是通过桶排序令节点形成拓扑序，然后从大到小遍历，实际上我们同样可以通过DFS来实现这种操作，每次都优先走“小边去DFS”即可。

不过值得一提的是，我觉得这种DFS适用性蛮小的，代码很容易就会变得很冗长。

#include
using namespace std;
#define int long long
const int N=5e5+100;
char s[N];
int n,m,t,kth;

struct SuffixAutoMaton
{
   // vectorright[N<<1];
    int tire[N<<1][26]/*如果确定了只有小写字母再用26吧,这tire树*/;
    int fail[N<<1],len[N<<1]/*fail数组，len和上方说的一样*/;
    int size[N<<1];/*在build函数的第五个for循环执行完之后得到的size[i]代表了节点i所代表的的right集合大小，也就可以说是节点i代表了几个子串*/
    int last,tot,k[N<<1],c[N<<1];/*用于在构建树的时候使用*/
    int vis[N<<1];
    int sum[N<<1];
    void init()
    {
        last=tot=1;memset(tire[1],0,sizeof tire[1]);//初始化没什么好说的吧，注意last和tot从1开始
    }
    void ins(int c,int pos)//传入当前插入的第i个字符，和i
    {
        int p=last;//上一个构建的节点是last，现在让p暂存last
        int np=++tot;//现在要构建的节点
        last=np;//更新last，你也可以把这一步放在后面
        len[np]=len[p]+1;//自然现在新构建的节点的最长长度是上一个节点的最长长度+1
        memset(tire[tot],0,sizeof tire[tot]);//初始化这一层的tire数
        for(;p&&!tire[p][c];p=fail[p])//构建tire树
            tire[p][c]=np;
        if(!p)//构建fail树的第一种情况，
            fail[np]=1;
        else//第二种
        {
            int q=tire[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else//第三种
            {
                int nq=++tot;//nq，我们在第三种情况下和第二种情况发生了本质的变化，我们再也不能通过现存节点来找到符合约定的fail节点，只能自己生成一个。第三种情况内部显然可以对nq的信息加以统计
                len[nq]=len[p]+1;
                memcpy(tire[nq],tire[q],sizeof(tire[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;tire[p][c]==q;p=fail[p])
                tire[p][c]=nq;
            }
        }
        size[np]=1;
      //  right[np].push_back(pos);//把right集求出
    }
    void DFS(int n)
    {
        if(vis[n])
            return ;
        vis[n]=1;
        for(int i=0;i<=25;i++)
        {
            if(tire[n][i])
            {
                DFS(tire[n][i]);
                sum[n]+=sum[tire[n][i]];
            }
        }
    }
    bool falg=false;
    string ans;
    void qry(int cnt,int x)
    {
        cnt--;
        if(falg)
            return;
        if(!cnt)
        {
            falg=1;
            return ;
        }
        for(int i=0;i<26;i++)
        {
            if(sum[tire[x][i]]>=cnt)
            {
                ans+=(char)('a'+i);
                qry(cnt,tire[x][i]);
            }
            else
            {
                cnt-=sum[tire[x][i]];
            }
        }
    }
    void build(int n)
    {
        init();
        for(int i=1;i<=n;i++) ins(s[i]-'a',i);//插入节点
        for(int i=1;i<=tot;i++) sum[i]=1;
        DFS(1);
        int m,cnt;
        cin>>m;
        while(m--)
        {
            ans="";
            falg=false;
            cin>>cnt;
            qry(cnt+1,1);
            cout<<ans<<endl;
        }
    }
}sam;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
 //   cin>>t>>kth;
    sam.build(n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

然后是一个PAM的训练题
P5555 秩序魔咒

求两个字符串的最长公共回文子串长度，并且要求你求出这个长度公共回文串个数。

思路：字符串问题回文串首先想到了PAM嘛，然后是最长如何考虑呢，对于一个字符串我们分奇偶长度记录有两棵回文树，分别可以从奇偶回文树的顶端下手，两个字符串同时进行回文树的DFS，直到两个字符串的回文树出现了差别则可以确定最长回文串。

又知道回文树每一个节点唯一确定一个回文串，那么可以顺手统计出个数。

/*求最长回文串的长度和这个长度的回文串的个数*/
#include
#include
#include
using namespace std;
const int N = 5e5+100;
int num,maxx;
struct PAM
{
    int len[N],n,num[N],fail[N],last,cur,pos,trie[N][26],tot=1;
    char s[N];
    void init()
    {
        cin>>(s+1);
    }
    int getfail(int x,int i)
    {
        while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])
            x=fail[x];
        return x;
    }
    void pam()
    {
        fail[0]=1;
        len[1]=-1;
        for(int i=1;i<=(int)strlen(s+1);i++)
        {
            pos=getfail(cur,i);
            if(!trie[pos][s[i]-'a'])
            {
                fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
                trie[pos][s[i]-'a']=tot;
                len[tot]=len[pos]+2;
                num[tot]=num[fail[tot]]+1;
            }
            cur=trie[pos][s[i]-'a'];
        }
    }
};
PAM p1,p2;
void DFS(int nl,int nr)
{
    if(maxx<p1.len[nl])
    {
        maxx=p1.len[nl];
        num=1;
    }
    else if(maxx==p1.len[nl])
        ++num;
    for(int i=0;i<26;++i)
    if(p1.trie[nl][i]&&p2.trie[nr][i])
    DFS(p1.trie[nl][i],p2.trie[nr][i]);
}
int main()
{
    int n1,n2;
    cin>>n1>>n2;
	p1.init();
	p2.init();
	p1.pam();
	p2.pam();
	DFS(1,1);
	DFS(0,0);
	cout<<maxx<<" "<<num<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

P1368 【模板】最小表示法

模板题捏，没啥好说的，只不过一般可能用不上这个模板。

对于一个字符串 abcd 我们如果环形的去看，最小表示就是abcd bcda cdab dabc中字典序最小的那个

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;
}
int n,ans,A[300009];
int Min_show()
{
    int i=0,j=1,k=0;
    //两个指针i,j,任意时刻i!=j,当前匹配长度为k
    //循环同构串要复制一遍字串(成环)接在A序列后面
    //由于数组过大,(i+k)%n和(j+k)%n代表了字串
    //复制一遍接在原序列后各字符的对应位置
    while(i<n&&j<n&&k<n)
          {
      	    if(A[(i+k)%n]==A[(j+k)%n])
      	    //两个位置数值相等，匹配长度k++
      	       k++;
      	    else
      	       {
      	   	    if(A[(i+k)%n]>A[(j+k)%n])
      	   	    //[i,i+k-1]与[j,j+k-1]相同
                     //那么在[i,i+k-1]中不可能有最小表示
			         //则i+=k+1,令k=0
      	   	        i+=k+1;
      	   	    else j+=k+1;
      	   	    //同上
      	   	    if(i==j)i++;
                     //任何时候都要满足i!=j
      	   	    k=0;//匹配长度k归零
		       }
	      }
    return min(i,j);//返回最小表示
}
int main()
{
    n=read();
    for(int i=0;i<n;i++)//初始字串
        A[i]=read();
    ans=Min_show();//求最小表示
    for(int i=0;i<n;i++)//输出最小表示
        printf("%d ",A[(i+ans)%n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

P5826 【模板】子序列自动机

就是，能够判断一个字符串是不是另一个字符串的子序列。

emmmm，咋感觉贪心即可捏。

#include
using namespace std;
const int maxn=100010;
int t,m,n,q;
vector<int> v[maxn];
int main()
{
	cin>>m>>n>>q>>t;
	for(int i=1,temp;i<=n;i++)
    {
        cin>>temp;
        v[temp].push_back(i);
    }
	while(q--)
    {
		int l,pos=0;
		cin>>l;
		bool flag=true;
		while(l--)
        {
			int x;
			cin>>x;
			if(!flag)
                continue;
			vector<int>::iterator it=lower_bound(v[x].begin(),v[x].end(),pos+1);
			if(it==v[x].end())
			     flag=false;
			else
			 pos=*it;
		}
		puts(flag?"Yes":"No");
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

emmmm，明天看完DLX之后再刷几天字符串就要看看SG函数了，下周要开点别的算法。