Reverse and Compare
Time limit : 2sec / Memory limit : 256MB
Score : 500 points
Problem Statement
You have a string A=A1A2…An consisting of lowercase English letters.
You can choose any two indices i and j such that 1≤i≤j≤n and reverse substring AiAi+1…Aj.
You can perform this operation at most once.
How many different strings can you obtain?
Constraints
- 1≤|A|≤200,000
- A consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
A
Output
Print the number of different strings you can obtain by reversing any substring in A at most once.
Sample Input 1
Copy
aatt
Sample Output 1
Copy
5
You can obtain aatt (don’t do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).
Sample Input 2
Copy
xxxxxxxxxx
Sample Output 2
Copy
1
Whatever substring you reverse, you’ll always get xxxxxxxxxx.
Sample Input 3
Copy
abracadabra
Sample Output 3
Copy
44//很简单的一道DP，但是难想到，想到极其简单
dp[i]为前 i 个数的不同串数的话,dp[i] = dp[i-1] + sum[ str[j]!=str[i] ] (1<=j<i) (前面不等于字符 i 的所有字符的个数)
因为，只要不同，就能reverse[j,i]出一个新串，相同时，reverse[j+1,i-1]是和前相同的，算过了
此题，容易想到回文串什么的，回文串就是个坑，根本不对，跳进去就很难出来了
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define LL long long
#define MX 200500 LL dp[MX];
LL num[];
char s[MX]; int main()
{
scanf("%s",s+);
int len = strlen(s+);
dp[]=;
for (int i=;i<=len;i++)
{
dp[i]=dp[i-];
for (int j=;j<;j++)
{
if (s[i]=='a'+j) continue;
dp[i] += num[j];
}
num[ s[i]-'a' ]++;
}
printf("%lld\n",dp[len]);
return ;
}
