第九届中国大学生程序设计竞赛（深圳）

现场题解：CCPC2023深圳-题目讲解

A. 一道好题

不错的分治题，作为签到刚刚好

题意 初始为 0 的序列，两种操作，一是给下标为xx 的数+1+1，二是给值为xx 的数+1+1，至多2000020000 次操作得到目标序列。n⩽1000n \leqslant 1000。

思路 对操作分治，则操作一每个数至多log⁡n\log n 次，操作二至多nn 次，总次数是Θ(nlog⁡n)\Theta(n\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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<pair<int, int>> res;
    auto dfs = [&](auto&& self, int l, int r) -> void {
        if (r - l < 2) return;
        int mid = l + r >> 1;
        for (int i = 0; i < n; ++i) {
            if (mid <= a[i] && a[i] < r) {
                res.push_back({ 2, i + 1 });
            }
        }
        for (int i = l + 1; i < mid; ++i) {
            res.push_back({ 1, i });
        }
        self(self, l, mid);
        self(self, mid, r);
    };
    dfs(dfs, 0, n + 1);

    cout << res.size() << "\n";
    for (auto& [a, b] : res) {
        cout << a << " " << b << "\n";
    }

    return 0;
}
/**********************************************************************
	Problem: 1237
	User: KobicGend
	Language: C++
	Result: AC
	Time:24 ms
	Memory:2548 kb
**********************************************************************/

简单的验证程序：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n = 4;
    vector<int> a(n);

    int q;
    cin >> q;
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            for (int i = 0; i < n; ++i) {
                if (a[i] == x) a[i]++;
            }
        }
        else {
            x--;
            a[x]++;
        }
    }
    
    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }

    return 0;
}

初见时写的代码（略有修改）：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

	int n;
    cin >> n;

    vector<pair<int, int>> a(n);
	for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
		a[i] = { x, i + 1 };
	}
	sort(a.begin(), a.end());

    vector<pair<int, int>> ans;
    auto solve = [&](auto&& self, int l, int r, int mn = 0) -> void {
        if (l > r) return;
        int mx = -1, mxnum = 0;
        for (int i = l; i <= r; ++i) {
            if ((r - i + 1) * (a[i].first - mn) > mx) {
                mx = (r - i + 1) * (a[i].first - mn);
                mxnum = i;
            }
        }
        if (a[mxnum].first > mn) {
            for (int i = mxnum; i <= r; ++i) {
                ans.push_back({ 2, a[i].second });
            }
        }
        for (int i = mn + 1; i < a[mxnum].first; ++i) {
            ans.push_back({ 1, i });
        }
        self(self, mxnum + 1, r, a[mxnum].first);
        self(self, l, mxnum - 1, mn);
    };
    solve(solve, 0, n - 1);

	cout << ans.size() << "\n";
	for (auto [k, v] : ans) {
		cout << k << " " << v << "\n";
	}

    return 0;
}

/**********************************************************************
	Problem: 1237
	User: KobicGend
	Language: C++
	Result: AC
	Time:19 ms
	Memory:2552 kb
**********************************************************************/

F. 见面礼

小思维，初学图论时的练习题，队友提的思路我写的代码，做出来还是很得意的。当时不懂基环树，写了个很丑的 dfs 找环

题意 给定一个无向图，你需要求有多少种选择图上的一个点 pp 和一条边的方案，使得删去这条边后图变成一棵树，且这棵树以 pp 为根时每个节点的儿子个数均不超过33。保证至少存在一种这样的方案。

思路 保证有解所以一定是基环树，删去的边是环上的边，而且每个点的度数⩽5\leqslant 5 。枚举删去的边，剩下的点如果有度数为55 的，则不合法，如果合法，度数⩽3\leqslant 3 的点都可以为根。

时间复杂度Θ(n)\Theta(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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

	int n;
    cin >> n;

    vector<vector<pair<int, int>>> E(n);
	for (int i = 0; i < n; ++i) {
		int u, v;
        cin >> u >> v;
        u--, v--;
		E[u].push_back({ v, i });
		E[v].push_back({ u, i });
	}

	// 拓扑排序
	queue<int> Q;
    vector<int> deg(n), vis(n);
	for (int u = 0; u < n; ++u) {
        deg[u] = E[u].size();
		if (deg[u] == 1) Q.push(u);
	}
	while (!Q.empty()) {
		int v = Q.front(); Q.pop();
        vis[v] = 1;
		for (auto [u, id] : E[v]) {
			if (deg[u] > 1) {
				if (--deg[u] == 1) Q.push(u);
			}
		}
	}

    // dfs找环
    vector<int> V;
	for (int u = 0; u < n; ++u) {
		if (vis[u]) continue; 
        V.push_back(u);
		int fromid = -1;
		do for (auto [v, id] : E[V.back()]) {
			if (deg[v] != 1 && id != fromid) {
				vis[v] = 1;
                fromid = id;
				V.push_back(v);
				break;
			}
		} while (u != V.back());
    }

	ll ans = 0;
	vector<int> cnt(6);
	for (int u = 0; u < n; ++u) {
        deg[u] = E[u].size();
		cnt[deg[u]]++;
	}
	for (int i = 1; i < V.size(); ++i) {
		int u = V[i], v = V[i - 1];
		auto tcnt = cnt;
		--tcnt[deg[u]];
		--tcnt[deg[v]];
		++tcnt[deg[u] - 1];
		++tcnt[deg[v] - 1];

		if (tcnt[5]) continue;
		ans += tcnt[1] + tcnt[2] + tcnt[3];
	}

	cout << ans << "\n";

    return 0;
}
/**********************************************************************
	Problem: 1242
	User: KobicGend
	Language: C++
	Result: AC
	Time:85 ms
	Memory:9448 kb
**********************************************************************/

丑陋的 dfs：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool flag = 0;
void dfs(int u, int fau = 0) {
	if (vis[u]) {
		circle.push_back(u);
		for (int i = fau; i != u; i = fa[i]) {
			circle.push_back(i);
		}
		flag = 1;
		circle.push_back(u);
		return;
	}
	vis[u] = 1;
	fa[u] = fau;
	for (auto v : E[u]) {
		if (v != fau) {
			dfs(v, u);
			if (flag) return;
		}
	}
}

G. 相似基因序列问题

题意 给定 nn 个长度为 mm 的字符串 s1,…,sNs_1, \dots,s_N。定义两个字符串相似：最多只有 kk 个对应字母不同。qq 组询问，每次给出一个长度为 mm 的字符串，问与几个sis_{i} 相似。数据范围：1⩽n,q⩽3001 \leqslant n, q \leqslant 300，1⩽m⩽60,0001 \leqslant m \leqslant 60,000，1⩽K⩽101 \leqslant K \leqslant 10。

思路 突破口是kk 很小，也就是说字符串大部分是相同的，用倍增 / 二分跳到下一个不相同的位置。n,qn,q 也很小，所以两两匹配就行。时间复杂度Θ(qnklog⁡m)\Theta(qnk\log m)。

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ulll = __uint128_t;

constexpr int N = 1e6 + 8;
constexpr ull mod = (1ull << 61) - 1;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ull> dist(mod / 2, mod - 1);
const ull H = dist(rnd);

struct mull {
    ull x;
    constexpr mull(ull x = 0) : x{ norm(x) } {}
    constexpr ull norm(ull x) const { return x >= mod ? x - mod : x; }
    friend constexpr mull operator*(mull a, mull b) { return ulll(a.x) * b.x % mod; }
    friend constexpr mull operator+(mull a, mull b) { return a.norm(a.x + b.x); }
    friend constexpr mull operator-(mull a, mull b) { return a.norm(a.x + mod - b.x); }
    friend constexpr bool operator==(mull a, mull b) { return a.x == b.x; }
    friend constexpr bool operator!=(mull a, mull b) { return a.x != b.x; }
} power[N];

struct Hash {
    string s;
    vector<mull> h;
    Hash() {
        cin >> s;
        init(s);
    }
    Hash(const string& s) : s(s) {
        init(s);
    }
    void init(const string& s) {
        if (power[0] == 0) {
            power[0] = 1;
            for (int i = 1; i < N; i++) {
                power[i] = power[i - 1] * H;
            }
        }
        const int n = s.;
        h.resize(n + 1);
        for (int i = 0; i < length(); i++) {
            h[i + 1] = h[i] * H + s[i];
        }
    }
    mull operator()(int l, int r) {
        return h[r] - h[l] * power[r - l];
    }
    auto length() {
        return s.length();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, q, m, k;
    cin >> n >> q >> m >> k;

    vector<Hash> s(n);

    while (q--) {
        Hash t;
        
        int res = 0;
        for (int id = 0; id < n; ++id) {
            int kcnt = 0, i = 0;
            while (i < m) {  // 比较第i位是否相同
                if (t(i, i + 1) != s[id](i, i + 1)) {
                    if (++kcnt > k) break;
                }
                int len = m - i;
                while (len) {
                    if (t(i, i + len) != s[id](i, i + len)) len /= 2;
                    else break;
                }
                i += max(1, len);
            }
            res += kcnt <= k;
        }
        cout << res << endl;
    }

    return 0;
}

I. 不定方程

讨厌推式子，讨厌炸 LL 且用 double 会炸精度的题

题意 求不定方程n=ak−bkn=a^{k}-b^{k} 的正整数解。

思路a−b∣na-b\mid n，枚举nn 的约数t=a−bt=a-b。但枚举约数的复杂度是n\sqrt{ n } 的，需要优化。事实上a−ba-b 不会很大，做个简单的估计：

n=ak−bk⩾a3−b3=(a−b)(a2+ab+b2)>ta2>t3n=a^{k}-b^{k} \geqslant a^{3}-b^{3}=(a-b)(a^{2}+ab+b^{2})>ta^{2}>t^{3}

因此t⩽n3⩽106t \leqslant \sqrt[3]{ n } \leqslant 10^{6}。代入得n=(t+b)k−bkn=(t+b)^{k}-b^{k}，单调，二分bb 看是否有整数解。

慎用 double。

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>
using namespace std;
using ll = long long;
constexpr ll mx = 1e12;
constexpr ll inf = 2e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        ll n, k;
        cin >> n >> k;

        int ans = 0;
        auto solve = [&](ll t) {
            auto cal = [&](ll b) {
                ll a = b + t;
                vector<ll> powa(k), powb(k);
                powa[0] = powb[0] = 1;
                for (int i = 1; i < k; ++i) {
                    if (1.0 * powa[i - 1] * a > inf) return inf;
                    powa[i] = powa[i - 1] * a;
                    if (1.0 * powb[i - 1] * b > inf) return inf;
                    powb[i] = powb[i - 1] * b;
                }
                ll sum = 0;
                for (int i = 0; i < k; ++i) {
                    if (1.0 + sum + powa[i] * powb[k - 1 - i] > inf) return inf;
                    sum += powa[i] * powb[k - 1 - i];
                }
                if (1.0 * sum * (a - b) > inf) return inf;
                sum *= a - b;
                return sum;
            };
            ll l = 1, r = 1e9;
            while (l < r) {
                ll mid = l + r >> 1;
                if (cal(mid) >= n) r = mid;
                else l = mid + 1;
            }
            ans += cal(l) == n;
        };

        for (ll i = 1; i * i <= min(mx, n); ++i) {
            if (n % i) continue;
            solve(i);
            if (i != n / i) solve(n / i);
        }

        cout << ans << "\n";
    }

    return 0;
}

/**********************************************************************
	Problem: 1245
	User: KobicGend
	Language: C++
	Result: AC
	Time:259 ms
	Memory:2380 kb
**********************************************************************/

又是数学

暴力的复杂度是Θ(kn3)\Theta(kn^{3})，不能通过，期望复杂度Θ(kn)\Theta(kn)，突破口在M=10k−1M=10^{k}-1。

先给所有数aia_{i} 取模，这样三个数加起来不会超过3M3M，只能是2M2M 或MM（还有00，特判），也就是199…98199\dots98 和99…9999\dots99。这个199…98199\dots98 看上去不是很友好，可以做一个转换：把每个数aia_{i} 变成ai−Ma_{i}-M，这样原先加起来是199…98199\dots98 现在就是−99…99-99\dots99 了。

先考虑和为99…9999\dots99 的。