时间限制:8000ms
单点时限:4000ms
内存限制:256MB
描述
你的硬盘上有一个神秘的文件占用了大量空间，你决定将其压缩以节省空间。不幸的是，你还没有安装任何压缩软件，所以你决定自己编写一个压缩程序。你发现这是一个文本文件，包括很多行。每行是一个长度恰好为L的字符串，而且字符串可能有重复。行的顺序并不重要，换言之，打乱顺序之后仍然可以认为文件内容和原来相同。
例如，这个文件的内容可以是这样的：
bar
car
bat
cat
cat
经过一段时间观察，你发现同一列的字符往往是相同的，于是你设计了一个简单的压缩框架。首先以某种策略调整行的顺序，然后把所有字符串按照先列后行的顺序变换成单个字符串，例如上面的例子，不调整顺序则直接变换成：
bcbccaaaaarrttt
然后使用游程编码(RLE)的到压缩变换后的字符串：
1b1c1b2c5a2r3t
当然也可以先调换顺序：
car
cat
cat
bat
bar
这样的压缩字符串为：
3c2b5a1r3t1r
比不调整顺序的稍短一些。
现在，你已经得到了两个不同的压缩字符串，你想知道他们解压后的文件是否相同，请写一个程序解决这个问题。
输入
第一行是一个整数T (T <= 30)，表示测试数据组数。
每组测试数据占三行。第一行为整数L，表示原始文件中每一行字符串的长度。第二行和第三行分别是两个压缩字符串，格式如c1 n1 c2 n2 … cMnM,表示字符ci连续出现了ni次。具体格式见样例。输入字符串只含a到z的小写字母，确保压缩字符串合法有效，且不为空。
输出
对每组测试数据，首先输出”Case x: ”，其中x表示测试数据编号。如果两个压缩字符串对应于相同的文件内容，则输出”Yes”，否则输出”No”。
数据范围
小数据：1<=L<=10, 1<=ni<=100,压缩字符串长度不超过10^4
大数据：1<=L<=1000, 1<=ni<=10^9,压缩字符串长度不超过10^6
样例输入
2
3
1b1c1b2c5a2r3t
3c2b5a1r3t1r
2
20a20b10a20b10a
20a20b20a20b
样例输出
Case 1: Yes
Case 2: No
代码如下：
#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include <stdlib.h>
using namespace std;int main()
{int T,num=0;cin>>T;vector<string> okresult(T);for(int i=0;i<T;++i){int a,step;int sum[2]={0,0};vector<vector<string> > result(2);vector<string> tep(2);vector<string> tep1(2);cin>>a;cin>>tep[0];cin>>tep[1];for (int t=0;t<2;++t){for (string::iterator st1=tep[t].begin();st1!=tep[t].end();++st1){int count=0;string ct1;while('0'<=*st1&&*st1<='9'){ct1+=*(st1++);}count=atoi(ct1.c_str());sum[t]+=count;for (int j=count;j>0;--j){tep1[t]+=*(st1);}}}if (sum[0]==sum[1]){step=sum[0]/a;string temp;for (int t=0;t<2;++t){for (int j=0;j<step;j++){temp.clear();for (int k=j;k<tep1[t].size();k+=step){temp+=tep1[t][k];}//result[t].insert(temp);result[t].push_back(temp);}}sort(result[0].begin(),result[0].end());sort(result[1].begin(),result[1].end());if (result[0]==result[1]){//cout<<"Case "<<i+1<<": "<<"Yes"<<endl;okresult[num++]="Yes";}else{//cout<<"Case "<<i+1<<": "<<"No"<<endl;okresult[num++]="No";}}else{//cout<<"Case "<<i+1<<": "<<"No"<<endl;okresult[num++]="No";}}for (int j=0;j<T;++j){cout<<"Case "<<j+1<<": "<<okresult[j]<<endl;}system("pause"); return 0;
}
