2020-team12-025

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-W3standings.png, 1000px)]]

== 教训 ==

不要过于去赌玄学题。

== 题解 == 

A:签到

B:半平面交板子，我们的板子终于对一回了！

C:签到

D:树形DP，szb挂一发没考虑0点可能连上很多个节点。

E:读题题，whn读完以后szb想到了横坐标*2然后旋转下坐标就变成两个点满足y2>x2,y1>x1就在范围内，所以按x排序随便搞搞就可以了。

F:考虑从小到大排序是最多的情况，从大到小是最小的情况，然后每次交换头和尾可以加上<=1次满分，直接二分即可，ctc有些失误，一开始没有发现<的情况。

G:签到

H:（竟然可以化为）建分层图染色，细节较多，待补。

I:神奇的交互题，题解做法：从100到5e6以“合适的密度”选取k个candidate，比如100，100*1.01.100*1.01^2...，然后随机50次，算出“假设答案=candidate有多大的概率得到这个询问的结果”，50次以后选取最大概率。
随机和k都很玄学

J:签到

K:高精度+贪心，whn先后挂了“比数大小只比字典序不比长度”以及“做法未考虑连续退位”，算是失误。

L：奇妙构造。
先反转成n小的n*m矩阵，然后一种颜色光占一列，另外两种颜色分别从右上、右下开始向内绕螺旋。

这样就给每个点钦定了一个颜色，使得所有格四联通的点周围至少有一个和他的颜色不一样，然后对于2的那些点从他周围的那些不同色的取一个进来就可以了。

无解情况：只有一行时，格子<3且没有2， 或者连着的2数量大于等于3个是impossible.

注意写反转需要是 if(i<j(且保证n<m,否则是i>j)) swap..， 否则就会有反转两次负负得正或者只反转了一个正方形子矩阵的情况。



M：签到。

H题：

[[Image(sol.png, 1000px)]]

[/wiki/2020-team12 返回]

教训

不要过于去赌玄学题。

题解

A:签到

B:半平面交板子，我们的板子终于对一回了！

C:签到

D:树形DP，szb挂一发没考虑0点可能连上很多个节点。

E:读题题，whn读完以后szb想到了横坐标*2然后旋转下坐标就变成两个点满足y2>x2,y1>x1就在范围内，所以按x排序随便搞搞就可以了。

F:考虑从小到大排序是最多的情况，从大到小是最小的情况，然后每次交换头和尾可以加上<=1次满分，直接二分即可，ctc有些失误，一开始没有发现<的情况。

G:签到

H:（竟然可以化为）建分层图染色，细节较多，待补。

I:神奇的交互题，题解做法：从100到5e6以“合适的密度”选取k个candidate，比如100，100*1.01.100*1.01^2...，然后随机50次，算出“假设答案=candidate有多大的概率得到这个询问的结果”，50次以后选取最大概率。

随机和k都很玄学

J:签到

K:高精度+贪心，whn先后挂了“比数大小只比字典序不比长度”以及“做法未考虑连续退位”，算是失误。

L：奇妙构造。

先反转成n小的n*m矩阵，然后一种颜色光占一列，另外两种颜色分别从右上、右下开始向内绕螺旋。

这样就给每个点钦定了一个颜色，使得所有格四联通的点周围至少有一个和他的颜色不一样，然后对于2的那些点从他周围的那些不同色的取一个进来就可以了。

无解情况：只有一行时，格子<3且没有2， 或者连着的2数量大于等于3个是impossible.

注意写反转需要是 if(ij)) swap..， 否则就会有反转两次负负得正或者只反转了一个正方形子矩阵的情况。

M：签到。

H题：

附加文件