2020-team06/C101
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== trac writer == 没有自己账号所以只能用zhouyihe的l1ll5
== 训练模式 == 三人参与，线上连麦。
== 赛时提交 == [[Image(1.png)]]
== 最终结果 == [[Image(2.png)]]
== 比赛链接 == https://codeforces.com/gym/102538/
== 训练经历 ==
(因为zgz咕的太久被zyh乱写一通补上了)
上来大家都很兴奋，导致什么题目都不会做，榜也长时间没人a题，终于zgz发现I似乎可做，很快写完。cyb表示b应该很简单但是他不会，和zyh交换题目，zyh扔给他一个E。
zyh手玩了几个样例瞎猜结论上去写B,猜完zgz表示疑惑cyb表示这个一定是对的，经历一些傻逼之后确实过了,此时大家发现J过得较多次数cyb开始表演他的玄学之力?
zgz:它肯定是5的倍数
cyb:他是5的次方？
zyh:????
zgz：为什么
cyb:手完感受一下
zgz:你手玩还能玩出5的次方？？？
cyb接连便是难懂的话，什么“加一条边*5”，什么“奇环无效”，什么“手玩.jpg”之类，引得众人都懵逼起来：队里却充满了快活的空气。
因为暂时没题会做，可怜的zgz甚至在cyb胡结论的时候给他写好了对拍。试了几个数据发现很对...
此时zyh在刚E，感觉有点想法但实际上此时跑偏了。
之后zgz感觉F似乎noi上见过，回忆了一下这题还是个弱化版，想明白之后五分钟ac,很强。
看了看榜大家感觉只剩EC，因为zyh感觉自己E有点思路，所以暂时让他们俩先去做C。
最后似乎C和E都绕了好大的圈终于艹了过去...事后凭借印象，感觉cyb+zgz合作调一个代码的水平提升了不少.
但是cyb今天一道题没写。
== 简易题解 ==
A：
题意：
题解：
B：
题意：给出一棵树每个点的度数序列，输出可能的最大匹配值。
题解：不妨钦定所有叶子都和一个非叶子节点匹配，则剩余节点都可以两两匹配。需要注意n=2的情况会被认为是两个叶子节点。
C：
题意：给出一个由空地和墙构成的网格图，选择两个不同的空地将其修改为墙，问可以使得(1,1)和(n,m)不连通的方案数。（所有路径均为向左下方移动）
题解：考虑一条从(1,1)到(n,m)的路径，必然穿过了所有对角线恰好一次。那么处理出所有节点与(1,1)和(n,m)的连通性，枚举每一条对角线，讨论其上有多少与(1,1)和(n,m)都连通的空地，则可以计数答案。
具体一点的话，若只有一个点满足，则选择这个点和其余任意一个空地，若有多个点满足，则按顺序排列它们，固定一个墙在最右上角或者左下角，维护出剩余所有路径中最右上的一条和最左下的一条，则另一个墙必然放在它们的交处。
需要注意的细节是计数去重和初始便(1,1)与(n,m)不连通的情况。
D：
题意：询问有多少个长度为n的排列可以拆成两个上升子序列。
题解：
E：
solved by zhouyihe，由他补坑。
题意：n堆石子两人博弈，问当一次取石子上限为1~n时分别谁会赢
题解：对每个bit分开做，维护fij表示（t>i）且（t-i）&（1<<j）=1 的t的个数，维护方法f[i][j]=f[i+(1<<(j+1)))][j]+getsum(i+(1<<j),i+(1<<j+1)-1);
然后 对每段[kx,kx+x）用类似的方法计算，总体思路就是用fij这个类似后缀和的东西算出大部分，边角部分在保证其&（1<<j）一定=1的前提下 直接拿前缀和去算.
F：
题意：和另一个人竞争打怪，有n个怪物，每个怪物的血量为 hp_i，你的攻击力为a，对方的攻击力为b，轮流攻击，你可以任意选择攻击对象，也可以摸鱼，你的对手只能按照顺序攻击，问你最多能获得多少个击杀数。
题解：首先显然若想获得某个怪物的击杀，需要攻击的次数是固定的，多余的攻击没有意义，可以预处理出这个数字。此后类似NOI2018蔬菜，若获得某个收益需要在某个时间节点前付出某个代价，可以进行经典的贪心转化。不妨顺序考虑所有怪物，用一个堆维护目前击杀怪物的集合。每次读入一个新怪物，要么用目前剩余的时间击杀它，要么用堆中最劣的元素替代它，要么放弃它。按顺序决策即可。
G：
题意：
题解：
H：
题意：
题解：
I：
题意：咕一会就补。
题解：
J：
题意：给出一张简单无向图，由你给每条边决定一个[0,4]的边权，问使得最后每个点所有相邻边边权和模5为0的方案数有多少。
题解：对每个连通块分别考虑，对于一个连通块，答案为 5^(m-n+x)，其中x为是否有奇环（是二分图），或者是是否没有奇环，记不住了（。
证明等待无敌的乱搞大师cyb补上来。== trac writer == 没有自己账号所以只能用zhouyihe的l1ll5
== 训练模式 == 三人参与，线上连麦。
== 赛时提交 ==
== 最终结果 ==
== 比赛链接 == https://codeforces.com/gym/102538/
训练经历
(因为zgz咕的太久被zyh乱写一通补上了)
上来大家都很兴奋，导致什么题目都不会做，榜也长时间没人a题，终于zgz发现I似乎可做，很快写完。cyb表示b应该很简单但是他不会，和zyh交换题目，zyh扔给他一个E。
zyh手玩了几个样例瞎猜结论上去写B,猜完zgz表示疑惑cyb表示这个一定是对的，经历一些傻逼之后确实过了,此时大家发现J过得较多次数cyb开始表演他的玄学之力?
zgz:它肯定是5的倍数
cyb:他是5的次方？
zyh:????
zgz：为什么
cyb:手完感受一下
zgz:你手玩还能玩出5的次方？？？
cyb接连便是难懂的话，什么“加一条边*5”，什么“奇环无效”，什么“手玩.jpg”之类，引得众人都懵逼起来：队里却充满了快活的空气。
因为暂时没题会做，可怜的zgz甚至在cyb胡结论的时候给他写好了对拍。试了几个数据发现很对...
此时zyh在刚E，感觉有点想法但实际上此时跑偏了。
之后zgz感觉F似乎noi上见过，回忆了一下这题还是个弱化版，想明白之后五分钟ac,很强。
看了看榜大家感觉只剩EC，因为zyh感觉自己E有点思路，所以暂时让他们俩先去做C。
最后似乎C和E都绕了好大的圈终于艹了过去...事后凭借印象，感觉cyb+zgz合作调一个代码的水平提升了不少.
但是cyb今天一道题没写。
简易题解
A：
题意：
题解：
B：
题意：给出一棵树每个点的度数序列，输出可能的最大匹配值。
题解：不妨钦定所有叶子都和一个非叶子节点匹配，则剩余节点都可以两两匹配。需要注意n=2的情况会被认为是两个叶子节点。
C：
题意：给出一个由空地和墙构成的网格图，选择两个不同的空地将其修改为墙，问可以使得(1,1)和(n,m)不连通的方案数。（所有路径均为向左下方移动）
题解：考虑一条从(1,1)到(n,m)的路径，必然穿过了所有对角线恰好一次。那么处理出所有节点与(1,1)和(n,m)的连通性，枚举每一条对角线，讨论其上有多少与(1,1)和(n,m)都连通的空地，则可以计数答案。
具体一点的话，若只有一个点满足，则选择这个点和其余任意一个空地，若有多个点满足，则按顺序排列它们，固定一个墙在最右上角或者左下角，维护出剩余所有路径中最右上的一条和最左下的一条，则另一个墙必然放在它们的交处。
需要注意的细节是计数去重和初始便(1,1)与(n,m)不连通的情况。
D：
题意：询问有多少个长度为n的排列可以拆成两个上升子序列。
题解：
E：
solved by zhouyihe，由他补坑。
题意：n堆石子两人博弈，问当一次取石子上限为1~n时分别谁会赢
题解：对每个bit分开做，维护fij表示（t>i）且（t-i）&（1< 然后 对每段[kx,kx+x）用类似的方法计算，总体思路就是用fij这个类似后缀和的东西算出大部分，边角部分在保证其&（1< F： 题意：和另一个人竞争打怪，有n个怪物，每个怪物的血量为 hp_i，你的攻击力为a，对方的攻击力为b，轮流攻击，你可以任意选择攻击对象，也可以摸鱼，你的对手只能按照顺序攻击，问你最多能获得多少个击杀数。 题解：首先显然若想获得某个怪物的击杀，需要攻击的次数是固定的，多余的攻击没有意义，可以预处理出这个数字。此后类似NOI2018蔬菜，若获得某个收益需要在某个时间节点前付出某个代价，可以进行经典的贪心转化。不妨顺序考虑所有怪物，用一个堆维护目前击杀怪物的集合。每次读入一个新怪物，要么用目前剩余的时间击杀它，要么用堆中最劣的元素替代它，要么放弃它。按顺序决策即可。 G： 题意： 题解： H： 题意： 题解： I： 题意：咕一会就补。 题解： J： 题意：给出一张简单无向图，由你给每条边决定一个[0,4]的边权，问使得最后每个点所有相邻边边权和模5为0的方案数有多少。 题解：对每个连通块分别考虑，对于一个连通块，答案为 5^(m-n+x)，其中x为是否有奇环（是二分图），或者是是否没有奇环，记不住了（。 证明等待无敌的乱搞大师cyb补上来。