1.【題目鏈接】https://www.luogu.com.cn/problem/CF578D

題目描述

You are given a string?S?of length?n?with each character being one of the first?m?lowercase English letters.

Calculate how many different strings?T?of length?n?composed from the first?m?lowercase English letters exist such that the length of LCS (longest common subsequence) between?S?and?T?is?n-1?.

Recall that LCS of two strings?S?and?T?is the longest string?C?such that?C?both in?S?and?T?as a subsequence.

輸入格式

The first line contains two numbers?nn?and?mm?denoting the length of string?SS?and number of first English lowercase characters forming the character set for strings (?1<=n<=100000?,?2<=m<=26?).

The second line contains string?S?.

輸出格式

Print the only line containing the answer.

題意翻譯

題目描述

給定一個長度為n,前m個字母都是小寫字母的字符串S. 試計算有多少個長度為n,前m個字母為小寫字母且與字符串S的LCS(最長上升子序列,Longest Common Subsequence)長度為n-1的字符串T 注:字符串S和T的LCS是指一個在S和T中都能找得到的最長子序列.

輸入輸出格式

輸入格式:

第一行包括兩個數(shù)字n和m,第二行是給定的字符串S.

感謝@mMmP 提供的翻譯

輸入輸出樣例

輸入 #1復(fù)制

3 3?

aaa

輸出 #1復(fù)制

6

輸入 #2復(fù)制

3 3?

aab

輸出 #2復(fù)制

11

輸入 #3復(fù)制

1 2?

a

輸出 #3復(fù)制

1

輸入 #4復(fù)制

10 9?

abacadefgh

輸出 #4復(fù)制

789

說明/提示

For the first sample, the?66?possible strings?TT?are: aab, aac, aba, aca, baa, caa.

For the second sample, the?1111?possible strings?TT?are: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab.

For the third sample, the only possible string?TT?is b.

2.思路

題解給了一個不用DP的機智做法。

我們現(xiàn)在采取的策略是，用算重方案數(shù)減去重復(fù)的方案數(shù)。 我們考慮三個條件：

1、取出哪個字符

2、放在哪個位置

3、放置什么字符

首先，很容易知道每個字符在原位置上就有m-1種方案，那么初始方案就有n*(m-1)種。

然后我們考慮取出串中的一個字符，然后再把這個字符放入字符串中，這樣顯然會有大量重復(fù)，我們發(fā)現(xiàn)大部分的重復(fù)情況都是s[i]=s[i-1]這樣，由相鄰且相同的串組成的很多歌塊，每個塊中都是相同的字符，這樣取出來再填進去，同一個塊中的放置后情況完全一樣。例如aaabaccc，按照相鄰且相同來分塊， aaa|b|a|ccc，一共四個塊，例如要在第一個塊中取出一個那么就變成了aa|b|a|ccc，然后再把a插入，可以發(fā)現(xiàn)在第一個塊中取任意一個的放置情況都是一樣的，所以可以把一個塊中值拿出一個點來計算，這樣就不會被相鄰且相同的字符影響。然后我們考慮，取出的這些字符放置成什么字符。如上個例子，把取出的a放在b右邊，可以變成aabaaccc，aabbaccc，aabcaccc……假如把a放在b的右邊可以變成aabbaccc，aacbaccc……我們可以發(fā)現(xiàn)算多了一個，而這種情況會有n次，就是說從一個塊中取出一個數(shù)再放到任意位置只能放m-1種字符。

scanf("%d%d",&n,&m);scanf("%s",s+1);
? ?ans=n*(m-1);
? ?fo(i,2,n)if(s[i]!=s[i-1])ans+=n*(m-1);

然而還會算重?。。。?！

比如說abababab這樣的字符串，例如把第3個a放到后面變成abbaabab，但是把第4個b放到前面也可以變成abbaabab，這樣也會算重。這種字符串中每個字符會與前面任意一個字符算重一次，所以答案還要減去k*(k-1)/2（k是字符串的大小，因為第一個字符前面有0個字符，第二個字符前面有1個……第k個字符前面有k-1個，總和=（首項+末項）?項數(shù)/2=（0+k-1）?k/2=k *（k-1）/2

k=1;
? ?fo(i,2,n){
? ? ? ?if(k==1){if(s[i]!=s[i-1])k++;else continue;}
? ? ? ?else{
? ? ? ? ? ?if(s[i]==s[i-2])k++;
? ? ? ? ? ?else{
? ? ? ? ? ? ? ?ans-=(k-1)*k/2;k=1;
? ? ? ? ? ? ? ?if(s[i]!=s[i-1])k=2;
? ? ? ? ? ?} ? ??
? ? ? ?}
? ?}
? ?ans-=(k-1)*k/2;

3.Code

//Happynewyear 2019/1/23 20:22
#include<bits/stdc++.h> ? ? ? ? //萬能頭文件
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100007;
int i,j,l,t,n,m;
long long ans,k;
char s[maxn];
int main(){
? ?scanf("%d%d",&n,&m);scanf("%s",s+1); ? //輸入
? ?ans=n*(m-1);
? ?fo(i,2,n)if(s[i]!=s[i-1])ans+=n*(m-1);k=1;
? ?fo(i,2,n){
? ? ? ?if(k==1){if(s[i]!=s[i-1])k++;else continue;}
? ? ? ?else{
? ? ? ? ? ?if(s[i]==s[i-2])k++;
? ? ? ? ? ?else{
? ? ? ? ? ? ? ?ans-=(k-1)*k/2;k=1;
? ? ? ? ? ? ? ?if(s[i]!=s[i-1])k=2;
? ? ? ? ? ?} ? ?
? ? ? ?}
? ?}
? ?ans-=(k-1)*k/2;
? ?printf("%lld\n",ans); ? //輸出
}

提交記錄 in 2019-10-10