SimoneandGraphColoring

NC220422. SimoneandGraphColoring

描述

Simone, a student of Graph Coloring University, is interested in permutation. Now she is given a permutation of length $n$ , and she finds that if she connects each inverse pair, she will get a graph. Formally, for the given permutation, if $i<j$ and $a_i>a_j$ , then there will be an undirected edge between node $i$ and node $j$ in the graph.

Then she wants to color this graph. Please achieve poor Simone's dream. To simplify the problem, you just need to find a way of coloring the vertices of the graph such that no two adjacent vertices are of the same color and minimize the number of colors used.

输入描述

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. 

For each test case, the first line contains an integer , indicating the length of the permutation. 

The second line contains  integers , indicating the permutation.

It is guaranteed that the sum of  over all test cases does not exceed .

输出描述

For each test case, the first line contains an integer , the chromatic number(the minimal number of colors been used when coloring) of the graph.

The second line contains  integers , the color of each node.

Notice that  should satisfy the limit that .

If there are several answers, it is acceptable to print any of them.

示例1

输入:

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 1426ms, 内存消耗: 20984K, 提交时间: 2021-04-07 19:08:25

#include<bits/stdc++.h>
using namespace std;
int t, n, a, maxx, ans[1<<20], p, b[1<<20];
int main()
{
	for(cin >> t; t--; )
	{
		cin >> n;
		maxx = 0;
		for(int i = 0; i < n; i++)
		{
			cin >> a;
			p = lower_bound(b+1, b+1+maxx, a, greater<int>()) - b;
			b[p] = a;
			maxx = max(maxx, ans[i] = p);
		}
		cout << maxx << "\n";
		for(int i = 0; i < n; i++)
			cout << ans[i] << " \n"[i==n-1];
	}
}

上一题

下一题

详情