[20200426] 2020 Petrozavodsk Winter Camp Day 5

发表于 分类于

Review

triple_a 问我和 clp012345 要不要来玩，于是我就打了，前 World Finalist 带飞谁不爱呢。

因为纯属娱乐所以可能并不是全力打，不过也并没有做到同一时刻只有一个人写……总之就是图一乐吧。

刚开场的时候因为是娱乐所以他们两个也就随便开题不跟榜了，我们各自读了一下几道题。clp012345 开始猛凹 C 凹了接近两个小时，结果是 C 最后也没过。我看到有人过 L 就大力 WA 了一发，发现把大于写成大于等于，43min2A。B 题 triple_a 说只会 TLE 的枚举子集，于是 clp012345 说 Sum over Submask DP 能做，51min1A。triple_a 又读了 I 题，说做法显然但是难写，我一看题居然是原题（2016 CCPC Changchun J），可能毛子出题人没看过国内这场，于是直接复制粘贴交了，71min1A。G 我之前就说是大力枚举，但我不会计算几何，让 triple_a 写了，105min2A。我们交流了一下 F 的题意，然后 triple_a 觉得他大概会写，然后他说反正是随便打打所以他有事要出门了（草）。我大力猜了一下 A 题有个结论，但是需要筛 $10^{11}$ 以内的质数个数，时间复杂度没法接受，clp012345 告诉我有一种叫作 Meissel-Lehmer 的神棍算法可以 $O(n^\frac 23)$ 求这个东西……找了个板子复制粘贴（？），然后我搞错边界，又贡献一发罚时，156min2A。期间 clp012345 单切了 H（我题都没读……），167min2A。接下来我假装看 C 和 E，其实已经没思路了完全躺了。但他们两个还是很猛，clp012345 单切了 J，230min4A。triple_a 回来把 F 写了，257min2A。我跟 clp012345 说 E 题的圆其实就是竖线，他说用离散化线段树维护一下就行，293min4A。

前 World Finalist 带飞果然牛逼，9 个题，力压 dmy，我全程躺着被带飞。

Solution（待完善）

Problem A. Bags of Candies

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-A/

Problem B. Binomial

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-B/

Problem C. Bookface

大致题意：数轴上有 $n$ 个点 $a_1,a_2,\dots,a_n$，每次你可以花费 $1$ 代价使某个点向某个方向移动 $1$（但所有点必须时刻在正半轴上）。现在，希望你求出最小总代价，使得任意两点间的距离都大于等于 $d$。有 $z$ 组测试数据。

$1 \leq z \leq 10^5$

$1 \leq n \leq 2 \times 10^5$, $1 \leq d \leq 10^6$, $0 \leq a_i \leq 3 \times 10^{11}$

$\sum n \leq 10^6$

Solution

World Finalist 凹了两个小时都没出的题，鸽。

Problem D. Clique

没读，全场最不可做的题。

Problem E. Contamination

triple_a 给我说的大致题意：平面上，给定 $n$ 个圆 $(c_x, c_y, r)$ 以及 $q$ 个询问 $(p_x,p_y,q_x,q_y,y_{min},y_{max})$，问能不能从 $(p_x,p_y) $ 走到 $(q_x,q_y)$，并满足路线不能碰到圆且任意时刻都有 $y \in [y_{min},y_{max}]$。

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

$-10^9 \leq c_x, c_y \leq 10^9$, $1 \leq r \leq 10^9$

$-10^9 \leq p_x,p_y,q_x,q_y,y_{min},y_{max} \leq 10^9$, $y_{min} \leq p_y, q_y \leq y_{max}$

一直到最后一个小时，我都是按这个题意理解的。我提出，如果圆两两不交，那么圆其实等价于其平行于 $y$ 轴的直径；但圆如果相交，就没有任何办法可做。最后一个小时 clp012345 来看 E，他自己读了一遍题，然后告诉我，题目里面说了圆是不交的……

Solution

但我没想到怎么维护这个东西，clp012345 说就是一棵离散化线段树。有空的时候再具体问他。

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
#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 2300001
#define M 1000000007
#define NINF -2002100100
#define LL long long
 
using namespace std;
 
int n, q;
 
struct P {
	int x, y, r;	
};
 
P p[K];
 
int cx[2 * K];
 
struct Q {
	int sx, ymin, ymax, ex, id;	
};
 
Q qu[K];
 
bool cmpY(P A, P B) {
	return A.y < B.y;	
}
 
bool cmpQY(Q A, Q B) {
	return A.ymin < B.ymin;	
}
 
int l[4 * K], r[4 * K];
LL a[4 * K];
int h;
 
int sol[K];
 
void build(int u, int lb, int rb) {
	a[u] = NINF;
	if (lb == rb) return;
	
	build(l[u] = ++h, lb, (lb + rb) >> 1);
	build(r[u] = ++h, (lb + rb) / 2 + 1, rb); 	
}
 
void insert(int u, int lb, int rb, int pos, LL val) {
	if (lb == rb) {
		a[u] = val; return;
	}
	
	int mid = (lb + rb) >> 1;
	
	if (mid >= pos) {
		insert(l[u], lb, mid, pos, val); 
	} else {
		insert(r[u], mid + 1, rb, pos, val);	
	}
	
	a[u] = max(a[l[u]], a[r[u]]);
}
 
LL query(int u, int lb, int rb, int lq, int rq) {
	if (lq <= lb && rb <= rq) {
		return a[u];
	}
	
	if (rb < lq || rq < lb) return NINF;
	
	int mid = (lb + rb) >> 1;
	
	LL a1 = query(l[u], lb, mid, lq, rq);
	LL a2 = query(r[u], mid + 1, rb, lq, rq);
	
	return max(a1, a2);
}
 
int tx[2 * K], head;
 
int findX(int val) {
	int low = 1, high = head;
	int res;
	
	while (low <= high) {
		int mid = (low + high) >> 1;
		
		if (tx[mid] <= val) {
			low = mid + 1;
			res = mid;
		} else {
			high = mid - 1;	
		}
	}
		
	return res;
}
 
void solve() {
	scanf("%d%d", &n, &q);
	
	FOE(i, 1, n) {
		int x, y, r;
		scanf("%d%d%d", &x, &y, &r);
		p[i].x = x; p[i].y = y - r; p[i].r = r;	
		cx[i] = x;
	}
	
	FOE(i, 1, q) {
		int px, py, qx, qy, ymin, ymax;
		scanf("%d%d%d%d%d%d", &px, &py, &qx, &qy, &ymin, &ymax);
	
		cx[i + n] = px;
		cx[i + n + q] = qx;
		
		qu[i].sx = min(px, qx);
		qu[i].ex = max(px, qx);
		qu[i].ymin = ymin;
		qu[i].id = i;
		qu[i].ymax = ymax;
	}
	
	sort(p + 1, p + n + 1, cmpY);
	sort(qu + 1, qu + q + 1, cmpQY);
	sort(cx + 1, cx + n + 2 * q + 1);
	
	int last;
	FOE(i, 1, n + 2 * q) {
		if (i == 1 || cx[i] != last) {
			head++; tx[head] = cx[i];
			last = cx[i];
		}
	}
	
	build(0, 1, head);
	
	int ptr = 1;
	
	FOE(i, 1, q) {
		int cmin = qu[i].ymin;
		
	//	printf("cmin is %d\n", cmin);
		
		while (ptr <= n && p[ptr].y <= cmin) {
			int qx = findX(p[ptr].x);
		//	printf("INSERT %d\n", ptr);
			insert(0, 1, head, qx, p[ptr].y + p[ptr].r * 2);
			
		//	printf("PTR is %d\n", ptr);
			
			ptr++;	
		}
		
		int qsx = findX(qu[i].sx);
		int qex = findX(qu[i].ex);
		
	//	printf("? %d %d\n", qsx, qex);
		
		int id = qu[i].id;
		
		sol[id] = (query(0, 1, head, qsx, qex) < qu[i].ymax);
	}
	
	FOE(i, 1, q) {
		if (sol[i]) puts("YES"); else puts("NO");	
	}
}
 
int main() {
	solve();
}

Problem F. The Halfwitters

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-F/

Problem G. Invited Speakers

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-G/

Problem H. Lighthouses

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-H/

Problem I. Sum of Palindromes

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-I/

Problem J. Space Gophers

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-J/

Problem K. To argue, or not to argue

大致题意：一个 $n \times m$ 的网格，某些位置是可用的（可以坐一个人），某些位置是不可用的（不能坐人）。现在有 $k$ 对共 $2k$ 个人，所有人两两不同。每个人都要坐到一个可用的位置，且每一对人坐的两个位置都不能相邻。问安排座位的方案数对 $10^9+7$ 取余后的结果。有 $z$ 组测试数据，数据保证可用的座位至少有 $2k$ 个。

$1 \leq z \leq 10$

$1 \leq n, m \leq 144$, $1 \leq k \leq \frac{nm}{2}$

Solution

我读的题，第一反应是反过来统计有相邻的情况的方案数然后做个容斥。跟 clp012345 说了下题意，他说要再上个插头 DP。

事实证明这两个思路都是对的，但具体实现实在是太过复杂，我们在有更简单的题没写完的情况下也就放弃了，没继续往下讨论。

Problem L. Wizards Unite

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-L/