2024-09-102024-10-18Contest Notes

VP 2023 SDCPC

Problems	AC
A. Orders	○
B. Building Company	○
C. Trie
D. Fast and Fat	○
E. Math Problem	○
F. Colorful Segments	⊕
G. Matching	○
H. Be Careful 2
I. Three Dice	○
J. Not Another Path Query Problem	⊕
K. Difficult Constructive Problem
L. Puzzle: Sashigane	○
M. Computational Geometry	○

E 数学

给定 $n$ 和 $k$, 可以进行以下两种操作任意次：

选择一个整数 $x$ 满足 $0 \leq x<k$, 将 $n$ 变为 $k \cdot n+x$ 。该操作每次花费 $a$ 枚金币。每次选择的整数 $x$ 可以不同。

将 $n$ 变为 $\left\lfloor\frac{n}{k}\right\rfloor$ 。该操作每次花费 $b$ 枚金币。其中 $\left\lfloor\frac{n}{k}\right\rfloor$ 表示小于等于 $\frac{n}{k}$ 的最大整数。

给定正整数 $m$, 求将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。

一个道理是，一定是先除再乘。因为这里是整除，会把你先乘上去的东西除掉，就没有意义。

进行 $p$ 次乘法操作后，$n$ 的范围是 $[k^p \times n, k^p \times (n + 1) )$，只要这个范围里面包括 $m$ 的倍数即可停止乘法操作。因此乘法操作至多进行 $\log_k m$ 次

除法操作类似，最多 $\log_k n$ 次。

$O(\log_k n \times \log_k m)$ 枚举即可

J 位运算

类似于数位 dp 的思想，大于 $V$ 的数都与 $V$ 都有一段前缀与 $V$ 相同，我们枚举这个前缀的长度 $i$。

那么对于 $V$ 和 $V^{\prime}$ 的前 $i$ 高位是相同的，则 $V$ 第 $i + 1$ 位上的情况只能是 $0$，$V^{\prime}$ 则是 $1$。那么剩下的位都是可以任意选择的。

那么我们只要让这 $i + 1$ 个 $0$ 都出现，用 BFS 判断连通性即可。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
i64 read(i64 x = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return x;
}

void solve() {
    int n = read(), m = read(), q = read();
    int V = read();

    using pii = std::pair<int, int>;
    #define fi first
    #define se second

    vector<vector<pii>> g(n + 1);

    while (m--) {
        int u = read(), v = read();
        int w = read();

        g[u].eb(v, w);
        g[v].eb(u, w);
    }

    vector<int> ans(q);
    vector<pii> qry(q);
    for (auto &[x, y] : qry) {
        x = read(), y = read();
    }

    auto check = [&](int V) {
        int cnt = 0;
        vector<int> bel(n + 1);

        std::function<void(int, int)> bfs = [&](int s, int V) {
            std::queue<int> q;
            q.push(s), bel[s] = ++cnt;

            while (!q.empty()) {
                int u = q.front(); q.pop();

                for (auto [v, dis] : g[u]) {
                    if (bel[v] or (dis & V) != V) continue;
                    bel[v] = bel[u];
                    q.push(v);
                }
            }
        };

        for (int i = 1; i <= n; i++) {
            if (!bel[i]) {
                bfs(i, V);
            }
        }

        for (int i = 0; i < q; i++) {
            auto &[x, y] = qry[i];
            ans[i] |= (bel[x] == bel[y]);
        }
    };

    if (V == 0LL) {
        check(0);
    } else {
        for (int t = V; t < (1LL << 60); t += t & (-t)) {
            check(t);
        }
    }

    for (auto x : ans) {
        puts(x ? "Yes" : "No");
    }
}

signed main() {
    solve();
    return 0;
}

F 线段树优化 DP

有 $n$ 条线段，第 $i$ 条线段的颜色为 $c_i$ $(0 \le ci \le 1)$。
您需要选择若干条线段。
如果选择的两条线段有重合，则这两条线段的颜色必须相同。
求选择线段的不同方案数。

$1 \le n \le 10^5$

这题其实和暑假给小朋友出的一个题形式类似，都是 dp 乘上一个 2 的幂次形式的。两个结合一下感觉还是很套路的。

官方题解上面介绍了一种常见的错误解法。在这种解法中，将线段按右端点排序，并单独考虑每条线段。状态的设置并不包括线段的颜色，所以在考虑第一条线段的时候，并不一定能从前面的状态转移，因为这条线段可能和之前的方案有冲突。

所以每次我们要同时考虑线段的颜色，设 $f(i, c)$ 表示前 $i$ 条线段中，$i$ 必选，且线段 $i$ 的颜色是 $c$ 的方案数。转移时，我们枚举上一条选的线段 $j$（必须颜色不同），则前 $i - 1$ 条线段中，左端点大于 $r_j$ 的线段都可以随便选，转移方程就是：

$$
f(i, c) = \sum_{j = 0}^{p_i} f(j, 1 - c) \times 2 ^ {g(i - 1, r_j + 1, c)}
$$

其中，对于每个 $i$，$p_i$ 可以一只 log 二分出来。

考虑维护 $g$，容易发现，每加入一条线段 $i$，会让一段前缀都乘上 2 （相当于可选择的线段多了一条）。

用线段树维护一下即可。更详细的题解详见官方题解

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
i64 read(i64 x = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return x;
}
template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

struct SGT {
	#define mid (l + r >> 1)
	#define ls (p << 1)
	#define rs (p << 1 | 1)
	vector<Z> sum, laz;

	SGT() {}
    SGT(int n) { init(n); }

    void init(int n) { 
    	int siz = 4 * n + 5;
    	sum.resize(siz), laz.resize(siz);
    	sum.assign(siz, 0), laz.assign(siz, 1);
    }

    void down(int p) {
    	auto &t = laz[p];
    	if (t == 1) return;

    	sum[ls] *= t;
    	sum[rs] *= t;
    	laz[ls] *= t;
    	laz[rs] *= t;
    	t = 1;
    }
    void up(int p) {
    	sum[p] = sum[ls] + sum[rs];
    }

    void add(int p, int l, int r, int pos, Z val) {
    	if (l == r) {
    		sum[p] += val;
    	} else {
    		down(p);
	    	if (pos <= mid) add(ls, l, mid, pos, val);
	    	else add(rs, mid + 1, r, pos, val);
	    	up(p);	
    	}
    }

    void mul2(int p, int l, int r, int pos) {
    	if (r <= pos) {
    		sum[p] *= 2;
    		laz[p] *= 2;
    	} else {
    		down(p);
    		mul2(ls, l, mid, pos);
    		if (mid < pos) mul2(rs, mid + 1, r, pos);
    		up(p);
    	}
    }

    Z query(int p, int l, int r, int pos) {
    	if (r <= pos) {
    		return sum[p];
    	} else {
    		down(p);
    		Z res = query(ls, l, mid, pos);
    		if (mid < pos) res += query(rs, mid + 1, r, pos);
    		up(p);
    		return res;
    	}
    }

};

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

	vector<std::array<int, 3>> a(n + 1);
	for (int i = 1; i <= n; i++) {
		for (auto &x : a[i]) {
			x = read();
		}
	}

	std::sort(a.begin() + 1, a.end(), [](auto a, auto b){
		return a[1] < b[1];
	});

	SGT t[2] {SGT(n), SGT(n)};

	for (int k = 0; k < 2; k++) {
		t[k].add(1, 0, n, 0, 1);
	}

	Z ans = 1;
	for (int i = 1; i <= n; i++) {
		int p = 0;
		int &c = a[i][2];
		for (int l = 0, r = i - 1; l <= r; ) {
			if (a[mid][1] < a[i][0]) p = mid, l = mid + 1;
			else r = mid - 1;
		}

		Z val = t[c ^ 1].query(1, 0, n, p);
		t[c].add(1, 0, n, i, val);
		t[c ^ 1].mul2(1, 0, n, p);
		ans += val;
	}
	cout << ans << '\n';
}

signed main() {
    for (int T = read(); T--; solve());
    return 0;
}

VP 2023 SDCPC

https://tosakaucw.github.io/vp-2023-sdcpc/

Author

TosakaUCW

Posted on

2024-09-10

Updated on

2024-10-18

Licensed under

#XCPC VP

VP 2023 SDCPC

E 数学

J 位运算

F 线段树优化 DP

Author

Posted on

Updated on

Licensed under

Comments

Catalogue