个人测试

发表于 分类于

Problem L. Wizards Unite

Statement

给 $1$ 把金钥匙（可多次使用的钥匙），$k$ 把银钥匙（只能用一次）。给 $n$ 个箱子，每个箱子有一个打开所需时间 $t_i$（跟钥匙类型无关）。一把钥匙同时只能开一个箱子，问打开所有箱子所需的最小总时间。有 $z$ 组测试数据。

$0 \leq k < n \leq 10^5$

$0 \leq t_i \leq 10^9$

$\sum n \leq 10^6$

Solution

本场最简单的题。

不失一般性，我们认为所有箱子按 $t_i$ 排升序。显然方案只能是 $k$ 把银钥匙都用来开一个箱子，金钥匙开其他所有箱子，而答案就是以下两者中的较大值：用银钥匙的箱子中耗时最长的一个的耗时；金钥匙开其他所有箱子的耗时之和。

注意到答案无论如何也不可能小于 $t_n$，也就是说用银钥匙开 $t_n$ 箱子一定不会浪费时间。那么为了令金钥匙耗时之和尽可能小，实际上 $k$ 把银钥匙开的就是最右边的 $k$ 个箱子，于是答案就很显然了。时间复杂度 $O(n \log n)$。

我读的，读完第一反应居然是二分答案找一个分界点使得银钥匙开的是这个分界点左边的 $k$ 个……要说的话虽然更慢（我写的是 $O(n \log^2 n)$……）但是结果也是对的，但我一个大于写成了大于等于交了一发 WA……签到题都 WA，很惭愧……

下面的代码还是赛中交的二分答案版本，反正正解上面说的很清楚了，也很简单，懒得再写了。

Code (By Nanako)

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
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main0 ();
int main () {
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
	#endif
	ios::sync_with_stdio(false);
	clock_t start, end;
	// start = clock();
	main0();
	// end = clock();
	// cout << (end - start) << endl;
	#ifndef ONLINE_JUDGE
		fclose(stdin);
	#endif
	return 0;
}
 
const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int N = 2e5 + 5;
const int M = 1e5;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);
 
ll a[N];
 
int main0 () {
	MULTI {
		int n, k;
		cin >> n >> k;
		ll sum = 0;
		for (int i = 1;i <= n;++i) {
			cin >> a[i];
			sum += a[i];
		}
		sort(a + 1, a + n + 1);
		
		ll l = 0, r = sum;
		while (l <= r) {
			ll mid = (l + r + 1) / 2;
			int pos = upper_bound(a + 1, a + n + 1, mid) - a; pos--;
			ll silver = 0;
			for (int i = max(1, pos - k + 1);i <= pos;++i) silver += a[i];
			//cout << l << ' ' << r << ' ' << mid << ':' << pos << ' ' << silver << endl;
			if (sum - silver > mid) l = mid + 1;
			else r = mid - 1;
		}
		cout << l << endl;
	}
}

发表于 分类于 ，

Problem J. Space Gophers

Statement

有一个由边长为 $1$ 的小正方体组成的边长为 $10^6$ 的实心正方体。在其中挖 $n$ 条隧道，每条隧道用 $(-,y_i,z_i)$ 或 $(x_i,-,z_i)$ 或 $(x_i,y_i,-)$ 表示。挖隧道的含义是，指定其中两个维度的坐标，沿平行于另一个维度轴线的方向把 $10^6$ 个方块拿走。挖完 $n$ 条隧道之后，$q$ 次询问两个点 $(s_x,s_y,s_z)$ 和 $(t_x,t_y,t_z)$ 是否可以通过若干条隧道连通。保证 $s$ 和 $t$ 处于隧道中。有 $z$ 组测试数据。

$1 \leq z \leq 6$

$1 \leq n \leq 3 \times 10^5$, $1 \leq x_i,y_i,z_i \leq 10^6$

$1 \leq q \leq 5 \times 10^5$, $1 \leq s_x,s_y,s_z,t_x,t_y,t_z \leq 10^6$

Solution

clp 单切之前大致跟我讲了一下做法。实际上两条隧道连通 iff 某一个维度坐标相等或相差 1，于是我们要做的事情就是把所有这样的隧道对找出来，在并查集上 merge 起来。

这个东西说起来简单，实现起来就比较呕吐……具体还是看代码吧……似乎是这篇文章里最长的代码

Code (By clp012345)

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <bits/stdc++.h>
 
#define FOE(i, s, t) for (int i = s; i <= t; i++)
#define FOR(i, s, t) for (int i = s; i < t; i++)
#define K 5000001
#define D 1000000
#define mp make_pair
#define pb push_back
#define LL long long
 
using namespace std;
 
int nxt[K], sz[K];
 
int par(int u) {
	return (nxt[u] == u ? u : nxt[u] = par(nxt[u]));	
}
 
void merge(int u, int v) {
	int s1 = par(u);
	int s2 = par(v);
	
	if (s1 == s2) return;
	
	if (sz[s1] > sz[s2]) swap(s1, s2);
	
	nxt[s1] = s2;
	sz[s2] += sz[s1];
}
 
int n;
 
vector<int> x[D + 100], y[D + 100], z[D + 100];
 
int goodX[D], goodY[D], goodZ[D];
 
map<pair<pair<int, int>, int>, int > M;
 
int px[D], py[D], pz[D];
 
int seek(int x, int y, int z) {
//	printf("seek %d %d %d ? %d %d %d \n", x, y, z, M[mp(mp(x, y), -1)], M[mp(mp(x, -1), z)], M[mp(mp(-1, y), z)]);
	int a1 = M[mp(mp(x, y), -1)];
	if (a1) return a1;
	
	int a2 = M[mp(mp(x, -1), z)];
	
	if (a2) return a2;
	return M[mp(mp(-1, y), z)];
}
 
int q;
 
void solve() {
	scanf("%d", &n);
 
	M.clear();	
	
	FOE(i, 1, D) {
		x[i].clear(); y[i].clear(); z[i].clear();	
	}
	
	FOE(i, 1, n) {
		scanf("%d%d%d", &px[i], &py[i], &pz[i]);
		
		M[mp(mp(px[i], py[i]), pz[i])] = i;
		
		if (px[i] != -1) {
			x[px[i]].pb(i);
		}
		
		if (py[i] != -1) {
			y[py[i]].pb(i);	
		}
		
		if (pz[i] != -1) {
			z[pz[i]].pb(i);	
		}
	}
	
	FOE(i, 1, n + 3 * D) {
		nxt[i] = i;
		sz[i] = 1;	
	}
	
	FOE(i, 1, n) {
		if (pz[i] == -1) {
			for (int dx = 0; dx <= 1; dx++) for (int dy = 0; dy <= 1; dy++) if (abs(dx) + abs(dy) == 1) {
				int id2 = M[mp(mp(px[i] + dx, py[i] + dy), -1)];
				
				if (id2) merge(id2, i);
			}
		}
		if (py[i] == -1) {
			for (int dx = 0; dx <= 1; dx++) for (int dz = 0; dz <= 1; dz++) if (abs(dx) + abs(dz) == 1) {
				int id2 = M[mp(mp(px[i] + dx, -1), pz[i] + dz)];
				
				if (id2) merge(id2, i);
			}
		}
		if (px[i] == -1) {
			for (int dy = 0; dy <= 1; dy++) for (int dz = 0; dz <= 1; dz++) if (abs(dy) + abs(dz) == 1) {
				int id2 = M[mp(mp(-1, py[i] + dy), pz[i] + dz)];
				
				if (id2) merge(id2, i);
			}
		}
	}
	
	FOE(i, 1, D) {
		int g1 = 0, g2 = 0;
		FOR(j, 0, x[i].size()) {
			int id = x[i][j];
			
			if (py[id] == -1) g1 = 1;
			if (pz[id] == -1) g2 = 1;
		}
		
		goodX[i] = g1 * 2 + g2;
	}
	
	FOR(i, 1, D) {
		if ((goodX[i] | goodX[i + 1]) == 3) {
			FOR(j, 0, x[i].size()) merge(i + n, x[i][j]);
			FOR(j, 0, x[i + 1].size()) merge(i + n, x[i + 1][j]);
		}
	}
	
	FOE(i, 1, D) {
		int g1 = 0, g2 = 0;
		FOR(j, 0, y[i].size()) {
			int id = y[i][j];
			
			if (px[id] == -1) g1 = 1;
			if (pz[id] == -1) g2 = 1;
		}
		
		goodY[i] = g1 * 2 + g2;
	}
 
	FOR(i, 1, D) {
		if ((goodY[i] | goodY[i + 1]) == 3) {
			FOR(j, 0, y[i].size()) merge(i + D + n, y[i][j]);
			FOR(j, 0, y[i + 1].size()) merge(i + D + n, y[i + 1][j]);
		}
	}
	
	FOE(i, 1, D) {
		int g1 = 0, g2 = 0;
		FOR(j, 0, z[i].size()) {
			int id = z[i][j];
			
			if (px[id] == -1) g1 = 1;
			if (py[id] == -1) g2 = 1;
		}
		
		goodZ[i] = g1 * 2 + g2;
	}
	
	FOR(i, 1, D) {
		if ((goodZ[i] | goodZ[i + 1]) == 3) {
			FOR(j, 0, z[i].size()) merge(i + 2 * D + n, z[i][j]);
			FOR(j, 0, z[i + 1].size()) merge(i + 2 * D + n, z[i + 1][j]);
		}
	}
 
	scanf("%d", &q);
	
	while (q--) {
		int a1, a2, a3, a4, a5, a6;
		scanf("%d%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5, &a6);
		int id1 = seek(a1, a2, a3);
		int id2 = seek(a4, a5, a6);
		
	//	printf("conv %d %d\n", id1, id2);
		
		if (par(id1) == par(id2)) {
			puts("YES");	
		} else {
			puts("NO");	
		}
	}
}
 
int main() {
	int t; scanf("%d", &t);
	while (t--) solve();
}

发表于 分类于

Problem I. Sum of Palindromes

Statement

把给定的 $n$ 位数分解成不超过 $25$ 个回文数（不允许前导零）。有 $z$ 组测试数据。

$1 \leq z \leq 20000$

$1 \leq n \leq 10^5$

$\sum n \leq 3 \times 10^6$

Solution

跟国内比赛撞车了（2016 CCPC Changchun J），可能这些毛子出题人没怎么看国内比赛的题。

做法很简单，就是每次减掉小于当前数的最大的回文数。很显然每次可以减掉一半的长度，所以大概只需要 $\log n$ 次就够了。唯一的难点在于实现有点恶心，需要上高精度，不过我直接复制以前打 16 长春时候的代码了。（那个时候写得很丑不要骂我呜呜呜）

Code (By Nanako)

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
 
const int N = 2e5;
 
char s[N];
int a[N], b[N], c[N];
int ans[55][N];
int cnt = 0;
 
int main () {
	int T;
	scanf("%d", &T);
	for (int it = 1;it <= T;it++) {
		cnt = 0;
		scanf("%s", &s);
		a[0] = strlen(s);
		for (int i = 0;i < a[0];i++) {
			a[a[0] - i] = s[i] - 48;
		}
		while (a[a[0]] == 0) a[0]--;
		
		while (a[0] > 1) {
			if ((a[0] == 2) && (a[2] == 1) && (a[1] == 0)) break;
			for (int i = 1;i <= a[0];i++) b[i] = 0;
			for (int i = a[0];i >= (a[0] + 1) / 2;i--) {
				b[i] = a[i];
			}
			int p = (a[0] & 1) ? (a[0] + 1) / 2 : a[0] / 2 + 1;
			b[p]--;
			while (b[p] < 0) {
				b[p] += 10;
				b[++p]--;
			}
			//for (int i = a[0];i >= 1;i--) cout << b[i];cout << " b" << endl;
			for (int i = 1;i <= a[0];i++) c[i] = 0;
			c[0] = a[0];
			for (int i = a[0];i >= (a[0] + 1) / 2;i--) {
				c[i] = b[i];
			}
			for (int i = 1;i <= (a[0] + 1) / 2;i++) {
				c[i] = b[a[0] - i + 1];
			}
			if (b[a[0]] == 0) c[1] = 9;
			while (c[c[0]] == 0) c[0]--;
			//for (int i = a[0];i >= 1;i--) cout << c[i];cout << " c" << endl;
			
			ans[++cnt][0] = c[0];
			for (int i = 1;i <= c[0];i++) {
				ans[cnt][i] = c[i];
			}
			
			for (int i = 1;i <= a[0];i++) {
				a[i] -= c[i];
				if (a[i] < 0) {
					a[i + 1]--;
					a[i] += 10;
				}
			}
			while (a[a[0]] == 0) a[0]--;
			//for (int i = a[0];i >= 1;i--) cout << a[i];cout << a[0] << " a" << endl;
		}
		if (a[0] == 1) {
			ans[++cnt][0] = 1;
			ans[cnt][1] = a[1];
		}
		if (a[0] == 2) {
			ans[++cnt][0] = 1;
			ans[cnt][1] = 9;
			ans[++cnt][0] = 1;
			ans[cnt][1] = 1;
		}
		
        printf("%d\n",cnt);
		for (int i = 1;i <= cnt;i++) {
			for (int j = ans[i][0];j >= 1;j--) {
				printf("%d", ans[i][j]);
			}
			printf("\n");
		}
	}
}

发表于 分类于 ，

Problem H. Lighthouses

Statement

给一个有 $n$ 个顶点的凸多边形，其顶点用 $(x_i,y_i)$ 表示。以 $n$ 个顶点为结点，给定 $m$ 条边 $(u_i,v_i)$。希望求出图上最长的（指欧几里得距离）且不和自己相交的（几何意义上）路的长度。有 $z$ 组测试数据。

$3 \leq n \leq 300$, $0 \leq m \leq \frac{n(n-1)}{2}$, $1 \leq u_i \neq v_i \leq n$

$-10^9 \leq x_i, y_i \leq 10^9$

$\sum n \leq 3000$

Solution

这题赛中我读都没读就被 clp012345 切了，赛后才看。

经过观察我们发现其实合法的路只能是在环上往一个方向转，那么我们上一个区间 DP 就可以了。开三个维度，分别表示起点、终点、顺/逆时针，状态转移 $O(n)$ 枚举。时间复杂度 $O(n^3)$。

区间 DP 要上环的话，通常做法就是开两倍数组复制一遍吧，参考石子合并。

Code (By clp012345)

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
#include <bits/stdc++.h>
 
#define FOE(i, s, t) for (int i = s; i <= t; i++)
#define FOR(i, s, t) for (int i = s; i < t; i++)
#define K 601
#define M 1000000007
#define LL long long
 
using namespace std;
 
int n;
int x[K], y[K];
 
double dist(int id1, int id2) {
	double dx = abs(x[id1] - x[id2]);
	double dy = abs(y[id1] - y[id2]);
	
	return sqrt(dx * dx + dy * dy);	
}
 
int ok[K][K][2];
double dp[K][K][2];
 
int has[K][K];
 
int prev(int u) {
	return (u == 1 ? n : u - 1);	
}
 
int nxt(int u) {
	return (u == n ? 1 : u + 1);	
}
 
double solve2(int sta, int fin, int dir) {
	if (sta == fin) return 0.00;
	if (ok[sta][fin][dir] == 0) {
		dp[sta][fin][dir] = 0.00;
		ok[sta][fin][dir] = 1;
		if (dir == 1) {
			// clockwise
			for (int i = nxt(sta); i != fin; i = nxt(i)) {
			//	printf("sta %d fin %d i %d %d\n", sta, fin, i, has[sta][i]);
				if (has[sta][i]) {
					dp[sta][fin][dir] = max(dp[sta][fin][dir], max(solve2(i, fin, 1), solve2(i, sta, 0)) + dist(sta, i));
				}
			}
			
		} else {
			// anti clockwise
			for (int i = prev(sta); i != fin; i = prev(i)) {
				if (has[sta][i]) {
					dp[sta][fin][dir] = max(dp[sta][fin][dir], max(solve2(i, fin, 0), solve2(i, sta, 1)) + dist(sta, i));
				}
			}
		}
	}
	
	return dp[sta][fin][dir];
}
 
void solve() {
	scanf("%d", &n);
	
	FOE(i, 1, n) scanf("%d%d", &x[i], &y[i]);
	
	FOE(i, 1, n) FOE(j, 1, n) ok[i][j][0] = ok[i][j][1] = 0;
	
	double ret = 0.00;
	
	FOE(i, 1, n) FOE(j, 1, n) has[i][j] = 0;
	int m; scanf("%d", &m);
	
	FOE(i, 1, m) {
		int u, v; scanf("%d%d", &u, &v);
		has[u][v] = has[v][u] = 1;
	}
	
	FOE(i, 1, n) FOE(j, 1, n) if (has[i][j]) {
		double temp = max(solve2(j, i, 1), solve2(j, i, 0)) + dist(i, j);
		
		if (temp > ret) ret = temp;	
	}
	
	printf("%.9f\n", ret);
}
 
int main() {
	int t; scanf("%d", &t);
	while (t--) solve();
}

发表于 分类于

Problem G. Invited Speakers

Statement

给定 $2n$ 个不同的点 $(x_i,y_i)$，$A$ 类型和 $B$ 类型各 $n$ 个，保证不存在三点共线。希望你能给出一种方案把它们配对成 $n$ 对 $AB$，并且每对 $AB$ 之间用折线（$[1, 100]$ 条首尾相连的线段）相连，折线之间两两不交。有 $z$ 组测试数据。

$1 \leq z \leq 200$

$1 \leq n \leq 6$

$0 \leq |x_i|,|y_i| \leq 100$

Solution

我读的题，第一反应是：就这？

还害我确认了好几遍题意和数据范围。

精通脚撕 FFT 的各种姿势的队友 Luowaterbi 曾经告诉我，没有三点共线的时候，两种一样多的点必然存在一种配对方案使得每对之间只用一条线段相连并且所有线段都不交。既然这题数据范围这么小，直接大力枚举配对方案，再大力枚举判断是否存在两线段交就行了。时间复杂度 $O(n!n^2)$。

由于我计算几何过于垃圾不想写，我就交给 triple_a 写了。triple_a 写得也很有意思，没用到计算几何的线段交判定，直接 $O(n!n)$ 取所有线段长度之和最小的方案，而这其实就是所有线段都不交的那个方案。

官方题解是个构造，懒得看具体折线怎么画了，反正意义不大，出题人可能是没想到有结论。

Code (By triple_a)

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
#include<bits/stdc++.h>
using namespace std;
 
int t,n;
int p[7],res[7];
pair<int,int> a[7],b[7];
double dist;
int main(){
    cin>>t;
    while (t--){
        cin>>n;
        for (int i=0;i<n;++i){
            cin>>a[i].first>>a[i].second;
        }
        for (int i=0;i<n;++i){
            cin>>b[i].first>>b[i].second;
        }
        dist=1e9;
        for (int i=0;i<n;++i){
            p[i]=i;
        }
        auto f=[&](pair<int,int>u, pair<int,int> v){
            return (u.first-v.first)*(u.first-v.first)+(u.second-v.second)*(u.second-v.second);
        };
        do{
            double sum=0;
            for (int i=0;i<n;++i){
                sum+=sqrt(f(a[i],b[p[i]]));
            }
            if (sum<dist){
                dist=sum;
                for (int i=0;i<n;++i){
                    res[i]=p[i];
                }
            }
        }while(next_permutation(p,p+n));
        for (int i=0;i<n;++i){
            cout<<2<<" "<<a[i].first<<" "<<a[i].second<<" "<<b[res[i]].first<<" "<<b[res[i]].second<<endl;
        }
    }
}

发表于 分类于 ，

Problem F. The Halfwitters

Statement

给定长度 $n$，给定 $a, b, c$，给 $d$ 次询问。每次询问是一个长度为 $n$ 的排列，你可以对这个票列做三种操作：

  1. 花费 $a$ 代价，交换相邻的两个数；

  2. 花费 $b$ 代价，翻转这个排列；

  3. 花费 $c$ 代价，shuffle 这个排列。

对于每次询问，你需要求出，在最优的操作策略下，把排列排成升序所需的最小期望代价。有 $z$ 组测试数据。

$2 \leq n \leq 16$, $1 \leq a, b, c \leq 1000$, $1 \leq d \leq 10000$

$\sum d \leq 10^5$

Solution

考虑只有第一种操作，我们不难发现，总代价只跟逆序对数 $inv$ 有关。
$$
ans_{1}(inv) = inv \cdot a
$$
考虑加上第二种操作，我们不难发现，先翻转一下再只进行以上操作可能会更快！
$$
ans_{12}(inv) = \min(ans_{1}(inv), b + (\frac{n(n-1)}{2} - inv) \cdot a)
$$
考虑加上第三种操作，我们不难发现，先 shuffle 一下再只进行以上操作可能会更快！我们令 shuffle 后代价的期望是 $x$。
$$
ans_{123} = \min(ans_{12}(inv), x + c)
$$
那么，怎么求 $x$ 呢？记逆序对数为 $inv$ 的排列有 $L_{inv}$ 个，如果我们只能进行一次 shuffle 操作，那么显然
$$
x = \frac
{\sum_{inv = 0}^{\frac{n(n-1)}{2}} L_{inv} \cdot ans_{12}(inv)}
{n!}
$$
但是实际上，有可能 shuffle 一次之后我们不满意，那就有可能继续 shuffle。所以我们只好列一个方程来计算 $x$。

我们知道，shuffle 后有一部分满意的情况（即 $ans_{12}(inv) \leq x + c$），其中每种情况的代价是 $ans_{12}(inv)$；也有一部分不满意的情况（即 $ans_{12}(inv) > x + c$），其中每种情况的代价是 $x + c$。于是我们可以把上面那个错误的式子改成这样一个正确的式子：
$$
x = \frac
{\sum_{ans_{12}(inv) \leq x + c} L_{inv} \cdot ans_{12}(inv) +
\sum_{ans_{12}(inv) > x + c} L_{inv} \cdot (x + c) }
{n!}
$$
为了方便计算这个东西，我们变换一下下标。令 $id$ 是一个排列且满足 $ans_{12}(id_i)$ 关于 $i$ 单增（用排序就可以实现），那么显然会有一个分界点 $k$ 使得
$$
x = \frac
{\sum_{i = 0}^{k} L_{id_i} \cdot ans_{12}(id_i) +
\sum_{i = k + 1}^{\frac{n(n-1)}{2}} L_{id_i} \cdot (x + c) }
{n!}
$$
把 $x$ 挪到一边
$$
x = \frac
{\sum_{i = 0}^{k} L_{id_i} \cdot ans_{12}(id_i) +
\sum_{i = k + 1}^{\frac{n(n-1)}{2}} L_{id_i} \cdot c }
{n! - \sum_{i = k + 1}^{\frac{n(n-1)}{2}} L_{id_i}}
$$
考虑到 $n! = \sum_{i=0}^{\frac{n(n-1)}{2}} L_i$，我们可以修改得好看一点
$$
x + c = \frac
{\sum_{i = 0}^{k} L_{id_i} \cdot ans_{12}(id_i) + n! \cdot c}
{\sum_{i = 0}^{k} L_{id_i}}
$$
这个方程有两个未知量 $x$ 和 $k$，但是我们不难发现它们必定满足 $ans_{12}(k) \leq x + c \leq ans_{12}(k + 1)$。然后我们预处理一下前缀和，枚举 $k$ 找合法解就可以辣！

$L_i$ 不会求的话，可以参考 [HAOI2009] 逆序对数列 。

Code

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main0 ();
int main () {
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
	#endif
	ios::sync_with_stdio(false);
	clock_t start, end;
	// start = clock();
	main0();
	// end = clock();
	// cout << (end - start) << endl;
	#ifndef ONLINE_JUDGE
		fclose(stdin);
	#endif
	return 0;
}

const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int N = 20;
const int M = 200;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);

ll L[N][M];
ll fac[N];

void init () {
	L[1][0] = 1;
	for (int i = 2;i <= 16;++i) {
		ll pre = 0;
		for (int j = 0;j <= 120;++j) {
			pre += L[i - 1][j];
			if (j - i >= 0) pre -= L[i - 1][j - i];
			L[i][j] = pre;
			//cout << i << ' ' << j << ':' << f[i][j] << endl;
		}
	}
	
	fac[0] = 1;
	for (int i = 1;i <= 16;++i) {
		fac[i] = fac[i - 1] * i;
	}
}

ll v[N];
ll t[M], id[M];
ll pre1[M], pre2[M];

bool cmp (int x, int y) {
	return t[x] < t[y];
}

ll gcd (ll x, ll y) {
	if (!y) return x;
	return gcd(y, x % y);
}

int main0 () {
	init();
	MULTI {
		ll n, a, b, c, d;
		cin >> n >> a >> b >> c >> d;
		ll lim = n * (n - 1) / 2;
		
		for (int i = 0;i <= lim;++i) {
			t[i] = min(i * a, b + (lim - i) * a);
			id[i] = i;
		}
		sort(id, id + lim + 1, cmp);
		
		pre1[0] = L[n][0];
		pre2[0] = L[n][0] * t[0];
		for (int i = 1;i <= lim;++i) {
			pre1[i] = pre1[i - 1] + L[n][id[i]];
			pre2[i] = pre2[i - 1] + L[n][id[i]] * t[id[i]];
		}
		
		ll k, p, q;
		double x;
		for (k = 0;k < lim;++k) {
			p = pre2[k] + c * fac[n];
			q = pre1[k];
			ll gcdd = gcd(p, q);
			p /= gcdd;
			q /= gcdd;
			x = 1.0 * p / q;
			//cout<<k<<':'<<p<<'/'<<q<<'='<<x<<' '<<t[id[k]]<<'~'<<t[id[k+1]]<< endl;
			if ((t[id[k]] <= x) && (x <= t[id[k+1]])) break;
		}
		
		for (int cur = 1;cur <= d;++cur) {
			int inv = 0;
			for (int i = 1;i <= n;++i) {
				cin >> v[i];
				for (int j = 1;j <= i - 1;++j) {
					inv += (v[j] > v[i]);
				}
			}
			
			if (t[inv] <= x) cout << t[inv] << '/' << 1 << endl;
			else cout << p << '/' << q << endl;
		}
	}
}

发表于 分类于 ，

Problem B. Binomial

Statement

给定序列 $a_1,a_2,\dots, a_n$，问有多少对 $(a_i,a_j)$ 满足 $\binom{a_i}{a_j} \bmod 2 = 1$ 。有 $z$ 组测试数据。

$1 \leq z \leq 10$

$1 \leq n \leq 10^6$, $1 \leq a_i \leq 10^6$

Solution

Lucas 定理有一个经典的推论：

$$
\binom{a_i}{a_j} \bmod 2 = 1 \leftrightarrow a_i & a_j = a_j
$$

因此，问题转化为求

$$
\sum_{i=1}^{n} \sum_{j=1}^{n} [a_i & a_j = a_j]
$$
记 $m = \lceil \log (\max a_i) \rceil$。显然，暴力枚举可以做到 $O(n^2)$ 的复杂度。优化一下，枚举子集可以做到 $O(3^m)$ 的复杂度。但是要通过这题还是不够。clp012345 说可以 Sum over Submask DP 做到 $O(m2^m)$，于是 triple_a 就现学现用写了一个。

这个算法本身就不讲了，可以看上面链接的文章。在国内，这个算法一般被称作快速莫比乌斯变换 (FMT) 或者子集和变换，英文不好的话也可以搜这两个词，但感觉其实大部分文章都写得对新手不是很友好。个人觉得可以看这篇，我觉得下面这张插图真的把 FMT 解释得非常清楚。

一个栗子

是的，FMT 和 FWT 相关的题代码基本都不长，但是，我觉得确实不太好懂。

Code (By triple_a)

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int maxn=(1<<20);
int a[maxn],b[maxn],F[maxn],n,t;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>t;
	while (t--){
		cin>>n;
		for (int i=0;i<(1<<20);++i) b[i]=0;
		for (int i=0;i<n;++i) cin>>a[i], b[a[i]]++;
		for(int i = 0; i<(1<<20); ++i)
			F[i] = b[i];
		for(int i = 0;i < 20; ++i) for(int mask = 0; mask < (1<<20); ++mask){
			if(mask & (1<<i))
				F[mask] += F[mask^(1<<i)];
		}
		int res=0;
		for (int i=0;i<(1<<20);++i){
			res+=b[i]*F[i];
		}
		cout<<res<<endl;
	}
	return 0;
 
}

发表于 更新于 分类于 ，

Problem A. Bags of Candies

Statement

把 $A = {1,2,\dots,n}$ 分成尽可能多对，使得每一对的两个数都不互质，问 $n$ 减去配对次数的值。有 $z$ 组测试数据。

$1 \leq z \leq 5$

$2 \leq n \leq 10^{11}$

Solution

半场的时候动这个题的队伍只有个位数。可能大家都觉得有别的题可做，不像我这么菜别的都不会就来瞎猜结论了啊。于是结论就是，将 $1$ 和大于 $\lfloor \frac n2 \rfloor$ 的质数从 $A$ 里删掉，剩下的集合 $A’$ 一定是可以匹配满的，所以配对次数就是 $\frac {|A’|}2$。

赛中是瞎猜的，这里给一个简单证明。

将 $A’$ 的所有元素按最大质因子 $d$ 分组，那么每组都可以表示成 $A_d = {d,2d,\dots,\lfloor \frac nd \rfloor d}$ 的形式（注意并不一定 $|A_d|=\lfloor \frac nd \rfloor$，比如 $77 \notin A_7$），显然组内的数都是不互质的。

如果 $|A_d|$ 是偶数，直接令组内的数任意两两配对；如果 $|A_d|$ 是奇数，则除了 $2d$ 以外任意两两配对。所有组都作完以上匹配之后，剩下的数都是 $2$ 的倍数，所以也都不互质，也可以任意两两配对。注意到对于任意 $d$ 有 $|A_d| \geq 2$ 即不存在 $|A_d| = 1$，所以最后剩下的数显然至多只有一个。

至此，剩下的任务就是筛 $10^{11}$ 以内的质数个数。这东西听上去很不可做，又或者是某种奥妙重重的高级筛法，但 clp012345 说有一种叫作 Meissel-Lehmer 的神棍算法可以 $O(n^\frac 23)$ 求这个东西，于是我临时找了个板子复制粘贴交了两发过了（？）。赛后看官方题解居然是分段打表，太暴力了……

关于这个算法的更多内容可以看上面的链接。

Code

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main0 ();
int main () {
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
	#endif
	ios::sync_with_stdio(false);
	clock_t start, end;
	// start = clock();
	main0();
	// end = clock();
	// cout << (end - start) << endl;
	#ifndef ONLINE_JUDGE
		fclose(stdin);
	#endif
	return 0;
}
 
const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);
 
const int N = 5e6 + 2;//通过知道前面的n^1/3的=质数可以推断后面n^2/3的质数所以可以适当减小
bool np[N];
int prime[N], pi[N];
int getprime()
{
    int cnt = 0;
    np[0] = np[1] = true;
    pi[0] = pi[1] = 0;
    for(int i = 2; i < N; ++i)
    {
        if(!np[i]) prime[++cnt] = i;
        pi[i] = cnt;
        for(int j = 1; j <= cnt && i * prime[j] < N; ++j)
        {
            np[i * prime[j]] = true;
            if(i % prime[j] == 0)   break;
        }
    }
    return cnt;
}
const int M = 7;//为了减小内存可以不过是质数
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;//为了减小内存可以不过要按质数减小如去掉17
int phi[PM + 1][M + 1], sz[M + 1];
void init()
{
    getprime();
    sz[0] = 1;
    for(int i = 0; i <= PM; ++i)  phi[i][0] = i;
    for(int i = 1; i <= M; ++i)
    {
        sz[i] = prime[i] * sz[i - 1];
        for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
    }
}
int sqrt2(ll x)
{
    ll r = (ll)sqrt(x - 0.1);
    while(r * r <= x)   ++r;
    return int(r - 1);
}
int sqrt3(ll x)
{
    ll r = (ll)cbrt(x - 0.1);
    while(r * r * r <= x)   ++r;
    return int(r - 1);
}
ll getphi(ll x, int s)
{
    if(s == 0)  return x;
    if(s <= M)  return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
    if(x <= prime[s]*prime[s])   return pi[x] - s + 1;
    if(x <= prime[s]*prime[s]*prime[s] && x < N)
    {
        int s2x = pi[sqrt2(x)];
        ll ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
        for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
        return ans;
    }
    return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
ll getpi(ll x)
{
    if(x < N)   return pi[x];
    ll ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
    for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
    return ans;
}
ll lehmer_pi(ll x)
{
    if(x < N)   return pi[x];
    int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
    int b = (int)lehmer_pi(sqrt2(x));
    int c = (int)lehmer_pi(sqrt3(x));
    ll sum = getphi(x, a) +(ll)(b + a - 2) * (b - a + 1) / 2;
    for (int i = a + 1; i <= b; i++)
    {
        ll w = x / prime[i];
        sum -= lehmer_pi(w);
        if (i > c) continue;
        ll lim = lehmer_pi(sqrt2(w));
        for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
    }
    return sum;
}
 
int main0 () {
	init();
	MULTI {
		ll n;
		cin >> n;
		//cout << lehmer_pi(n) << ' ' << lehmer_pi(n / 2) << endl;
		ll k = lehmer_pi(n) - lehmer_pi(n / 2) + 1;
		cout << n - (n - k) / 2 << endl;
	}
}