The 7th CCPC Guilin Regional

Summary

热身赛是澳门的三道题,B 题卡常带 $8$ 倍常数卡过去了, C 没有做出来。

正赛开场我们比较顺利,AGI过的很快,D猜了一次结论WA了,很快找出了反例。

之后猜到了E的结论,spfa 被卡了两发,改 dijkstra 之后过了,大概耗了一个小时。

之后 D 想出来了能通过写出所有反例的方法,WA了一发,发现是数组开小了,过了。

之后开了BFJK,因为 J 最先想到了一种做法,选择了先写 J ,复杂度有点高卡不过去。

还剩下一个半小时,觉得 B 的线段树比较有把握,写 + 调 + 对拍花了一个小时,过了。

最后半个小时感觉写 F 不是很有信心,于是调 JK,都是 TLE/MLE 左右横跳,卡到最后。

这次参赛体验还是不错的,我也没有像往常一样挂机,输出还可以。

赛程后一半机位交给了两个大数据结构 + 一个乱搞,我也无能为力,对于结果只能说菜是原罪了。

比较遗憾的是 F 很轻松地看出了正解,但是因为没写过不敢上机,希望之后的比赛能敢冲计算几何吧。

Resource

热身赛题面.pdf   正式赛题面.pdf   官方题解.pdf   F 题 Heltion 参考代码

A. A Hero Named Magnus

从第 $x$ 轮之后就会一直胜,此前胜率 $50\%$ ,问至少比几轮保证能一定胜利(获胜轮数多者胜)

前面全输,答案是 $2x-1$ ,开 long long 或者 python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

int main() {
for (int t = rd(); t; --t) printf("%lld\n", rd() * 2 - 1);
return 0;
}

B. A Plus B Problem

维护一个 $n \ (n\le 10^6)$ 位数加法器,包含三个 $n$ 位数 $A+B=C$ (忽略最高位进位)。

每次修改 $A$ 或 $B$ 中的一位,求修改后 $C$ 这一位的结果,以及加法器中有多少位受影响。

线段树是可以直接模拟的,支持查询前缀 $0$ 长度,前缀 $9$ 长度,区间赋值 $0$ ,区间赋值 $9$ 即可。

比较妙的做法:$C_i=(A_i+B_i+[A_j+B_j\ge 10])\ \text{mod}\ 10$ ,$j$ 为 $i$ 后面第一个 $A_i+B_i\not= 9$ 的位置。

进位/退位影响的话,也是影响前缀 $A_j+B_j=9$ 的一段,因此需要查询 $i$ 前面第一个 $A_i+B_i\not= 9$ 的位置。

综上,set 维护 $A_i+B_i\not= 9$ 的位置 $i$ 即可,复杂度 $O((n+q)\log n)$ .

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
#include <bits/stdc++.h>
#define N 1000007
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

inline int rdc() {
char c = getchar();
while (!isdigit(c)) c = getchar();
return c - '0';
}

set<int> s;

int a[3][N];
//a[0] = c, a[1] = a, a[2] = b

inline void work() {
int r = rd(), c = rd(), x = rd();
int pos = *s.upper_bound(c);
int old = a[0][c] + (a[0][pos] >= 10);

if (a[r][c] == x) {printf("%d 0\n", old % 10);return;}

if (a[0][c] != 9) s.erase(c);
a[r][c] = x; a[0][c] = a[1][c] + a[2][c];
if (a[0][c] != 9) s.insert(c);

int nw = a[0][c] + (a[0][pos] >= 10);

int ans = 2;
if ((old >= 10) ^ (nw >= 10)) {
int pre = *(--s.lower_bound(c));
ans = c - pre + 1 + (pre != 0);
}
printf("%d %d\n", nw % 10, ans);
}

int main() {
int n = rd(), q = rd();
for (int i = 1; i <= n; ++i) a[1][i] = rdc();
for (int i = 1; i <= n; ++i) {
a[2][i] = rdc();
a[0][i] = a[1][i] + a[2][i];
if (a[0][i] != 9) s.insert(i);
}
s.insert(0); s.insert(n + 1);
for (int i = 1; i <= q; ++i) work();
return 0;
}

D. Assumption is All You Need

E. Buy and Delete

给一个有向图,每条边有一个价值 $w_i$ ,你可以选总价值不超过 $c$ 的边保留,其余边删除。

一组边可以被删除,当且仅当这组边不包含一个有向环。

另一个人采取最优策略删除所得图的边(最少次数),问你最多能让他操作几次。

一条边都买不起的时候答案是 0 ;

买得起一条边但买不起一个环的时候答案是 1 ;

买得起环的时候,可以发现所有边可以分成无环的两组:$u>v$ 和 $u<v$ ,因此答案最大为 2 .

因此只需要找出最小环,使用 dijkstra 枚举起点 $O(n(m+n)\log m)$ 即可。

spfa 已死!真的不要幻想在正赛继续用 spfa 了…

$n=2000,m=5000$ 的时候竟然也能把 spfa 卡掉…

「历史的经验教训告诉我们,人们不会从历史的经验中吸取教训。」

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
#include <bits/stdc++.h>
#define N 2007
#define fr first
#define sc second
#define mp make_pair
#define pii pair<int, int>
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

int tot, hd[N], mnw = 1e9;

struct edge {int w, to, nxt;} e[N << 2];

inline void add() {
int u = rd();
e[++tot].to = rd();
mnw = min(mnw, (e[tot].w = rd()));
e[tot].nxt = hd[u]; hd[u] = tot;
}

bool vis[N];

int ans = 1e9, dis[N];

priority_queue<pii> q;

inline void dij(int s) {
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0; q.push(mp(0, s));
while (!q.empty()) {
int u = q.top().sc; q.pop();
if (vis[u]) continue; vis[u] = 1;
for (int i = hd[u], v; i; i = e[i].nxt)
if (dis[v = e[i].to] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push(make_pair(-dis[v], v));
} else if (v == s) ans = min(ans, dis[u] + e[i].w);
}
}

int main() {
int n = rd(), m = rd(), c = rd();
for (int i = 1; i <= m; ++i) add();
for (int i = 1; i <= n; ++i) dij(i);
puts( c < mnw ? "0" : (c < ans ? "1" : "2"));
return 0;
}

F. Illuminations II

给两个凸包,小凸包严格在大凸包内,现在在大凸包边界上等概率放一个点光源,问能照到小凸包周长的期望长度。

根据期望的线性,考虑小凸包每条边的贡献,有贡献的概率是:

(这条边所在直线切割大凸包周长所得的可以照射到这条边的长度)/(大凸包周长)

因此只需要求出直线和凸包的两个交点即可,按照时针顺序枚举小凸包的边,交点移动方向单调。

具体找交点的方法是将直线拆成两条射线,然后射线 $s\to t$ 和线段 $cd$ 判交,然后直线 $st$ 和直线 $cd$ 求交点即可。

实现的时候参考 Heltion 的代码学到很多!代码中有很妙的技巧,限于篇幅 没时间写 就先只贴一下我的代码

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
#include <bits/stdc++.h>
#define N 1000007
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

struct vec {
long double x, y;
long double norm2() const {return x * x + y * y;}
long double norm() const {return sqrt(norm2());}
vec operator + (const vec &obj) const {return (vec){x + obj.x, y + obj.y};}
vec operator - (const vec &obj) const {return (vec){x - obj.x, y - obj.y};}
vec operator * (const long double &t) const {return (vec){x * t, y * t};}
long double operator * (const vec &obj) const {return x * obj.x + y * obj.y;}
long double cross (const vec &obj) const {return x * obj.y - y * obj.x;}
long double dis(const vec &obj) const {return ((*this) - obj).norm();}
};

bool cross(const vec &s, const vec &t, const vec &c, const vec &d) {
long double w1 = (t - s).cross(c - s);
long double w2 = (t - s).cross(d - s);
long double w3 = (d - c).cross(s - c);
long double w4 = (d - c).cross(t - c);
long double w5 = (d - c).cross(t - s);
if (w1 * w2 > 0 || (w3 * w4 > 0 && w3 * w5 > 0)) return 0;
if (w1 * w2 < 0 || w3 * w4 < 0) return 1;
long double v1 = (t - s) * (c - s);
long double v2 = (t - s) * (d - s);
return (v1 >= 0 || v2 >= 0);
}

vec cross_point(const vec &a, const vec &b, const vec &c, const vec &d) {
vec d0 = b - a, d1 = d - c, u = c - a;
long double t = u.cross(d1) / d0.cross(d1);
return a + d0 * t;
}

int main() {
int n = rd(), m = rd();
vector<vec> p(n), q(m);
for (auto& [x, y] : p) {x = rd(); y = rd();}
for (auto& [x, y] : q) {x = rd(); y = rd();}
vector<long double> sum(n);
for (int i = 0; i < n; ++i) {
sum[i] = (p[i] - p[(i + 1) % n]).norm();
if (i) sum[i] += sum[i - 1];
}
int f = 0, t = 0;
long double ans = 0;
for (int i = 0; i < m; ++i) {
const vec &A = q[i], &B = q[(i + 1) % m];
while (!cross(B, A, p[f], p[(f + 1) % n])) f = (f + 1) % n;
while (!cross(A, B, p[t], p[(t + 1) % n])) t = (t + 1) % n;
long double df = cross_point(B, A, p[f], p[(f + 1) % n]).dis(p[f]) + sum[(f - 1 + n) % n];
long double dt = cross_point(A, B, p[t], p[(t + 1) % n]).dis(p[t]) + sum[(t - 1 + n) % n];
if (dt < df) dt += sum.back();
ans += (A - B).norm() * (dt - df);
}
printf("%.15Lf\n", ans / sum.back());
return 0;
}

G. Occupy the Cities

给一个 $01$ 序列,每秒每个 $1$ 可以选择将左侧右侧的数变成 $1$ ,问最少多少秒全部变成 $1$ 。

可以发现连续 $1$ 的长度大于 $1$ 时,每秒向左向右都可以扩展 $1$ 个位置。

因此考虑二分答案 $x$ ,从左往右依次判断,对于长度大于 $1$ 的连续段直接计算左右扩展范围。

对于单个的 $1$ ,如果 $x-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
#include <bits/stdc++.h>
#define N 500007
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

inline int rdc() {
char c = getchar();
while (!isdigit(c)) c = getchar();
return c - '0';
}

int n, tot;

struct seg {int l, r;}c[N];

inline void add(int l, int r) {
c[++tot].l = l; c[tot].r = r;
}

inline bool valid(int x) {
int nwr = 0;
for (int i = 1, dis; i <= tot; ++i) {
dis = c[i].l - nwr - 1;
if (dis > x) return 0;
nwr = c[i].r + x;
if (c[i].r == c[i].l && dis == x) --nwr;
}
return nwr >= n;
}

inline void work() {
n = rd(); tot = 0;
int l = 0, r = 0;
for (int i = 1; i <= n; ++i) {
int x = rdc();
if (x) {if (!l) l = i; r = i;}
else {if (l) add(l, r); l = 0; r = 0;}
}
if (l) add(l, r);
if (c[1].l == 1 && c[1].r == n) {puts("0"); return;}
l = 1; r = n;
while (l < r) {
int mid = (l + r) / 2;
valid(mid) ? r = mid : l = mid + 1;
}
printf("%d\n", l);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

此外官方题解给出了两个 $O(n)$ 的写法。我尝试了一下 WA 了并且非常难调遂放弃了…

I. PTSD

$n$ 个数 $1,\cdots ,n$ ,第 $i$ 个数有权值 $a_i=0/1$ 。将所有数划分成若干组,答案为每组第二大 $i\times a_i$ 的和。

贪心的拿正确性比较显然,同情况下第二名可以是大的一定拿大的,可以多拿一定多拿。

因此方案就是尽可能两两一组,第二大的 $a_i=1$ ,第一大的 $a_i=0$ 。

因此维护一个 cnt,记录还有多少个比当前大的数字还没被分组。

从大往小考虑,只要 cnt>0 并且 $a_i=1$ 就将 $i$ 累加进答案,--cnt,否则 ++cnt

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
#include <bits/stdc++.h>
#define N 1000007
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

inline int rdc() {
char c = getchar();
while (!isdigit(c)) c = getchar();
return c - '0';
}

int n, a[N], tot;

inline void work() {
n = rd(); tot = 0;
for (int i = 1; i <= n; ++i) a[i] = rdc();
ll ans = 0;
for (int i = n; i; --i) {
if (a[i] && tot) {ans += i; --tot;}
else ++tot;
}
printf("%lld\n", ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

J. Suffix Automaton

队友强强补掉了~ 有空再来看

K. Tax

队友强强补掉了~ 有空再来看


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!