传送门
A: Colorful Subsequence
•题意
给一个长为n的小写字母序列，从中选出字母组成子序列
问最多能组成多少种每个字母都不相同的子序列
(不同位置的相同字母也算是不同的一种)
•思路
对于每种字母有选与不选两种情况，
①如果选的话,j假设这种字母有xi种，那就有xi种选法
②如果不选的话，有不选这一种方法
那总和起来就有(xi+1)中方法
设num[i]为每种字母的个数
对于所有的字母，总的种类数就是
但是要注意全不选的这种情况，对于上述种类数-1
即
•代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long mod=1e9+
7;
char s[
100005];
int Count[
27];
int main()
{
int n;
cin>>
n;
ll ans=
1;
for(
int i=
0;i<n;i++
)
{
cin>>
s[i];
Count[s[i]-
'a']++
;
}
for(
int i=
0;i<
26;i++
)
ans=(ans%mod*(Count[i]+
1)%mod)%
mod;
cout<<ans-
1<<
endl;
}
View Code
B: Reversi
•题意
有n块石头，从左往右第i块颜色为ci
现有一操作，可以进行0次或多次
选择颜色相同的两块石头，可以把这两块石头之间的石头全部变为此种颜色
问经过所有可能的操作后，最多有多少种不同的颜色序列
•思路
对于一个石头颜色序列，从左往右一次添加石头，在右边加一块石头，位置为x，颜色为xi
① 首先不挑选x，也就是x不是区间右端点，
把x放在（x-1）块石头后面，相当于前(x-1)块石头变化有ans[x-1]种，再在末尾加上第x块石头，形成ans[x-1]种序列
②挑选x,也就是x为某个区间的右端点，
如果x想成为某个区间的右端点，那就要找他前面与他颜色相同的石头，
第x块石头和他前面距离他最近的第一块石头组合形成序列，即ans[pos[x]]种。pos[x]为第x块石头前面距离他最近的第一块石头
为什么是第一块石头呢？
因为我们是从左往右一次添加的石头，加入一个颜色为col的石头，再加入其它颜色的石头，再加入col的石头，那第一块col和第二块col可以组成，
...再加入第三块col，那第三块col可以根据第二块形成的col，再形成若干种，
为什么不根据第一块col变化呢？因为在根据第二块变化时已经包括根据第一块变化了！(第二块是根据第一块变化的！)
•代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+
5;
const long long mod=1e9+
7;
#define ll long long
ll s[maxn];
ll pos[maxn];//记录每种颜色的位置，用来得到②的种数
ll ans[maxn];
//第i块石头的答案
int main()
{
int n;
cin>>
n;
s[0]=
0;
for(
int i=
1;i<=n;i++
)
{
cin>>
s[i];
if(i==
1)
//加第一块的时候肯定为1
ans[i]=
1,pos[s[i]]=i;
//记录答案和位置
else if(s[i]==s[i-
1])
//如果相邻颜色相同的话就只有①的种类数
ans[i]=ans[i-
1];
//因为两块之间没有石头不能变化
else
{
ans[i]=(ans[i-
1]+ans[flag[s[i]]]%mod)%mod;
//①的种类数+②的种类数
flag[s[i]]=i;
//记录位置
}
}
cout<<ans[n]<<
endl;
}
View Code
转载于:https://www.cnblogs.com/MMMinoz/p/11185427.html
