程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 2014 BNU 邀請賽A題(構造問題）

2014 BNU 邀請賽A題(構造問題）

編輯：C++入門知識

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;
}