ICPC2020济南站

话说线上赛有啥游记好写的…但是作为惯例还是写一个.

Day -inf

没训练, 从CCPC长春之后就没训练过了, 结果文化课也没卷好, 属实爪巴.

Day 0

晚上去机房打热身赛, 2020题竟然贡献了n发罚时, 最后由队友过了, 奠定了第二天零贡献的基础. 使用大屏幕感觉很屌, 分屏之后看得仍然很舒服.

Day 1

9:30-10:00身份验证, 我9:35左右才起床, 差点没了. 不过有我没我似乎也没有差很多 (

11:00开赛, 我发现D很简单却没人做, 我开始想. WA了两发. 以为结论错了, 后来发现结论又对了. 这. . . 其实是代码出锅了. 思路就是首先看每个人卷最多字数的情况下, 有一个序. 我们要求新的方案仍然满足这个序, 并且相同$R_i$对应的人卷的字数一样多且尽可能少 (如果卷的字数不一样多就会有人变差, 所以相同Ri的人在新计划下仍应卷相同字数) . 所以只需要对每个$R_i$统计这些人中最大的$L_i$, 然后按$R_i$从小到大遍历, 注意$L_{i}<L_{i-1}$时不能取$L_i$, 需要取$L_{i-1}$. 答案一定要保持$R_i$的那个序. 就可以了.

队友签了另外三个到, 没细看. 四题之后就开始罚坐.

队友想了J, 想了假做法, 就是对树分层, 每层全使用相同的数, 只需要构造链, 使相邻两个异或起来全1, 并且不相邻的异或起来不全1. 我构造出来了, 还交了一发. 才发现算法假了. 因为这样会让每相邻的两层都变成一个二部团的样子, 就是每对相邻层的点之间都会连边, 比树中的边要多. 于是gg. 我开始想A, 队友接着想J.

对着A题N=4的样例开始列方程. C中有16个元素, 每个元素左边等于右边, 有16个方程. 我发现对$C_{i,j}$列的方程中, $j$相同的, 也就是同一列的元素列出的方程中, 只包含这一列的$C_{i,j}$, 并且由其他列元素列的方程中不包含这一列的元素. 也就是这4个方程作为一组可以单独拿出来解. 解的时候可能会出现自由变元. 把四列对应的四组方程都解一遍, 若自由变元共有$k$个, 那么答案是$2^k\%998244353$. 感觉挺真的. 要写出每一组方程组, 例如第一列元素对应的方程组, 只需要将A中对角线元素与B中第一列元素对应相加 (模2加法其实是异或) . 即$A_{i,i}$换成$A_{i,i}\land B_{i,1}$. 然后求秩就好了, 不知道哪里写错了, 挂掉了. 最后也没调出来. 最后5min队友过了L, 好像保住了铜牌 (

赛后大家说A是线性基, 也没听太懂. . . 最重要的是, 看了一下午屏幕+玄学调试属实头晕, 直到8:00睡了一觉才缓过来. 裂开来.

假期要加强训练. . . 最近太摸鱼了. 等一波题解, 补一下A和J. E似乎也可以补.