首页 > ACM题库 > HDU-杭电 > HDU 4662-MU Puzzle-字符串-[解题报告]HOJ
2015
09-17

HDU 4662-MU Puzzle-字符串-[解题报告]HOJ

MU Puzzle

问题描述 :

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?

输入:

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.

输出:

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.

样例输入:

2
MI
MU

样例输出:

Yes
No

来源:点击打开链接

这个题目的来源是人工智能领域MU猜想。比赛的时候也参考了相关资料,可是最后差一点没有把规律推出来。

注意到以下几个性质。第一,MI怎么变换M永远只能在第一位。第二,因为变换时只能在I和U之间变换,因此,除了第一个是M以外,后面如果有字符串不是U、I以内的话永远不可能变换得到。第三,U可以看成是3个I,无论是I先变换成U再操作还是转化成一定数量的I,最后再准换成一定数量的U即可,因此将所有的字母用I作为一般等价物进行交换即可。

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int main()
{
	int testcase;
	cin>>testcase;
	while(testcase--)
	{
		string p="MI";
		int counti=1,countu=0,counti2=0,countu2=0,cm=0,pos=0;
		string tar;
		cin>>tar;
		for(int i=0;i<tar.length();i++)
		{
			
			if(tar[i]=='M')
			{
				cm++;
			}
				
			if(tar[i]=='I')
			{
				counti2++;
			}
				
			if(tar[i]=='U')
			{
				countu2++;
			}
				
		}
		
		if( cm==1 && tar[0]=='M'&& (((countu2*3+counti2)%2==0 && (countu2*3+counti2)%3!=0)||(countu2*3+counti2)==1))
		{
			pos=1;
		}
		else
		{
			pos=0;
		}
		
	
		if(pos==0)
		{
			cout<<"No"<<endl;
		}
		else if(pos==1)
			cout<<"Yes"<<endl;
		
		
	}
	
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/mig_davidli/article/details/9965361