程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BNUOJ 34981 A Matrix

BNUOJ 34981 A Matrix

編輯:C++入門知識

BNUOJ 34981 A Matrix

題目地址:BNUOJ 34981

題意:
給你一個把一個排列放到矩陣裡面的算法和矩陣,要你從矩陣寫出排列。
如果答案有多個,輸出翻轉後字典序最大的那個。

分析:
想了半天只能想到鏈表版的,而且很可能TLE,看了帆神的題解後豁然開朗..Orz..

代碼:

/*
*  Author:      illuz 
*  File:        a.cpp
*  Create Date: 2014-05-29 21:05:38
*  Descripton:   
*/

#include 
#include 
using namespace std;

const int N = 1e5 + 10;
int t, n, m, p[N], tmp, ans[N], cnt;
bool flag;
vector v[N];

void dfs(int r, int val) {
	if (r >= m || p[r] - 1 < 0 || v[r][p[r] - 1] < val)
		return;
	ans[cnt++] = v[r][p[r] - 1];
	dfs(r + 1, v[r][p[r] - 1]);
	p[r]--;
}

int main()
{
	scanf("%d", &t);
	for (int cas = 1; cas <= t; cas++) {
		printf("Case #%d:", cas);

		scanf("%d%d", &n, &m);
		flag = false;

		for (int i = 0; i < m; i++) {
			v[i].clear();
			scanf("%d", &p[i]);

			for (int j = 0; j < p[i]; j++) {
				scanf("%d", &tmp);
				v[i].push_back(tmp);
				if (j > 0 && v[i][j] < v[i][j - 1])
					flag = true;
			}

			if (i > 0 && v[i][0] < v[i - 1][0])
				flag = true;
		}

		if (flag) {
			puts(" No solution");
			continue;
		}

		cnt = 0;
		for (int i = p[0] - 1; i >= 0; i--) {
			ans[cnt++] = v[0][i];
			dfs(1, v[0][i]);
		}

		if (cnt != n) {
			puts(" No solution");
			continue;
		}
		for (int i = cnt - 1; i >= 0; i--)
			printf(" %d", ans[i]);
		puts("");
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved