组合题6 个小题
已作答 0 / 6
1#include <iostream>2#include <queue>3using namespace std;4 5const int maxl = 20000000;6 7class Map {8 struct item {9 string key; int value;10 } d[maxl];11 int cnt;12 public:13 int find(string x) {14 for (int i = 0; i < cnt; ++i)15 if (d[i].key == x)16 return d[i].value;17 return -1;18 }19 static int end() { return -1; }20 void insert(string k, int v) {21 d[cnt].key = k; d[cnt++].value = v;22 }23} s[2];24 25class Queue {26 string q[maxl];27 int head, tail;28 public:29 void pop() { ++head; }30 string front() { return q[head + 1]; }31 bool empty() { return head == tail; }32 void push(string x) { q[++tail] = x; }33} q[2];34 35string st0, st1;36int m;37 38string LtoR(string s, int L, int R) {39 string t = s;40 char tmp = t[L];41 for (int i = L; i < R; ++i)42 t[i] = t[i + 1];43 t[R] = tmp;44 return t;45}46 47string RtoL(string s, int L, int R) {48 string t = s;49 char tmp = t[R];50 for (int i = R; i > L; --i)51 t[i] = t[i - 1];52 t[L] = tmp;53 return t;54}55 56bool check(string st , int p, int step) {57 if (s[p].find(st) != s[p].end())58 return false;59 ++step;60 if (s[p ^ 1].find(st) == s[p].end()) {61 s[p].insert(st, step);62 q[p].push(st);63 return false;64 }65 cout << s[p ^ 1].find(st) + step << endl;66 return true;67}68 69int main() {70 cin >> st0 >> st1;71 int len = st0.length();72 if (len != st1.length()) {73 cout << -1 << endl;74 return 0;75 }76 if (st0 == st1) {77 cout << 0 << endl;78 return 0;79 }80 cin >> m;81 s[0].insert(st0, 0); s[1].insert(st1, 0);82 q[0].push(st0); q[1].push(st1);83 for (int p = 0;84 !(q[0].empty() && q[1].empty());85 p ^= 1) {86 string st = q[p].front(); q[p].pop();87 int step = s[p].find(st);88 if ((p == 0 &&89 (check(LtoR(st, m, len - 1), p, step) ||90 check(RtoL(st, 0, m), p, step)))91 ||92 (p == 1 &&93 (check(LtoR(st, 0, m), p, step) ||94 check(RtoL(st, m, len - 1), p, step))))95 return 0;96 }97 cout << -1 << endl;98 return 0;99}100 （4 分）若两个字符串的长度均为 n，且 0<m<n−1，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（ ）。提示：考虑输入与输出有多少对字符前后顺序不一样。