Rikka with string
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 581 Accepted Submission(s): 227
One day, Yuta got a string which contains n letters but Rikka lost it in accident. Now they want to recover the string. Yuta remembers that the string only contains lowercase letters and it is not a palindrome string. Unfortunately he cannot remember some letters. Can you help him recover the string?
It is too difficult for Rikka. Can you help her?
a?bb?
3
aaa
QwQ
#include<stdio.h>
#include<string.h>
int cnt = ;
char st[ + ] ;
char rst [ + ] ;
int n , vis[ + ]; void rev (char s[ + ])
{
char tmp[ + ] ;
int k = , i ;
for (i = strlen (st) - ; i >= ; i-- , k ++) {
tmp[k] = st[i] ;
}
tmp[k] = '\0' ;
strcpy (s , tmp) ;
} int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
while (~ scanf ("%d" , &n)) {
getchar () ;
gets (st) ;
cnt = ;
for (int i = ; st[i] != '\0' ;i ++) {
if (st[i] == '?') {
vis[cnt ++] = i ;
st[i] = 'a' ;
}
}
int i ;
rev (rst) ;
if (strcmp (st , rst)== ) {
for (i = cnt - ; i >= ; i--) {
st[vis[i]] = 'b' ;
rev (rst) ;
if (strcmp (rst , st)!= ) {
break ;
}
st[vis[i]] = 'a' ;
}
if (i == - ) puts ("QwQ") ;
else puts (st) ;
}
else puts (st) ;
}
return ;
}
如果没有不是回文串的限制可以把所有的?都变成a,这样一定是字典序最小的。而现在有了回文串的限制,我们可以从小到大枚举最靠后的不在字符串正中心的问号选什么,其他的问号依然换成a,显然如果有解,这样一定可以得到字典序最小的解。注意特判没有问号以及问号在正中心的情况。
时间复杂度O(n)
hdu.5202.Rikka with string(贪心)的更多相关文章
-
HDU 6086 Rikka with String
Rikka with String http://acm.hdu.edu.cn/showproblem.php?pid=6086 题意: 求一个长度为2L的,包含所给定的n的串,并且满足非对称. 分析 ...
-
HDU 6086 Rikka with String AC自动机 + DP
Rikka with String Problem Description As we know, Rikka is poor at math. Yuta is worrying about this ...
-
hdoj - 5202 Rikka with string (BestCoder Round #37 ($))
http://acm.hdu.edu.cn/showproblem.php?pid=5202 字符串处理的题,要细心. 给定一个只包含小写字母和问号的字符串,让我们还原出本来的字符串,把问号替换成任意 ...
-
hdu 6086 -- Rikka with String(AC自动机 + 状压DP)
题目链接 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, s ...
-
HDU 6086 Rikka with String ——(AC自动机 + DP)
这是一个AC自动机+dp的问题,在中间的串的处理可以枚举中断点来插入自动机内来实现,具体参见代码. 在这题上不止为何一直MLE,一直找不到结果(lyf相同写法的代码消耗内存较少),还好考虑到这题节点应 ...
-
HDU 5831 Rikka with Parenthesis II(六花与括号II)
31 Rikka with Parenthesis II (六花与括号II) Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536 ...
-
HDU 6093 - Rikka with Number | 2017 Multi-University Training Contest 5
JAVA+大数搞了一遍- - 不是很麻烦- - /* HDU 6093 - Rikka with Number [ 进制转换,康托展开,大数 ] | 2017 Multi-University Tra ...
-
HDU 5842 Lweb and String(Lweb与字符串)
p.MsoNormal { margin: 0pt; margin-bottom: .0001pt; text-align: justify; font-family: Calibri; font-s ...
-
判断相同区间(lazy) 多校8 HDU 5828 Rikka with Sequence
// 判断相同区间(lazy) 多校8 HDU 5828 Rikka with Sequence // 题意:三种操作,1增加值,2开根,3求和 // 思路:这题与HDU 4027 和HDU 5634 ...
随机推荐
-
ACM ICPC 2015 Moscow Subregional Russia, Moscow, Dolgoprudny, October, 18, 2015 H. Hashing
H. Hashing time limit per test 1 second memory limit per test 512 megabytes input standard input out ...
-
zoj 1010 Area【线段相交问题】
链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1010 http://acm.hust.edu.cn/vjudge/ ...
-
javascript回调函数
function $$(f) { if (typeof f == 'function') {//f是一个函数 f(); } else { alert('not a function'); } } $$ ...
-
windows7 iis安装与配置
方法/步骤 一. Windows 7环境下的安装配置 打开控制面板——程序和功能 点击左侧“打开或关闭Windows功能”,弹出Windows功能 对话框. 在Windows功能对话框中进 ...
-
[译]ava 设计模式之职责链
(文章翻译自Java Design Pattern: Chain of Responsibility) 职责链模式的主要设计思想是为了构建一连串的处理单元,如果阈值满足的话那么这个单元就来处理这个请求 ...
-
[CentOS] rsync同步目录进行备份文件
操作不难,网上一堆.这里列几个 CentOS7 参考地址: https://www.server-world.info/en/note?os=CentOS_7&p=rsync Copy fil ...
-
python:数据类型set
一.集合 集合是无序的,不重复的数据集合,它里面的元素是可哈希的(不可变数据类型),但是集合本身是不可哈希(所以集合做不了字典的键)的.以下是集合最重要的两点: 去重,把一个列表变成集合,就自动去重了 ...
-
设置VMware随系统开机自动启动并引导虚拟机操作系统
设置VMware随系统开机自动启动并引导虚拟机操作系统 转载 2012年03月15日 19:50:53 标签: vmware / 虚拟机 / windows / parameters / tools ...
-
开源监控zabbix的搭建
yum-nginx-php-mysql 1.依赖安装 1.依赖 yum -y install pcre* openssl* 2.php rpm -Uvh https://mirror.webtatic ...
-
Netbackup8.0以上版本,服务端生成证书,客户端获取、更新证书方式(整理中)
创建重发令牌 如果非主控主机已在主服务器上注册但其基于主机ID的证书不再有效,则可以重新颁发基于主机ID的证书.例如,证书在过期,被撤销或丢失时无效. 重发令牌是一种可用于重新颁发证书的令牌.它是一种 ...