2020-team2-028
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2020-team2 返回]
[[Image(Rank.png,1000px)]]
= 概述 =
solved: 5/12
rank: 14
= 流水账 =
开场yyc读A发现是个签到，上机写完提交后WA了，冷静了一下发现自己不会数数把7数成了6，改后过了。
D(...)。
pb中途@了一下沉迷于后三题的cxt表示F好像可做，cxt听完题意后感觉他会一个两个log的小常数的dsu on tree做法，于是直接上机，不久通过。
pb发现K的结论在以前集训中出现过，于是提出了一个map+启发式合并做法，算复杂度发现是log^3^n,pb觉得写unorderedmap就能过，提交后返回TLE，只能改cxt的离线建树做法，最后成功通过。
看榜发现榜上Ldirt很高，HJ有人过，稍微想了想H发现不能套用带环博弈的做法。cxt讲了J后yyc提出一个状压做法，cxt提出一个只考虑外面的环的做法，并认为自己做法更好写，于是交给cxt去想。
yyc想了B的二分判定，pb发现可以树套树维护，于是上机写写写，调了一会过样例但是发现卡空间，提交后竟然WA了。
最后时刻由于B可能要重构优化空间，决定放弃去做L，cxt上去写J。经过一通exgcd+乱搞最后也没能通过，结束后发现别的队做法都怪怪的？
= 总结 =
=== pb： ===
今天非常划水，写了若干不能过题的东西。
数据结构应该算好空间再写，这个确实要背锅，然后有点卡常数也比较烦。
upd:这场好像背大锅，K的复杂度写假了，大概浪费了1h？
=== Creatix： ===
我这场几乎就是闭眼玩家……
开场读了三道可做又没那么简单的题（J，K，L）
然后就是码码码 & 调调调。
我对比赛过程一无所知，只知道自己写的J，K，F，外加知道题意的H，L
然
后
'''我真的会证明L啊！！！'''
cyb 就不管了……
至少 heltion 说过一句话：'''我觉得L没有细节啊？'''
H 是我菜了。
然
后
'''希望以后写题前算一下空间……'''
upd1：重复造轮子补了一下 L。
upd2：写了一下H，然而因为建边不小心double了一下，T了好久。
upd3：写了一下B的分块，我是截至11/10，最短的（71行），第二快的（3744ms）。
upd4：写了一下E。为什么这么好写的题当时没过啊？48行
upd5：写了一下I。~~为什么这么好写的题当时没过啊？~~
=== yyc： ===
比赛策略上感觉说不太清楚有没有问题，可能应该先写J后写B？但是我对于做出L不要做的判断感觉还是正确的，赛后问了通过的队伍他们的做法也都没办法严格的证明，题解的做法高妙许多。
H被卡套路了，时间太久了真的没什么印象。
之后有比较长的一段调整的时间，目前的训练计划是多组织一些个人训练，补一补之前没补的题，涨一涨姿势水平。
= 题解 =
* A：
* B：叮咚~您点的'''树套树卡空间合集'''：1，写块状链表。2，离线后每个点开个树状数组。3，线段树套平衡树（或者pbds）。
二分答案mid，那么只需要check一下sum(min(mid,m-1-a[i]))和mid*(r-l+1-k)
权值线段树套平衡树，在权值线段树上二分，用维护位置的平衡树查询
* C：
* D：
* E：直接压状态然后dp
* F：科普一下写法……当要处理树上节点对间信息维护问题的时候，我们可以在每个LCA处理他子树的信息合并。
* 定义Solve(x)表示计算x的子树贡献并且把x中所有点的信息加入一个DS。
* Solve(x)的实现方法是：1，Solve(x 的轻儿子)，并且每次Solve完后记得清空DS。2，Solve(x 的重儿子)。3，遍历x的轻儿子，统计贡献。4，将x的所有轻儿子以及x本身加入DS。
* 复杂度分析：容易发现x的重儿子只被x访问过1次，而轻儿子则只被访问过有限次。同理树剖复杂度分析，可知算法复杂度正确。
* G：
* H：二分图博弈。
若包含起点的图的最大匹配，与不包含起点的图的最大匹配'''相等'''，则说明存在一个最大匹配，不包含起点。'''那么后手必胜'''。
后手策略：手持任意一张不包含起点的最大匹配图，每次先手无论怎么走，后手都走该点的匹配边。如果某次后手无法操作，说明存在增广路，与这张图是最大匹配矛盾，故后手必胜。
若包含起点的图的最大匹配，与不包含起点的图的最大匹配'''不相等'''，则说明所有最大匹配都包含起点。'''那么先手必胜'''。
先手策略：手持任意一张包含起点的最大匹配图，每次后手无论怎么走，先手都走该点的匹配边。
如果某次先手无法操作，说明存在长为偶数的交错路，反转该路径则出现一个不包含起点的最大匹配，与这张图所有最大匹配包含起点矛盾，故先手必胜。
* I：树上随机游走概率dp经典做法，正着dp一遍，每个点的dp值表示为:dp[x] = k * dp[fa] + b。完成后倒着dp一遍求出每个dp值。注意系数较难以用数值维护，故选择矩阵维护。
* J：枚举最外层圆的大小然后DP。
* K：发现，对于每个数，和它能产生贡献的数不会太多（orz pb）。然后类似F的写法。
* L：找到最小的非负整数a1，使得 (a1 * n + n * (n - 1) / 2) % (k + 1) = s % (k + 1) 并且以a1为首的最小总和小于等于s。若找不到，显然无解
* 然后开始增大这个数。首先通过对全局进行若干次+=k+1的操作使得误差小于n * (k + 1)，然后每次选取一个...a, (a-k), (a-k+1)...，将它变成...a, (a+1), (a-k+1)...
* 另外，我写完标算以后顺手验证了一下之前我证明的结论的正确性（见下图）：如果存在合法的解，那么模(k+1)意义下，最小的解或最大的解一定有至少一组合法。
* （快出一道新题，n，k，s，1e18，判断是否存在合法解）
* ~~我花了好久调整我编辑器的位置才让背景恰到好处~~
[[Image(L的验证.png,1000px)]][/wiki/2020-team2 返回]
概述
solved: 5/12
rank: 14
流水账
开场yyc读A发现是个签到，上机写完提交后WA了，冷静了一下发现自己不会数数把7数成了6，改后过了。
D(...)。
pb中途@了一下沉迷于后三题的cxt表示F好像可做，cxt听完题意后感觉他会一个两个log的小常数的dsu on tree做法，于是直接上机，不久通过。
pb发现K的结论在以前集训中出现过，于是提出了一个map+启发式合并做法，算复杂度发现是log3n,pb觉得写unorderedmap就能过，提交后返回TLE，只能改cxt的离线建树做法，最后成功通过。
看榜发现榜上Ldirt很高，HJ有人过，稍微想了想H发现不能套用带环博弈的做法。cxt讲了J后yyc提出一个状压做法，cxt提出一个只考虑外面的环的做法，并认为自己做法更好写，于是交给cxt去想。
yyc想了B的二分判定，pb发现可以树套树维护，于是上机写写写，调了一会过样例但是发现卡空间，提交后竟然WA了。
最后时刻由于B可能要重构优化空间，决定放弃去做L，cxt上去写J。经过一通exgcd+乱搞最后也没能通过，结束后发现别的队做法都怪怪的？
总结
pb：
今天非常划水，写了若干不能过题的东西。
数据结构应该算好空间再写，这个确实要背锅，然后有点卡常数也比较烦。
upd:这场好像背大锅，K的复杂度写假了，大概浪费了1h？
Creatix：
我这场几乎就是闭眼玩家……
开场读了三道可做又没那么简单的题（J，K，L）
然后就是码码码 & 调调调。
我对比赛过程一无所知，只知道自己写的J，K，F，外加知道题意的H，L
然
后
我真的会证明L啊！！！
cyb 就不管了……
至少 heltion 说过一句话：我觉得L没有细节啊？
H 是我菜了。
然
后
希望以后写题前算一下空间……
upd1：重复造轮子补了一下 L。
upd2：写了一下H，然而因为建边不小心double了一下，T了好久。
upd3：写了一下B的分块，我是截至11/10，最短的（71行），第二快的（3744ms）。
upd4：写了一下E。为什么这么好写的题当时没过啊？48行
upd5：写了一下I。为什么这么好写的题当时没过啊？
yyc：
比赛策略上感觉说不太清楚有没有问题，可能应该先写J后写B？但是我对于做出L不要做的判断感觉还是正确的，赛后问了通过的队伍他们的做法也都没办法严格的证明，题解的做法高妙许多。
H被卡套路了，时间太久了真的没什么印象。
之后有比较长的一段调整的时间，目前的训练计划是多组织一些个人训练，补一补之前没补的题，涨一涨姿势水平。
题解
- A：
- B：叮咚~您点的树套树卡空间合集：1，写块状链表。2，离线后每个点开个树状数组。3，线段树套平衡树（或者pbds）。
二分答案mid，那么只需要check一下sum(min(mid,m-1-a[i]))和mid*(r-l+1-k)
权值线段树套平衡树，在权值线段树上二分，用维护位置的平衡树查询
- C：
- D：
- E：直接压状态然后dp
- F：科普一下写法……当要处理树上节点对间信息维护问题的时候，我们可以在每个LCA处理他子树的信息合并。
- 定义Solve(x)表示计算x的子树贡献并且把x中所有点的信息加入一个DS。
- Solve(x)的实现方法是：1，Solve(x 的轻儿子)，并且每次Solve完后记得清空DS。2，Solve(x 的重儿子)。3，遍历x的轻儿子，统计贡献。4，将x的所有轻儿子以及x本身加入DS。
- 复杂度分析：容易发现x的重儿子只被x访问过1次，而轻儿子则只被访问过有限次。同理树剖复杂度分析，可知算法复杂度正确。
- G：
- H：二分图博弈。
若包含起点的图的最大匹配，与不包含起点的图的最大匹配相等，则说明存在一个最大匹配，不包含起点。那么后手必胜。
后手策略：手持任意一张不包含起点的最大匹配图，每次先手无论怎么走，后手都走该点的匹配边。如果某次后手无法操作，说明存在增广路，与这张图是最大匹配矛盾，故后手必胜。
若包含起点的图的最大匹配，与不包含起点的图的最大匹配不相等，则说明所有最大匹配都包含起点。那么先手必胜。
先手策略：手持任意一张包含起点的最大匹配图，每次后手无论怎么走，先手都走该点的匹配边。
如果某次先手无法操作，说明存在长为偶数的交错路，反转该路径则出现一个不包含起点的最大匹配，与这张图所有最大匹配包含起点矛盾，故先手必胜。
- I：树上随机游走概率dp经典做法，正着dp一遍，每个点的dp值表示为:dp[x] = k * dp[fa] + b。完成后倒着dp一遍求出每个dp值。注意系数较难以用数值维护，故选择矩阵维护。
- J：枚举最外层圆的大小然后DP。
- K：发现，对于每个数，和它能产生贡献的数不会太多（orz pb）。然后类似F的写法。
- L：找到最小的非负整数a1，使得 (a1 * n + n * (n - 1) / 2) % (k + 1) = s % (k + 1) 并且以a1为首的最小总和小于等于s。若找不到，显然无解
- 然后开始增大这个数。首先通过对全局进行若干次+=k+1的操作使得误差小于n * (k + 1)，然后每次选取一个...a, (a-k), (a-k+1)...，将它变成...a, (a+1), (a-k+1)...
- 另外，我写完标算以后顺手验证了一下之前我证明的结论的正确性（见下图）：如果存在合法的解，那么模(k+1)意义下，最小的解或最大的解一定有至少一组合法。
- （快出一道新题，n，k，s，1e18，判断是否存在合法解）
我花了好久调整我编辑器的位置才让背景恰到好处
