夏晓光(loveJY)的博客

SDOI2019D2T1..吗?

唔母,他D几T几不重要,重要的是咕咕咕咕咕咕

这当然是假的了,我怎么可能咕,强力推荐<<这就是僵尸啊>>两季

他的联系薄上有 $n$ 位好友，他们两两之间或者互相认识，或者互相不认识。小 Q 希望在周六办一个热闹的聚会，再在周日办一个尴尬的聚会。

• 一场热闹度为 $p$ 的聚会请来了任意多位好友，对于每一位到场的好友来说都有至少 $p$ 位他认识的好友也参加了聚会，且至少对于一位到场的好友来说现场恰好有 $p$ 位他认识的好友；
• 一场尴尬度为 $q$ 的聚会请来了恰好 $q$ 位好友，且他们两两互不认识。

两场聚会可能有重复的参与者，联系薄上也有可能有某些好友同时缺席了两场聚会。

小 Q 喜欢周六聚会的热闹度 $p$ 与周日聚会的尴尬度 $q$ 之间满足：$\left\lfloor \frac{n}{p+1} \right\rfloor! \le $ 且 $\left\lfloor \frac{n}{q+1} \right\rfloor! \le $

请帮助小 Q 找出一个可行的邀请方案。

这个题意其实并不需要简化,因为很容易读懂

首先,看到这个尴尬的聚会,一眼就知道是求一个独立集,这好像是NPC问题啊,看看有没有什么丢掉的条件?

好像只有一个人数的限制QAQ,最大独立集肯定求不了,所以我们要尽可能的求个小的独立集,由于人数的限制可以变成乘起来大于n,所以我们第一问的p要尽可能的大

首先我们按照相识关系建立一个图,那么第一问就是要保留一个最小度数至少为p的子图,显然最后一个限制没啥意义,因为既然最小度数都有了.....

这个显然可以二分一个最小度数,然后把原图中度数小于最小的度数的点删除,再看剩下的点最小的度数是否大于p.不大于就是继续删

最后要么存在一些点,要么删光,就对应成立不成立...

还有一个是链表的做法,你会发现我们最后的答案图一定满足所有点的最小度数作为答案对吧,如果我们想要答案变大首先要把那些最小度数的点全部删掉,然后再对应的减一下相邻点的度数,得到新的答案,重复这个过程直到没有点,那么过程中所有答案得到最大值就是答案了

正确性显然吧

有了操作1的p,操作2最小q直接枚举得到,然后我们随机一个序列,按这个序列的顺序去保存独立集,这样一个玄学随机算法就可以过掉此题,毕竟他出的题复杂度和数据范围不严格一致,所以我们也概率正确

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#define add(x,y) (ct(x,y),ct(y,x))
using namespace std;

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = BUF_SIZE + buf, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		register char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;
const int MAXN = 3e5;
int T, n, m;
int to[MAXN], nxt[MAXN], home[MAXN], tot, ccnt, deg[MAXN], cnt[MAXN], ansp, ansq;
int ans1[MAXN], ans2[MAXN], ans3[MAXN];
inline void ct(int x, int y) {
	//printf("%d %d\n", x, y);
	++deg[x];
	++ccnt;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}
int Q[MAXN], ql, qr;
inline int check(int v) {
	int siz = n, i, x, y, p;
	ql = 1, qr = 0;
	for(i = 1; i <= n; ++i) {
		if(deg[i] < v)ans3[i] = 0, Q[++qr] = i, --siz;
		else ans3[i] = 1;

	}
	while(ql <= qr && siz > v) {
		x = Q[ql], ++ql;
		//printf("%dQWE\n", x);
		for(p = home[x]; p; p = nxt[p]) {
			if(ans3[y = to[p]]) {
				--deg[y];
				if(deg[y] < v) {
					ans3[y] = 0;
					Q[++qr] = y;
					--siz;
				}
			}
		}
	}
	memcpy(deg, cnt, (n + 2) *sizeof(int));
	if(siz > v) {
		memcpy(ans1, ans3, (n + 2) *sizeof(int));
		return 1;
	}
	return 0;
}
int id[MAXN], vis[MAXN];
int main() {
	//freopen("test.in", "r", stdin);
	srand(time(NULL));
	int i, j, x, y, tot, p;
	T = read();
	while(T -- > 0) {
		n = read();
		m = read();
		ccnt = 0;
		memset(home, 0, (n + 2) *sizeof(int));
		memset(deg, 0, (n + 2) *sizeof(int));
		//任何时间复杂度都不能放过
		while(m-- > 0)x = read(), y = read(), add(x, y);
		memcpy(cnt, deg, (n + 2) *sizeof(int));
		//for(int i = 1; i <= n; ++i) {
		//	printf("%d\n", deg[i]);
		//}
		int l = 1, r = n - 1, mid;
		ansp = 0;
		while(l <= r) {
			mid = (l + r) >> 1;
			if(check(mid)) {
				ansp = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		tot = 0;
		for(i = 1; i <= n; ++i) {
			if(ans1[i])
				++tot;
			//printf("%d %d?\n", i, ans1[i]);
		}
		printf("%d ", tot);
		for(i = 1; i <= n; ++i)
			if(ans1[i])
				printf("%d ", i);
		puts("");
		//printf("%d\n", ansq);
		for(i = 1; i <= n; ++i) {
			if(n / (ansp + 1) <= i && n / (i + 1) <= ansp) {
				ansq = i;
				break;
			}
		}
		if(ansq == 1) {
			printf("1 1\n");
			continue;
		}
		if(ansq == n) {
			printf("%d ", n);
			for(i = 1; i <= n; ++i)printf("%d ", i);
			puts("");
		} else {
			for(i = 1; i <= n; ++i)id[i] = i;
			while(1) {
				tot = 0;
				random_shuffle(id + 1, id + n + 1);
				memset(vis, 0, (n + 2) *sizeof(int));
				memset(ans2, 0, (n + 2) *sizeof(int));
				for(i = 1; i <= n && tot < ansq; ++i) {
					if(!vis[x = id[i]]) {
						ans2[x] = 1;
						++tot;
						for(p = home[x]; p; p = nxt[p])vis[to[p]] = 1;
					}
				}
				if(tot == ansq) {
					printf("%d ", tot);
					for(i = 1; i <= n; ++i)if(ans2[i])printf("%d ", i);
					puts("");
					break;
				}
			}
		}
	}
	return 0;
}