| Rank | Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| --/-- | --/11 | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø |
O: 当场通过
Ø: 赛后通过
.: 尚未通过
A Age of Moyu
upsolved by chelly
chelly's solution
可以将边看做点，对于一个原图中一个点相连的边，我们可以给它连出平方条边，颜色相同权值就是0，颜色不同权值就是1，然后跑最短路
这个东西显然会被卡掉，我们考虑优化建图
考虑原图的点u时候，我们考虑把与u相连的边的所有颜色拉出来，表示成(color_1,color_2,...)，特别的，我们定义(color_0)是无色点，我们把这些当作新的点
然后对于一条颜色为color的原图边，我们考虑它有两种途径，一种是走无色点转到别的颜色的边，花费是1，一种就是走自己颜色的边，花费是0，所以就这样把对应的新图建出来
这样注意到是建出的图是线性的
至于跑最短路的时候，因为是01图，所以可以不需要优先队列，用一个双端队列即可
B AraBellaC
upsolved by chelly
chelly's solution
枚举循环节L，然后遍历一遍所有的线索，就可以知道在循环节L内，A出现的最前和最后，B出现的最前和最后，C出现的最前和最后了，就可以判断解是否存在，循环节为L的情况下最小的abc了
但是这样时间复杂度是(O(m imes MAX))，会TLE
考虑枚举循环节L之后，分成了(frac{MAX}{L})段，对于每一段我们要求的是A出现的最前和最后，B出现的最前和最后，C出现的最前和最后，这个直接RMQ就行了
所以时间复杂度是(O(MAX log {MAX}))
C YJJ’s Stack
upsolved by chelly
注意到值域只有1~5，所以对于每个值域我们可以分别按照时间戳维护push和delete序列
先假设没有pop操作，那么对于query操作，就是在5个序列里找出栈顶，然后选择最晚入栈的那个作为答案
我们可以将push当作+1，delete当作-1，对于一个询问query T，就相当于找出一个最大的x满足x<T，并且sum[x..T]=1，这个用线段树即可解决
然后对于pop操作，每次query操作的时候，可以先对于每个pop操作那里先进行query，把pop 换成对应的delete操作，再进行询问即可
D Go to school
upsolved by ch
ch's solution
E GuGuFishtion
upsolved by chelly
考虑如何计算(Gu(a,b))，发现对于a和b共有的质因子p，对答案的贡献是(frac{p}{p-1})，而其它的贡献都是1，所以(Gu(a,b)=frac{gcd(a,b)}{varphi (gcd(a,b))})
然后就是经典的统计有多少点对的gcd是k这个问题了，直接容斥或者莫比乌斯反演
F Lord Li's problem
upsolved by chelly
chelly's solution
非常牛批的DP
首先我们容易发现总共位数为m，选择n个数进行异或出的结果，若1的个数相同，那么方案数也相同
所以我们统计出S^T里面有多少个1就行了，假设有cnt个
设dp[i][j]表示在总共m位的情况下，选择了i个数字（当然数字的1的个数要是3个），异或的结果里面有j个1的方案数
那么答案就是(frac{dp[n][cnt]}{inom {m}{cnt}})
现在考虑如何求解这个dp
我们先这样考虑，假设你可以选择n个数，数字不需要不重复，数字的排列顺序也对结果有影响，那么有以下递推式子
这个就是相当于枚举我当前选择的这个数字消掉几个0消掉几个1
然后考虑如何消去重复的影响
假设第i个来的数字是重复的，那说明在1~i-1位当中已经有一个和它一样的数字了，剩下来的就相当于dp[i-2][j]，我们枚举重复的数字是谁，重复的是哪个位置即可
(dp[i][j]-=dp[i-2][j] imes (i-1) imes (inom{m}{3}-(i-2)))
至于顺序问题，我们只需要在最后除以对应个数的阶乘即可
G Reverse Game
upsolved by chelly
chelly's solution
线段树的区间[l,r]表示维护第l~r列中0/1连通块个数，以及最左边一列的连通性（连通的位置颜色一样），最右边一列的连通性（连通的位置颜色一样），注意如果第i行的颜色从左贯穿到右，那么左边第i行的颜色和右边第i行的颜色也要一样
然后就无脑向上update即可
H Traffic Network in Numazu
upsolved by chelly
把环上一条边扣掉，那么每次就是经过环或者不经过环
问题就变成了，给一个树，修改边权，询问两点路径和，这就是经典树链剖分题了
当然也可以不用树链剖分，可以维护每个点到根的路径和，修改就相当于给一个子树里的所有点加x，这个可以dfs序+树状数组
I Tree
upsolved by chelly
LCT模板题
J Sequence
upsolved by chelly
chelly's solution
分段矩阵乘法即可
K Swordsman
upsolved by chelly
银行家算法(雾)
