题目信息

题目类型
提高级
题目年份
2020
题目题型
判断题
关 键 词
时间复杂度

题目题干

第30题
  1. #include <iostream> 
  2. #include <queue> 
  3. using namespace std; 
  4.    
  5. const int maxl = 2000000000; 
  6.    
  7. class 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.    
  25. class 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.    
  35. string st0, st1; 
  36. int m; 
  37.    
  38. string 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. string RtoL(string s, int L, int R) { 
  47.     string t = s; 
  48.     char tmp = t[R]; 
  49.     for (int i = R; i > L; --i) 
  50.         t[i] = t[i - 1]; 
  51.     t[L] = tmp; 
  52.     return t; 
  53.    
  54. bool check(string st, int p, int step) { 
  55.     if (s[p].find(st) != s[p].end()) 
  56.         return false
  57.     ++step; 
  58.     if (s[p ^ 1].find(st) == s[p].end()) { 
  59.         s[p].insert(st, step); 
  60.         q[p].push(st); 
  61.         return false
  62.     } 
  63.     cout << s[p ^ 1].find(st) + step << endl; 
  64.     return true
  65.    
  66. int main() { 
  67.     cin >> st0 >> st1; 
  68.     int len = st0.length(); 
  69.     if (len != st1.length()) { 
  70.         cout << -1 << endl; 
  71.         return 0; 
  72.     } 
  73.     if (st0 == st1) { 
  74.         cout << 0 << endl; 
  75.         return 0; 
  76.     } 
  77.     cin >> m; 
  78.     s[0].insert(st0, 0); s[1].insert(st1, 0); 
  79.     q[0].push(st0); q[1].push(st1); 
  80.     for (int p = 0; 
  81.          !(q[0].empty() && q[1].empty()); 
  82.          p ^= 1) { 
  83.         string st = q[p].front(); q[p].pop(); 
  84.         int step = s[p].find(st); 
  85.         if ((p == 0 && 
  86.               (check(LtoR(st, m, len - 1), p, step) || 
  87.                check(RtoL(st, 0, m), p, step))) 
  88.                   || 
  89.             (p == 1 && 
  90.               (check(LtoR(st, 0, m), p, step) || 
  91.                check(RtoL(st, m, len - 1), p, step)))) 
  92.             return 0; 
  93.     } 
  94.     cout << -1 << endl; 
  95.     return 0; 

3)判断:若两个字符串的长度均为 n,则最坏情况下,此程序的时间复杂度为 Θ(n!)。( )wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
wKC100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 

答案解析

相关题目

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢