2024年冬第八届河北工业大学程序设计校赛赛后总结与题解

写在前面：牛客的 markdown 中的 $\LaTeX$ 格式目前存在严重影响阅读的恶性bug，具体为：

等号后的内容会被直接吞掉。
加号会被吞掉。
多行公式无法使用 & 对齐。

因此在上述问题解决前，牛客平台上本文将不会进行任何维护更新。

你可以通过下面的三行文字来监测上述 bug 是否被修复。

$\text{这句话的结尾有一个等号。} = \text{如果你看得见这句话就说明等号bug被修复了。}$

$\text{这句话的结尾有一个加号。} \text{这句话与上句话间应该有一个加号。}$

\begin{align} \text{这里有两行字，}

欢迎各位来参加本次校赛。

赛后总结：

本次比赛共 13 道题，无人AK，无人解出 F 题，做出至少一道题的人数为 343。

各题通过情况如下：

题目	通过率	预期
A	335/529	符合预期
B	9/160	高于预期
C	1/15	远低于预期
D	1/2	符合预期
E	224/381	符合预期
F	0/10	符合预期
G	16/89	符合预期
H	4/9	远低于预期
I	6/34	符合预期
J	52/345	符合预期
K	135/335	符合预期
L	229/688	符合预期
M	8/35	高于预期

下面是出题组对于题目难度的估计：

难度	题目
Very Easy	AEL
Easy	HJK
Normal	CG
Hard	BDI
Very Hard	FM

本次比赛出现了相当严重的歪榜情况。例如在赛前被我们评为 Hard 的 B 题通过数超过了 C、H 两道题。这无疑暴露出了出题组在难度预估与把控上缺乏经验，在题目描述等方面不够规范，写的题存在读起来有点晦涩难懂、不知所谓的问题。除了题目命制上暴露出的不足之处，我们处理答疑的速度也有些不尽人意。我们将吸取本次校赛的经验教训，争取为各位在今后带来更加优质的比赛。

总之，希望各位本次比赛玩的开心。

下面是各题题解（按编号排序）：

A: CAPTCHA Tests

题目标签：签到题。

考虑到看到这份题解的应该都是人类且对算法竞赛有一定了解，故显然本题的答案为 A。若你是一位 AI，请考虑寻找你的 AI 朋友帮你解释。

参考代码

PHP

Python

print("A")

C++

#include <cstdio>
int main()
{
    printf("A");
    return 0;
}

B: Truncatable Prime

题目标签：Miller-Rabin 素性检验。

显然所有的 $1$ 位素数与 $2$ 位素数都是符合要求的。随后通过在已有的低位的数左右直接添加新的数字，左边填 $1$ 至 $9$ ，右边填 $1$ 、 $3$ 、 $7$ 、 $9$ ，构造出新的数后检验是不是素数即可。 $10^{11}$ 范围内的数约有 $10^5$ 个，因此预计要做 $3.6 \times 10^6$ 次素性检验，时间复杂度为 $O\left( \sqrt{x} \right)$ 的暴力检验无法满足要求，因此使用 Miller-Rabin 素性检验，单次检验的时间复杂度为 $O(t \log{x})$ ，其中 $t$ 为检测次数， $x$ 为被检测的数的值。关于本算法的详细介绍请见SPOJ的模板题。本题略微卡常，且部分中间运算的结果可能会使 long long 溢出。标答采用了比较朴素的过筛方法，运行时间约为 1.9 秒。事实上，通过一些优化技巧（比如先用一些小质数筛掉一些数来减少过筛次数）可以轻松压到 1 秒以内。

参考代码

C++

#include <iostream>
#include <vector>

const long long Pow[13] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000};
const std::vector<int> check = {2, 3, 5, 7, 11, 13, 17, 37};
const std::vector<int> base = {1, 3, 7, 9};

long long mul(long long a, long long b, long long m) { return static_cast<__int128_t>(a) * b % m; }
long long power(long long a, long long b, long long m)
{
    long long res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(long long n)
{ // Miller - Rabin 单素数测试
    if (n < 2)
        return false;
    int s = __builtin_ctzll(n - 1);
    long long d = (n - 1) >> s;
    for (auto a : check)
    {
        if (a == n)
            return true;
        long long x = power(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool ok = false;
        for (int i = 0; i < s - 1; ++i)
        {
            x = mul(x, x, n);
            if (x == n - 1)
            {
                ok = true;
                break;
            }
        }
        if (!ok)
            return false;
    }
    return true;
}

long long n;
std::vector<long long> odds = {2, 3, 5, 7}, evens = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

void solve()
{
    int digits = 3, odd_ptr = 0, evens_ptr = 0;
    while (1)
    {
        if (digits % 2) // use odds
        {
            int tmp = odds.size();
            for (size_t front = 1; front <= 9; front++)
            {
                for (size_t mid = odd_ptr; mid < tmp; mid++)
                {
                    for (auto end : base)
                    {
                        long long candi = front * Pow[digits - 1] + odds[mid] * 10 + end;
                        if (candi > n)
                        {
                            return;
                        }
                        else if (isprime(candi))
                        {
                            odds.push_back(candi);
                        }
                    }
                }
            }
            digits++;
            odd_ptr = tmp;
        }
        else
        {
            int tmp = evens.size();
            for (size_t front = 1; front <= 9; front++)
            {
                for (size_t mid = evens_ptr; mid < tmp; mid++)
                {
                    for (auto end : base)
                    {
                        long long candi = front * Pow[digits - 1] + evens[mid] * 10 + end;
                        if (candi > n)
                        {
                            return;
                        }
                        else if (isprime(candi) && candi <= n)
                        {
                            evens.push_back(candi);
                        }
                    }
                }
            }
            digits++;
            evens_ptr = tmp;
        }
    }
}

int main()
{
    std::cin >> n;
    if (n <= 10)
    {
        std::cout << std::upper_bound(odds.begin(), odds.end(), n) - odds.begin();
    }
    else if (n <= 100)
    {
        std::cout << std::upper_bound(evens.begin(), evens.end(), n) - evens.begin() + 4;
    }
    else
    {
        solve();
        std::cout << odds.size() + evens.size();
    }

    return 0;
}

C: Eschatology of 0s and 1s

题目标签：贪心、分类讨论、思维。

先考虑如何满足题目要求。

通过观察不难注意到所有满足条件的二元组中，差值最大的总是 $i = 1$ 或 $j = n$ 的。考虑反证法证明此结论。假设某个具有最大差值的二元组 $\left[ p,q \right]$ 满足 $p>1$ , $q<n$ ，显然 $s_p \oplus s_q = 1$ ，不妨设 $s_{p} = 0$ , $s_{q} = 1$ 。随后考虑第 $p-1$ 位与第 $q 1$ 位所有可能取值：

若 $s_{p-1} = 0$ , $s_{q 1} = 0$ ，则二元组 $\left[ p-1,q \right]$ 也满足题目要求且具有更大差值，假设不成立。
若 $s_{p-1} = 0$ , $s_{q 1} = 1$ ，则二元组 $\left[ p-1,q 1 \right]$ 也满足题目要求且具有更大差值，假设不成立。
若 $s_{p-1} = 1$ , $s_{q 1} = 0$ ，则二元组 $\left[ p-1,q 1 \right]$ 也满足题目要求且具有更大差值，假设不成立。
若 $s_{p-1} = 1$ , $s_{q 1} = 1$ ，则二元组 $\left[ p,q 1 \right]$ 也满足题目要求且具有更大差值，假设不成立。

综上，无论何种情况下总存在一个差值大于 $\left[ p,q \right]$ 的二元组。故该假设不成立，即差值最大的二元组 $\left[ p,q \right]$ 必须满足 $i = 1$ 或 $j = n$ 。

证明该结论后，题目要求便可以转化为与首位不同的位只能出现在前 $k 1$ 位，与末位不同的位只能出现在后 $k 1$ 位。首先特判当 $k \ge n-1$ 时， $f(s) \leq k$ 恒成立，故花费为 $0$ 。

当 $k < n-1$ 时，显然首末两位应当相同，进一步转化为修改 $s$ 使得与首末两位值不同的位置只在区间 $\left[n-k, 1 k\right]$ 内。显然当 $1 k<n-k$ 即 $2k<n-1$ 时，整个串最终必须变为全 $0$ 或全 $1$ 。

接下来可分为两种基本情况讨论如何进行修改：将两端修改为 $0$ ，或将两端修改为 $1$ 。为方便阅读，下文称按位与、按位或、按位异或分别为 $\texttt{AND}$ , $\texttt{OR}$ 与 $\texttt{XOR}$ 。

首先我们需要扫一遍串数一下需要改变的位的数量。假设我们希望将两端修改为 $0$ ， $1$ 变 $0$ 时可用操作是 $\texttt{AND}$ 与 $\texttt{XOR}$ ，前者一次只能修改一位 $1$ ，后者当存在两个及以上的 $1$ 时可一次修改两位 $1$ ，但当只剩一个 $1$ 时为了修改这个 $1$ 却要进行两次 $\texttt{XOR}$ 。因而当需要修改的 $1$ 的个数为奇数个时需要特判，这是因为修改最后一位 $1$ 的处理方式较为复杂，首先需要判断是能否一次 $\texttt{XOR}$ 搞定，若不能，考虑用一次 $\texttt{AND}$ 还是一次 $\texttt{OR}$ 加一次 $\texttt{XOR}$ ，抑或是两次 $\texttt{XOR}$ 。

我们希望两端是 $1$ 的情况要简单许多，因为我们可以使用的 $\texttt{OR}$ 及 $\texttt{XOR}$ 都只能一次将一位 $0$ 修改为 $1$ ，故直接 $\min(b,c)$ ，取两种修改方案中花费较小的即可。

对于每组测试数据，该算法的时间复杂度为 $O(n)$ 。

参考代码

C++

#include <iostream>
#include <string>

void solve()
{
    int n, k;
    long long a, b, c;
    std::string s;
    std::cin >> n >> a >> b >> c >> k >> s;
    long long ans_0, ans_1;
    bool outer_1s = false;
    int cnt0 = 0, cnt1 = 0;
    if (2 * k < n - 1) {
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') { cnt0++; }
            else {
                cnt1++;
            }
        }
    }
    else {
        for (int i = 0; i < n - k - 1; i++) {
            if (s[i] == '0') { cnt0++; }
            else {
                cnt1++;
            }
        }
        for (size_t i = n - k - 1; i <= k; i++) {
            if (s[i] == '1') { outer_1s = true; }
        }

        for (int i = k + 1; i < n; i++) {
            if (s[i] == '0') { cnt0++; }
            else {
                cnt1++;
            }
        }
    }
    // to all zero
    if (cnt1 % 2) { ans_0 = std::min(cnt1 / 2 * c, (cnt1 - 1) * a) + std::min({c + (outer_1s ? 0 : c), a, c + b}); }
    else {
        ans_0 = std::min(cnt1 / 2 * c, cnt1 * a);
    }

    // to all one
    ans_1 = std::min(b, c) * cnt0;

    std::cout << std::min(ans_0, ans_1) << '\n';
}

int main()
{
    int t;
    std::cin >> t;
    while (t--) { solve(); }
    return 0;
}

D: Serious Dedication II

（见另一篇题解）

E: Color Inversion

题目标签：签到题、数制转换。

简而言之，题目要求做三个十六进制数的减法。可以通过 C++ 与 Python 内置的方法将十六进制转换成十进制数，运算完之后再转为十六进制输出。如果不知道这些东西，也可以自己手写十六进制数的运算。

参考代码

C++

#include <bits/stdc++.h>
 
void solve()
{
    std::string c;
    std::cin >> c;
    int r = std::stoi(c.substr(1, 2), nullptr, 16), g = std::stoi(c.substr(3, 2), nullptr, 16), b = std::stoi(c.substr(5, 2), nullptr, 16);
    printf("#%02X%02X%02X\n", 255 - r, 255 - g, 255 - b);
    // std::cout << '#' << std::setiosflags(std::ios::uppercase) << std::setw(2) << std::setfill('0') << std::hex << 255 - r << std::hex << std::setw(2) << std::setfill('0') << 255 - g << std::hex << std::setw(2) << std::setfill('0') << 255 - b << '\n';
}
 
int main()
{
    int t;
    std::cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Python

for i in range(int(input())):
    c = input()
    r, g, b = int(c[1:3], 16), int(c[3:5], 16), int(c[5:], 16)
    print(
        "#"
        + "{:02X}".format(255 - r)
        + "{:02X}".format(255 - g)
        + "{:02X}".format(255 - b)
    )

F: Rheanna's General List

（见另一篇题解）

G: Artificial Blossom

题目标签：图论、最短路、前缀和。

披着最短路外衣的前缀和题。

容易发现对图上任意两个结点间的最短路径的备选项只有四条，即起始结点沿着哪个方向从所处的花瓣中出来与沿着哪个方向进入目标结点所在的花瓣。因此对每篇花瓣预处理出从中心结点沿两个方向绕一圈到达各个结点时的两个前缀和，每次询问时即可用 $O(1)$ 的时间拼接出这四条路径取其中最小值即可。总的时间复杂度为 $O(n q)$ 。

预处理时建立结点与前缀和映射关系的方法有很多，可以直接从 1 号结点起给每个花瓣 dfs 一次，也可以跑一次 Dijkstra。

本题在实现时需要注意的细节较多，可参考下面的标答代码。

参考代码

#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int N = 2e5 + 5;

struct node {
    int v, w;
};

vector<node> e[N];
vector<int> pre[N], suf[N];//前缀和 和 后缀和
int fa[N];                 // 从属于哪个花瓣
int vis[N];                // 判断与1号点相连的点有没有被访问过
int f[N];                  // 属于第几个点
int buc[N];                // 桶(暂时没用到)
////////////////////////////////////

void dfs(int ori, int u, int cnt)
{
    int _1 = 0, p = 0;
    vector<int> length;
    while (1) {
        for (int i = 0; i < 2; ++i) {

            vis[u] = true;
            fa[u] = cnt;

            if (vis[e[u][i].v]) {
                if (e[u][i].v == 1) {
                    length.push_back(e[u][i].w);
                    _1++;
                }

                continue;
            }
            length.push_back(e[u][i].w);
            f[u] = ++p;
            buc[cnt]++;
            u = e[u][i].v;
        }

        if (_1 == 2) break;
    }

    f[u] = ++p, buc[cnt]++;
    pre[cnt].push_back(0);
    suf[cnt].push_back(0);
    int size = length.size();
    for (int i = 0; i < size; ++i) {
        pre[cnt].push_back(pre[cnt][i] + length[i]);
        suf[cnt].push_back(suf[cnt][i] + length[size - 1 - i]);
    }
    reverse(suf[cnt].begin() + 1, suf[cnt].begin() + size);
}

void solve()
{
    int n, p, q;
    cin >> n >> p >> q;
    for (int i = 1; i <= n + p - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    int cnt = 0;
    vis[1] = true;
    for (auto i: e[1]) {
        if (!vis[i.v]) dfs(i.v, i.v, ++cnt);
    }

    while (q--) {
        int x, y;
        cin >> x >> y;

        if (x == y) {
            cout << 0 << '\n';
            continue;
        }

        if (x == 1 || y == 1) {
            if (x > y) swap(x, y);

            cout << min(pre[fa[y]][f[y]], suf[fa[y]][f[y]]) << '\n';
            continue;
        }

        if (fa[x] == fa[y]) {
            if (f[x] < f[y]) swap(x, y);
            cout << min(pre[fa[x]][f[x]] - pre[fa[y]][f[y]], suf[fa[x]][f[x]] + pre[fa[y]][f[y]]) << '\n';
        }
        else {
            cout << min(pre[fa[x]][f[x]], suf[fa[x]][f[x]]) + min(pre[fa[y]][f[y]], suf[fa[y]][f[y]]) << '\n';
        }
    }
}

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

H: Meteorite Shower

题目标签：bfs

本题改编自洛谷P2895

考虑以时间为第二个维度扩展出一个 $\left(D \max_{i=1}^N d_i - x_i \right) \times \max_{i=1}^N t_i$ 的二维平面，暴力标记出所有的危险位置后直接 bfs 即可。需要注意的有以下几点：

可以一直向后移动至无穷远，且显然此时任何冲击波都追不上，故本题一定有解。
自己的代码是否允许了“穿过冲击波”的行为：

参考代码

#include <bits/stdc++.h>
using namespace std;

int dtime = 1, dx[3] = {-1, 0, 1};
int D,N, ans = inf;
int vis[4050][2050], min_time[4050][2050]; 
// 1冲击波波及到的地方
// 0在i秒时 x=j处有没有受到冲击波影响

struct node
{
	int time, x;
};

void bfs(int st)
{
	queue<node> q;
	q.push({0, 0 + offset});
	min_time[0][0 + offset] = 0;
	while (!q.empty())
	{

		int time = q.front().time;
		int x = q.front().x;
		q.pop();
		if (x == D + offset)
		{
			ans = time;
			return;
		}
		for (int i = 0; i < 3; ++i)
		{

			if (vis[time + dtime][x + dx[i]] || min_time[time + dtime][x + dx[i]] <= time + 1)
				continue;

			min_time[time + dtime][x + dx[i]] = time + 1;
			q.push({time + dtime, x + dx[i]});
		}
	}
}

void solve()
{
	cin >> D >> N;

	for (int i = 0; i < 4050; ++i)
	{
		for (int j = -1000; j < 1050; ++j)
		{
			min_time[i][j + offset] = 10000;
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		int x, t, d;
		cin >> x >> t >> d;
		for (int j = 0; j < d; ++j)
		{
			vis[t + j][x + j + offset] = 1;
			vis[t + j][x - j + offset] = 1;
			if (j > 0)
			{
				vis[t + j][x + j + offset - 1] = 1;
				vis[t + j][x - j + offset + 1] = 1;
			}
		}
	}

	bfs(0);

	cout << (ans == inf ? -1 : ans);
}

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

I: The Magician's Puzzle

题目标签：图论建模、异或域高斯消元

异或域高斯消元模板题。

注意到每支蜡烛只有点燃与否两种状态，且每一支蜡烛的最终状态只与自身和与它有连边的蜡烛的操作次数决定，而与操作次序无关。

显然每一支蜡烛我们最多只会操作 1 次，故考虑建立异或域下的线性方程组求解此问题：

\begin{equation*} \begin{cases} c_{11}x_1 \oplus c_{12}x_2 \oplus \cdots \oplus c_{1n}x_n = 1 \\ c_{21}x_1 \oplus c_{22}x_2 \oplus \cdots \oplus c_{2n}x_n = 1 \\ \cdots \\ c_{n1}x_1 \oplus c_{n2}x_2 \oplus \cdots \oplus c_{nn}x_n = 1 \end{cases} \end{equation*}

方程组中， $x_{i}$ ( $1 \leq i \leq n$ ) 为待求的未知数，其表示是否改变第 $i$ 支蜡烛的状态，取值只有 $0$ 与 $1$ 两种。对所有的 $1 \leq i \leq n$ 有 $c_{ii} = 1$ 。若蜡烛 $u$ 与蜡烛 $v$ 间有连边，则 $c_{uv} = c_{vu} = 1$ 。其余的 $c_{ij} = 0$ 。

设定好系数后，我们就可以开始进行高斯消元了，其时间复杂度为 $O(n^3)$ ，采用 std::bitset 加速运算，可以在时限内通过本题。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 50;
const int MOD = 998244353;

bitset<N> matrix[N]; // 1-n列 是系数矩阵 加上0列是增广矩阵
bool ans[N];
int GaussElimination(int n)
{
	int r, c;
	for (r = c = 1; c <= n; ++c)
	{
		int t = r;
		for (int i = r; i <= n; ++i)
		{
			if (matrix[i].test(c))
			{
				t = i;
				break;
			}
		}

		if (!matrix[t].test(c))
			continue;

		swap(matrix[r], matrix[t]);

		for (int i = r + 1; i <= n; ++i)
		{
			if (matrix[i].test(c))
				matrix[i] ^= matrix[r];
		}

		r++;
	}

	if (r < n + 1)
	{
		for (int i = r; i <= n; ++i)
		{
			if (matrix[i].test(0))
				return 2;
		}

		int cnt = n - r, flag = false; // 0行的个数
		for (int i = n; i >= 1; --i)
		{
			if (matrix[n].none())
			{
				for (int j = n - 1; j >= 1; --j)
				{
					int t = matrix[j].test(j);
					if (matrix[j].test(j))
						break;
					swap(matrix[j], matrix[j + 1]);
				}
			}
		}
	}
	for (int i = n; i >= 1; --i)
	{
		for (int j = i + 1; j <= n; ++j)
		{
			matrix[i].set(0, matrix[i].test(0) ^ (matrix[j].test(0) & matrix[i].test(j)));
		}
	}
	return 0;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int u, v;
		cin >> u >> v;
		matrix[u].set(v, 1);
		matrix[v].set(u, 1);
	}
	for (int i = 1; i <= n; ++i) // 设初始时蜡烛的状态都是0，那么最后的结果都是1
		matrix[i].set(0, 1), matrix[i].set(i, 1);

	int res = GaussElimination(n);

	if (res == 2)
		cout << -1 << '\n';

	else
	{
		vector<int> ans;
		for (int i = 1; i <= n; ++i)
		{
			if (matrix[i].test(0))
			{

				ans.push_back(i); // cout << matrix[i].test(0) << " ";
			}
		}
		cout << ans.size() << '\n';
		for (auto i : ans)
		{
			cout << i << " ";
		}
	}
}

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

J: Basic Geometry Problem

题目标签：简单欧氏几何、二分。

这只是一个简单的欧氏几何，画个图推个式子就结束了跟计算几何比还是差远了......

（图过两天补......）

最终能得到 $S$ 与 $R$ 的关系式：

alt

对着这个式子二分 $R$ 的值即可。存在一定精度运算要求，如果自己的精度炸了请检查自己的式子是否存在某些会导致精度飞天的地方。

参考代码

#include <bits/stdc++.h>
#define PI 3.141592653589793
using namespace std;
typedef long double ld;
bool check(ld x, int l, int w, int s)
{
	ld res;
	res = w * sqrtl(x * x - w * w / 4.0) + 2 * x * x * asinl(w / (2 * x));
	return res > s;
}

ld max_s(int l, int w)
{
	ld res, x = l / 2.0;
	res = w * sqrtl(x * x - w * w / 4.0) + 2 * x * x * asinl(w / (2 * x));
	return res;
}
void solve()
{
	int l, w, s;
	cin >> l >> w >> s;
	ld s_max = max_s(l, w);
	if (max_s(l, w) < s || s < PI * (w / 2.0) * (w / 2.0))
	{
		printf("-1\n");
		return;
	}
	ld L = w / 2.0, R = l / 2.0;
	ld eps = 1e-12;
	while (R - L > eps)
	{
		ld mid = (L + R) / 2;

		if (check(mid, l, w, s)) // 二分答案
			R = mid;			 // 最小化
		else
			L = mid;
	}
	printf("%.12LF\n", R);
}

int main()
{

	int T;
	cin >> T;
	while (T--)
		solve();
	return 0;
}

K: Yet Another Card Game I

题目标签：博弈论。

本题为标准的田忌赛马。双倍经验。

参考代码

#include <bits/stdc++.h>
using namespace std;

int a[N], b[N];
void solve()
{
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	for (int i = 1; i <= n; ++i)
		cin >> b[i];

	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	for (int i = 1, j = 1; i <= n; i++)
	{
		if (b[i] >= a[j])
			++j, ++ans;
	}
	if (ans >= n / 2 + 1)
		cout << "Yasmine" << '\n';
	else
		cout << "Rheanna" << '\n';
}

signed main()
{
	int T;
	cin >> T;
	while (T--)
		solve();
	return 0;
}

L: Acronyms

题目标签：签到题、模拟。

简单的字符串题，直接将 $s$ 串中的首位字母与所有 _ 符号前的字母提取出来与串 $a$ 比较即可。

参考代码

#include <bits/stdc++.h>

void solve()
{
    std::string s,a,check;
    std::cin >> s >> a;
    check = s.substr(0,1);
    for (size_t i = 1; i < s.size()-1; i++)
    {
        if (s[i] == '_')
        {
            check.push_back(s[i+1]);
        }
        
    }
    std::cout << (check == a ? "YES\n" : "NO\n");
}

int main()
{
    int t;
    std::cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

M: Study

题目标签：换根 dp。

双倍经验：CF1187E

如果之前做过上面这道题，那么就会发现这两道题除了具体需要处理的式子外在题目翻译、条件转化上几乎一模一样。

为了方便下面的叙述，我们先简化一下题意：

给定一棵 $n$ 个结点的树，初始每个结点均为白色。

现在要给这棵树的所有结点染色。每一次染色可以选定一个与一个黑点相隔一条边的白点，将它染成黑点，染色的代价为

alt

第一次操作可以任意选点。求将这棵树所有结点染黑的最小代价。

首先我们需要推出一个结论：

$\displaystyle \sum_{i=1}^n t_i$ 的值只与选择的第一个结点即根结点有关，与剩余结点染色顺序无关。

显然总代价中， $\displaystyle \sum_{i=1}^n c_i$ 是一个与染色顺序无关的固定代价。对于某个结点 $u$ 。其本身一定先于子树内的所有结点被染色，则 $\operatorname{sub}(u)$ 只与选择的根结点有关，而 $d(u,v)$ 与 $k_v$ 均为定值，则该结论成立。

接下来便是考虑两次 dfs 的转移式。对第一次 dfs，我们的目标是计算出当钦定 $1$ 为根结点时，各 $t_i$ 的值。

对第一次转移而言，考虑某子结点 $u$ 向其父亲 $v$ 转移时的关系：

alt

式中的 $\operatorname{sub}(v) - \operatorname{sub}(u)$ 为结点 $v$ 除子结点 $u$ 外其余子结点的子树与结点 $v$ 本身。该式对于其余的这些子结点同样使用。不妨记 $\displaystyle s_u = \sum_{v \in \operatorname{sub}(u)} k_v$ ，我们便可以得到第一次 dfs 的转移式:

$t_u = k_u \sum_{v \in \operatorname{sub}(u)} (t_v s_v)$

仿照上述推导方法，考虑第二次 dfs 中，当根结点从结点 $u$ 换为结点 $v$ 时答案会如何变化。

首先，对于除 $u$ ， $v$ 以外的结点，容易发现其子树没有发生变化，因此它们的 $t$ 也不会发生变化。只有结点 $u$ 的子树从整棵树变为了整棵树除结点 $v$ 的子树外的所有结点，而结点 $v$ 由其子树变为了整棵树。记 $T$ 为整棵树的点集， $t^{\prime}_u$ 与 $t^{\prime}_v$ 代表换根后结点 $u$ ， $v$ 的 $t$ 值，有： alt

需要注意的是，上式显然表明 $t_u$ 与 $t_v$ 会随根结点的变化而变化。因此当我们进一步计算由结点 $v$ 换根至其某个子结点前，需要及时更新 $t_v$ 的值，当搜索完这颗子树时再回溯回来。具体可以看参考代码。

则当以 $u$ ， $v$ 为根时的代价和有关系

alt

推导出这些转移关系后，便可愉悦地开始 dfs 了。时间复杂度 $O(n)$ 。

参考代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <vector>

const int inf = 0x3f3f3f3f;
const long long inf_64 = 0x3f3f3f3f3f3f3f3f;

template<typename T>
class adj_table {
protected:
    typedef struct {
        size_t b;
        T x;
    } edge;
    std::vector<std::vector<edge>> _graph;
    std::vector<T> _vertex_weight;
    size_t _n;

public:
    adj_table() {}
    adj_table(size_t n)
    {
        _graph.resize(n + 1);
        _vertex_weight.resize(n + 1, 1);
        _vertex_weight[0] = 0;
        _n = n;
    }
    void resize(size_t n)
    {
        _graph.resize(n + 1);
        _vertex_weight.resize(n + 1, 1);
        _vertex_weight[0] = 0;
        _n = n;
    }
    void build_edge(size_t a, size_t b, T x = 1) { _graph[a].push_back({b, x}); }
    void set_vertex_weight(size_t pos, T weight) { _vertex_weight[pos] = weight; }
    T get_vertex_weight(size_t pos) { return _vertex_weight[pos]; }
    size_t get_vertex_count() { return _n; }
    T get_edge(size_t a, size_t b)
    {
        for (auto i: _graph[a]) {
            if (i.b == b) { return i.x; }
        }
        return 0;
    }
    void modify_edge(size_t a, size_t b, T x, T y)
    {
        for (auto i: _graph[a]) {
            if (i.b == b && i.x == x) { i.x = y; }
        }
    }
    std::vector<size_t> get_neighbour(size_t a)
    {
        std::vector<size_t> ans;
        for (auto i: _graph[a]) { ans.push_back(i.b); }
        return ans;
    }
    std::vector<edge> &get_outedge(size_t a) { return _graph[a]; }
};

int main()
{
    int n, u, v, tmp;
    std::cin >> n;
    adj_table<long long> tree(n);
    long long base = 0;
    std::vector<long long> multi(n + 1);

    for (int i = 1; i <= n; i++) {
        std::cin >> tmp;
        base += tmp;
    }

    for (int i = 1; i <= n; i++) { std::cin >> multi[i]; }

    for (int i = 1; i < n; i++) {
        std::cin >> u >> v;
        tree.build_edge(u, v);
        tree.build_edge(v, u);
    }

    std::vector<long long> ans(n + 1), wei_sum(n + 1), subtree(n + 1);

    std::function<void(int, int, int)> dfs1 = [&](int u, int father, int dist) {
        wei_sum[u] = multi[u];

        for (auto v: tree.get_neighbour(u)) {
            if (v == father) { continue; }
            dfs1(v, u, dist + 1);
            wei_sum[u] += wei_sum[v];
            subtree[u] += subtree[v] + wei_sum[v];
        }

        ans[1] += subtree[u];
    };

    dfs1(1, 1, 1);

    std::function<void(int, int)> dfs2 = [&](int u, int father) {
        for (auto v: tree.get_neighbour(u)) {
            if (v == father) { continue; }
            ans[v] = ans[u] - 2 * subtree[v] - 3 * wei_sum[v] + wei_sum[1] + subtree[u];
            long long orig = subtree[v];
            subtree[v] = wei_sum[1] - 2 * wei_sum[v] + subtree[u];
            dfs2(v, u);
            subtree[v] = orig;
        }
    };

    dfs2(1, 1);

    std::cout << *std::min_element(ans.begin() + 1, ans.end()) + base;
}

2024年冬第八届河北工业大学程序设计校赛 赛后总结与题解

赛后总结：

下面是各题题解（按编号排序）：

A: CAPTCHA Tests

参考代码

B: Truncatable Prime

参考代码

C: Eschatology of 0s and 1s

参考代码

D: Serious Dedication II

E: Color Inversion

参考代码

F: Rheanna's General List

G: Artificial Blossom

参考代码

H: Meteorite Shower

参考代码

I: The Magician's Puzzle

参考代码

J: Basic Geometry Problem

参考代码

K: Yet Another Card Game I

参考代码

L: Acronyms

参考代码

M: Study

参考代码

2024年冬第八届河北工业大学程序设计校赛赛后总结与题解