鱼C论坛

 找回密码
 立即注册
查看: 2701|回复: 5

[已解决]【C++板块提升计划】梦想护卫舰 第17关 旋转与回文【答题有奖】

[复制链接]
发表于 2023-1-29 07:28:14 | 显示全部楼层 |阅读模式
本帖最后由 zhangjinxuan 于 2023-1-30 14:00 编辑

上一关:阶乘之和


梦想护卫舰 第17关 旋转与回文


好了,你们通过了宝箱守护者的挑战,可以打开装有 1e5 的鱼币宝箱了~(好耶!)

但是(我就知道)

你们发现宝箱需要密码,宝箱上面只有一个长度为 N 的字符串 S(所以到底要干什么)

因为你成功答对了宝箱守护者的题目,所以他们给了你一些提示:

我们先定义 Si 为 S 从左往右的第 i 个字符(有点废话)

你可以按任意顺序执行下列操作 0 次或很多次:
  • 花费 A 的体力,将 S1 添加到 Sn 的后面,并把 S1 删除,换句话说,把原本 S 的 S1,S2, …… Sn 变成 S2,S3, …… Sn,S1
  • 花费 B 的体力,更改 S 的其中一个字符,新字符必须是小写字母


你需要把 S 变成回文串

你至少花费的体力,就是打开宝箱的密码

数据范围
1 <= n <= 5000
1 <= A, B <= 1e9
Si (1 <= i <= n) 是小写字母
除了 S,所有数据都是整数

输入格式

所有输入参照以下格式:
N A B
S

输出格式

输出一个整数表示答案

输入样例1
5 1 2
rrefa

输出样例1
3

样例解释1
(请自行翻译,宝箱守护者是歪果仁
First, pay 2 yen to perform the operation of the second kind once:
let i=5 to replace S 5 with e. S is now "rrefe".
Then, pay 1 yen to perform the operation of the first kind once.
S is now "refer", which is a palindrome.
Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.


输入样例2
8 1000000000 1000000000
bcdfcgaa

输入样例2
4000000000

样例解释2
Note that the answer may not fit into a 32-bit integer type.


注意:本题非原创,改编于 ABC 286 C,题解个人原创



                               
登录/注册后可看大图


答案与解析
请认真思考再查看答案!
游客,如果您要查看本帖隐藏内容请回复
[/hide]

最佳题解排行榜
(排行未确定,大家还有上榜机会!)


第一名第二名第三名
名字ExiaGN001等待着聪明的编程王者~
链接戳我
语言C++
效率34ms
代码得分100
综合得分100
奖励5鱼币5荣誉+“最佳答案”3鱼币3荣誉2鱼币2荣誉

/*综合评分会参照运行时间(代码效率),代码长度,代码可读性,解题思路,代码得分等来进行评分*/


答题规则
1. 不能抄题解,否则无奖励,可能还会扣分;
2. 爆零的代码,视为普通回帖,不会奖励;
3. 语言任意。
4. 当您遇到问题时,您可以回贴提问,我会为您解答


奖励规则
1. 奖励3天后统一发,3天内发布的题解才有效;
2. 提供完整题解,但没有上排行榜,奖励1鱼币+1荣誉
3. 高于1鱼币1荣誉的奖励,仅给排行榜上的鱼油(因为经济原因,请谅解);
4. 因为额度原因,部分鱼油可能下一天才能奖励。



                               
登录/注册后可看大图


游客,如果您要查看本帖隐藏内容请回复
[/hide]

下一关:解密(2)

创作不易,如果你喜欢,别忘了分、顶


本关满意度调查
最佳答案
2023-1-29 08:26:31
本帖最后由 ExiaGN001 于 2023-1-29 08:28 编辑

已测ACcepted 17/17(含2sample)
评测记录可查:
https://www.luogu.com.cn/record/100716963

https://atcoder.jp/contests/abc286/submissions/38436035
//洛谷/ATCoder
//AT_abc286_c [ABC286C]
//Rotate and Palindrome

#include<bits/stdc++.h>
using namespace std;
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        long long n,a,b;
        unsigned long long ans,tmpans;
        char s[11451];
        char s2[11451];

        scanf("%lld%lld%lld",&n,&a,&b);
        scanf("%s",s+1);

        ans=1000000000000000000;
        tmpans=0;

        for(int i=0;i<=n;i++)
        {
                tmpans=a*i;

                for(int j=1;j<=n-i;j++)s2[j]=s[j+i];
                for(int j=n-i+1;j<=n;j++)s2[j]=s[j-n+i];

                if(n%2==0)
                        for(int l=n/2,r=n/2+1;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                else
                        for(int l=n/2,r=n/2+2;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                ans=min(ans,tmpans);
        }
        cout<<ans;
        return 0;
}
多选投票: ( 最多可选 3 项 ), 共有 4 人参与投票
您所在的用户组没有投票权限

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-29 08:26:31 | 显示全部楼层    本楼为最佳答案   
本帖最后由 ExiaGN001 于 2023-1-29 08:28 编辑

已测ACcepted 17/17(含2sample)
评测记录可查:
https://www.luogu.com.cn/record/100716963

https://atcoder.jp/contests/abc286/submissions/38436035
//洛谷/ATCoder
//AT_abc286_c [ABC286C]
//Rotate and Palindrome

#include<bits/stdc++.h>
using namespace std;
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        long long n,a,b;
        unsigned long long ans,tmpans;
        char s[11451];
        char s2[11451];

        scanf("%lld%lld%lld",&n,&a,&b);
        scanf("%s",s+1);

        ans=1000000000000000000;
        tmpans=0;

        for(int i=0;i<=n;i++)
        {
                tmpans=a*i;

                for(int j=1;j<=n-i;j++)s2[j]=s[j+i];
                for(int j=n-i+1;j<=n;j++)s2[j]=s[j-n+i];

                if(n%2==0)
                        for(int l=n/2,r=n/2+1;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                else
                        for(int l=n/2,r=n/2+2;l>=1&&r<=n;l--,r++)
                        {
                                if(s2[l]!=s2[r])tmpans+=b;
                        }
                ans=min(ans,tmpans);
        }
        cout<<ans;
        return 0;
}

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zhangjinxuan + 5 + 5 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-29 07:39:22 | 显示全部楼层
本帖最后由 ExiaGN001 于 2023-1-29 07:53 编辑

给大家一些题意补充。首先捉虫
1.在操作之后,S必须是回文串(自己理解)
2.答案可能用 32位整数 存不下。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-1-29 08:25:57 | 显示全部楼层
ExiaGN001 发表于 2023-1-29 07:39
给大家一些题意补充。首先捉虫。
1.在操作之后,S必须是回文串(自己理解)
2.答案可能用 32位整数 存不下 ...

不好意思,1忘了写上去
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-29 08:39:40 | 显示全部楼层
ExiaGN001 发表于 2023-1-29 08:26
已测ACcepted 17/17(含2sample)
评测记录可查:
https://www.luogu.com.cn/record/100716963

太强了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-2-3 10:15:13 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 21:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表