The 46th ICPC Asia Shenyang Regional

Summary

热身赛的ABC都是去年沈阳的三道签到题,D 题是计算几何 HDU 6697。

Closest Pair of Segments    Author:Yaohui Zeng

二分答案之后考虑将线段扩张成 “香肠”,检查是否有一对“香肠”相交。

考虑对 $x$ 扫描线,用 set 维护这些香肠关于 $y$ 的顺序,那么总是只需要检查相邻的两个香肠是否相交。亦即,对于一个插入事件,检查新的香肠是否和上下相邻的两个香肠相交,对于一个删除事件,删除香肠之后检查上下两个相邻的香肠是否相交。如果判定到相交说明答案偏大,否则答案偏小。

由于在判定到相交之前的扫描过程中,香肠都是互不相交的凸图形,可以简单地用一条连接香肠最左点和最右点的线段来描述香肠在扫描线上的相对顺序,判定香肠相交直接计算扩张前的两个线段的距离即可。

复杂度是 $O(n\log n\log (1/\epsilon))$ 。

正赛开场签 BEFJ 比较顺利,F 卡了一会 charstring 不能直接 + ,后来改字符数组了。

之后两个半小时没过题,H 假做法 + 假代码卡了两个多小时过了。

然后 I 简单分讨了一下,不想调破罐子破摔就直接过了,这个时候刚封榜。

最后 1h 队友搞 L,最后 5 min 成功冲出来了!非常激动!

虽然又是遗憾银首,但这次参赛体验还是很棒的,收获很多。

首先是虽然中期血崩,但是还是顶住了,在最后一个多小时补救了三题。赛后看看觉得题目并不难,重点还是赛中要有信心,I 题这种题其实有信心的话很早就可以冲出来了。

然后就是相信队友,在最后一个小时还是担心过一段时间的,甚至有点想抢机位写 G 。好在综合过题数考虑后,最后一个小时决定让队友集中精力,搞出来了 L。此外负责乱搞和思路题的队友这场也相当给力,J 题上机之后很快就过了,没有像往常一样调试很久,I 题的推式子也是他提供的方向。整场比赛中真实的感受到整个队都有在努力,很满足。

Resource

热身赛题面.pdf   正式赛题面.pdf   官方题解.pptx

B. Bitwise Exclusive-OR Sequence

构造 $n$ 个数 $a_1,\dots,a_n$,满足 $m$ 个约束条件,形如 $a_{p_i}\oplus a_{q_i} = w_i$ ,且 $\sum a_i$ 最小。

按位考虑,那么按照每一位都可以建出来一张图,边权为 $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
#include <bits/stdc++.h>
#define N 200007
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 n, m;

struct node {int a, b, w;} c[N];

ll ans = 0;

int tot, cnt[2], hd[N], col[N];

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

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

bool fl = 0;

void dfs(int u) {
++cnt[col[u]];
for (int i = hd[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (col[v] != -1) {
if (col[v] != (col[u] ^ e[i].w)) {fl = 1; return;}
continue;
}
col[v] = (col[u] ^ e[i].w);
dfs(v); if(fl) return;
}
}

inline bool work(int p) {
tot = 0;
for (int i = 1; i <= n; ++i) hd[i] = 0, col[i] = -1;
for (int i = 1; i <= m; ++i)
add(c[i].a, c[i].b, ((c[i].w & (1 << p)) > 0));
for (int i = 1; i <= n; ++i)
if (col[i] == -1) {
cnt[0] = 0; cnt[1] = 0;
col[i] = 0; dfs(i);
if (fl) return 1;
ans += 1ll * (1 << p) * min(cnt[0], cnt[1]);
}
return 0;
}

int main() {
n = rd(); m = rd();
for (int i = 1; i <= m; ++i) {
c[i].a = rd(); c[i].b = rd(); c[i].w = rd();
}
for (int i = 30; i >= 0; --i)
if (work(i)) {puts("-1"); return 0;}
printf("%lld\n", ans);
return 0;
}

E. Edward Gaming, the Champion

给定一个串,数串里有多少个 edgnb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
#define N 200007
using namespace std;

int ans;
char s[N];

int main(){
scanf("%s", s);
for (int i = 0; s[i]; ++i)
if (!strncmp(s + i, "edgnb", 5)) ++ans;
printf("%d\n", ans);
return 0;
}

F. Encoded Strings I

设从后往前看,字符 $c$ 第一次出现之前出现过 $k$ 个不同的字母,则映射 f(c)='a'+k

定义一个串 $s$ 的 Encoded String $s’$ :对 $\forall i\le |s|, s’[i] = f(s[i])$

求给定串所有前缀对应的 Encoded String 中,字典序最大的那个。

暴力求,然后按字典序排序。

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

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;
}

char S[N];

map<char, int> f;

struct node {
int len;
char a[N];
}s[N];

inline bool cmp(node a, node b) {
int tot = min(a.len, b.len);
for (int i = 1; i <= tot; ++i)
if (a.a[i] != b.a[i]) return a.a[i] < b.a[i];
return a.len < b.len;
}

inline void work(int p) {
int cnt = 0; f.clear();
s[p].len = p;
for (int i = p; i; --i) {
if (!f[S[i]]) f[S[i]] = ++cnt;
s[p].a[i] ='a' - 1 + f[S[i]];
}
}

int main() {
int n = rd();
scanf("%s", S + 1);
for (int i = 1; i <= n; ++i) work(i);
sort(s + 1, s + 1 + n, cmp);
for (int i = 1; i <= s[n].len; ++i) putchar(s[n].a[i]);
puts("");
return 0;
}

H. Line Graph Matching

一个猜结论 + tarjan 题

I. Linear Fractional Transformation

定义复数函数 $f(z)=\frac{az+b}{cz+d}\ (a,b,c,d\in \mathbb{C},ad-bc\not=0)$,给定 $f(z_1)=w_1,f(z_2)=w_2,f(z_3)=w_3$ ,求 $f(z_0)$

数据保证 $z_1,z_2,z_3,w_1,w_2,w_3$ 两两不同

  1. 若 $c=0$ ,则 $f(z)=kz+b$ ,直接用两个方程把 $k,b$ 求出后,判断第三个方程是否正确,然后代入即可。

  2. 若 $c\not = 0$ ,则 $zf(z)+k_3f(z)=k_1z+k_2$ ,手动消元一下得:
    $$
    k_3=\displaystyle\frac{(w_2z_2 - w_1z_1) - \displaystyle\frac{z_2-z_1}{z_3-z_1} * (w_3z_3 - w_1z_1)}{\displaystyle\frac{z_2-z_1}{z_3-z_1} * (w_3 - w_1) - (w_2 - w_1)}
    $$

比赛的时候本来想用自带的 complex<double> 类,但是发现 realimag 不能直接赋值,就不会用了遂手写…

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
#include <bits/stdc++.h>
#define N 200007
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 double sqr(double x) {
return x * x;
}

struct cp {
double a, b;
inline cp operator + (const cp &obj) const{
return (cp){a + obj.a, b + obj.b};
}
inline cp operator - (const cp &obj) const{
return (cp){a - obj.a, b - obj.b};
}
inline cp operator * (const cp &obj) const{
return (cp){a * obj.a - b * obj.b, a * obj.b + b * obj.a};
}
inline cp operator / (const double x) const {
return (cp){a / x, b / x};
}
inline cp operator / (const cp &obj) const{
return (cp){a * obj.a + b * obj.b, b * obj.a - a * obj.b} / (sqr(obj.a) + sqr(obj.b));
}
inline bool operator == (const cp &obj) const{
return (fabs(a - obj.a) <= 1e-6 && fabs(b - obj.b) <= 1e-6);
}
};

inline void work() {
cp z0, z1, z2, z3, w1, w2, w3;
z1.a = rd(); z1.b = rd(); w1.a = rd(); w1.b = rd();
z2.a = rd(); z2.b = rd(); w2.a = rd(); w2.b = rd();
z3.a = rd(); z3.b = rd(); w3.a = rd(); w3.b = rd();
z0.a = rd(); z0.b = rd();

cp k = (w2 - w1) / (z2 - z1);
cp b = w1 - k * z1;
if (w3 == k * z3 + b) {
cp res = k * z0 + b;
printf("%.10lf %.10lf\n", res.a, res.b);
return;
}
cp g1, g2, g3;
g1 = z1 * w1; g2 = z2 * w2; g3 = z3 * w3;
cp kk = (z2 - z1) / (z3 - z1);
cp k3 = ((g2 - g1) - kk * (g3 - g1)) / (kk * (w3 - w1) - (w2 - w1));
cp k1 = ((g2 - g1) + k3 * (w2 - w1)) / (z2 - z1);
cp k2 = z1 * w1 + k3 * w1 - k1 * z1;
cp res = (k1 * z0 + k2) / (z0 + k3);
printf("%.10lf %.10lf\n", res.a, res.b);
}

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

题解提供的做法比较神仙,先抄上:分式线性变换保交换比,有:
$$
\frac{w_0-w_1}{w_0-w_2}\bigg/\frac{w_3-w_1}{w_3-w_2}=\frac{z_0-z_1}{z_0-z_2}\bigg/\frac{z_3-z_1}{z_3-z_2}
$$

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
#include <bits/stdc++.h>
using namespace std;

typedef complex<double> C;

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 C rdc() {
int x = rd(), y = rd();
return C(x, y);
}

inline void work() {
C z1 = rdc(), w1 = rdc(), z2 = rdc(), w2 = rdc(), z3 = rdc(), w3 = rdc(), z0 = rdc();
C res = ((z0 - z1) / (z0 - z2)) / ((z3 - z1) / (z3 - z2)) * ((w3 - w1) / (w3 - w2));
res = w2 + (w2 - w1) / (res - C(1, 0));
printf("%.12lf %.12lf\n", res.real(), res.imag());
}

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

J. Luggage Lock

队友强强切掉了~回头再来看

L. Perfect Matchings

队友强强切掉了~回头再来看


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