中国计量大学第六届个人校赛题解
这里是一篇关于中国计量大学第六届个人校赛的题解。
顺便写一点校赛的经历和想法，稍微给这次参与校赛组织的经历留下一点回忆
C题配图的候选项之一，姑且就放在这里啦
A 闰年判断
题意：
判断闰年
知识点：
判断语句
非常简单且模板的一题，没有任何的陷阱。这甚至不是我们自己出的题（这么原的题有什么重新出一遍的必要嘛。这题的定位是一道保证大家能够成功签到的题目。只要熟练掌握C/C++中的if语法并知道闰年的判断方法，即可通过该题。
代码简单，就不另外放出了
B 我不爱发明
题意：
输出v的个数
知识点：
字符串
和上面一题一样，是一道定位为签到的题目。这题的灵感来源于出题时这样的一个问题“能不能出一个题，就算不会算法也能慢慢做出来”。以平常的出题思路，自然是要来一题轻松愉快的大模拟。然而为了大家的比赛体验（实际上是大模拟我也不想写，于是整了一道目前这样的题。思路同样非常简单，将字符串复制到程序里遍历即可。
C 读心也没用
题意：
给定一个根为\(1\)大小为\(n\)的树，两人轮流将初始位于\(1\)的棋子向节点的儿子移动，最终结果为棋子移动路径的权值和。先手想要让权值尽可能大，后手想要让棋子尽可能小。问两人都采用最优策略时的权值结果。
知识点：
树，dfs
思路：
两人轮流向节点儿子移动，由此可以得到结论奇数深度的点都由先手选择儿子，偶数深度的点都由后手选择儿子，因为每次向儿子移动后，深度+1，操作的人交换。得到这一信息后，就可以像做经典dp的思路一样进行求解答案。在dfs中，对于当前节点\(p\)，我们对于每一个\(p\)的儿子\(q\)，dfs计算出\(f[q]\)代表移动到\(q\)后，后续移动会对答案产生\(f[q]\)的贡献。因此对于奇数层的点，我们要找到最大的\(f[q] + w_q\)，(\(w_q\)表示儿子\(q\)对应的边)，同理对于偶数层的点，我们要找到最小的\(f[q] + w_q\)，然后将找到的答案作为\(f[p]\)并返回，继续计算上层答案。最终我们得到的\(f[1]\)即为\(1\)出发对答案的贡献，即为最终答案。
\[f[p] = \left\{ \begin{aligned} \max_{q \in edges[p]} f[q] + w_q &°[p] \% 2==1\\ \min_{q \in edges[p]} f[q] + w_q &°[p] \% 2 == 0 \end{aligned} \right. \]核心代码
ll dfs(int p, int fa)
{
dep[p] = dep[fa] + 1;
ll num;
if (dep[p] & 1)
num = 0;
else
num = INF;
if (edges[p].size() == 1 && p != 1)//在叶子节点处需要特判直接赋值
num = 0;
for (auto &[q, w] : edges[p])
{
if (q == fa)
continue;
if (dep[p] & 1)
num = max(num, dfs(q, p) + w);
else
num = min(num, dfs(q, p) + w);
}
return num;
}
这题的idea在一开始诞生之初时是一个需要比较多分类讨论判断的树形dp，想着想着觉得，为什么不来一个带一点博弈味道，但是最终还是用dp解决的问题呢。于是选择了这种比较经典的“一人想让答案最大，一人想让答案最小”的题型。这种题目虽然通常为两人玩游戏， 不过大多数都和博弈实际上没什么关系，只要分辨出最优策略的情况就可以直接算。题目预期的定位是一道中期时大家都能顺利完成的题目，不过在赛场上顺利通过的人比较少，我推测可能是被博弈的外表吓住了（。这题实际上并不复杂，代码也较短，如果不了解树形dp的话可以借这题熟悉一下思路。
D 致命的食欲
题意：
区间赋值为\(0\)或\(1\)，问最终区间每一个位置的情况。区间大小和操作次数范围都为\(10^6\)。
知识点：
核心思路实际上没什么知识点，具体实现可以用并查集或STL set
思路：
因为操作是区间赋值，所以每一个位置最终的状态，只取决于该位置最后一次被覆盖时操作是变\(0\)还是变\(1\)。所以我们可以把操作离线下来，从后往前遍历操作。接下来的工作就是，如果快速地找到一个区间内没有被操作过的位置。我的思路是使用并查集来实现。用并查集维护每一个位置的下一个没有被操作过的位置，在一开始时t[i] = i，每一次操作完，都merge(t[i],t[i + 1])，使用pos = find(pos + 1)作为每次位置的步进。显然在使用该算法的情况下，每一个位置只会被经过一次，时间复杂度为\(O(nlogn)\)，加上每一次询问时需要确定一开始的位置，总时间复杂度为\(O((n + m)logn)\)。使用set也可以用类似的方法实现。
此外，该题也可以简单的使用线段树的区间修改实现。当然双\(10^6\)的数据结构显然有一点卡常，所以线段树需要实现地比较精巧，经过测试，大概需要用时800ms。
核心代码
for (int i = m; i >= 1; i--)
{
auto [t, l, r] = op[i];
l = find(l);
for (int j = l; j <= r; j = find(j))
{
res[j] = t;
merge(j, j + 1);
}
}
for (int i = 1; i <= n; i++)
{
cout << res[i] << " ";
}
个人觉得非常有意思的一题。一开始想着是搞一个轻松愉快的差分签到题，然后差分的题意却很难编一个合理的题目描述（是的，这题我先想好了题面再想的具体题目内容）（话说真的有人能把食物吃成负数吗？。于是折腾来折腾去变成了现在这个样子。数据再一开始也没这么大，一开始定的数据范围是\(10^5\)，然而被暴力很快地跑过去了，于是便改成了现在这个样子。在测试时非常恰到好处地允许设计精准的线段树通过，因此就保留了下来。我认为这是合理的，用更偏向思维的思路和更加通用的数据结构都应该具有通过题目的能力。
在赛中时看到一个很有趣的做法，对于每一个位置从后往前遍历，被覆盖到就break，也可以很快的通过（虽然没有我的std快。然后就被其他出题人狠狠地吐槽说数据水了。按照std的思路的话确实如此，只要构造一组数据，有多个位置没有被覆盖，就可以把时间复杂度卡到\(O(nq)\)。不过由于我的数据是随机生成的，可以证明每一个位置被覆盖到的时间期望并不大。虽然做法并非标准答案，不过考虑到赛中这题令人悲伤的通过率，能想到从后往前做的思路也值得鼓励。
E 斗地主（无人版）
题意
本题是一个模拟，题意就不再赘述
知识点：
模拟
思路：
由于懒得写（（（，所以这题我自己也还没通过过，不过可以简述一下我的想法。首先将所有的牌型按照大小，从大到小编号，设计一个函数，可以按照题目要求将某个人的手牌得出对应的牌型编号序列（尽可能凑大的，贪心即可）。然后我们可以按每个人的牌型从大到小编号完。之后每个人就可以贪心的论列出牌，能打完就可以获胜。
虽然说起来比较简单，但是也需要大约100行左右的实现。模拟题通常不需要复杂的算法，但是需要细心的实现过程。
有机会一定补上我的做法（下次一定。
F T酱的数学题 - easy version
题意
给出非负整数$ A,B,C\(，判断是否存在非负整数\)X\(满足\)A \oplus X + B == C$
\(0 \leq A,B,C \leq 10^{18}\)
知识点
异或的运算性质
思路
由异或的运算性质可知，\(X == (C-B)\oplus A\)
因此，只要\(C - B\)非负，那么\(X\)也一定是一个非负整数，直接判断输出即可。
G T酱的数学题 - medium version
题意
给出非负整数$ A,B,C\(，判断是否存在非负整数\)X\(满足\)A \oplus X + B \oplus X == C$
\(0 \leq A,B,C \leq 10^{18}\)
知识点
dp
思路
和异或有关的题通常可以用按位dp的方法解决。这一题中，我们考虑用dp来逐位确定\(X\)在每一位上的取值。对于每一位\(i\)，我们可以列出这样的一条式子
\[y_{i-1} + bit_A \oplus bit_X + bit_B \oplus bit_x == bit_C \]其中\(bit\)表示对应的数字在当前位的取值，\(y_{i-1}\)表示上一位是否产生了进位。因为\(bit_A,bit_B,bit_C\)均为确定值，所以当我们确定\(y_{i-1}\)时，我们可以计算出一个确定的\(bit_X\)，同时我们可以确定\(y_i =(y_{i-1} + bit_A \oplus bit_X + bit_B \oplus bit_x)/2\)，表示当上一位取\(y_{i-1}\)时，下一位的\(y_i\)取值。到这一步我们就可以发现，对于每一位我们只有两个状态\(y_i = 0\)和\(y_i = 1\)。所以我们可以使用动态规划的思想，定义\(f[i][0/1]\)表示第\(i\)位的\(y\)取\(0/1\)是否可行。初始状态位\(f[0][0] = 1\)，根据上面的式子，我们可以继续列出状态转移方程
当满足
\[(bit_X \oplus bit_A + bit_X \oplus bit_B) \% 2 == bit_C \]有转移方程
\[ f[i + 1][((bit_X \oplus bit_A) + (bit_X \oplus bit_B) + y_i) / 2] |=f[i][y_i] \]枚举\(bit_X\)和\(y_i\)的取值，就可以得到下一位的所有状态。
从低到高进行状态转移，如果最终\(f[61][0] = 1\)说明有解。
代码
for (int i = 0; i <= 60; i++) {
int ba = (a >> i) & 1;
int bb = (b >> i) & 1;
int bc = (c >> i) & 1;
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
if (((x ^ ba) + (x ^ bb) + y) % 2 == x) {
dp[i + 1][((x ^ ba) + (x ^ bb) + y) / 2] |= dp[i][y];
}
}
}
}
if (dp[61][0]) {
cout << "YES\n";
}
H T酱的数学题 - hard version
题意
给出非负整数$ A,B,C\(，判断是否存在非负整数\)X\(满足\)A \oplus X + B \oplus X == C \oplus X$
\(0 \leq A,B,C \leq 10^{18}\)
知识点
dp
思路
经过上一题的思考，我们可以发现，这一题和上一题实际上本质完全相同，下一位的状态只取决于当前位的状态和\(bit_X\)的状态。所以稍稍改一下判断条件为
\[(bit_X \oplus bit_A + bit_X \oplus bit_B) \% 2 == bit_C \oplus bit_X \]即可通过本题。
关于F，G，H
实际上一开始就只有G和H，F是后来补上的签到题，然而没有想到F赛中的通过人数也并不理想。G和H的dp并不难想，实际上我一开始还想复杂了，以为需要枚举等式两侧的进位情况，实际上后来一写才注意到只有一侧，因为右侧的情况是确定的。关于H和G，出题人有一个非常精巧的结论，然而数学证明并不是我擅长的部分，这里就不展开说明了。G题的题面，虽然和H题类似，不过H题的数学结论和G仍有较多不同，不过对于dp做法倒是没有什么影响。dp做法作为一种通解的思路非常好的发挥了预期的效果。
I 笑里藏刀
题意
找出最大的连通块大小
知识点
dfs
思路
基础的dfs板子题，如果不会的话可以使用搜索引擎找资料学习。活用搜索引擎也是成为一名优秀的ACMer必备的技能，不过当然不是指在比赛中。
J 反转后缀
题意
仅通过反转后缀的操作对一个01串进行排序，问最小的操作次数
知识点
贪心
思路
对于每一个01的交界的位置，如果我们不去操作它，那么它就会一直存在。所以如果我们要得到一个除了\(cnt_0\)其余位置都没有交界的串，那么我们就要在所有交界的位置进行操作。而\(cnt_0\)的位置比较特殊，如果初始时这里不是一个交界点，那么这里需要操作一次，否则不用操作。注意第一个数字为\(1\)，以及数字全为\(1\)时的特判。
int ans = 0;
for (int i = 1; i < n; i++) {
if (i == cnt) {
if (s[i] == s[i + 1])
ans++;
}
else {
if (s[i] != s[i + 1])
ans++;
}
}
if (s[1] == '1' && cnt)
ans++;
K Advanced CFer
题意
每次可以对序列的一个区间进行区间\(+1\)的操作，每次操作为，输出序列中满足\(a[i] > a[i - 1] \&\& a[i] > a[i + 1],2\leq i\leq n-1\)的位置。
知识点
线段树维护特殊区间
思路
线段树的节点定义为
struct Node
{
int l, r;
int lval[2], rval[2];
int lazy;
int cnt;
}
cnt表示节点范围内符合要求的位置数量，lval和rval分别表示区间左端的两个数和区间右端的两个数。
当进行区间合并时，如果\(rs.lval[0] > rs.lval[1] \&\& rs.lval[0] >ls.rval[0]\)或\(ls.rval[0] > ls.rval[1] \&\& ls.rval[0] > rs.lval[0]\)，那么根的\(cnt = cnt + 1\)，再依次合并其他信息，就完成了区间合并
最终查询时直接输出\(t[1].cnt\)即可
核心代码
void pushup(Node &rt, Node &ls, Node &rs)
{
rt.cnt = ls.cnt + rs.cnt;
rt.l = ls.l;
rt.r = rs.r;
if (rs.r - rs.l > 0 && rs.lval[0] > rs.lval[1] && rs.lval[0] > ls.rval[0])
rt.cnt++;
if (ls.r - ls.l > 0 && ls.rval[0] > ls.rval[1] && ls.rval[0] > rs.lval[0])
rt.cnt++;
rt.lval[0] = ls.lval[0];
rt.lval[1] = ls.lval[1];
rt.rval[0] = rs.rval[0];
rt.rval[1] = rs.rval[1];
if (ls.r - ls.l == 0)
{
rt.lval[1] = rs.lval[0];
}
if (rs.r - rs.l == 0)
{
rt.rval[1] = ls.rval[0];
}
}
这题在一开始时的题意比现在更加困难，以至于验题时大家都做不来。于是经过讨论把题目砍成了现在这样。实际上，现在的题意，并不需要线段树也可以完成，因为在目前的题意下，区间修改的操作只会影响两端的位置的答案，对于区间中间的答案没有任何影响，只要用差分维护一下每个位置的影响，就可以完成这题。
赛中发现这题的数据似乎出弱了，不过并没有很多的人尝试这题，非常的遗憾。
L String
题意
给出字符串\(s,t\)，请问能否至多修改\(s\)中的一个字母，使得\(s\)经过若干次循环移位后与\(t\)相同。
知识点
字符串hash
思路
将\(t\)拓展为两倍长度，然后用set存下\(t\)在每一种循环移位情况下的hash值。然后我们可以依次遍历\(s,t\)根据两个字符串的不同的字符——如果需要变化一个字母，那么这个字母在两个串中出现的次数一定不同——得到我们变化的目标字母\(c\)。我们遍历字符串\(s\)，将每一位都尝试替换为\(c\)，通过运算得到新的hash值，我们判断set中是否存在该hash值，如果存在即可行。需要注意特判不需要变化的情况。
核心代码
hashv h[maxn + 10];
hashv gethash(int l, int r)
{
return h[r] - h[l - 1] * pw[r - l + 1];
}
hashv gethash2(int p, char c) {
return h[p - 1] * pw[n - p + 1] + hashv(c, c) * pw[n - p] + h[n] - h[p] * pw[n - p];
}
void solve() {
string s;
string t;
cin >> s >> t;
n = s.length();
map<char, int> cnt;
for (auto c : t)
cnt[c]++;
for (auto c : s)
cnt[c]--;
char c = 'a';
for (auto i : cnt) {
if (i.second > 0) {
c = i.first;
break;
}
}
t = " " + t + t;
s = " " + s;
for (int i = 1; i <= 2 * n; i++) {
h[i] = h[i - 1] * base + hashv(t[i], t[i]);
}
set<hashv> st;
for (int i = 1; i <= n; i++) {
st.insert(gethash(i, i + n - 1));
}
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * base + hashv(s[i], s[i]);
}
int f = 0;
if (st.count(gethash(1, n)))
f = 1;
for (int i = 1; i <= n && !f; i++) {
if (st.count(gethash2(i, c))) {
f = 1;
break;
}
}
if (f) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
我一直有这样的一个观念“字符串的题只要用自动机和hash就可以解决”，然而非常遗憾，我尝试使用SAM做这题的时候非常不幸的TLE了，看来SAM终究还是只能做一些特定的题，不过好在标准做法是hash，情况还不算太坏（。不过据出题人称，这题用kmp也可以通过，核心思路大概也差不多。
至此，本次个人校赛的题就全部讲解完毕了。感谢出题组以及志愿者在校赛组织过程中的努力工作。希望大家能够满意本次校赛的题目。
标签：cnt,题意,rs,int,题解,oplus,第六届,校赛,bit From： https://www.cnblogs.com/iceyz/p/16982376.html