碎碎念
赛时没出题（真可恶吖）在上晚自习，补了一下。ACD都套着字符串的外壳，差点直接劝退，后来仔细一读发现和字符串没什么关系...大概字符串的用处是为了劝退我这种有些怂字符串的人叭。
A. 小红的环形字符串
- 题意：对于给定的环形字符串s，可以删除相邻的两个相同字母，问最多删除多少个字符
- 思路：相邻删除和头尾删除，注意删之后的相邻如何判断——deque
- code:
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
char s[MAXN];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
}
int l=1,r=n,cnt=0;
while(s[l]==s[r]){
if(l>=r)break;
cnt+=2;
l++;
r--;
}
deque<char>q;
for(int i=l;i<=r;i++){
if(q.size() && q.back()==s[i]){
q.pop_back();
cnt+=2;
}
else if(q.front()==s[r]){
r--;
q.pop_front();
cnt+=2;
}
else{
q.push_back(s[i]);
}
}
cout<<cnt<<endl;
return 0;
}
B.小红的乘除变换
- 题意：通过多次将 x 乘以5，或当x 是6的倍数，将 x 除以6 的操作，使x转变为y。问最小操作次数
- 思路：最小操作次数=（y比x多的⑤的因数个数）+（x比y多的6的因数个数）。当含有其他因子时或这两项存在负数时为-1
- code
#include<iostream>
#define int long long
using namespace std;
void sol(){
int x,y,ans=0;
cin>>x>>y;
int x5=0,y5=0;
while(x%5==0){
x5++;
x/=5;
}
while(y%5==0){
y5++;
y/=5;
}
if(x5>y5){
cout<<"-1"<<endl;
return;
}
ans=y5-x5;
int x6=0,y6=0;
while(x%6==0){
x6++;
x/=6;
}
while(y%6==0){
y6++;
y/=6;
}
if(x6<y6){
cout<<"-1"<<endl;
return;
}
ans+=x6-y6;
if(x!=y){
cout<<"-1"<<endl;
}
else{
cout<<ans<<endl;
}
return;
}
signed main(){
int t;
cin>>t;
while(t--){
sol();
}
return 0;
}
C.小红的子串
- 题意：小红拿到了一个长度为n的字符串，她准备选取一段子串，满足该子串中字母的种类数量在[l,r]之间。小红想知道，一共有多少种选取方案？
- 思路：双指针
- code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, l, r, num;
char S[2 * N];
int solve(int m){
int b[26], res = 0, num = 0;
memset(b, 0, sizeof b);
for(int i = 0, j = 0 ; i < n ; i ++){
b[S[i] - 'a'] ++;
if(b[S[i] - 'a'] == 1) ++ num;
while(num > m){
b[S[j] - 'a'] --;
if(b[S[j] - 'a'] == 0) num --;
++ j;
}
res += i - j + 1;
}
return res;
}
signed main(){
scanf("%d%d%d%s", &n, &l, &r, S);
printf("%lld\n", solve(r) - solve(l - 1));
return 0;
}
D.回文权值和（总算没小红了）
- 题意：定义一个字符串的权值为：长度为3的回文子串的数量。
求长度为n的、仅由小写字母组成的所有字符串的权值之和。答案对10^9+7取模。 - 思路：第一和第三位相同，其余位置任选，所以26^(n-1)种，这两个相同的位置的话有n-2种可能。
所以总共为(n-2) * qpow(26,n-1)