A Matrix

题意：按照题目中给定的方法，给你一个矩阵，求出变换出该矩阵的字符串
思路：构造问题，在纸上多画几组就能发现，每次必须从上往下找到一条路径，最后输出这些路径，按照开头最大的最晚输出，找的过程中只要不断往下一层找一个大的即可，并且如果一开使有一行是非递增就是错误
代码：

#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; const int N = 100005; int t, n, m, ans[N], an, flag, num[N]; vector
       
         g[N]; void find(int i, int j) { if (i + 1 != m && g[i + 1][num[i + 1] - 1] > g[i][j]) { if (num[i + 1] - 1 < 0) return; ans[an++] = g[i + 1][num[i + 1] - 1]; find(i + 1, num[i + 1] - 1); num[i + 1]--; } } bool solve() { if (flag) return false; an = 0; int len = g[0].size(); for (int j = len - 1; j >




= 0; j--) { ans[an++] = g[0][j]; find(0, j); } return an == n; } int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); flag = 0; for (int i = 0; i < m; i++) { g[i].clear(); scanf("%d", &num[i]); int tmp; for (int j = 0; j < num[i]; j++) { scanf("%d", &tmp); if (j && tmp < g[i][j - 1]) flag = 1; g[i].push_back(tmp); } } printf("Case #%d:", ++ cas); if (!solve()) printf(" No solution\n"); else { for (int i = n - 1; i >= 0; i--) printf(" %d", ans[i]); printf("\n"); } } return 0; }

2014 BNU 邀请赛A题(构造问题）

A Matrix