https://vjudge.net/contest/438452

E - Counting Cliques

 

题意：给定一张无向图，找出点数等于 S 的团的个数。N ≤ 100,M ≤ 1000,2 ≤ S ≤ 10，每点的度不超过20.

暴力

只存小点到大点的边。从小到大枚举每点，dfs枚举与它相连的点集的子集，判断是否满足条件。

由于点数不超过100，则度为20的点最多有5个，再推下去能发现度为19的点也不超过5个，以此类推，如果枚举点集则最多是 5⋅(220+219+⋯ )=5⋅(221−1)5\cdot(2^{20}+2^{19}+\cdots)=5\cdot(2^{21}-1)。每次暴力双重循环判断是否为团，复杂度为 S2/2S^2/2，则总共为 5⋅221⋅50=5⋅1085\cdot2^{21}\cdot50=5\cdot10^8，再稍微剪下枝，当即使后面所有点都选上也不够 S 时，提前结束。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n, m, s;
vector<int>G[N], vc;
int ans;
int w[110][110];
void dfs(vector<int>& G, int dep) {
	if ((int)vc.size() == s) {
		int flg = 1;
		for (int i = 0; i < (int)vc.size() && flg; i++) {
			for (int j = i + 1; j < (int)vc.size() && flg; j++) {
				if (!w[vc[i]][vc[j]]) {
					flg = 0;
					break;
				}
			}
		}
		ans += flg;
		return;
	}
	if ((int)vc.size() + (int)G.size() - dep + 1 < s)return;
	vc.push_back(G[dep - 1]);
	dfs(G, dep + 1);
	vc.pop_back();
	dfs(G, dep + 1);
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &s);
		for (int i = 1; i <= n; i++)G[i].clear();
		memset(w, 0, sizeof(w));
		for (int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			if (u > v)swap(u, v);
			G[u].push_back(v);
			w[u][v] = w[v][u] = 1;
		}
		for (int i = 1; i <= n; i++) {
			sort(G[i].begin(), G[i].end());
			G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
		}
		ans = 0;
		for (int i = 1; i <= n; i++) {
			vc.clear();
			vc.push_back(i);
			dfs(G[i], 1);
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

H - Guessing the Dice Roll

 

题意：有 nn 个人，一个 6 面的骰子，每人给出一个长为 mm 的预测序列。开始投骰子，当最近 mm 次结果恰好为某人的预测序列时，立即结束游戏，这个人获胜。问每个人获胜的概率分别是多少。

AC自动机+高斯消元

把所有人的预测序列插入ac自动机，则每个节点可以看作一个状态，其中叶节点节点就是终止状态，这些节点不能再向外走了，因为此时已经结束游戏了。

对于一个状态 vv，走到它的概率等于 ∑u16prob[u]\sum\limits_u \frac{1}{6}prob[u]，其中 uu 能够转移到 vv。

能够发现所有状态都是由初始状态 0 走到的，所以 0 的概率必须是 1。这也隐含了所有终止状态的概率之和为 1，因为游戏会一直进行到结束，也就是说从初始状态出发，一定会停在某个终止状态。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;

double A[110][110], x[110];
void Gauss(int ne, int nv)
{
	int i, j;
	for (int ce = 0, cv = 0; cv < ne && cv < nv; ++ce, ++cv)
	{
		int te = ce;
		for (i = ce; i < ne; ++i)
			if (fabs(A[i][cv]) > fabs(A[te][cv]))
				te = i;
		if (te != ce)
		{
			for (j = cv; j <= nv; ++j)
				swap(A[ce][j], A[te][j]);
		}
		double bas = A[ce][cv];
		for (j = cv; j <= nv; ++j)
			A[ce][j] /= bas;
		for (i = ce + 1; i < ne; ++i)
		{
			for (int j = cv + 1; j <= nv; ++j)
				A[i][j] -= A[i][cv] * A[ce][j];
		}
	}
	for (i = ne - 1; i >= 0; --i)
	{
		x[i] = A[i][nv];
		for (j = i + 1; j < nv; ++j)
			x[i] -= x[j] * A[i][j];
		x[i] /= A[i][i];
	}
}
struct AC{
	int tr[N][26], tot;
	int e[N], fail[N];
	void init() {
		for (int i = 0; i <= tot; i++) {
			e[i] = fail[i] = 0;
			for (int j = 1; j <= 6; j++)tr[i][j] = 0;
		}
		tot = 0;
	}
	void insert(int *s, int n, int id) {
		int u = 0;
		for (int i = 1; i <= n; i++) {
			if (!tr[u][s[i]]) tr[u][s[i]] = ++tot;
			u = tr[u][s[i]];
		}
		e[u] = id;
	}
	queue<int> q;
	void build() {
		for (int i = 0; i < 26; i++)
			if (tr[0][i]) q.push(tr[0][i]);
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (tr[u][i]) {
					fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
				}
				else
					tr[u][i] = tr[fail[u]][i];
			}
		}
	}
}ac;
int T;
int n, m;
int t[N];
double ans[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				scanf("%d", &t[j]);
			}
			ac.insert(t, m, i);
		}
		ac.build();
		memset(A, 0, sizeof(A));
		A[0][ac.tot + 1] = -1;
		for (int i = 0; i <= ac.tot; i++) {
			A[i][i] = -1;
			if (ac.e[i])continue;
			for (int j = 1; j <= 6; j++) {
				A[ac.tr[i][j]][i] += 1.0 / 6.0;
			}
		}
		Gauss(ac.tot + 1, ac.tot + 1);
		for (int i = 1; i <= ac.tot; i++) {
			if (ac.e[i])ans[ac.e[i]] = x[i];
		}
		for (int i = 1; i <= n; i++)printf("%.6lf%c", ans[i], " \n"[i == n]);
		ac.init();
	}
	return 0;
}

 

G - Do not pour out

 

题意：给定一个底面半径为 11，高为 22 的圆柱体水杯，其中有高为 dd 的水，问倾斜到将要溢出时，水平水面的面积。

二分+积分

说是积分但其实并没有辛普森积分，纯手算。

两种情况：1. 倾斜后水能覆盖杯底。2. 水不能覆盖杯底。

对于第一种情况：水面是个椭圆，算出开始倾斜的位置后，用椭圆面积公式直接算出水面面积。

对于第二种情况：先二分出倾斜到溢出时杯底水的高度，再算出水面面积。

在二分时需要计算已知杯底水高度时水的体积。设杯底水的高度为 HH，水的体积 VV。

当 H≤1H\le 1 时有

V(H)=∫02arccos⁡(1−Hx2)−(1−Hx2)2⋅Hx2−(Hx2)2 dx=2H⋅[2H−H2⋅(1−23H+13H2)−(1−H)arccos⁡(1−H)]\begin{align} V(H)&=\int_0^2 \arccos(1-\frac{Hx}{2})-(1-\frac{Hx}{2})\sqrt{2\cdot\frac{Hx}{2}-(\frac{Hx}{2})^2} \,{\rm d}x\\ &=\frac{2}{H}\cdot [\sqrt{2H-H^2}\cdot(1-\frac{2}{3}H+\frac{1}{3}H^2)-(1-H)\arccos(1-H)]\\ \end{align}

当 H>1H>1 时有

V′(H)=V(2−H)+2Hπ(H−1)V'(H)=V(2-H)+\frac{2}{H}\pi(H-1)\\

二分出 HH 后，还要积分算出水面面积。

这里积分的时候要注意水面是斜的，不能直接乘  dx\,{\rm d}x。

当 H≤1H\le 1 时有

S(H)=2⋅∫012⋅Hx2−(Hx2)2⋅4+H22 dx=2H⋅4+H22⋅[arccos⁡(1−H)−(1−H)⋅2H−H2]\begin{align} S(H)&=2\cdot\int_0^1 \sqrt{2\cdot \frac{Hx}{2}-(\frac{Hx}{2})^2}\cdot\frac{\sqrt{4+H^2}}{2}\,{\rm d}x\\ &=\frac{2}{H}\cdot \frac{\sqrt{4+H^2}}{2}\cdot [\arccos(1-H)-(1-H)\cdot\sqrt{2H-H^2}]\\ \end{align}

当 H>1H>1 时有

S′(H)=2S(1)−S(2−H)S'(H)=2S(1)-S(2-H)\\

注意特判 H=1H=1 的情况。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const double eps = 1e-8;
const double PI = acos(-1);
int T;
double f(double h) {
	return sqrt(2.0 * h - h * h)*(1.0 - 2.0 / 3.0 * h + 1.0 / 3.0 * h*h) - (1.0 - h)*acos(1.0 - h);
}
double V(double h) {
	if (h <= 1)return 2.0/h*f(h);
	else return 2.0 / h * (f(2 - h) + PI * (h - 1));
}
double g(double h) {
	return acos(1.0 - h) - (1.0 - h)*sqrt(2.0 * h - h * h);
}
double S(double h) {
	if (h <= 1)return 2.0 / h * sqrt(4 + h * h) / 2.0 * g(h);
	else return 2.0 / h * sqrt(4 + h * h) / 2.0 * (2 * g(1) - g(2 - h));
}
int main() {
	scanf("%d", &T);
	while (T--) {
		double d;
		scanf("%lf", &d);
		if (d >= 1) {
			double x = 4 - 2 * d;
			printf("%.5lf\n", PI / 2 * sqrt(4 + x * x));
		}
		else {
			double L = 0, R = 2.0;
			while (R - L > eps) {
				double mid = (L + R) / 2;
				if (V(mid) > PI*d)R = mid;
				else L = mid;
			}
			if (L < eps)puts("0.00000");
			else printf("%.5lf\n", S(L));
		}
	}
	return 0;
}