[关闭]
@Dmaxiya 2022-12-04T22:23:20.000000Z 字数 6116 阅读 237

移花接木题解

出题

通过观察可以发现行与列的操作互不影响，都不会改变两个元素在矩阵内同一行 / 列的相对关系，可以分别对行、列操作进行统计。

可以通过 暴力枚举所有可能的交换情况，然后对每种情况进行校验。

每行内若使用双重 for 循环校验时间复杂度为：，若检查每个数的倍数是否在当前行内时间复杂度为 ，由于全排列只能通过 的数据，因此使用 的最坏时间复杂度更小。

每列内只要记录上一次出现的非 值是否小于当前位置上的数字，就可以 次完成校验。

总时间复杂度为 ，可通过 的数据。

一、考虑到交换列时同一列内的元素相互绑定，在每一行内，必须保证一个数的约数在其之前，倍数在其之后，即某些列之间的前后关系是确定的，而另一些不能完全确定，最终需要将这些列按从 到 的顺序进行排序，若将每一列视为一个点，约数与倍数的相对关系就是一个有向图，判断能否在无限次交换内满足目标条件，可使用拓扑排序判断有向图内是否存在环，若存在环输出 no，不存在输出 yes。交换行的做法同理不再赘述。

二、如何快速找到有向边需要指向的数字，对于交换行而言，只需要将每列的数字取出排序，然后将相邻的两个非零数字连边即可。对于交换列而言，每行内的处理方式为：将所有数字放到一个集合中，跑到每一个正整数 时，判断其 倍是否存在于集合中，若存在则将两个数字所在列连一条有向边。

时间复杂度的计算：第一步拓扑排序时间复杂度是 ，第二步每列内排序时间复杂度是 ，每行内的最坏情况是 到 均匀分布在同一行，其时间复杂度约为：


由于一行最多只有 个数据且较为随机，因此实际上达不到 ，加上 组数据，最终总的时间复杂度为 ，可通过 的数据。

暴力解法

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long LL;
  5. const int maxn = 100;
  6. int T, n, m;
  7. bool ans;
  8. int nums[maxn][maxn], idx[maxn];
  10. bool judgeRow() {
  11.     for (int j = 0; j < m; ++j) {
  12.         int last = 0;
  13.         for (int i = 0; i < n; ++i) {
  14.             if (nums[idx[i]][j] == 0) {
  15.                 continue;
  16.             }
  17.             if (nums[idx[i]][j] < last) {
  18.                 return false;
  19.             }
  20.             last = nums[idx[i]][j];
  21.         }
  22.     }
  23.     return true;
  24. }
  26. bool judgeCol() {
  27.     for (int i = 0; i < n; ++i) {
  28.         for (int j = 0; j < m; ++j) {
  29.             if (nums[i][idx[j]] == 0) {
  30.                 continue;
  31.             }
  32.             for (int k = j + 1; k < m; ++k) {
  33.                 if (nums[i][idx[k]] == 0) {
  34.                     continue;
  35.                 }
  36.                 if (nums[i][idx[j]] % nums[i][idx[k]] == 0) {
  37.                     return false;
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     return true;
  43. }
  45. int main() {
  46.     scanf("%d", &T);
  47.     while (T--) {
  48.         scanf("%d%d", &n, &m);
  49.         for (int i = 0; i < n; ++i) {
  50.             for (int j = 0; j < m; ++j) {
  51.                 scanf("%d", &nums[i][j]);
  52.             }
  53.         }
  55.         for (int i = 0; i < n; ++i) {
  56.             idx[i] = i;
  57.         }
  58.         ans = false;
  59.         do {
  60.             if (judgeRow()) {
  61.                 ans = true;
  62.                 break;
  63.             }
  64.         } while (next_permutation(idx, idx + n));
  65.         if (!ans) {
  66.             printf("no\n");
  67.             continue;
  68.         }
  70.         for (int j = 0; j < m; ++j) {
  71.             idx[j] = j;
  72.         }
  73.         ans = false;
  74.         do {
  75.             if (judgeCol()) {
  76.                 ans = true;
  77.                 break;
  78.             }
  79.         } while (next_permutation(idx, idx + m));
  80.         if (ans) {
  81.             printf("yes\n");
  82.         } else {
  83.             printf("no\n");
  84.         }
  85.     }
  87.     return 0;
  88. }

标程

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long LL;
  5. const int maxn = 1000000 + 100;
  6. const int maxnm = 100000 + 100;
  7. int T, n, m;
  8. bool ans;
  9. int nums[maxnm], degIn[maxnm], numsTmp[maxnm];
  10. int idxOfNum[maxn];
  11. int vis[maxn];
  12. vector<int> G[maxnm];
  13. queue<int> que;
  15. inline int id(int x, int y) {
  16.     return x * m + y;
  17. }
  19. bool topsort(int n) {
  20.     while (!que.empty()) {
  21.         que.pop();
  22.     }
  24.     for (int i = 0; i < n; ++i) {
  25.         if (degIn[i] == 0) {
  26.             que.push(i);
  27.         }
  28.     }
  30.     while (!que.empty()) {
  31.         int tmp = que.front();
  32.         que.pop();
  33.         for (auto pos: G[tmp]) {
  34.             --degIn[pos];
  35.             if (degIn[pos] == 0) {
  36.                 que.push(pos);
  37.             }
  38.         }
  39.     }
  41.     for (int i = 0; i < n; ++i) {
  42.         if (degIn[i] != 0) {
  43.             return false;
  44.         }
  45.     }
  46.     return true;
  47. }
  49. int main() {
  50.     scanf("%d", &T);
  52.     while (T--) {
  53.         scanf("%d%d", &n, &m);
  55.         memset(vis, -1, sizeof(vis));
  56.         for (int i = 0; i < n; ++i) {
  57.             for (int j = 0; j < m; ++j) {
  58.                 scanf("%d", &nums[id(i, j)]);
  59.            }
  60.         }
  62.         for (int i = 0; i < m; ++i) {
  63.             G[i].clear();
  64.             degIn[i] = 0;
  65.         }
  66.         for (int i = 0; i < n; ++i) {
  67.             for (int j = 0; j < m; ++j) {
  68.                 int x = nums[id(i, j)];
  69.                 if (x == 0) {
  70.                     continue;
  71.                 }
  72.                 vis[x] = i;
  73.                 idxOfNum[x] = j;
  74.             }
  75.             for (int j = 0; j < m; ++j) {
  76.                 int x = nums[id(i, j)];
  77.                 if (x == 0) {
  78.                     continue;
  79.                 }
  80.                 for (int k = x + x; k < maxn; k += x) {
  81.                     if (vis[k] == i) {
  82.                         G[idxOfNum[k]].push_back(j);
  83.                         ++degIn[j];
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.         if (!topsort(m)) {
  89.             printf("no\n");
  90.             continue;
  91.         }
  93.         for (int i = 0; i < n; ++i) {
  94.             G[i].clear();
  95.             degIn[i] = 0;
  96.         }
  97.         for (int j = 0; j < m; ++j) {
  98.             int cnt = 0;
  99.             for (int i = 0; i < n; ++i) {
  100.                 int x = nums[id(i, j)];
  101.                 if (x == 0) {
  102.                     continue;
  103.                 }
  105.                 numsTmp[cnt++] = x;
  106.                 idxOfNum[x] = i;
  107.             }
  108.             sort(numsTmp, numsTmp + cnt);
  109.             for (int i = 1; i < cnt; ++i) {
  110.                 G[idxOfNum[numsTmp[i]]].push_back(idxOfNum[numsTmp[i - 1]]);
  111.                 ++degIn[idxOfNum[numsTmp[i - 1]]];
  112.             }
  113.         }
  114.         if (!topsort(n)) {
  115.             printf("no\n");
  116.             continue;
  117.         }
  118.         printf("yes\n");
  119.     }
  121.     return 0;
  122. }

数据生成

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int maxn = 1000001;
  5. const int maxnm = 100000;
  6. const int testCases = 25;
  8. struct Set {
  9. public:
  10.     set<int> st;
  11.     vector<set<int>::iterator> vct;
  13.     void init() {
  14.         st.clear();
  15.         vct.clear();
  16.     }
  18.     void add(int x) {
  19.         pair<set<int>::iterator, bool> pr = st.insert(x);
  20.         vct.push_back(pr.first);
  21.         assert(st.size() == vct.size());
  22.     }
  24.     void del(int index) {
  25.         assert(!st.empty());
  26.         st.erase(vct[index]);
  27.         vct[index] = vct.back();
  28.         vct.pop_back();
  29.         assert(st.size() == vct.size());
  30.     }
  32.     int size() {
  33.         return vct.size();
  34.     }
  35. };
  37. vector<int> multiple[maxn];
  38. ofstream fout;
  39. int T, n, m;
  40. Set st;
  41. int finalNums[maxnm], nums[maxnm], tmpNums[maxnm];
  42. int degIn[maxn], originDegIn[maxn];
  43. int rowIndex[maxnm], colIndex[maxnm];
  45. void initDAG() {
  46.     for (int i = 1; i < maxn; ++i) {
  47.         for (int j = i + i; j < maxn; j += i) {
  48.             multiple[i].push_back(j);
  49.             ++originDegIn[j];
  50.         }
  51.     }
  52. }
  54. string numToStr(int x) {
  55.     string str;
  56.     while (x != 0) {
  57.         str = char('0' + x % 10) + str;
  58.         x /= 10;
  59.     }
  60.     return str;
  61. }
  63. string getFileName(int index) {
  64.     return "data/" + numToStr(index) + ".in";
  65. }
  67. int getRand(int l, int r) {
  68.     return rand() % (r - l + 1) + l;
  69. }
  71. void initDegIn() {
  72.     memcpy(degIn, originDegIn, sizeof(degIn));
  73. }
  75. inline int id(int x, int y) {
  76.     return x * m + y;
  77. }
  79. void randomShuffle() {
  80.     for (int i = 0; i < n; ++i) {
  81.         rowIndex[i] = i;
  82.     }
  83.     random_shuffle(rowIndex, rowIndex + n);
  84.     for (int j = 0; j < m; ++j) {
  85.         colIndex[j] = j;
  86.     }
  87.     random_shuffle(colIndex, colIndex + m);
  88.     for (int i = 0; i < n; ++i) {
  89.         for (int j = 0; j < m; ++j) {
  90.             finalNums[id(rowIndex[i], colIndex[j])] = nums[id(i, j)];
  91.         }
  92.     }
  93. }
  95. void genData() {
  96.     if (getRand(0, 1) == 0) {
  97.         // all in random, whether there is a solution or not
  98.         int last = 0;
  99.         for (int i = 0; i < n * m; ++i) {
  100.             finalNums[i] = getRand(last + 1, (i + 1) * (maxn / maxnm));
  101.             last = finalNums[i];
  102.         }
  103.         for (int i = 0; i < n * m / 3; ++i) {
  104.             finalNums[getRand(0, n * m - 1)] = 0;
  105.         }
  106.         random_shuffle(finalNums, finalNums + n * m);
  107.         return ;
  108.     }
  110.     st.init();
  111.     st.add(1);
  112.     initDegIn();
  113.     for (int j = 0; j < m; ++j) {
  114.         for (int i = 0; i < n; ++i) {
  115.             int index = getRand(0, st.size() - 1);
  116.             tmpNums[i] = *st.vct[index];
  117.             st.del(index);
  118.             for (auto mult: multiple[tmpNums[i]]) {
  119.                 --degIn[mult];
  120.                 if (degIn[mult] == 0) {
  121.                     st.add(mult);
  122.                 }
  123.             }
  124.         }
  125.         sort(tmpNums, tmpNums + n);
  126.         for (int i = 0; i < n; ++i) {
  127.             nums[id(i, j)] = tmpNums[i];
  128.         }
  129.     }
  130.     for (int i = 0; i < n * m / 2; ++i) {
  131.         nums[getRand(0, n * m - 1)] = 0;
  132.     }
  133.     randomShuffle();
  134. }
  136. void writeToFile() {
  137.     fout << n << " " << m << endl;
  138.     for (int i = 0; i < n; ++i) {
  139.         for (int j = 0; j < m; ++j) {
  140.             if (j != 0) {
  141.                 fout << " ";
  142.             }
  143.             fout << finalNums[i * m + j];
  144.         }
  145.         fout << endl;
  146.     }
  147. }
  149. void genDatas() {
  150.     fout << T << endl;
  151. }
  153. int main() {
  154.     srand(time(0));
  155.     initDAG();
  157.     // data in 20%, 1 <= T <= 10, 1 <= n,m <= 8
  158.     int one = testCases * 20 / 100;
  159.     for (int i = 1; i <= one; ++i) {
  160.         fout.open(getFileName(i));
  161.         T = 10;
  162.         fout << T << endl;
  163.         for (int j = 0; j < T; ++j) {
  164.             n = 8;
  165.             m = 8;
  166.             genData();
  167.             writeToFile();
  168.         }
  169.         fout.close();
  170.     }
  172.     // data in 80%, 1 <= T <= 10000, 1 <= n*m <= 100000
  173.     int two = testCases * 80 / 100;
  174.     for (int i = one + 1; i <= two; ++i) {
  175.         fout.open(getFileName(i));
  176.         T = 10;
  177.         fout << T << endl;
  178.         for (int j = 0; j < T; ++j) {
  179.             n = getRand(100, 1000);
  180.             m = getRand(maxnm / n - 10, maxnm / n);
  181.             genData();
  182.             writeToFile();
  183.         }
  184.         fout.close();
  185.     }
  187.     // data in last 20%, cornerCase
  188.     for (int i = two + 1; i <= testCases; ++i) {
  189.         fout.open(getFileName(i));
  190.         T = 5;
  191.         fout << T << endl;
  192.         for (int j = 0; j < T; ++j) {
  193.             switch (getRand(0, 2)) {
  194.             case 0:
  195.                 n = 1;
  196.                 m = maxnm;
  197.                 break;
  198.             case 1:
  199.                 n = maxnm;
  200.                 m = 1;
  201.                 break;
  202.             case 2:
  203.                 n = getRand(2, 5);
  204.                 m = maxnm / n;
  205.                 break;
  206.             }
  207.             genData();
  208.             writeToFile();
  209.         }
  210.         fout.close();
  211.     }
  213.     return 0;
  214. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注