周围的人都写了篇小作文, 那我也跟按照圈子里的惯例写个小流水帐吧,文笔不好,算给日后的自己留个纪念吧 首先恭喜我校2银3铜, 听说是校史上就牌子数量的的最好成绩. 其次恭喜我自己终于拿到了XCPC上的第一块牌子(算是弥补了去年打铁的遗憾, RK55 也算是一个好开始吧). 这次的队伍算是重组后的队伍, 前前后后自行进行了几场训练, 也参加了几场学校里的自行组织的几场训练, 现在回想起来这些确实给我们队伍的合作提供了很大的帮助. 十分感谢学校提供的训练场地(尽管有点难以描述)和 yrh lmy 等人的帮助. 不同于 lmy 的队伍, 我们队其实是到学校统一组织训练的时候才知道出题人是 SUA 并开始专门挑 SUA 的题目训练, 如果不是因为 lmy 的消息和 yrh 及学校老师组织的训练, 我们队伍这次比赛大概并不会这么轻松愉快. day(-9) 突然抗原阳了,在此之前我还没阳过, 在家里烧

比赛链接 C - Cat virus 对于一颗树, 它的节点可以被染为黑色或者白色. 如果一个节点是白色,那么她的子节点可以是白色,也可以是黑色. 如果这个节点是黑色, 那么她的子节点一定是黑色. 现在输入一个数字 $2\le K \le 2\times 10^{18}$, 根据上述方式构造一棵数, 使之不同的染色方式有 $K$ 种 思维 构造 刚开始做的时候没带脑子,直接构造了一个 $(1,2), (2,3) \ldots (n-1, n)$,结果狠狠的 TLE 反向思考,当 $x$ 为白色的时候,它的父节点一定也为白色,而当这个节点是黑色的时候,它的父节点可以是白色,也可以是黑色. 设节点 a 及其子树有 $n$ 中染色方式, 增加一节点 b 连接到 a, 有以下情况: 当 a 为黑色时, 所有节点都为黑色, 1 种染色方式 当 a 为白色, b 为黑色时, 有 $n-1$ 中染

Gym-104076 A - Tower 有 $n$ 个塔, 每个塔的高度为 $a_i$. 首先先移除其中 $m$ 个塔, 然后可以进行以下操作: 将一个塔的高度 $a_i$ 加 1 将一个塔的高度 $a_i$ 减 1 将一个塔的高度 $a_i$ 折半,结果向下取整 操作中,塔的高度不允许取 $0$, 现在要使剩下的 $n-m$ 个塔的高度相同, 问最小的操作次数. 思维 比较暴力的一种做法, 首先大胆猜测最终所有的塔取的结果一定是通过折半获得的,而数越大时,折半时变化越大,因此其他的元素一定是先进行折半,再进行加减操作 在读入数字的时候首先将所有可能取的值存入 std::set div2, 然后对每个数 $i \in div2$,求出数 $a_i$ 到 $i$ 的所需的变化次数.找到最小的即可 #include <bits/stdc++.h> #include &l

前几天基本每场都遇到树形DP，趁此熟悉抓紧练练 在网上找了个树形DP专项 P1352: 没有上司的舞会 热个身 $$ \begin{cases} f[i][0] = \sum_{son}{\text{ReLU}(\max{(f[son][0], f[son][1]))}}\\ f[i][1] = \sum_{son}{\text{ReLU}(f[son][0])} \end{cases} $$ 其中 $f[i][j]$ 中的$i$表示当前节点编号，$j$表示是否参加舞会 加ReLU是因为怎么有人去了还不高兴啊 54 行后才是代码主体 // clang-format off #include <bits/stdc++.h> #include <limits> using ll = long long; using ul = unsigned long long; u

上海就是神仙打架 <table> <tr> <td> 题目链接 </td> <td> <center> 官方题解 </center> 竟然是ppt，他真的，我哭死 </td> </tr> </table> D - Strange Fractions 给出整数$p$和$q$，找到两个正整数满足$\frac{p}{q} = \frac{a}{b} + \frac{b}{a}$ 数学 使用换元法，令$y=\frac{p}{q}, x=\frac{a}{b}$ 则原式等于$y=x + \frac{1}{x}$ 即 $x^2 - xy + 1 = 0$ 题目中已经给了 $y$，我们只需要找到其中一个 $x$即可。 当 $\Delta=y^2-4\lt 0$时，输出 Imposs

<table> <tr> <td> 题目链接 </td> <td> 官方题解 </td> </tr> </table> A - Ah, It’s Yesterday Once More 构造一张二维地图，仅有墙壁和空白组成。在每个空白处都有一个人，每个人在接下来的 50000 步中将向一个方向随机移动。 要求构造的地图必须小于 $20\times 20$，至少有两个空白，每个空白之前必须是相互可达的，不能有环，50000步后所有的人$25%$的可能性不在同一个格子。 构造 很奇怪的一道题，练习的时候莫名其妙的就 A 了。 由于题目并没有输入数据，所有的人的行动数据都是随机的。很明显按照题目的意思，答案可以是固定的，没必要在程序中生成。而且路线长什么样子没什么关系（因为人的行动完全随机）。 只

The 2020 ICPC Asia Shenyang Regional Programming Contest - Codeforces Gym B - Whispers of the Old Gods 给出一个正则表达式 pattern 和字符串 str，要求对字符串中的数字进行尽可能少的插入，删除，替换操作。输出最小的操作次数。 做老题结果发现专业对口这件事 首先根据题目给出的 BNF 写出正则的解析器，然后用 Thompson's Construction 构造和 pattern 对应的 NFA， 重合 NFA 的起点和 str 的开始符，向后匹配到 NFA 的结束状态即可。当 str 的下一个字符使得 NFA 没有对应转移时， 修改 str 的下一个字符，其实也就相当于一个 01-最短路。 有关 Thompson's Construction 构造可以参考 Comp412 课

Codeforces Round #841 (Div. 2) and Divide by Zero 2022 A - Joey Takes Money 给一个长度为 n 的整数序列 $a_i \ge 1$ 选择两个数 $a_i$ 和 $b_i$，将其替换为 $x$, $y$，其中 $x * y = a_i * a_j $，这个操作可以进行无数次 输出这个序列的和乘以$2022$ 直接暴力就行: // clang-format off #include <bits/stdc++.h> #include <functional> using ll = long long; using ul = unsigned long long; using ld = long double; template <typename T> inline typenam

A-莲子的软件工程学 记得开 long long 就好，防止取绝对值时爆炸 #include<bits/stdc++.h> using ll = long long; using ul = unsigned long long; using ld = long double; template <typename T> inline typename std::enable_if<std::is_integral<T>::value>::type read(T &x){ char c;T f=1; while(!isdigit(c=getchar())) if(c=='-')f=-1; x=(c&15); while(isdigit(c=getchar())) x= (x<<1) + (x<&

只把签到题做了做。 回头把剩下的题补一下 听说今年要七道题才能铜 😂 C - Clone Ranran 题目大意 然然要准备 $c$ 道题，它可以进行两种操作： 克隆一个自己，使自己的数量变为原来的二倍，这需要消耗 $a$ 分钟时间 每个自己准备一道题，这需要消耗 $b$ 分钟的时间 然然不可能同时做两件事，问准备 $c$ 道题目最少用时。 思路 经过分析我们可以得知，先进行克隆操作总是不亏的，因为每次克隆操作都能使接下来用相同的时间 准备的题目数量增加2倍。而且我们一定是先进行完所有的克隆操作，最后再准备题目。 那么什么时候停止克隆呢。我们可以计算每次克隆+准备所有题目的用时和不克隆准备所有题目的用时， 如果大于就不再克隆了。 确定了这两点，代码就不难写了 代码 #include <bits/stdc++.h> #define rep(NAME, MAX) for (i