https://codeforces.com/contest/1354

C2. Not So Simple Polygon Embedding

题意：一个正 2n 变形，求它的最小外接正方形边长，n为奇数。

正弦定理

asin⁡A=bsin⁡B=csin⁡C=2r=d\frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}=2r=d

做完C1就应该猜到C2里正方形一定是卡在某个点上的，所以直接画图。

以上面n=7时的正14边形为例。

先在小三角形里用正弦定理求得 x；再在a1，x所在的三角形里用正弦定理求得a1；最后在a2，x所在的三角形同理求得a2。结果就是a1+a2.

主要是要知道角P，即正方形卡在哪个点，画出n=5，7的图应该能发现n=5时共10个小角t，1/4个正方形占了10/4个t，而卡在的点又在1/4个正方形中间位置，所以猜P=n/4个t，然后发现要取整，那么再画出n=7，发现一个下取整一个上取整，所以就要找最近的整数，就是四舍五入了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const double PI = acos(-1);
const double eps = 1e-10;
int T;
int main() {
	scanf("%d", &T);
	while (T--) {
		double n;
		scanf("%lf", &n);
		double t = PI / n;
		double x = sin((PI - t) / 2) / sin(t);
		double p = round(n / 4)*t;
		double a1 = x * sin(p)/sin(PI / 4);
		double a2 = x * sin(PI / 2 - p)/sin(PI / 4);
		printf("%.12lf\n", a1 + a2);
	}
	return 0;
}

 

D. Multiset

 

题意：一个数组，两种操作：向数组中加入数字k，或者删去数组中第k小的数。最终要求给出任意一个数组中的数，或数组为空。

树状数组+二分

本题特别点就在于空间限制只有28M。

本来用权值线段树可以直接做，但是感觉空间不太够，所以还是用树状数组+二分找第k小的数，虽然时间多了个log，但还是够的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
int n, q, x, L, R;
int sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
	for (int i = p; i <= n; i += lowbit(i)) {
		sum[i] += x;
	}
}
int qry(int r) {
	int ans = 0;
	for (int i = r; i > 0; i -= lowbit(i)) {
		ans += sum[i];
	}
	return ans;
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		add(x, 1);
	}
	while (q--) {
		scanf("%d", &x);
		if (x >= 1 && x <= n)add(x, 1);
		else if (x < 0) {
			x = -x;
			L = 1, R = n;
			while (L < R) {
				int mid = (L + R) / 2;
				int t = qry(mid);
				if (t >= x)R = mid;
				else L = mid + 1;
			}
			add(L, -1);
		}
	}
	if (qry(n) == 0)puts("0");
	else {
		for (int i = 1; i <= n; i++)if (qry(i) > 0) {
			printf("%d\n", i);
			return 0;
		}
	}
	return 0;
}

 

E. Graph Coloring

 

题意：给定一个无向图，给每个点染色1，2，或3。要求每条边的两个端点的颜色的差的绝对值为1，并且颜色为1，为2，为3的点的个数分别为n1，n2，n3，给出方案，或不行。

二分图染色+dp

1只能和2连，3也只能和2连，2能和1，3连。1不能和3连。

所以可以把1，3看作同一类，2看作另一类，在类内不能连边，类间连边。所以可以变成二分图染色。

对于每个连通分量染色后，得到每个分量的两类的点数。

所以要在每个分量中选择一类染色1，3，另一类染色2。

这里就可以dp了，dp[i][j]=0/1dp[i][j]=0/1 表示第1到第i类，共有j个点染色1，是否可行。两个转移。

同时还要记录转移的父亲，因为最后要输出方案。

都染了1或者2之后，因为还要染3，所以从颜色为1的点里选出n3个染3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
int n, m;
int n1, n2, n3;
int tot, cnt[N][3], dp[N][N];
int col[N], ans[N];
vector<int>G[N];
vector<int>cc[N];
bool bipar(int u, int c) {	//1,2
	col[u] = c;
	cnt[tot][c]++;
	cc[tot].push_back(u);
	for (int v : G[u]) {
		if (col[v] == col[u])return false;
		if (!col[v]) {
			if (!bipar(v, 3 - c))return false;
		}
	}
	return true;
}
int main() {
	scanf("%d%d", &n, &m);
	scanf("%d%d%d", &n1, &n2, &n3);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!col[i]) {
			tot++;
			if (!bipar(i, 1)) { puts("NO"); return 0; }
		}
	}
	int N1 = n1 + n3;
	dp[0][0] = 1;
	for (int i = 1; i <= tot; i++) {
		for (int j = 0; j <= N1; j++) {
			if (dp[i - 1][j]) {
				dp[i][j + cnt[i][1]] = 1;
				dp[i][j + cnt[i][2]] = 2;
			}
		}
	}
	if (dp[tot][N1])puts("YES");
	else { puts("NO"); return 0; }
	for (int i = tot; i >= 1; i--) {
		if (dp[i][N1] == 1) {
			for (int u : cc[i]) {
				if (col[u] == 1)ans[u] = 1;
				else ans[u] = 2;
			}
			N1 -= cnt[i][1];
		}
		else {
			for (int u : cc[i]) {
				if (col[u] == 2)ans[u] = 1;
				else ans[u] = 2;
			}
			N1 -= cnt[i][2];
		}

	}
	for (int i = 1; i <= n && n3; i++) {
		if (ans[i] == 1)ans[i] = 3, n3--;
	}
	for (int i = 1; i <= n; i++)printf("%d%s", ans[i], i == n ? "\n" : "");
	return 0;
}