JOISC2021 D2T1 Escape Route
好题。首先我们考虑一天之内能到达的情况。我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ,使得在 $T$ 之前的时刻出发,都可以在当天到达 $t$ (这里要注意有可能一天之内到不了,也就是可能 $T < 0$ )。 这个东西如何计算?首先有一种非常暴力的想法,我们每次加入一个当前连通块连出去的边,同时可能导致 $T$ 减小,然后重新跑一次最短路。考虑这样的复杂度,枚举点 $O(n)$ ,加边次数是 $O(n^2)$ ,每次跑最短路使用 dijkstra (这里显然 $O(n^2 ...
阅读更多
LOJ3282. 「JOISC 2020 Day4」治疗计划
考虑一个 $dp$ ,设 $dp[R][t]$ 表示在 $t$ 时刻已经解决了 $1 \sim R$ 的所有患者。考虑转移就是枚举下一个治疗计划用哪一个。设下一个治疗计划为 $(l,r,c)$ 那么分为两类: $c > t$ ,那么在下一次使用治疗计划的时间在现在之后,由于中间不能有剩余的患者,有 $l \le R-(c-t)$ ,也就是 $c > t,l + c \le R+t$ 。 $c < t$ ,也就是说之前进行了一次治疗计划用来覆盖 $R$ 后的一段,那么中间没有剩 ...
阅读更多
Gym101190G Game On Graph
一道很有意思的题,我也不知道这个题解是否写清楚了。。 设 A 是 Gennady , B 是 Georgiy 。 首先考虑如何找出所有会使游戏无限进行下去的点。这种点分为两种,一种是从这个点,A 先手出发,就会导致最终平局,还有一种是 B 先手出发却会导致不得不平局。 首先考虑所有出度为 $0$ 的点,显然不管谁从这个点先手,游戏都会结束。 由于 A 的决策是尽量平局,所以一个点 A 出发无法平局当且仅当它的所有后继点都是 B 出发会导致不平局的情况。 由于 B 的决策是尽量不平局,所以一个点 ...
阅读更多
Gym100801G Graph
从一般的求字典序最小的拓扑排序入手。考虑第一次加入无入度点后,得到了一个小根堆 $mn$ 。我们的目标是让这一次拿的是这个小根堆里面尽量大的数。先假装 $k$ 足够,于是我们把这里面除了最后一个数之外的所有数全部丢出小根堆并且维护到一个大根堆里面。然后对于最后一个数,如果它比大根堆的最大值还大,显然没有必要把它丢出去,直接用就是最优的。否则,肯定是把它也丢出去,然后拿大根堆里面的最大的出来,从拓扑序上上一次的点向这个点连边,这样一定能钦定在字典序最小的情况下,这个点的位置就在这里。 也就是说,当 ...
阅读更多
CF757F Team Rocket Rises Again
为了做这个题学了一下支配树大概是个什么玩意。一般图支配树被鸽了,只写一下 DAG 上支配树的做法。 考虑一个单源有向图,上的一个点 $u$ 如果存在一个点 $v$ 满足删除 $v$ 后 $u$ 无法从源点到达,那么我们称 $v$ 支配点 $u$ 。 显然,同一个点的支配点很多,设这些点是 $v_1,v_2, \dots ,v_k$ ,同时显然源点也是一个支配点。 如果 $a$ 支配 $b$ ,$b$ 支配 $c$ ,那么有 $a$ 支配 $c$ 。证明显然。 如果 $a$ 支配 $c$ ,$b ...
阅读更多
ARC098D Donation
也是道不错的题,大概是第一次做到按点权建 Kruskal 重构树。 捐赠的过程是一个经典的问题,一般的做法是倒着考虑后贪心。倒着考虑这个问题,于是变成了选择一个初始点,在任意点的时候身上的钱的数量必须不小于 $\max(A_i - B_i , 0)$ ,并且到达一个点后就可以选择获得 $B_i$ 块钱,你需要最小化最终的钱数。 为了方便,我们设 $C_i = \max(A_i - B_i , 0)$ 。如果是个完全图就可以直接按照 $C_i$ 从小到大贪心拿。但是事实上,由于具有图的限制,想要拿 ...
阅读更多
LOJ3280. 「JOISC 2020 Day4」首都城市
需要注意的是,这个题当把一个颜色合并进选择的颜色后,会导致一些其他的颜色原本无法影响最开始选择的颜色,但是合并后会影响了。也就是说影响关系是具有传递性的。 因此考虑如果设定一个颜色 $i$ 为首都需要将另一个颜色 $j$ 合并进 $i$ ,那么加边 $j \to i$ 。这样加边后,显然只需要一次缩点就能求出答案。具体来说,最后选择的一定是入度为 $0$ 的点,并且需要合并的次数就是这个点的大小 $-1$ 。 考虑怎么进行加边。我们考虑以 $i$ 作为首都,那么显然将 $i$ 颜色建立虚树后所有 ...
阅读更多
CF1456E XOR-ranges
神仙题。不愧是 3500 。 我们考虑对于每个数,它必然有一个脱离限制的位。也就是说,每个位置实际上放的值,必然是和 $L$ 或者 $R$ 存在一段 $\text{LCP}$ ,然后下一位脱离限制,然后后面的随意填。 于是我们考虑一个贪心,如果我们知道了 $1 \sim n$ 的所有数中脱离限制位最低的是谁,那么这个脱离限制位之下的所有位对于所有数都是可以随便放的,所以我们一定全放 $0$ 或者全放 $1$ 最优。 我们可以把这个问题推广到任何一个区间上。对于一段区间 $l,r$ ,我们可以枚举 ...
阅读更多
DP 训练2 部分简要题解
CF1204E Natasha, Sasha and the Prefix Sums首先,看到这个 $\max$ 可以想到转化成求和最大值大于等于 $i$ 的方案个数。 按照这种 prefix sum 的一般想法,会发现这个东西就是画成折线后和 $y=i$ 的交点。然后枚举 $i$ 分情况讨论,由于结束点显然在 $(n+m,n-m)$ 那么: 如果 $n-m \ge i$ ,显然必然有交点。方案数为 $\binom {n+m} n$ 。 否则,我们考虑把 $(0,0)$ 翻折到 $(0,2i) ...
阅读更多
JOISC D3T3 Meeting 2
每天只挑最简单的做就是我了 称有人的点为关键点。 首先观察样例会发现,如果关键点的个数为奇数,答案肯定是 $1$ 。我们设任意一个开会地点为 $u$ ,那么显然有所有儿子子树内的关键点个数不超过一半,而又是奇数,往任何一个方向走肯定都无法使得答案保持不变,而且一定是变得不优。同时如果你一直往某个方向走,原本子树大小不超过一半之后也一定不超过,所以一定会越来越不优。 类似的思路,考虑偶数的时候,如果存在多解,肯定是找到了一个点,使得所有点被平均分配到两个子树里面,这样就可以把根向这两个子树移动,如 ...
阅读更多
LOJ3395 「2020-2021 集训队作业」Yet Another Permutation Problem
考虑什么样的排列可以通过 $k$ 次操作达到。不难发现当且仅当排列中存在一个区间,满足区间单增且区间长度 $\ge n - k$ 。由于存在会比较难以统计,可以考虑求出所有极长连续段长度 $\le n - k - 1$ 的排列数量,然后用 $n!$ 减去即可。 考虑枚举 $t$ ,计算所有极长上升段都 $\le t$ 的方案数。考虑一个暴力,先暴力对整个序列分段,令这些段就是极长上升段,然后不难发现限制是 段内 $<$ 和 段间 $>$ 。这个东西非常难以统计,所以考虑容斥掉 $&g ...
阅读更多
LOJ3399「2020-2021 集训队作业」Communication Network
看到这题第一想法就是口罩,感觉做过口罩这题的过程就很自然了。我们考虑设 $f(k)$ 表示恰好 $k$ 条边与原树相同的树的个数,$g(k)$ 表示钦定 $k$ 条边,于是: \sum_{k \ge 0} f(k)k2^k\\ \sum_{k \ge 0} k2^k \sum_{j \ge k} g(j)(-1)^{j-k} \binom j k\\ \sum_{j \ge 0} jg(j) \sum_{k \le j} 2^k(-1)^{j-k} \binom {j-1} {k-1}\\ \ ...
阅读更多
AGC050C Block Game
考虑第一次操作,必然会放在当前 Snuke 的任意一边。 然后考虑第二次操作,必然放在当前 Snuke 的另一边。 然后现在 Snuke 就被圈起来了,仔细考虑一下会发现,它的决策必然是往尽量中间的位置靠。因为在下一次放方块的操作中,你肯定会让 Snuke 的活动范围尽量减少。也就是说,设你放方块的时候 Snuke 到左边长度是 $l$ ,到右边是 $r$ ,那么放完后他的范围肯定是变为 $\min(l,r)$ 。 我们考虑什么样的 B 操作,会导致能确定之后必然能堵死 Snuke 。对于最后两 ...
阅读更多
ARC104F Visibility Sequence
大概有两种做法。 首先写一下官方题解的做法。 我们设 $i \to P_i$ 存在一条边,同时将 $P_i=-1$ 看做 $P_i = 0$ ,并添加虚点 $0$ ,于是对于任意一个排列,必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。 然后会发现,对于整棵树的一个子树,它必然在序列上对应一个区间,而它的根就是区间的左端点。考虑任意一个位置 $i$ ,它后面的第一个比它大的位置在 $j$ ,考虑 $[i+1,j-1]$ 这一段之间的所有数,显然它们不会连到 $i$ 的 ...
阅读更多
CF1240F Football
神仙构造题。写一下 pb 讲的做法。 考虑极差不超过 $2$ 这个限制。可以把每条边 $u,v$ ,令 $u<v$ ,则变成 $u,v+n$ 的一条边,也就是拆成一个二分图。 考虑在这个图上染色,然后再把 $u,u+n$ 合并起来。如果在这个得到的二分图上可以染色使得每个点极差不超过 $1$ ,那么合并后一定可以让每个点极差不超过 $2$ 。 下面将说明这样的合法的染色方案一定存在。假设一个点 $u$ 的度数是 $ak+b$ ,那么我们可以把一个点拆成 $a+1$ 个点,然后前 $a$ 个 ...
阅读更多
2.18 数论题
目前咕咕咕:T6 T8 以及 T5 的 魔改 Min25 。 T1$T\le 5000,a,b\le 10^9$ 求: \sum_{i=a}^b \text{lcm}(i,b) \bmod 10^9 + 7前缀和一下即求 \sum_{i=1}^n \text{lcm}(i,b)有一种曾经卷老师教过的非常不错的推法,考虑求和 $\gcd$ 的时候可以直接转乘 $\varphi$ , \begin{aligned} & \sum_{i=1}^n \gcd(i,n)\\ &= \sum_{i=1 ...
阅读更多
Powerful Number 筛
题目: Powerful Number 筛也是一种筛,它是 $O(\sqrt n)$ 的。应用时必须满足 它是积性函数 这个东西在质数处取值的函数可以快速计算前缀和。例如此题,显然有 $f(p) = 1$ 。 首先 Powerful Number 的定义,是所有质因子次数都 $\ge 2$ 的数。这种数的个数是 $O(\sqrt n)$ 级别的。因为显然,每个这样的数都可以被表示成 $a^2b^3$ ,所以寻找这种数的时候可以暴力枚举这里的 $a,b$ ,复杂度是 $\sum_{i=1 ...
阅读更多
CF1148G Gold Experience
神仙题。大概是一篇只有做法没有思路的题解。。 显然这个题 $\gcd > 1$ 就是想建补图。然后问题就变成了选出一个点集使得大小正好为 $k$ 且要么每个点都在导出子图里有边,要么所有点都是孤立点。构造一组方案即可。 需要注意的是第二种情况,如果可以找到一个 $\ge k$ 的独立集,那么只需要保留 $k$ 个点即可。 首先要会求所有点的度数。不难发现 $a_i$ 的度数是 \sum_{1 \le j \le v} occ[j][\gcd(a_i,a_j) = 1]\\ =\sum_{ ...
阅读更多
ARC112
这场我感觉题很不错的QwQ C DFS Game考虑先手到达一个根。然后先手必然会取走这个根上的硬币。然后后手会选择一个儿子向下,然后又变成先手到达一个根的问题。所以感觉上需要考虑 $dp$ 。但是事实上从这个子树回溯回来之后,不一定开始的先手仍然作为先手。所以可以考虑 $dp[u]$ 表示先手到达 $u$ 后可以获得的价值减去后手可以获得的价值的最大值。设最终先手获得硬币数是 $a$ ,后手是 $b$ ,那么 $a+b=n$ ,所以只需要最大化 $a-b$ 即可。 考虑如何转移。不难发现当我们 ...
阅读更多
WC2021 兼 SCOI2021 游记
时间好快啊,感觉 SCOI 2020 游记还没写多久就到 2021 年的省选了。 终于,没有了垃圾 SCOI 计算几何。 Day 0早上看了看字符串板子,该看的板子其实大多都看过了,再复习了一遍 SAM PAM 以及 KMP 之类的,虽然多半也用不上。 下午一直在颓,大概 FC 了个 GOODFORTUNE,希望为明天考试带来好运。 晚上写了一遍 cdq 分治 NTT 的板子,发现好像这个板子没有以前想的那么难写。 反正感觉能准备的都准备了,实在不行就听天由命了。 Day 1又是笔记本差评,但 ...
阅读更多
topcoder DoubleLive
好题。类似 Students Camp 的优化。考虑 $dp[i][j][k]$ 表示当前还剩下 $i$ 个熊两血,$j$ 个一血,其中有 $k$ 个是人。 直接转移复杂度是 $O(1)$ 状态共 $O(n^3)$ 种,复杂度 $O(n^3)$ 。 考虑怎么优化这个 $dp$ 。先把状态转移的式子写出来 dp[i][j][k] = \frac{i+1}{i+j}dp[i+1][j-1][k]+\frac{j+1-k}{i+j+1}dp[i][j+1][k]+\frac{k+1}{i+j+1}d ...
阅读更多
Min_25 筛
Min_25 筛也是一种求积性函数前缀和的算法。 Min_25 筛的应用前提是可以找到一个完全积性函数在质数处和要求的函数相同。所以我们假装得到了一个完全积性函数 $f’$ 它在质数处的取值和 $f$ 相同。 首先,我们把 $1$ 扣掉,最后把 $1$ 加回来即可。所以后面的范围的下界都是 $2$ 。 我们考虑把所求拆一下,然后在非质数部分枚举一下最小的质因子以及这个质因子的次数: \sum_{i \in P} f(i) + \sum_{p^e \le n , p \le \sqrt n} f ...
阅读更多
数据结构专题 #1
A Strange Addition水题。 考虑 $dp[i]$ 表示当前考虑到第 $i$ 位,有多少种有序对 $(a,b)$ 在前 $i$ 位满足条件。 转移考虑每次往 $(a,b)$ 后面分别添加一位,然后考虑得到的数,要么得到的数会添加两位,要么只添加一位。所以转移就是 dp[i] = dp[i-1]S[A_i] + dp[i - 2] S[A_i+10A_{i-1}]其中 $S[i]$ 表示有多少种两个一位数加起来是 $i$ 。 这个转移显然可以写成矩阵乘法的形式,每个位置维护一个矩阵 ...
阅读更多
1.12 模拟赛
A 一次函数不难发现一个数真正重要的只有这个数中的连续段个数以及这个数最后一位是 $0/1$ 。 我们设 $f(x)$ 表示 $x$ 二进制表示下的连续段的个数。那么答案就是在 \sum_{i=1}^n f(ai + b)的基础上再减去除开最后一个位置的奇数的个数,因为这些数会和下一个数的 $1$ 合并成一段。 这个东西怎么求?不难发现这是个 $\bmod a$ 不变的式子,而这题正好 $a$ 非常小。所以我们考虑求 \sum_{i=1}^{an+b} [i \bmod a = 0] f( ...
阅读更多
1.14 模拟赛
A 环游看起来是毒瘤题,其实不然。 我们设首都是 $a$ ,秘密都市是 $b$ ,新建城市是 $c$ ,我们需要找到的就是一条 $a \to c \to b \to a$ 的路径,且保证 $a \to b$ 有至少三条点不相交路径。 现在假装我们已经拿出了三条 $a \to b$ 的路径。我们考虑先尝试找到一条 $a \to c$ 的路径,然后找出它最后一次经过 $a \to b$ 的三条路径之中的任意一条的某个点 $v$ 。然后我们可以把 $a \to c$ 变成 $a \to v \to c ...
阅读更多
一些 Topcoder DP题 题解
剩下的题有些不可做,可做的也懒得去写了。(咕咕咕 DifferenceSequence 定义对一个序列进行一次操作为 A_1,A_2,\dots ,A_n\\ \to |A_1-A_2|,|A_2-A_1|,\dots ,|A_n-A_1|对于任意一个序列,进行操作后必然会进入一个循环。我们定义循环内的最大字典序串为此串的代表串,求所有长度为 $n$ 的串的代表串去重后字典序第 $k$ 小的串。 我们先打个表观察一下会发现,任意一个序列在进行很多次操作后都会变成一些相同大小的数字与 $0$ ...
阅读更多
1.13 练习
A Codechef LUCKYDAY阴间题。除开卡常和细节还是道很好的题。 $L,R \le 10^{18}$ ,会想到寻找循环节。由于下一个数会和前两个数有关,因此循环结最大不会超过 $p^2$ ,也就是 $10^8$ 级别。但是这个数是可以卡满的,而这题 $500\text{ms}$ 显然不会放过去暴力。 如何找循环节呢,考虑这个转移写成矩乘,设转移矩阵是 $T$ ,于是问题就变成了找最小的 $k$ 使得 T^{k}A = A其中 $A$ 是初始的矩阵也就是 \begin{bmatr ...
阅读更多
CF566C A Logistical Questions
考虑当前在 $u$ ,如何确定带权重心在哪个子树中。考虑往某个子树移动一个微小距离,那么所有点到这个点距离的变化是 \sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta x)^{1.5} ) - \sum _{t \in S_v} ((x_t + \Delta x)^{1.5} - x_t^{1.5})如果这个东西大于 $0$ ,就意味着往这个点移是优的,也就是 \sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta ...
阅读更多
1.24 模拟赛
A Power看到这题数据随机就可以想到可不可以乱搞。我们考虑从 $P-1$ 开始向下枚举,每次用 BSGS 解出这个数第一次出现的位置,如果这个数小于之前的最小位置,我们就用它来代替最小位置继续做。然后考虑设置一个阈值 $B$ ,如果当前的数已经小于了 $B$ 就停止这个做法直接枚举前 $B$ 个数。 然后写出来试了试发现只能过 $10^7$ 。冷静分析一波复杂度,会发现如果 $B$ 控制合理大概是 $O(P^{\frac 3 4})$ 的东西。具体来说,随机情况下如果我们找到了一个比当前最优 ...
阅读更多
CF468E 积和式
任意模数下的积和式并没有多项式解法。考虑积和式的组合意义,$i,A_i$ 都是互不相同的,可以看作是二分图的一个完美匹配。因此任意矩阵的积和式就是 $A_{x,y}$ 看作左侧 $x$ 右侧 $y$ 之间的边权后所有完美匹配边权的积的和。 如果我们给所有 $A_{x,y} \neq 1$ 拆成 $1,A_{x,y} - 1$ 这两个东西,然后所有边上都有了一个长度为 $1$ 的边。于是现在就可以不考虑所有长度为 $1$ 的边了。我们求出除开边权为 $1$ 的边后的任意一个二分图匹配,那么这个匹配 ...
阅读更多