2020-team1-C020

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 6/12  dirt: 40%
rank: 18
[[Image(Rank.png,800px)]]
== 总结 ==
Grammy： 
这场的题意很shit被搞了
我的问题主要是中期搞出一个自以为正确的I的做法，wa了过了一段时间才发现他是假的，浪费了很多时间在I上面，之后去做G，被shit题面搞了，理解错了输入的方向向量的格式，给出的是点，需要和起点做差才是方向向量，我理解的题意是直接给出了方向向量，最搞的是错误的理解样例的答案是一样的，于是就对着一份正确的代码卡了半个多小时。这两件事情导致我没有时间去看E和H，事后发现这两个都是非常签到的题。
Oscar: 
开场写了个B，中间想了个F丢给Grammy，后期把L的子问题丢给Grammy被丢了回来，想了一下会了，写了个L。想了个J，没看见连通的条件。看了下Grammy的G，发现对的1b，看了眼读入，改了个读入方式给过了。
lwn_16:
感觉D只能说出的差强人意吧，也没有特别干净的过掉，前期还是占了不少机时的。检查时居然才发现上机之前提醒要加的一种情况忘加了
怎么sblwn才出了一道题，补这个H也补了一整晚
== 题解 ==
A: 求个相对速度，两个东西投影一下，判凸包是否有交，可以用半平面交或者闵可夫斯基和
B: sort一下，模拟
C: 推一下柿子是个调和级数相关的东西，用欧拉公式近似，近似那个常数c可以用打表算1e9时候的c。
D: 特判A=0；然后试图一直random原根g,令n=g(mod p),n=log(a-g^m^)(mod(p-1)),random100次不出结果就NO
E: dp算出K=1下横着的和竖着的两种牌中，K=0的横竖占比的期望，然后矩乘算出order=K下横竖牌中K=0的横竖占比期望，然后在dp一下这个矩形用的order=K的横竖牌的期望。 dp部分就直接n^2*2^n轮廓线dp
F: 
G: 求个凸包，给直线上点排序，双指针扫
H: 用DP算出要矩阵乘法的式子，然后矩乘
I: 
J: 转换成奇数度数点之间的一般图最大权匹配，可以抄板子或者记忆化搜索
K: 
L: 首先猜想只有一个矩阵真正对最终答案有贡献。
两个矩形如果是相同的行区间，交换位置后加起来总贡献为0，相同的列区间同理。如果可以找到两个这样的区间则直接输出0。
如果两个矩形所在行区间有一个端点相同，则由于上面的结论，可以把较长的区间缩短至两个区间没有交，列区间仍然同理。
由于不断进行这个操作后行区间左右端点都互不相同，所以每个矩形最终一定是1x1，可以直接数逆序对。
这个过程可以把区间右端点排序，用并查集维护当前左端点对应的区间可以延伸到什么位置，求出当前区间应该缩到什么地方。对行列各做一次即可。

[/wiki/2020-team1 返回]

概述

solved: 6/12 dirt: 40%

rank: 18

总结

Grammy：

这场的题意很shit被搞了

我的问题主要是中期搞出一个自以为正确的I的做法，wa了过了一段时间才发现他是假的，浪费了很多时间在I上面，之后去做G，被shit题面搞了，理解错了输入的方向向量的格式，给出的是点，需要和起点做差才是方向向量，我理解的题意是直接给出了方向向量，最搞的是错误的理解样例的答案是一样的，于是就对着一份正确的代码卡了半个多小时。这两件事情导致我没有时间去看E和H，事后发现这两个都是非常签到的题。

Oscar:

开场写了个B，中间想了个F丢给Grammy，后期把L的子问题丢给Grammy被丢了回来，想了一下会了，写了个L。想了个J，没看见连通的条件。看了下Grammy的G，发现对的1b，看了眼读入，改了个读入方式给过了。

lwn_16:

感觉D只能说出的差强人意吧，也没有特别干净的过掉，前期还是占了不少机时的。检查时居然才发现上机之前提醒要加的一种情况忘加了

怎么sblwn才出了一道题，补这个H也补了一整晚

题解

A: 求个相对速度，两个东西投影一下，判凸包是否有交，可以用半平面交或者闵可夫斯基和

B: sort一下，模拟

C: 推一下柿子是个调和级数相关的东西，用欧拉公式近似，近似那个常数c可以用打表算1e9时候的c。

D: 特判A=0；然后试图一直random原根g,令n=g(mod p),n=log(a-gm)(mod(p-1)),random100次不出结果就NO

E: dp算出K=1下横着的和竖着的两种牌中，K=0的横竖占比的期望，然后矩乘算出order=K下横竖牌中K=0的横竖占比期望，然后在dp一下这个矩形用的order=K的横竖牌的期望。 dp部分就直接n2*2n轮廓线dp

F:

G: 求个凸包，给直线上点排序，双指针扫

H: 用DP算出要矩阵乘法的式子，然后矩乘

I:

J: 转换成奇数度数点之间的一般图最大权匹配，可以抄板子或者记忆化搜索

K:

L: 首先猜想只有一个矩阵真正对最终答案有贡献。

两个矩形如果是相同的行区间，交换位置后加起来总贡献为0，相同的列区间同理。如果可以找到两个这样的区间则直接输出0。

如果两个矩形所在行区间有一个端点相同，则由于上面的结论，可以把较长的区间缩短至两个区间没有交，列区间仍然同理。

由于不断进行这个操作后行区间左右端点都互不相同，所以每个矩形最终一定是1x1，可以直接数逆序对。

这个过程可以把区间右端点排序，用并查集维护当前左端点对应的区间可以延伸到什么位置，求出当前区间应该缩到什么地方。对行列各做一次即可。

附加文件