次代猫

次代猫
一只有各种科技姿势的小喵~
  1. 首页
  2. 未分类
  3. 正文

阿里云在线编程挑战赛之Jerry的考验

2020年6月28日 152点热度 0人点赞 0条评论

Jerry的考验

描述

有一天Jerry给Tom出了一道题来考验他。Jerry给了Tom一个长度为2*n的只包含小写字母的字符串,让Tom将这个字符串任意挑选字符,将其分成两个等长的字符串a和b(对于一个si不能同时被选到a和b中),然后a要和reverse(b)相同(a和反转后的b相同),问这样的方案数有多少?Tom有些为难,所以请你来帮帮他吧。

输入

一个正整数n,和一个长度为2*n的字符串。

输出

方案数。

样例

输入:2,"abba"。

输出:4。

解题思路:

本题的关键在于理解题意:所谓挑选n个字符变成a和b两个字符串,是指在原字符串中抽出n个字符,这些字符的的顺序保持不变,剩下字符的顺序也保持不变,由此组成a和b两个字符串。

例如 "abcdef",挑选第2、3、5个字符,则分成 "bce" 和 "adf" 两个串。

接下来是整理的思路解析:整体框架是dfs,枚举每个字符属于a还是属于b,搜索过程中需要利用a和b的对称性做加速处理,否则会超时。

比方说:xcccddcccxdd。

从左往右枚举a字符串的构成,如果令第一个x属于a,根据对称性,倒数第三个字符x一定是属于b;如此推导出末尾的dd一定属于a,中间位置的dd一定属于b,而且是b的头两个字符;然后左边ccc一定a,右边ccc一定是b,由此得出1种方案。令第一个x属于b也可以用同样的方式得到1种方案。

用这个思路直接写代码不太好写,可以通过枚举二进制,固定左半边的选择情况,然后对于每一个case,通过dfs搜索右半边有多少种合法组合,搜索过程中利用对称性进行剪枝。

对于字符全部相同case如"aaaaaaaa",因为过程中无法剪枝,会退化成2^(2*n)。对于这种case,答案就是 C(2n,n) ,预判一下直接返回即可。
本站采用的阿里云ECS学生机是参与高校扶持计划的免费学生主机,可以通过这个链接进行参加:
[dm href='https://developer.aliyun.com/adc/college/']点击参与[/dm]

标签: 暂无
最后更新:2020年6月28日

宋艳雷

乘风破浪,时刻前行

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

宋艳雷

乘风破浪,时刻前行

分类目录
  • 未分类
  • 活动
最新 热点 随机
最新 热点 随机
WordPress动静分离优化,为网站Max提速,10秒伪娘变2秒猛男 云开发校园合伙人创造营Day2不踩坑、快速完成 哔哩哔哩夏日特供 免费领取大会员 腾讯云免费领取1H1G 3Mbps 轻量服务器 每日300台 手慢无 GitHub Student Pack 学生包如何申请(免学校邮箱) 阿里云“云开发平台校园合伙人招募” C位出道阿里实习、T恤、优酷VIP(必得)等奖品多多
哔哩哔哩夏日特供 免费领取大会员 次代猫 - 原蓝熊网络 秒懂阿里云生态 OwnCloud安装及挂载阿里云NAS 腾讯云免费领取1H1G 3Mbps 轻量服务器 每日300台 手慢无 云开发校园合伙人创造营Day2不踩坑、快速完成
最近评论
发布于 7 个月前(07月28日) 本站名称:iloveflag's Blog 本站地址:https://www.iloveflag....
发布于 8 个月前(07月26日) 老哥还是学生呢?
发布于 8 个月前(07月26日) 妹找到啊?
发布于 8 个月前(07月23日) 本站名称:Tang's Blog 本站地址:https://tangzhiqian.cn/ 本站...
发布于 8 个月前(07月18日) Parksi 半真半假,半信半疑。 https://www.parksi.xyz/images/...

COPYRIGHT © 2021 次代猫. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

豫ICP备20013021号