[Codeforces Round #514 (Div. 2)] 解题分析 Codeforces

Codeforces传送门 A.Cashier 题目描述
Vasya has recently got a job as a cashier at a local store. His day at work isL L L minutes long. Vasya has already memorizedn n n regular customers, thei ? t h i-th i?th of which comes aftert i t_i ti? minutes after the beginning of the day, and his service consumesl i l_i li? minutes. It is guaranteed that no customer will arrive while Vasya is servicing another customer.
Vasya is a bit lazy, so he likes taking smoke breaks fora a a minutes each. Those breaks may go one after another, but Vasya must be present at work during all the time periods he must serve regular customers, otherwise one of them may alert his boss. What is the maximum number of breaks Vasya can take during the day?
输入输出格式
输入格式： The first line contains three integersn n n,L L L anda a a ( 0 ≤ n ≤ 1 0 5 0≤n≤10^5 0≤n≤105,1 ≤ L ≤ 1 0 9 1≤L≤10^9 1≤L≤109,1 ≤ a ≤ L 1≤a≤L 1≤a≤L).
Thei ? t h i-th i?th of the nextn n n lines contains two integerst i t_i ti? andl i l_i li? ( 0 ≤ t i ≤ L ? 1 0≤t_i≤L?1 0≤ti?≤L?1,1 ≤ l i ≤ L 1≤l_i≤L 1≤li?≤L). It is guaranteed thatt i + l i ≤ t i + 1 t_i+l_i≤t_{i+1} ti?+li?≤ti+1? andt n + l n ≤ L t_n+l_n≤L tn?+ln?≤L.
输出格式： Output one integer — the maximum number of breaks.
输入输出样例
输入样例#1：

2 11 3 0 1 1 1

输出样例#1：

3

输入样例#2：

0 5 2

输出样例#2：

2

输入样例#3：

1 3 2 1 2

输出样例#3：

0

说明
In the first sample Vasya can take3 3 3 breaks starting after2 2 2,5 5 5 and8 8 8 minutes after the beginning of the day.
In the second sample Vasya can take2 2 2 breaks starting after0 0 0 and2 2 2 minutes after the beginning of the day.
In the third sample Vasya can’t take any breaks.
解题分析
加一个 0 0 0，加一个 L L L，然后间隔除以 a a a下取整就好了。
代码如下：

#include #include #include #include #include #include #include #include #include #include #include #include #include #define register #define IN inline #define R register #define W while #define gc getchar() #define ll long long #define db double #define lowbit(i) ((i) & (-(i))) const db PI = std::acos(-1.0); int seq[300050]; int main(void) { int a, b, cnt = 0, ans = 0; int n, l, k; scanf("%d%d%d", &n, &l, &k); for (R int i = 1; i <= n; ++i) { scanf("%d%d", &a, &b); seq[++cnt] = a, seq[++cnt] = a + b; } seq[++cnt] = 0, seq[++cnt] = l; std::sort(seq + 1, seq + 1 + cnt); for (R int i = 1; i < cnt; i += 2) ans += (seq[i + 1] - seq[i]) / k; printf("%d", ans); }

B.Forgery 题目描述
Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn’t give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor’s handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor’s signature is impossible to forge. Or is it?
For simplicity, the signature is represented as ann × m n×m n×m grid, where every cell is either filled with ink or empty. Andrey’s pen can fill a3 × 3 3×3 3×3square without its central cell if it is completely contained inside the grid, as shown below.

xxx x.x xxx

Determine whether is it possible to forge the signature on an emptyn × m n×m n×m grid.
输入输出格式
输入格式： The first line of input contains two integersn n n andm m m ( 3 ≤ n , m ≤ 1000 3≤n,m≤1000 3≤n,m≤1000).
Thenn n n lines follow, each containsm m m characters. Each of the characters is either., representing an empty cell, or #, representing an ink filled cell.
输出格式： If Andrey can forge the signature, output YES. Otherwise output NO.
You can print each letter in any case (upper or lower).
输入输出样例
输入样例#1：

3 3 ### #.# ###

输出样例#1：

YES

输入样例#2：

3 3 ### ### ###

输出样例#2：

NO

输入样例#3：

4 3 ### ### ### ###

输出样例#3：

YES

输入样例#4：

5 7 ....... .#####. .#.#.#. .#####. .......

输出样例#4：

YES

解题分析
一开始想这个图形是不是有什么特殊性质，然后忽然发现 n , m ≤ 1000 n,m\leq 1000 n,m≤1000…
直接枚举每个格子看作为左上角是不是可以涂色，如果可以涂就涂一下，最后看有没有没涂到的地方就好。
代码如下：（略宽…）

#include #include #include #include #include #include #include #include #include #include #include #include #include #define register #define IN inline #define R register #define W while #define gc getchar() #define ll long long #define db double #define lowbit(i) ((i) & (-(i))) const db PI = std::acos(-1.0); #define MX 1005 char mp[MX][MX]; int tim[MX][MX]; int n, m; IN bool check(R int x, R int y) { return ((mp[x][y] == '#') & (mp[x][y + 1] == '#') & (mp[x][y + 2] == '#') & (mp[x + 1][y] == '#') & (mp[x + 1][y + 2] == '#') & (mp[x + 2][y] == '#') & (mp[x + 2][y + 1] == '#') & (mp[x + 2][y + 2] == '#')); } IN void work(R int x, R int y) { tim[x][y]++; tim[x][y + 1]++; tim[x][y + 2]++; tim[x + 1][y]++; tim[x + 1][y + 2]++; tim[x + 2][y]++; tim[x + 2][y + 1]++; tim[x + 2][y + 2]++; } IN void fil(R int x, R int y) { if(x + 2 > n || y + 2 > m) return; if(check(x, y)) work(x, y); } int main(void) { scanf("%d%d", &n, &m); for (R int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1); for (R int i = 1; i <= n; ++i) for (R int j = 1; j <= m; ++j) { if(mp[i][j] == '#') fil(i, j); } for (R int i = 1; i <= n; ++i) for (R int j = 1; j <= m; ++j) if(mp[i][j] == '#' && (!tim[i][j])) return puts("NO"), 0; puts("YES"); }

C. Sequence Transformation 题目描述
Let’s call the following process a transformation of a sequence of lengthn n n.
If the sequence is empty, the process ends. Otherwise, append the greatest common divisor ( G C D GCD GCD) of all the elements of the sequence to the result and remove one arbitrary element from the sequence. Thus, when the process ends, we have a sequence ofn n n integers: the greatest common divisors of all the elements in the sequence before each deletion.
You are given an integer sequence1 , 2 , … , n 1,2,…,n 1,2,…,n. Find the lexicographically maximum result of its transformation.
A sequencea 1 , a 2 , … , a n a_1,a_2,…,a_n a1?,a2?,…,an?is lexicographically larger than a sequenceb 1 , b 2 , … , b n b_1,b_2,…,b_n b1?,b2?,…,bn?, if there is an indexi i i such thata j = b j a_j=b_j aj?=bj? for allj < i j< i jbi?.
输入输出格式
输入格式： 【[Codeforces Round #514 (Div. 2)] 解题分析】The first and only line of input contains one integern n n ( 1 ≤ n ≤ 1 0 6 1≤n≤10^6 1≤n≤106).
输出格式： Outputn n n integers — the lexicographically maximum result of the transformation.
输入输出样例
输入样例#1：

3

输出样例#1：

1 1 3

输入样例#2：

2

输出样例#2：

1 2

输入样例#3：

1

输出样例#3：

1

解题分析
看起来很水的样例其实好心地提醒了我们…
首先我们肯定会先将所有奇数删掉，这样就可以提出一个 2 2 2，而如果要提出其他的约数肯定(???)要多删一些。
然后我们发现这样可以递归处理提出 2 2 2之后的那个数列。
但这样就是对的吗？我们可以看下样例 1 1 1，发现 3 3 3的时候需要特判。
这样就能 A A A了。
代码如下：

#include #include #include #include #include #include #include #include #include #include #include #include #include #define register #define IN inline #define R register #define W while #define gc getchar() #define ll long long #define db double #define lowbit(i) ((i) & (-(i))) #define MX 1000050 const db PI = std::acos(-1.0); int n; void solve(R int len, R int mul) { if(len == 1) return printf("%d ", (int)pow(2, mul)), void(); if(len == 3) return printf("%d %d %d", (int)pow(2, mul), (int)pow(2, mul), (int)pow(2, mul) * 3), void(); int num = (len + 1) >> 1; int ans = pow(2, mul); for (R int i = 1; i <= num; ++i) printf("%d ", ans); solve(len >> 1, mul + 1); } int main(void) { scanf("%d", &n); solve(n, 0); }

D. Nature Reserve 题目描述
There is a forest that we model as a plane and liven n n rare animals. Animal numberi i i has its lair in the point( x i , y i ) (x_i,y_i) (xi?,yi?). In order to protect them, a decision to build a nature reserve has been made.
The reserve must have a form of a circle containing all lairs. There is also a straight river flowing through the forest. All animals drink from this river, therefore it must have at least one common point with the reserve. On the other hand, ships constantly sail along the river, so the reserve must not have more than one common point with the river.
For convenience, scientists have made a transformation of coordinates so that the river is defined byy = 0 y=0 y=0. Check whether it is possible to build a reserve, and if possible, find the minimum possible radius of such a reserve.
输入输出格式
输入格式： The first line contains one integern n n ( 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105) — the number of animals.
Each of the nextn n n lines contains two integersx i x_i xi?,y i y_i yi? ( ? 1 0 7 ≤ x i , y i ≤ 1 0 7 ?10^7≤x_i,y_i≤10^7 ?107≤xi?,yi?≤107) — the coordinates of thei ? t h i-th i?th animal’s lair. It is guaranteed thaty i ≠ 0 y_i≠0 yi???=0. No two lairs coincide.
输出格式： If the reserve cannot be built, print? 1 ?1 ?1. Otherwise print the minimum radius. Your answer will be accepted if absolute or relative error does not exceed1 0 ? 6 10^{?6} 10?6.
Formally, let your answer bea a a, and the jury’s answer beb b b. Your answer is considered correct if∣ a ? b ∣ m a x ( 1 , ∣ b ∣ ) \frac{|a-b|}{max(1,|b|)} max(1,∣b∣)∣a?b∣?.
输入输出样例
输入样例#1：

1 0 1

输出样例#1：

0.5

输入样例#2：

3 0 1 0 2 0 -3

输出样例#2：

-1

输入样例#3：

2 0 1 1 1

输出样例#3：

0.625

解题分析
比赛的时候一直去想凸包了，然后发现好像咋搞都不可能小于 O ( N 2 ) O(N^2) O(N2)的样子。
其实还有一个很好的条件没有用：切 y = 0 y=0 y=0这条直线。
那么如果半径是 R \mathcal{R} R，圆心可能的位置也就在一条平行于 y y y轴的直线上面。
那么二分这个半径，对于一个点 ( x , y ) (x,y) (x,y)在这个直线上有一段区间 [ l , r ] [l,r] [l,r]，在这段区间内圆心到这个点的距离是 ≤ R \leq \mathcal{R} ≤R的，如果有解即所有区间有公共部分。
精度十分爆炸，用 l o n gd o u b l e long\ double long double。
代码如下：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define register #define IN inline #define R register #define W while #define gc getchar() #define ll long long #define db long double #define lowbit(i) ((i) & (-(i))) #define MX 100050 #define EPS 1e-8 using std::cin; using std::cout; template IN T sqr(const T &x) {return x * x; } const db PI = std::acos(-1.0); struct pt {db x, y; } dat[MX]; IN pt operator + (const pt &x, const pt &y) {return {x.x + y.x, x.y + y.y}; } IN pt operator - (const pt &x, const pt &y) {return {x.x - y.x, x.y - y.y}; } IN db operator * (const pt &x, const pt &y) {return x.x * y.y - x.y * y.x; } int n, neg, pos; IN bool check(db r) { db lef = -2e16, rig = 2e16, lb, rb, del; for (R int i = 1; i <= n; ++i) { if(fabs(r - dat[i].y) > r) return false; del = std::sqrt(sqr(r) - sqr(r - dat[i].y)); lb = dat[i].x - del, rb = dat[i].x + del; lef = std::max(lef, lb), rig = std::min(rig, rb); if(lef > rig) return false; } return true; } int main(void) { std::ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (R int i = 1; i <= n; ++i) { cin >> dat[i].x >> dat[i].y; if(dat[i].y < 0) ++neg; else ++pos; } if(neg && pos) return puts("-1"), 0; if(neg) for (R int i = 1; i <= n; ++i) dat[i].y = -dat[i].y; db lef = 0, rig = 1e16, mid; int cnt = 250; W (cnt--) { mid = (lef + rig) / 2.0000000000; if(check(mid)) rig = mid; else lef = mid; } cout.precision(16); cout << std::fixed << rig; }

E. Split the Tree 题目描述
You are given a rooted tree onn n n vertices, its root is the vertex number1 1 1. Thei ? t h i-th i?th vertex contains a numberw i w_i wi?. Split it into the minimum possible number of vertical paths in such a way that each path contains no more thanL L L vertices and the sum of integersw i w_i wi? on each path does not exceedS S S. Each vertex should belong to exactly one path.
输入输出格式
输入格式： The first line contains three integersn n n,L L L,S S S ( 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105,1 ≤ L ≤ 1 0 5 1≤L≤10^5 1≤L≤105,1 ≤ S ≤ 1 0 18 1≤S≤10^{18} 1≤S≤1018) — the number of vertices, the maximum number of vertices in one path and the maximum sum in one path.
The second line contains nn integersw 1 , w 2 , … , w n w_1,w_2,…,w_n w1?,w2?,…,wn? ( 1 ≤ w i ≤ 1 0 9 1≤w_i≤10^9 1≤wi?≤109) — the numbers in the vertices of the tree.
The third line containsn ? 1 n?1 n?1 integersp 2 , … , p n p_2,…,p_n p2?,…,pn? ( 1 ≤ p i < i 1≤p_i< i 1≤pi? 输出格式： Output one number— the minimum number of vertical paths. If it is impossible to split the tree, output? 1 ?1 ?1.
输入输出样例
输入样例#1：

3 1 3 1 2 3 1 1

输出样例#1：

3

输入样例#2：

3 3 6 1 2 3 1 1

输出样例#2：

2

输入样例#3：

1 1 10000 10001

输出样例#3：

-1

解题分析
比赛的时候知道要贪心取向上延伸最远的，但不知道怎么维护…
WOC，这TM不就一个倍增吗？？
下次比赛的时候一定要先睡一觉…
代码如下：

#include #include #include #include #include #include #define R register #define IN inline #define W while #define gc getchar() #define MX 100050 #define ll long long int top[MX], dep[MX], fat[MX][18], to[MX], head[MX], val[MX]; ll pre[MX], mx; int dot, lim, ans, cnt, lg; struct Edge {int to, nex; } edge[MX << 1]; IN void add(R int from, R int to) {edge[++cnt] = {to, head[from]}, head[from] = cnt; } void DFS(R int now) { pre[now] = pre[fat[now][0]] + val[now]; to[now] = now; R int lm = lim; for (R int i = 1; i < lg; ++i) fat[now][i] = fat[fat[now][i - 1]][i - 1]; for (R int i = lg - 1; ~i; --i) { if((!fat[to[now]][i]) || (1 << i) > lm) continue; if(pre[now] - pre[fat[to[now]][i]] + val[fat[to[now]][i]] <= mx) lm -= (1 << i), to[now] = fat[to[now]][i]; } for (R int i = head[now]; i; i = edge[i].nex) { dep[edge[i].to] = dep[now] + 1; fat[edge[i].to][0] = now; DFS(edge[i].to); } } int solve(R int now) { int ret = 0, best = -1; for (R int i = head[now]; i; i = edge[i].nex) { ret += solve(edge[i].to); if(top[edge[i].to] == edge[i].to) continue; if(best == -1 || dep[top[edge[i].to]] < dep[best]) best = top[edge[i].to]; } if(best == -1) ++ret, best = to[now]; top[now] = best; return ret; } int main(void) { int a; scanf("%d%d%I64d", &dot, &lim, &mx); --lim; lg = log2(dot) + 1; for (R int i = 1; i <= dot; ++i) {scanf("%d", &val[i]); if(val[i] > mx) return puts("-1"), 0; } for (R int i = 2; i <= dot; ++i) scanf("%d", &a), add(a, i); DFS(1); printf("%d", solve(1)); }