2021-2022 ICPC Asia Shenyang Regional

Summary

还没补完：ACGKLM

难度：BEFJ - HIL - DM - ACG - K

热身赛 D - Closest Pair of Segments

原题是 HDU 6697 。

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

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

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

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

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\) 即可最小化。

复杂度 \(O(n\log \max a_i)\) 。

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

D - Cross the Maze

E - Edward Gaming, the Champion

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

#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 中，字典序最大的那个。

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

#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

给定一个带权图，求对应线图的最大权匹配。

按照线图的最大匹配算法，每个连通块中，如果边数是偶数就可以完美匹配，否则只需要扔掉一条边。

可以扔掉的条件是删除后形成的新连通块边数都是偶数，即删掉非割边或两侧边数都是偶数的割边。复杂度 \(O(n)\) 。

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\) 两两不同。

若 \(c=0\) ，则 \(f(z)=kz+b\) ，直接用两个方程把 \(k,b\) 求出后，判断第三个方程是否正确，然后代入即可。
若 \(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> 类，但是发现 real 和 imag 不能直接赋值，就不会用了遂手写...

#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} \]

#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

一个四位锁，每次可以把一个区间往上或往下拨动 \(1\) ，多次询问：

从 \(a_1a_2a_3a_4\) 状态拨到 \(b_1b_2b_3b_4\) 状态最少需要拨动的次数。

容易发现答案只和对应位的差有关，问题变为 \(0000\) 拨到 \(x_1x_2x_3x_4\) 所需的最少次数，bfs 求最短路。计算量 \(10^4\times 10\times 4\) 。

#include<bits/stdc++.h>
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 bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

#define N 10000

queue<int> q;

int dis[N];

int main() {
    memset(dis, 0x3f, sizeof(dis));
    q.push(0); dis[0] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        int a[4] = {u / 1000, u % 1000 / 100, u % 100 / 10, u % 10};
        for (int x = 1; x <= 4; ++x) {
            for (int l = 0; l <= 4 - x; ++l) {
                // up
                int v = 0;
                for (int i = 0; i < 4; ++i) 
                    if (i >= l && i < l + x) v = v * 10 + (a[i] + 1) % 10;
                    else v = v * 10 + a[i];
                if (dis[v] > dis[u] + 1) {dis[v] = dis[u] + 1; q.push(v);}
                v = 0;
                for (int i = 0; i < 4; ++i) 
                    if (i >= l && i < l + x) v = v * 10 + (a[i] + 9) % 10;
                    else v = v * 10 + a[i];
                if (dis[v] > dis[u] + 1) {dis[v] = dis[u] + 1; q.push(v);}
            }
        }
    }
    for (int t = rd(); t; --t) {
        int u = rd(), v = rd();
        int a[4] = {u / 1000, u % 1000 / 100, u % 100 / 10, u % 10};
        int b[4] = {v / 1000, v % 1000 / 100, v % 100 / 10, v % 10};
        int dlt = 0;
        for (int i = 0; i < 4; ++i) dlt = dlt * 10 + (b[i] - a[i] + 10) % 10;
        printf("%d\n", dis[dlt]);
    }
    return 0;
}

Official Contests

Graphs Connectivity

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

AtCoder Beginner Contest 237 Previous

AtCoder Beginner Contest 216 Next