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似乎也可以补。