[第一波模拟\day3\T2]{独立集}(bubble.cpp)

【问题描述】

有一天，一个名叫顺旺基的程序员从石头里诞生了。又有一天，他学会了冒泡排序和独立集。在一个图里，独立集就是一个点集，满足任意两个点之间没有边。于是他就想把这两个东西结合在一起。众所周知，独立集是需要一个图的。那么顺旺基同学创造了一个算法，从冒泡排序中产生一个无向图。

这个算法不标准的伪代码如下：

Pascal版本

C/C++版本

procedure bubblesortgraph(n, a[]) ：

/*输入：点数n，1到n的全排列a。

输出：一个点数为n的无向图G。*/

创建一个有n个点，0条边的无向图G。

repeat

swapped = false

for i 从 1 到 n-1 ：

if a[i] > a[i + 1] ：

在G中连接点a[i]和点a[i + 1]

交换a[i]和a[i + 1]

swapped = true

until not swapped

输出图G。

//结束。

void bubblesortgraph(n,a[])

//输入：点数n，1到n的全排列a

//输出：一个点数为n的无向图G

{ 创建一个有n个点，0条边的无向图G。

do{ swapped=false

for i 从1 到n-1

if(a[i]>a[i+1])

{ 在G中连接点a[i]和点a[i+1]

交换a[i]和a[i+1]

swapped =true

}

}while(swapped);

输出图G。

}

//结束。

那么我们要算出这个无向图G最大独立集的大小。但是事情不止于此。顺旺基同学有时候心情会不爽，这个时候他就会要求你再回答多一个问题：最大独立集可能不是唯一的，但有些点是一定要选的，问哪些点一定会在最大独立集里。今天恰好他不爽，被他问到的同学就求助于你了。

【输入】

输入包含两行，第一行为N，第二行为1到N的一个全排列。

【输出】

输出包含两行，第一行输出最大独立集的大小，第二行从小到大输出一定在最大独立集的点的编号。

【输入输出样例】

bubble.in

bubble.out

3 1 2

2 3

【样例说明】

如上图，顶点1和2一定在最大独立集中，其对应的编号为2和3。

【数据范围】

30%的数据满足 N<=16

60%的数据满足 N<=1,000

100%的数据满足 N<=100,000

【题解】

很经典的操作，求最长上升子序列的不动点和唯一点的交

#include <stdio.h>

#include <string.h>

#define RG register

#define oo 0x7fffffff

inline void read(RG int &x)

	{

	RG int c = getchar();

	while(c < '0' || c > '9') c = getchar();

	for(x = 0; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';

	}

int n, a[100003], d[100003], len, f[100003], g[100003], hash[100003];

int main()

	{

	freopen("bubble.in", "r", stdin), freopen("bubble.out", "w", stdout);

	read(n);

	for(RG int i = 1; i <= n; ++i) read(a[i]);

	for(RG int i = 1; i <= n; ++i)

		{

		if(a[i] > d[len]) d[++len] = a[i], f[i] = len;

		else

			{

			RG int L = 1, R = len, mid;

			while(L <= R)

				{

				mid = L + R >> 1;

				if(d[mid] >= a[i]) R = mid - 1;

				else L = mid + 1;

				}

			d[L] = a[i];

			f[i] = L;

			}

		}

	len = 0, d[0] = oo;

	for(RG int i = n; i; --i)

		{

		if(a[i] < d[len]) d[++len] = a[i], g[i] = len;

		else

			{

			RG int L = 1, R = len, mid;

			while(L <= R)

				{

				mid = L + R >> 1;

				if(d[mid] <= a[i]) R = mid - 1;

				else L = mid + 1;

				}

			d[L] = a[i];

			g[i] = L;

			}

		}

	for(RG int i = 1; i <= n; ++i)

		if(f[i] + g[i] == len + 1) ++hash[f[i]];

	printf("%d\n", len);

	for(RG int i = 1; i <= n; ++i)

		if(f[i] + g[i] == len + 1 && hash[f[i]] == 1)

			printf("%d ", i);

	fclose(stdin), fclose(stdout);

	return 0;

	}

巴特西