題目傳送

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format:
%lld

題目描述

有一款自走棋有26種操作,每種操作我們都用a,b,c,d,…,x,y,z的符號來代替.
現在牛牛有一個長度為nnn的操作序列,他現在可以從里面拿出某些操作來組合成一個操作視頻,
比如說操作序列是abcdabcdabcd,那么操作視頻就有a,b,c,d,ab,ac,ad等(也就是操作序列的子序列).他現在想知道長度為k且本質不同的操作視頻有多少種.
比如對于abab，長度為2且本質不同的結果有ab,aa,ba,bb 考慮到答案可能非常大,你只需要輸出在模1e9+7意義下的答案就可以了.

輸入描述:

第一行兩個整數n,k 第二行一個長度為n的字符串,保證只存在小寫字母.

輸出描述:

一行一個整數表示長度為k且本質不同的操作視頻的個數.

示例1
輸入

3 1 abc

輸出

3

備注:

1≤n≤1e3
0≤k≤n
題意：
給你一個長度為n的字符串，問有多有長度為k的子字符串，且不重復。
題解：
這種求子字符串數量題一般都用dp來做
dp[i][j]表示q前i個字符串中，長度為j的子字符串的數量
但是這個題是存在重復情況的，我們還要進行去重
這咋整？我們將dp從二維增加到三維，dp[i][j][k]新填一個k，k表示以什么字母結尾，（因為我們可以將a~z轉換成數字，a對應0，b對應1，一次類推），在dp添加時我們if判斷，如果當前結尾不是我們指定的字母，就不添加當前這位；如果是的話，就在前面的基礎在最后一位填上這個字母。
不明白？很正常（笑哭），我也快把自己講暈了
這個k就相當于是針對性的，dp[i][j][k]就是前i個字符串中選j個以k為結尾的字符數量
舉例大法：n=4 m=2
abab

你會發現鏈接對于abab，長度為2且本質不同的結果有ab,aa,ba,bb，雖然abab的子字符串中ab出現兩次，但是只統計了一次，因為在算以b（最后這個b）為結尾的時候，前面兩個a算作一個a處理
代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=1004; int dp[maxn][maxn][30]; char a[maxn]; const int mod=1e9+7; long long sum=0; int main() {int n,m;cin>>n>>m;char ch=getchar();cin>>a;if(m==0){cout<<1;return 0;}for(int i=1;i<=n;i++){dp[i][1][a[i-1]-'a']=1;for(int j=1;j<=m;j++){for(int w=0;w<=25;w++){if(a[i-1]-'a'==w){for(int k=0;k<=25;k++){dp[i][j][w]=(dp[i][j][w]+dp[i-1][j-1][k])%mod;}}else dp[i][j][w]=(dp[i][j][w]+dp[i-1][j][w])%mod;}}}for(int i=0;i<=25;i++)sum=(sum+dp[n][m][i])%mod;cout<<sum; }

**注意注意：**不要忘了MOD
據說還能優化，等學會了再更新

啦啦啦我又回來了

上面這個解法復雜度是O(26n²)
我們這次把26給省掉變成O（n²）
設兩個數組
g[i]：在前i個字符長度為j的本質不同的子序列個數
f[i][j]:前i個字符長度為j的本質不同的子序列個數
f[i][j]=f[i-1][j-1]+f[i-1][j]
f[i-1][j-1]就是不選擇s[i]
f[i-1][j]就是選擇s[i]
選擇的s[i]加上后有可能會重復，就需要我們先判斷當前的s[i]是否用過，然后把重復的部分去掉
f [ i ] [ j ] =f[ i ] [ j ]-f[ g [ s [ i ] ] - 1 ] [ j - 1 ]
還有在加的過程中注意不斷的mod

#include <bits/stdc++.h> using namespace std; #define LL long long const int mod=1e9+7;char s[100005]; LL f[1005][1005], g[30]={0}; int main() {int n, k;scanf("%d%d", &n, &k);scanf("%s", s+1);for(int i=1; i<=n; i++){f[i-1][0]=1;for(int j=1; j<=i; j++){f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;if(g[s[i]]){f[i][j]-=f[g[s[i]]-1][j-1];}f[i][j]=(f[i][j]+mod)%mod;}g[s[i]]=i;}f[n][0]=1;cout<<f[n][k]%mod<<endl;return 0; }

總結

以上是生活随笔為你收集整理的操作集锦【牛客网】 牛客练习赛60的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。