集训

$\text{OEIS}$ $trick$ $\text{score：100 + 0 + 0 = 100 rk：6/35}$ Problem A：数排列题面 题解打表，然后 $\text{OEIS}$ 第 A005802 序列 本来想着题解可能会给出正解，然而他这么说 问题是求一个数列的第 $n$ 项，但该数列显然不是线性递推数列， 但可以猜想该数列是整式递推数列。利用高斯消元或扩展 $BM$，可得…… 好了那估摸着正解就 $\text{OEIS}$ 吧 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace st ...

$\text{score：0 + 0 + 0 = 0 rk：32/39}$ Problem A：最短路题面 题解该路径一定是从 $1$ 走到 $n$ 后，在从 $n$ 返回 $1$ 时在外围走一遭，再回到 $1 \rightarrow n$ 的路径走一段，再出去向 $1$ 走一段。。 设往外围走时的起点为 $a$ 类点，回到 $1 \rightarrow n$ 路径的点为 $b$ 类点，容易知道 $a$ 和 $b$ 交错出现才可能最优，那么整个图大概就这么个样（起点和终点不作标记） 令 $f_{i, j}$ 表示从 $1$ 走到 $i$，最后一个点为 $i$，为 $a$ 类点，倒数第二个点为 $j$，为 $b$ 类点 令 $g_{i, j}$ 表示从 $1$ 走到 $i$，最后一个点为 $i$，$i, j$ 都为 $b$ 类点 实际上 $f$ 可以直接转移，不需要 $g$，但这样复杂度时 $O (n^4)$ 的，故 $g$ 相当于辅助函数 用类似 $Dijkstra$ 的形式转移，设 $i$ 到 $j$ 的最短路径为 $d_{i, j}$（即使路径上所有点的 ...

初来乍到，4h20min的题我打了2h，成功垫底，恭喜我自己 $\text{score：20 + 0 + 0 = 20 rk：26/27}$ Problen A题目描述 题解看他们都会写。。这种比较复杂的容斥我几乎都没写过。。 前置知识：高维前缀和举个例子，对比如现在要求解 $\sum\limits_{s = 0}^{2^n - 1}\sum\limits_{j \in s} a_j$（此处 $\in$ 是二进制表示下的意义），直接枚举子集是 $O (3^n)$ 的，那么高维前缀和可以优化到 $O (n2^n)$ 考虑低位前缀和，比如三位，我们是不是可以这么写 123456789101112for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) for (int k = 1; k <= n; k ++) a[i][j][k] += a[i - 1][j][k]for (int i = 1; i <= n; i ++) for (int j = 1; ...

成功由垫底转至中下水平。。 恭喜。。我？ $\text{score：55 + 0 + 0 = 55 rk：21/33}$ Problem A：猜想题目描述 数据范围对于所有测试数据，记 $l$ 表示 $n$ 的长度，则 $1 \le l \le 2 \times 10^5$，保证 $n$ 的最高位为 $1$，且除此之外的 $l - 1$ 位使用 $\text{std::mt19937}$ 随机生成 题解考场上敲了个 $55$ 分的暴力，本来想说看能不能枚举每一位然后直接算它的状态，然后不行 出题人提供的题解没看懂，就看了看其他 $A$ 掉的人的思路 首先考虑分块，使分出的块尽量大，取块大小 $L = 24$，对每一块分别处理 处理当前块时先不考虑右移删 $0$ 的情况，先只考虑乘三加一的情况，最后只要在答案上加上二进制位总数即可 设第 $i$ 块储存的数为 $a_i$ 类似线段树处理乘法时的操作，记两个变量 $mul, add$ 记录总共乘了多少，总共进位多少，那么转移到 $a_j$ 时则有 $a_j = mul * a_j + add$，以此类推 细节就看代码吧 12345678 ...

今天是几场下来第一次完整搞出一道题 虽然跑的贼慢，方法不够优，比 $\text{std}$ 慢 $200ms$。。 $\text{score：0 + 100 + 0 = 100 rk：16/32}$ Problem A：Geometric Progressions题目描述首项为 $a$ 且公比为 $b$ 的等比数列是一个形如 $a, ab, ab^2, ab^3, …$ 的数字序列 你被给定了 $n$ 个整数等比数列。你的任务是找出最小的整数 $x$，使得它是所有给定的序列的元素，或者声明这样的整数不存在 数据范围对 $100\%$ 的数据，$1 \le n \le 100, ~ 1 \le a, b \le 10^9$ 题解原题 CF571E 首先将所有 $a, b$ 分解质因数，得到大小为 $m$ 质因数集 $\{p_1, p_2, …, p_m\}$ 设 $c_{i, j}$ 表示 $a_i$ 分解质因数后 $p_j$ 的幂次，$d_{i, j}$ 表示 $b_i$ 分解质因数后 $p_j$ 的幂次，那么答案即可被表示为 $\prod\limits_{i = 1}^m p_i ...

今日依旧三道集训队原题，无部分分，连续三次 真该问候搬题人他母亲大人 $\text{score：NULL rk：NULL}$ Problem A：Sasha And CirclesProblem B：Choosing Ads题目描述给定一个长度为 $n$ 的序列和一个整数 $p$。 有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p\%$ 的数。 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}p \rfloor$ 数据范围对 $100\%$ 的数据，$n, m \le 1.5 \times 10^5, ~ 20 \le p \le 100$ 题解先考虑 $p = 51$ 的情况，很明显就是求区间众数 有一个经典区间众数套路，给数字 $i$ 一个数组 $c_i$，设当前众数 $p$，每次加一个数字 $t$，若该数字等于 $p$，则 $c_p ++$，反之则 $c_p –$，若删前 $c_p = 0$，则 $p = t$，同时 $c_p = 1$ 这样子虽然没有计算每种数 ...

今天有点人品，T1的50pts暴力怒压正解。。这数据。。不言而喻 $\text{score: 100 + 0 + 0 = 100 rk: 7/36}$ Problem A：时间管理带师题目描述众所周知，罗老师是时间管理带师 因为罗老师是时间管理带师，所以他的时间是以东为单位的 具体来讲，罗老师一天有nn东的时间 现在有很多妹子想跟罗老师约会 奇特的，她们每天总会提出两段约会时间（可能相同，代表一种），并且每天提出的总是一样的。 她们提出的约会时间形式形如i,j,代表希望在[i东,(i+1)东)[i东,(i+1)东)或[j东,(j+1)东)[j东,(j+1)东)与罗老师进行约会。 当然，罗老师可以这两段时间都与这个妹子约会,只选择一段，或者伤心地抛弃。 那么，作为时间管理带师的罗老师，每天会选择尽可能多的妹子进行约会 但你一定要注意,罗老师最近并不打算进行多人运动，所以他不会在1东的时间同时与两个或多个妹子约会 罗老师并不脸盲，与一个妹子约会2次并不能算成”2”次的贡献，只能是”1” 罗老师是时间管理带师，只要满足以上条件，他就可以安排好他的时间，不用担心别的 而且,每天可能会有新的 ...

今日继续垫底系列 T1题意理解错误暴力写挂 T2怒敲 $n \le 4$ 求根公式然后发现答案还得排序。。 $\text{score：0 + 10 + 0 = 10 rk：27/27}$ Problem A：游戏题目描述ysgh是一名Herthstone大师。现在他遇到了一个很严峻的问题： 场上总共有 $n+m$ 个随从，其中ysgh控制着 $n$ 个，对手控制着 $m$ 个。每个随从有自己的血量。 如果ysgh在这一回合成功解掉了对手的所有随从，则ysgh获胜。否则下一回合对手直接骑脸，ysgh就会输掉。 ysgh现在手里仅有一场牌，属性如下： 进行 $d$ 次，每一次等概率随机一个在场上的未死亡随从（包括自己和对手的）并且对其造成一点伤害。若不存在未死亡随从，则不进行此次攻击。一个随从未死亡当且仅当其血量严格大于 $0$。每一次攻击后，所有血量小于等于 $0$ 的随从立即死亡。 ysgh想要知道，他有多大概率可以取胜，也就是多大的概率使得在使用这张牌后，对手的随从全部死亡。 特别提醒：由于描述与实际游戏规则有出入，一切以实际题面描述为准。 数据范围对于所有测试数据，满足 $1 ...

再次垫底$\text{.jpg}$ $\text{score：20 + 0 + 10 = 30 rk：27/29}$ Problem A：sign题面 题解这题贼水，但我没想出来。。 我大概以为这不是数学所以没想到代入，或者是我忘记该点值表示可以 $O (\log A)$ 反正全村就我没到及格线 题解懒得写了，就搬出题人给的吧 事实上，这个做法不能通过。 考虑上面做法复杂度瓶颈是快速幂。一个简单的$\text{trick}$是对于一个固定的 $son_u = k$，令 $M = \lceil \sqrt{A} \rceil$，预处理出 $k^0, k^1, k^2, …, k^{M - 1}$ 以及 $(k^M)^0, (k^M)^1, …, (k^M)^{M - 1}$。这样单次求某个点值就可以用 $O (1)$ 次算术运算求得。 时间复杂度为 $O ((n + \sqrt{A})\sqrt{n})$。 以上是出题人提供题解 代码123456789101112131415161718192021222324252627282930313233343536373839404142 ...

今日又是三道集训队作业原题。。又没部分分。。 反正我都不会必定爆零就没交了。。 $\text{score：NULL rk：NULL}$ Problem A：Birthday题目描述给定 $n$ 个仅包含 a,b 的字符串。 你需要去掉尽可能少的字符串，使得剩下的字符串中不存在某一个串是另一个串的子串。 数据范围对 $100\%$ 的数据，$1 \le n \le 750, ~ \sum\limits_{i = 1}^n |s_i \le 10^7$ 题解原题 CF590E 由于 $n$ 很小，很显然可以对每一对字符串判断一个是不是另一个的子串，如果是就连个单向边，最终形成一个 $DAG$ 然后在上面搞 那么对于建图，先建个$\text{AC}$自动机，在 $trie$ 的结尾存一下编号，然后把每个串扔上去匹配，每次匹配与走到节点 $fail$ 树上的所有编号（即它的子串）连边 当然直接连边肯定会 $T$，实际上你只要往在 $fail$ 树往上找到的第一个编号以及本身节点的编号（如果存在的话）连边，然后传递闭包就好了，这样复杂度就正确了 那么接下来的任务就是在 $DAG$ 上求出最长 ...