给定两个长度为 len 的字符串 s1 和 s2, 接着给出一个长度为 len*2 的字符串 s12.
将字符串 s1 和 s2 通过一定的变换变成 s12, 找到变换次数
变换规则如下:
假设 s1=12345,s2=67890
变换后的序列 s=6172839405
如果 s 和 s12 完全相等那么输出变换次数
如果不完全相等, s 的前半部分作为 s1, 后半部分作为 s2, 重复上述过程.
Input
第一行给出 T(1≤T≤1000), 代表有 T 组数据, 每组数据首先给出 len(1≤len≤100), 接着给出两个长度为 len 的字符串 s1 s2 然后给出长度为 len*2 的字符串 s12.
Output
首先输出处理数据组的编号 (编号从 1 开始)
再输出变换次数并换行.
注意两个数字之间有空格.
对于变换次数, 如果无需变换直接得到 s12, 那么输出 0, 如果无论怎么变换都不会得到 s12, 那么输出 -1.
- Sample Input
- 2
- 4
- AHAH
- HAHA
- HHAAAAHH
- 3
- CDE
- CDE
- EEDDCC
- Sample Output
- 1 2
- 2 -1
用到的知识:
1. 首先是 set, 用于判断在若干次交换以后, 是否存在重复的元素.
set<string>tmp;
tmp.find(s) 找到 s 在 tmp 这个容器里面的位置, 返回值是一个迭代器.
tmp.end() 容器的末尾.
tmp.insert(s) 把 s 这个串插入到 tmp 里面.
2.string
s.push_back( ) 在 s 的尾部插入一个字符.
s1.assign(s.begin(),s.begin+s.length()) 给 s1 赋值, 形参是两个迭代器.
这里还可以用 s1 = s.substr(0,mid); s2 = s.substr(mid,2*mid) substr 函数是取字符的字串, 形参是区间边界.
- #include <iostream>
- #include <string>
- #include <set>
- using namespace std;
- string s1,s2,s12;
- int mid;
- set<string> tmp;
- int main()
- {
- int n;
- cin>>n;int l = n;
- while(n--)
- {
- int count = 1;
- cin>>mid;
- cin>>s1>>s2>>s12;
- while(1)
- {
- string s;
- for(int i = 0; i < mid; i++)
- s.push_back(s2[i]),s.push_back(s1[i]);
- if(s == s12) { cout<<l-n<<" "<<count<<endl; break; }
- if(tmp.find(s) == tmp.end()) tmp.insert(s); // 在 tmp 容器里面寻找 s, 未找到, 返回的迭代器就是 tmp.end(), 就插入 s.
- else{cout<<l-n<<" "<<-1<<endl; break;}
- s1.assign(s.begin(),s.begin()+mid);
- s2.assign(s.begin()+mid,s.begin()+2*mid);
- count++;
- }
- tmp.clear();
- }
- }
来源: http://www.bubuko.com/infodetail-2944657.html