Codeforces #410 题解

比赛题目链接:http://codeforces.com/contest/798

798A - Mike and palindrome

题意

给出一个字符串,判断是否能够只改变一个字符使得这个字符串变成一个回文串

题解

题目要求必须改变一个字符串(一开始被这个坑了),所以把整体分成三种情况,改变一处成为回文串输出YES;已经是回文串并且串的长度是奇数输出YES(因为改变最中间那个字符,这个字符串还是回文串);其他情况输出NO。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void solve()
{
string s;
while(cin>>s)
{
int n=s.size();
int u=0;
if(n==1)
{
printf("YES\n");
return ;
}
for(int i=0;i<n;i++)
{
if(s[i]!=s[n-1-i])
u++;
}
if(u==2)
printf("YES\n");
else if(u==0 && n%2==1)
printf("YES\n");
else
printf("NO\n");
}
}

798B - Mike and strings

题意

定义对字符串的一个操作:将首字符移到最后。给出n个字符串,问最少进行多少次这样的操作能够使得给出的所有字符串都相同。

题解

模拟法

首先将每一个字符串都复制一遍放到最后,这样左移k位就可以看成是从第k个字符开始长度为len的字符串了。遍历每一个字符串,将其当做目标字符串,计算其他的字符串变成这个字符串的最小开销,求出一个最小值就行了。加上检查是否相等的O(len)的时间复杂度,整体的时间复杂度为O(n^2*len^2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int n,len;
char s[51][101];
bool judge(char *a,char *b) //判断以a b两个字符串是否相等
{
for(int i=0;i<len;i++)
if(a[i]!=b[i]) return false;
return true;
}
void solve()
{
while(scanf("%d",&n)!=EOF)
{
bool flag=false;
for(int i=0;i<n;i++)
scanf("%s",s[i]);
len=strlen(s[0]);
for(int i=0;i<n;i++)
for(int j=0;j<len;j++)
s[i][j+len]=s[i][j]; //在原来的字符串后面加上相同的字符串
int res=0,ans=INF;
for(int i=0;i<n;i++) //作为基准字符串
{
res=0;
for(int j=0;j<n;j++)
{
if(i==j)
continue;
int k;
for(k=0;k<len;k++)
if(s[i][0]==s[j][k] && judge(s[i],s[j]+k)) //j串循环左移k位
{
res+=k;
break;
}
if(k==len)
{
printf("-1\n");
flag=1;
break;
}
}
if(flag)
break;
ans=min(ans,res);
}
if(flag) break;
printf("%d\n",ans);
}
}

798C - Mike and gcd problem

题意

首先定义对于序列的一个操作:将an 和 an+1的值分别替换为(an-an+1)和(an+an+1)。给出一个序列,问要进行多少步如上的操作才能使得这个序列的最大公因数大于1。

题解

如果两个操作数都是奇数的话,进行一次操作就全部变成偶数;如果两个数是一奇一偶的话,进行一次操作后变成两个都是奇数,再进行一次操作就得到两个偶数。如果一个序列全是偶数的话,他们的最大公因数至少是2,比1大。所以不管序列怎样,一定是有解的。
一个序列如果gcd是1的话那么这个序列中一定存在奇数,并且至少有两个数互质。所以采取将所有的奇数通过操作变换成偶数的方案。我们知道如果是两个奇数要进行一次操作,一奇一偶进行两次操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int a[maxn];
void solve()
{
int n;
while(scanf("%d",&n)!=EOF)
{
printf("YES\n");
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int g=gcd(a[0],a[1]);
for(int i=2;i<n;i++)
g=gcd(g,a[i]);
if(g>1)
printf("0\n");
else
{
int ans=0;
for(int i=0;i<n;i++)
{
if(!(a[i]&1)) //对奇数进行操作
continue;
if(i==n-1)
ans+=2;
else
{
int tmp=a[i];
a[i]=a[i]-a[i+1];
a[i+1]=tmp+a[i+1];
ans++;
if(a[i]&1) //进行两步操作
{
tmp=a[i];
a[i]=a[i]-a[i+1];
a[i+1]=tmp+a[i+1];
ans++;
}
}
}
printf("%d\n",ans);
}
}
}