#172. 【W(wǎng)C2016】論戰(zhàn)捆竹竿

這是一個美好的下午，小 W 和小 C 在竹林里切磋捆竹竿的技藝。

竹林里有無數(shù)根完全一樣的短竹子，每一根竹子由?nn?節(jié)組成。

這些竹子比較特別，每一節(jié)都被染上了顏色。可能的顏色一共?2626?種，分別用小寫英文字母?a?到?z?表示。也就是說，如果把竹子的底端到頂端的顏色按順序?qū)懗鰜砜梢耘懦梢粋€由小寫英文字母組成的字符串。

小 W 和小 C 都是捆竹竿的高手，他們知道怎樣才能把零散的短竹子捆成一整根長竹竿。初始時你拿著一根短竹子作為當(dāng)前的竹竿。每次你可以選擇一根短竹子，短竹子底端若干節(jié)（可以是?00?節(jié)）與竹竿的最上面若干節(jié)對應(yīng)地一節(jié)一節(jié)捆起來，而短竹子前面剩下的節(jié)伸出去，這樣就得到了一根更長的竹竿。注意，竹子的底端是靠近根部的那一端，不可以顛倒。

小 W 對竹竿的審美要求很高，他捆竹竿時有一個癖好：如果兩根竹子的某兩節(jié)被捆在了一起，那么它們的顏色必須相同。

我們假設(shè)一根短竹子從底端到頂端每節(jié)的顏色為?aba。

那么兩根竹子可以首尾捆在一起，可以得到一根顏色為?abaaba?的竹竿；也可以將第一根頂端的一節(jié)?a?與第二根底端的一節(jié)?a?捆在一起，得到一根顏色為?ababa?的竹竿；還可以直接將每一節(jié)都對應(yīng)起來，捆成一根顏色為?aba?的竹竿。

假設(shè)我們在顏色為?ababa?的竹竿頂端再捆一根竹子，則可以捆成?ababaaba，abababa?和?ababa?三種不同的情況。

但是小 C 在這個問題上有不同的看法，他認(rèn)為小 W 捆不出很多種長度不同的竹竿。小 W 非常不服，于是他找到了你——現(xiàn)在請你求出在竹竿長度不超過?ww?的情況下，小 W 可以捆出多少種長度不同的竹竿。其中，竹竿的長度指從底端到頂端的竹子的節(jié)的個數(shù)。

注意：如果?w<nw<n，則沒有合法的長度，此時答案為?00。

輸入格式

第一行包含?11?個正整數(shù)?TT，為數(shù)據(jù)組數(shù)。

每組數(shù)據(jù)的第一行包含?22?個正整數(shù)?nn?和?ww，表示短竹子的長度和竹竿的長度上限。

每組數(shù)據(jù)的第二行包含一個長度為?nn?的字符串，該字符串僅由小寫英文字母構(gòu)成，表示短竹子從底端到頂端每節(jié)的顏色。

輸出格式

輸出共?TT?行，每行包含一個整數(shù)表示捆成竹竿的不同長度種數(shù)。

樣例一

input

1 4 11 bbab

output

5

explanation

可以捆成長度不超過?1111?的竹竿有?66?種不同的情況:

bbab

bbabbab

bbabbbab

bbabbabbab

bbabbabbbab

bbabbbabbab

后兩種竹竿長度相同,因此不同長度的竹竿共有?55?種。長度分別為：4,7,8,10,114,7,8,10,11。

樣例二

input

2 44 1000 baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa 41 1000 abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

output

195 24

樣例三

見樣例數(shù)據(jù)下載。

限制與約定

對于所有的測試數(shù)據(jù),保證所有的字符串均由小寫字母構(gòu)成，保證?T=5T=5。

各測試點滿足以下約定：

測試點編號nnww約束

1	≤10≤10	≤10≤10	ss?僅包含字母?a?和?b
2	≤20≤20	≤20≤20
3	≤100≤100	≤1018≤1018	無
4
5	≤103≤103
6
7	≤5×104≤5×104	≤105≤105
8
9
10
11	≤7×104≤7×104	≤1018≤1018
12
13	≤105≤105
14
15
16
17	≤5×105≤5×105
18
19
20

時間限制：1s1s

空間限制：256MB

/*可能是因為string導(dǎo)致7~10爆了空間 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 500010 using namespace std; int n,w,nxt[maxn],ans; string s; bool vis[maxn]; void getnxt(){int i=0,j=-1;nxt[0]=-1;while(i!=n){if(s[i]==s[j]||j==-1)nxt[++i]=++j;else j=nxt[j];} } void dfs(string c,int len){if(!vis[len]&&len<=w)vis[len]=1,ans++;else return;int j=nxt[n];while(j){dfs(c+s.substr(j,n-j),len+(n-j));j=nxt[j];}dfs(c+s,len+n); } int main(){int T;scanf("%d",&T);while(T--){memset(vis,0,sizeof(vis));ans=0;scanf("%d%d",&n,&w);cin>>s;getnxt();dfs(s,n);printf("%d\n",ans);} } 10分 kmp暴力

?

#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; inline int read() {int t=1,sum=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9')sum=sum*10+ch-'0',ch=getchar();return t*sum; } const int Max=1e6+10; const LL inf=1e18; int nxt[Max],q[Max],Q[Max],len[Max],n,nm; LL f[Max],w[Max],W; char s[Max]; void get_nxt() {int i,j;for(nxt[1]=j=0,i=2;i<=n;i++){while(j&&s[j+1]!=s[i]) j=nxt[j];nxt[i]=s[j+1]==s[i]?++j:j;} } int gcd(int a,int b) {return !b?a:gcd(b,a%b); } void change(int x) {int d=gcd(x,nm),i,j,tot; static LL pre[Max];for(i=0;i<nm;i++) pre[i]=f[i];for(i=0;i<x;i++) f[i]=inf;for(i=0;i<nm;i++) if(pre[i]!=inf)j=pre[i]%x,f[j]=min(f[j],pre[i]);for(i=0;i<d;i++){tot=0; j=i;while(true){q[++tot]=j;j=(j+nm)%x;if(j==i) break;}for(j=1;j<=tot;j++) q[tot+j]=q[j];tot<<=1;for(j=2;j<=tot;j++) f[q[j]]=min(f[q[j]],f[q[j-1]]+nm);}nm=x; } void update(int a0,int d,int num) {int D=gcd(d,a0),i,j,k,tot,N,l,r; static LL w[Max],mi; change(a0);for(i=0;i<D;i++){tot=0; j=i;while(true){q[++tot]=j;j=(j+d)%a0;if(j==i) break;}for(mi=inf,j=1;j<=tot;j++) if(f[q[j]]<mi) mi=f[q[j]],k=j;if(mi==inf) continue;else N=0;for(j=k;j<=tot;j++) Q[++N]=q[j];for(j=1;j<k;j++) Q[++N]=q[j];q[1]=l=r=1; w[1]=f[Q[1]]-d;for(j=2;j<=N;j++){if(q[l]+num<=j) l++;if(l<=r) f[Q[j]]=min(f[Q[j]],w[l]+1LL*j*d+a0);while(l<=r&&w[r]>=f[Q[j]]-1LL*j*d) r--;q[++r]=j; w[r]=f[Q[j]]-1LL*j*d;}} } int main() {int T=read(),i,j,k; LL ans;while(T--){n=read(); scanf("%lld",&W); W-=n;scanf("%s",s+1); get_nxt();if(W<0){puts("0");continue;}for(j=0,i=nxt[n];i;i=nxt[i]) len[++j]=n-i;for(i=1;i<=(j>>1);i++) swap(len[i],len[j-i+1]);for(f[0]=0,i=1;i<n;i++) f[i]=inf;nm=n;for(i=1;i<=j;i=k){if(i==j) {update(len[i],1,1);break;}for(k=i+1;k<=j&&len[i]-len[i+1]==len[k-1]-len[k];k++);update(len[k-1],len[i]-len[i+1],k-i);}for(ans=i=0;i<nm;i++)if(f[i]!=inf&&f[i]<=W)ans+=(W-f[i])/nm+1;printf("%lld\n",ans);}return 0; } 100分 完全不明白

?

轉(zhuǎn)載于:https://www.cnblogs.com/thmyl/p/8098574.html

總結(jié)

以上是生活随笔為你收集整理的uoj #172. 【WC2016】论战捆竹竿的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。