首页 > 代码库 > hdu 4662 MU Puzzle
hdu 4662 MU Puzzle
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4662
MU Puzzle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1296 Accepted Submission(s): 539
Problem Description
Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called "words". We start with one word MI, and transform it to get a new word. In each step, we can use one of the following transformation rules:
1. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
2. Replace any III with a U. For example: MUIIIU to MUUU.
3. Remove any UU. For example: MUUU to MU.
Using these three rules is it possible to change MI into a given string in a finite number of steps?
1. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
2. Replace any III with a U. For example: MUIIIU to MUUU.
3. Remove any UU. For example: MUUU to MU.
Using these three rules is it possible to change MI into a given string in a finite number of steps?
Input
First line, number of strings, n.
Following n lines, each line contains a nonempty string which consists only of letters ‘M‘, ‘I‘ and ‘U‘.
Total length of all strings <= 106.
Following n lines, each line contains a nonempty string which consists only of letters ‘M‘, ‘I‘ and ‘U‘.
Total length of all strings <= 106.
Output
n lines, each line is ‘Yes‘ or ‘No‘.
Sample Input
2 MI MU
Sample Output
Yes No
Source
2013 Multi-University Training Contest 6
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you: 4822 4821 4820 4819 4818
规律题,把u全部化成i,然后多写下,就能发现规律
#include<iostream> #include<cstring> using namespace std; char str[1000010]; int main() { int n; cin>>n; while(n--) { cin>>str; int l=strlen(str),xi=0,xu=0,k=0; if(str[0]!=‘M‘) { cout<<"No"<<endl; continue; } for(int i=1;i<l;i++) { if(str[i]==‘I‘) xi++; else if(str[i]==‘U‘) xu++; else { k=1; break; } } if(k==1 || ((xi+xu)%2==1 && !(xi==1 && xu==0)) || xi%3==0) { cout<<"No"<<endl; continue; } else { cout<<"Yes"<<endl; continue; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。