2024 ICPC 网络赛 第二场

The 2024 ICPC Asia EC Regionals Online Contest (II)

双打 7 题，成功翻盘出线！！！

赛时榜单

Problems	AC
A. Gambling on Choosing Regionals	○
B. Mountain Booking
C. Prefix of Suffixes
D. Query on Tree
E. Escape	○
F. Tourist	○
G. Game	○
H. Points Selection
I. Strange Binary	○
J. Stacking of Goods	○
K. Match
L. 502 Bad Gateway	○

F 签到

void solve() {
    int n = read();
    int now = 1500;

    for (int i = 1; i <= n; i++) {
        now += read();

        if (now >= 4000) {
            cout << i;
            return;
        }
    }

    puts("-1");
}

J 排序

微扰法进行排序

struct Node {
    int w, v, c;
    bool friend operator < (Node a, Node b) {
        return a.w * b.c < b.w * a.c;
    }
};

void solve() {
    int n = read();

    vector<Node> a(n);
    for (int i = 0; i < n; i++) {
        a[i].w = read();
        a[i].v = read();
        a[i].c = read();
    }

    std::sort(a.begin(), a.end());

    i64 ans = 0;
    i64 sum = 0;
    for (int i = 0; i < n; i++) sum += a[i].w, ans += a[i].v;

    i64 tot = 0;
    for (int i = 0; i < n; i++) {
        ans -= a[i].c * sum;

        tot += a[i].w;
        ans += a[i].c * tot;
    }
    cout << ans << '\n';
}

I 二进制

L 期望

A

G gcd

E 分层图，奇偶 bfs

C border

解法一

每次新加入一个字符 $c_i$ 时，考虑答案的增量。

如果加入这个字符后，$z_j$ 变大了 $1$，那么答案就会增加 $B_j \times A_i$。

反之如果 $z_j$ 没有变大，那么以后就再也不会变大了，对应的 $B_j$ 以后也不会再有贡献了。

用 vector 动态地存那些没有被确定 $z$ 的位置。谔谔这个复杂度真的对吗，不会算，但是自己试随机数据好像均摊下来并没有多少。

void solve() {
	int n = read();

	vector<int> rems;
	i64 ans = 0, sumb = 0;

	vector<int> a(n), b(n), c(n);

	for (int i = 0; i < n; i++) {
		c[i] = read(), a[i] = read(), b[i] = read();

		c[i] = (c[i] + ans) % n;

		if (c[i] == c[0]) {
			sumb += b[i];
			rems.eb(i);
		}

		vector<int> nrems;

		for (int j : rems) {
			if (c[i] == c[i - j]) {
				nrems.eb(j);
			} else {
				sumb -= b[j];
			}
		}

		rems = std::move(nrems);
		ans += a[i] * sumb;
		cout << ans << "\n";
	}
}