Problem - 1389C - Codeforces
题意:
我们把某个字符串t1t2t3...tn-1tn的左循环移位称为字符串t2t3...tn-1tnt1。
类似地,我们把字符串t的右循环移动称为字符串tnt1t2t3...tn-1。
如果字符串t的左循环移位等于其右循环移位,我们就说它是好的。
给你一个由数字0-9组成的字符串s。
你需要从s中擦除多少个字符才能使其成为好字符串?
输入
第一行包含单个整数t(1≤t≤1000)--测试案例的数量。
接下来的t行包含测试用例--每行一个。每个测试用例的第一行也是唯一一行包含字符串s(2≤|s|≤2⋅105)。每个字符si是数字0-9。
保证字符串的总长度不超过2⋅105。
输出
对于每个测试案例,打印你需要从s中删除的最小字符数,以使其成为好的。
题解:
假设我们设这个字符串为奇数,长度为5
原
1 2 3 4 5
2 3 4 5 1
5 1 2 3 4
2 = 5
3 = 1
4 = 2
5 = 3
1 = 4
我们发现如果长度为奇数,只有所有字母相同的情况下才会出现
接着我们考虑偶数的情况
1 2 3 4
2 3 4 1
4 1 2 3
2 = 4
3 = 1
4 = 2
1 = 3
发现只有下标为偶数时都相等,为奇数时都相等才行;
为偶数时会有两种不同数字(相同的奇数n为奇数已经考虑了)
那么我们暴力枚举所有(奇数位,偶数位)为两种数字的情况
时间复杂度为9*9*2e5发现可以过
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
int n;
char a[200050];
int len1(int x,int y)
{
char o = x+'0';
char p = y+'0';
int f = 0;
int cnt = 0;
for(int i = 1;i <= n;i++)
{
if(a[i]==o&&f == 0)
{
f^=1;
}
if(a[i]==p&&f == 1)
{
f^= 1;
cnt += 2;
}
}
return cnt;
}
void solve()
{
cin >> a+1;
n = strlen(a+1);
map<int,int> vis;
int ans = 0;
for(int i = 1;i <= n;i++)
{
vis[a[i]-'0']++;
ans = max(ans,vis[a[i]-'0']);
}
for(int i = 0;i <= 9;i++)
{
for(int j = 0;j <= 9;j++)
{
if(i == j)
continue;
ans = max(ans,len1(i,j));
}
}
cout<<n-ans<<"\n";
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)