2020-team12-C04

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

== Ranklist ==

[[Image(2020-C07.png,800px)]]

== Submisson ==

[[Image(2020-C04submission.png)]]

== 概述 ==

solved: 11/12  dirt: 90.9%

rank: 7



==  ==

== 总结 ==


== 题解 ==

A: 水题，从左往右贪心能选就选，时间O(n) 

B: 水题，快速处理方案，因为只有2018和2020而且保证不出现其他，考虑数字1很特殊就是竖的直线而且只出现在2018里，判有无2018，时间O(n^2)

C：考虑到向下的操作实质是做异或运算。那么考虑第一行数对答案的贡献，其实第一行的数在答案里异或了C(i-1,n-1)次，那么偶数次无贡献，
奇数次的位置上如果无“？”，直接判断答案是否合法，记“？”个数为num，若奇数位上有“？”，
答案就是2^(num-1)^，无问号且合法，答案是2^(num-1)^。

D：需要对每个字符串求循环节然后看哪些字符串循环节相同。犯了三个错误：①不需要注意整个串是什么只需要求循环节②KMP求出的循环节在最后可能是不满的所以要特判③不要使用单哈希！！


E：

F：

G：

H：

I：水题，仔细阅读题面后发现y相同，直接拿最上面的两个线段构成的四边形的对角线在最小y的线段所在的直线截两个点，判断这两个点的线段与最小y的线段有无交点

J：考虑到如果已知最小生成树的边组合，那么权值是Σa+x*Σb,这是个线性函数最值肯定是在两端取到，那我们直接拿x=l与x=r分别做一遍最小生成树取小即可。

K：线代数学题，首先了解矩阵树定理和基尔霍夫矩阵，然后对于构造出的矩阵，我们去掉最后一行最后一列，所有行加到第一行，第一行会变为全1，发现每次最后一行一定是前面全0后面一个度数，
或是前面全-1后面一个度数，那么全-1的就加上第一行。按最后一行展开，一直到第一行0。

[/wiki/2020-team12 返回]

Ranklist

Submisson

概述

solved: 11/12 dirt: 90.9%

rank: 7

总结

题解

A: 水题，从左往右贪心能选就选，时间O(n)

B: 水题，快速处理方案，因为只有2018和2020而且保证不出现其他，考虑数字1很特殊就是竖的直线而且只出现在2018里，判有无2018，时间O(n^2)

C：考虑到向下的操作实质是做异或运算。那么考虑第一行数对答案的贡献，其实第一行的数在答案里异或了C(i-1,n-1)次，那么偶数次无贡献，

奇数次的位置上如果无“？”，直接判断答案是否合法，记“？”个数为num，若奇数位上有“？”，

答案就是2(num-1)，无问号且合法，答案是2(num-1)。

D：需要对每个字符串求循环节然后看哪些字符串循环节相同。犯了三个错误：①不需要注意整个串是什么只需要求循环节②KMP求出的循环节在最后可能是不满的所以要特判③不要使用单哈希！！

E：

F：

G：

H：

I：水题，仔细阅读题面后发现y相同，直接拿最上面的两个线段构成的四边形的对角线在最小y的线段所在的直线截两个点，判断这两个点的线段与最小y的线段有无交点

J：考虑到如果已知最小生成树的边组合，那么权值是Σa+x*Σb,这是个线性函数最值肯定是在两端取到，那我们直接拿x=l与x=r分别做一遍最小生成树取小即可。

K：线代数学题，首先了解矩阵树定理和基尔霍夫矩阵，然后对于构造出的矩阵，我们去掉最后一行最后一列，所有行加到第一行，第一行会变为全1，发现每次最后一行一定是前面全0后面一个度数，

或是前面全-1后面一个度数，那么全-1的就加上第一行。按最后一行展开，一直到第一行0。

附加文件