洛谷 CF1040A 题解

本文最后更新于 2024年7月15日 下午

洛谷题目传送门 | CF 原题传送门

基础回文数判断题。

感觉题目翻译并不是很好,需要注意回文串中不能出现 22,例如 102011 0 2 0 1 不能作为最终答案。

思路

直接把数组从 11 到 $\lfloor \frac{n}{2}\rfloor $ 扫一遍即可。

有以下几种情况需要分类讨论:

  1. 如果原串首尾不同但不是 22,即形如 1010010100 这样的,无法变为回文串,直接输出 1-1
  2. 如果原串首尾都为 22,只需要把两个 22 都换成 0011代价最小的数
  3. 如果原串首尾有且仅有一个是 22,把那一个 22 改为和另一端相同的数
  4. 最后再特判 nn 为奇数的情况,如果中间数为 22ansans 需要再加上 min(a,b)\min(a,b)形成不含 22 的回文串

然后这道题就很简单了。

代码

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
#include<cmath>
#include<iostream>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,a,b,t[30],ans=0;
int main()
{
n=read();a=read();b=read();
for(int i=1;i<=n;i++) t[i]=read();
for(int i=1;i<=n/2;i++)
{
if((t[i]==0 && t[n-i+1]==1) || (t[i]==1 && t[n-i+1]==0))//首尾不同且不是2
{
cout<<-1<<endl;
return 0;
}
else if(t[i]==2 && t[n-i+1]==2)//首尾都为2
{
ans+=min(a,b)*2;
if(a<b) t[i]=t[n-i+1]=0;
else t[i]=t[n-i+1]=1;
}
else if(t[i]!=2 && t[n-i+1]==2)//结尾为2
{
if(t[i]==0) ans+=a,t[n-i+1]=0;
else ans+=b,t[n-i+1]=1;
}
else if(t[i]==2 && t[n-i+1]!=2)//开头为2
{
if(t[n-i+1]==0) ans+=a,t[i]=0;
else ans+=b,t[i]=1;
}
}
if(n%2==1 && t[n/2+1]==2) ans+=min(a,b);//n为奇数需要特判
cout<<ans<<endl;
return 0;
}

洛谷 CF1040A 题解
https://blog.makerlife.top/post/solution-CF1040A/
作者
Makerlife
发布于
2022年7月12日
更新于
2024年7月15日
许可协议