Mike and strings CodeForces - 798B (又水又坑)

时间:2022-02-14 15:10:04

题目链接

题意:英语很简单,自己取读吧。

思路:

既然n和i字符串的长度都很小,最大才50,那么就是只要能出答案就任意暴力瞎搞。

本人本着暴力瞎搞的初衷,写了又臭又长的200多行(代码框架占了50行)。反正不忘初衷就对了。

暴力:枚举每一个字符串,然后暴力去算其他字符串变成该字符串需要用多少步骤,然后在众多答案中取最小值。

需要注意的是答案是-1的情况,需要用到字符串的最小表示法,预处理进行把所有的字符串变成最小表示法的字符串,如果有不一样的,那么就输出-1。因为可以通过首位对接搞成的字符串的最小表示法是唯一的。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb std::ios::sync_with_stdio(false)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
char s[][];
char b[][];
int bj[];
int fbj[];
void findMin(char* s)
{
int len =strlen(s);
int i=,j=,k=;
while(i<len&&k<len&&j<len)
{
if(s[(i+k)%len]==s[(j+k)%len])
{
k++;
}
else if(s[(i+k)%len]>s[(j+k)%len])
{
i=i+k+;
k=;
}
else
{
j=j+k+;
k=;
}
if(i==j) j++;
}
int tt=min(i,j);// findMin里的
char str[];
strcpy(str,s);
for(i=;i<len;i++)
{
s[i]=str[(tt+i)%len];
}
s[len]='\0';
}
int main()
{
gbtb;
cin>>n;
repd(i,,n)
{
cin>>s[i]; }
int len=strlen(s[]);
repd(i,,len-)
{
bj[s[][i]]++;
}
repd(i,,n)
{
MS0(fbj);
repd(j,,len-)
{
fbj[s[i][j]]++;
}
repd(j,,)
{
if(fbj[j]!=bj[j])
{
cout<<-<<'\n';
return ;
}
}
}
repd(i,,n)
{
repd(j,,len-)
{
b[i][j]=s[i][j];
}
b[i][len]='\0';
findMin(b[i]);
}
repd(i,,n-)
{
if(strcmp(b[i],b[n])!=)
{
cout<<-<<'\n';
return ;
}
}
int ans=0x3f3f3f3f;
repd(i,,n)
{ int num=;
repd(j,,n)
{
if(i!=j)
{
int cnt=;
int deng=;
int f=;
for(int k=;k<len;k++)
{
if(s[i][f]!=s[j][k])
{
if(deng)
{ cnt+=deng;
deng=;
f=;
k--;
continue;
}
// if(k+1<len&&s[i][f]!=s[j][k+1])
cnt++;
}else
{
f++;
deng++;
}
}
num+=cnt;
}
}
ans=min(ans,num);
}
cout<<ans<<'\n';
return ;
} inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * - ch + '';
}
}
else {
*p = ch - '';
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}