2017CCPC网络赛

solved	A	B	C	D	E	F	G	H	I	J	K
4 / 11	O	·	O	O	O	·	·	·	·	·	·

• O：比赛时通过
• Ø：赛后通过
• !：比赛时尝试了未通过
• ·：比赛时未尝试

REPLY： 寒假在家的状态太差了，题目稍难一点就自闭得做不进题目

比赛链接

A - Vertex Cover

solved by lllllan. 04:51(+5)

题意： 最小点覆盖的问题，题目中给出贪心思想的程序，（显然贪心是不对的），要求构造一份数据（简单无向图，包含输入输出）。条件是该图在贪心程序下求得的答案，是正解的三倍及以上。

题解： 先看懂题目中的贪心程序，是优先处理度数大、编号大的点。顺着他的思路，优先处理的点都是最小点覆盖的答案集，那我们要构造的图，就要和他恰恰相反，让他优先处理的点，偏偏不在答案内。

• 从二分图入手，划分成左右两块。假设左边$n$个点，就是正解的所有点。而右边的所有点，则是他贪心会去选择的点。
• 我们的目标，就是让右边，有$3n$及以上的点

前面两点其实是在明确问题。就是要逆着贪心程序，去构造一个图，使得贪心答案是正确答案的三倍及以上。

• 思考：如果左边$n$个点，编号$1$到$n$；右边也是$n$个点，编号则是$n+1$到$2n$。然后左右两边的点恰好两两相连。此时按照贪心程序，则会优先处理右边的$n$个点，答案为$n$.
• 而我们要尝试往右边点集加入更多的点，条件是，加入一些点以后，贪心程序依然优先处理右边点集中的点。以前面 $n$对$n$并且两两相连的二分图为条件 ，开始往右边点集加入点。
• 比如在右边点集加入一个点，连接左边点集的两个点。此时左边部分有两个度数为2的点，右边部分有一个度数为2的点。按照贪心程序，会优先处理右边部分编号较大的点。处理该点并删除边之后，左右两边又恢复成都是度数为1的点，之后还是仍然会优先处理右边点集。而这样度数为2的点，我们可以加入$n/2$个
• 同理，现在向右边点集中加入一个点，连接左边点集的三个点。此时左边部分又三个度数为3的点，右边部分只有一个度数为3的点。按照贪心程序，处理完右边部分度数为3的点之后，两边就只剩度数为2和度数为1的点了。而这样度数为3的点，我们可以加入$n/3$个
• 以此类推，我们依次加入度数为2的点、度数为3，直到度数为n，使得右边点集中有足够多的点，到达左边点数的三倍即可。

AC代码

#include<bits/stdc++.h>
using namespace std;

int n, m, sum;

int main () {
	n = 20, sum = n + 1;
	
	printf("86 339\n");
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n - (n % i); ++j) {
			printf("%d %d\n", j, sum, m++);
			if (j % i == 0) sum++;
		}
	}
	
//	printf("m = %d\n", m);
	printf("%d\n", n);
	for (int i = 1; i <= n; ++i) printf("%d\n", i);
	return 0;
}

C - Friend-Graph

solved by lllllan. 00:18(+1)

题意： 一个n个人的团队，如果有3个人相互之间都不认识，或者相互之间全都认识，则为badteam，剩下所有情况都属于goodteam。【虽然题意奇奇怪怪的，但确实就是这样。

题解： 无他，但暴力尔。【直接三个for循环嵌套起手，孩怕TLE，结果MLE了。

题目卡的点比较刁钻，不卡暴力超时，而是int占内存太大。需要把数组定义成bool才行。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 10;

int _, n;
bool a[maxn][maxn];

void run () {
	memset(a, 0, sizeof a);
	
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			int x; scanf("%d", &x);
			a[i][j] = a[j][i] = x;
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			for (int k = j + 1; k <= n; ++k) {
				if (a[i][j] && a[i][k] && a[j][k] || (!a[i][j] && !a[i][k] && !a[j][k]))
					return (void)(printf("Bad Team!\n"));
			}
		}
	}
	printf("Great Team!\n");
}

int main () {
	scanf("%d", &_);
	while (_--) run();
	return 0;
}

E - CaoHaha’s staff

solved by llllan. 02:01(+)

题意： 要求每次只能画长度为$1$或长度为$\sqrt{2}$边，要求画出的图形面积为$s$。求满足面积条件最少需要多少条边。

题解： 【说实话样例都画了好久

• 计算k条边最大能画多少面积，记录在$s[]$
• 理论上，只要k条边能画至少s面积的图形，小于s的面积，我们用不着直到图形长什么样，都应该是能过满足的。
• 提前计算好$s[]$之后，二分计算最小边数。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

int _, n;
ll s[maxn];

void init () {
	for (ll i = 4; i < maxn; ++i) {
		if (i % 4 == 0) s[i] = (i / 4) * (i / 4) * 2;
		if (i % 4 == 1) s[i] = s[i - 1] + i / 4 - 0.5;
		if (i % 4 == 2) s[i] = (i / 4) * (i / 4 + 1) * 2;
		if (i % 4 == 3) s[i] = (i / 4 + 1) * (i / 4 + 1) * 2 - i / 4;
	}
}

void run () {
	scanf("%d", &n);
	int l = 4, r = maxn;
	while (l < r) {
		int mid = (l + r) / 2;
		if (s[mid] >= n) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", r);
}

int main () {
	init ();
	scanf("%d", &_);
	while (_--) run();
	return 0;
}