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中都能找得到的最长子序列.

输入输出格式

输入格式:

第一行包括两个数字n和m,第二行是给定的字符串S.

感谢@mMmP 提供的翻译

输入输出样例

输入 #1复制

3 3 

aaa

输出 #1复制

6

输入 #2复制

3 3 

aab

输出 #2复制

11

输入 #3复制

1 2 

a

输出 #3复制

1

输入 #4复制

10 9 

abacadefgh

输出 #4复制

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的机智做法。

我们现在采取的策略是，用算重方案数减去重复的方案数。 我们考虑三个条件：

1、取出哪个字符

2、放在哪个位置

3、放置什么字符

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

然后我们考虑取出串中的一个字符，然后再把这个字符放入字符串中，这样显然会有大量重复，我们发现大部分的重复情况都是s[i]=s[i-1]这样，由相邻且相同的串组成的很多歌块，每个块中都是相同的字符，这样取出来再填进去，同一个块中的放置后情况完全一样。例如aaabaccc，按照相邻且相同来分块， aaa|b|a|ccc，一共四个块，例如要在第一个块中取出一个那么就变成了aa|b|a|ccc，然后再把a插入，可以发现在第一个块中取任意一个的放置情况都是一样的，所以可以把一个块中值拿出一个点来计算，这样就不会被相邻且相同的字符影响。然后我们考虑，取出的这些字符放置成什么字符。如上个例子，把取出的a放在b右边，可以变成aabaaccc，aabbaccc，aabcaccc……假如把a放在b的右边可以变成aabbaccc，aacbaccc……我们可以发现算多了一个，而这种情况会有n次，就是说从一个块中取出一个数再放到任意位置只能放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个，总和=（首项+末项） 项数/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