2019-Sp044-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(3.png,700px)]]
[[Image(1.png,700px)]]
[[Image(2.png,700px)]]
[wiki:2019-team2 返回Runespoor]
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010231 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 今天状态很糟。今天读题和写题太慌了，有些浮躁。可能是因为很重视这次zju camp，有点打出像区域赛上的压力。
前期读题很惨。B和J一直没有读懂
我的G题自己手写__int128然而写错了。最后直接用__int128过了
后来我的K题写错了没有仔细检查代码，但是对算法不够自信，一直在修改算法，花了一个多小时。其实第一份有一个小错误没有发现，改了就过了
H题我看漏了条件，本来是非常简单的bitset。
这些最后导致lyk的C题没有时间调完了。
今天8个签到题。K有一点需要思考。C题比较难写。D题套路没有见过。I是一个很巧妙也非常难的几何构造题。
== 题解 ==
[wiki:2017-Sp261-team2 legilimens]
[https://www.cnblogs.com/clrs97/p/5944424.html claris]
* C ： 因为数据是随机的。可以暴搜。但是很容易TLE。'''暴搜的顺序要随机，不能排序！'''
更加稳定的做法是DP
* D ：压位暴力。但是可以分块优化。将26位分成前面21位和后面5位两部分。块内的转移可以预处理。复杂度O(2^26) , 块外转移是O(2 ^ 21 * 21) . 其实分成16 + 10位更加优秀。注意要先从小到大做一次，标记所有终态的超级也是终态，然后再从大到小做，只要能够转移到必败态就是必胜的。
* E ：我们写了生成函数。其实直接枚举两个质数，然后再枚举一次累加答案，ans=\sum f[i]f[n-i]。以为是单点求值，O(n)即可，不需要fft
* F ：对于精度问题可以取log再exp，也可以用eps判断。结论是：ans=⌊LM / N⌋ 。
* G ： 最大匹配，但是要求最大化的是字典序。这种模型可以把费用设置为1000^(10 - x)^, 费用流。直接用__int128即可
* K ： 三个两两线性无关的向量(a,b,c)要线性相关，当且仅当 b 对 a, c 对 a进行消元并归一化后相同。本来线性相关的一定可以都选。这里的消元指用a的第一个非零位去消b和c的对应位。
== 补题 ==
* C [lyk,zqq] 那个dp还是很好写的，统计三角形个数可以写n^4^暴力，我一个小时就写完，调完了
* D [zqq]
* I []
流水账
总结
zqq: 今天状态很糟。今天读题和写题太慌了，有些浮躁。可能是因为很重视这次zju camp，有点打出像区域赛上的压力。
前期读题很惨。B和J一直没有读懂
我的G题自己手写int128然而写错了。最后直接用int128过了
后来我的K题写错了没有仔细检查代码，但是对算法不够自信，一直在修改算法，花了一个多小时。其实第一份有一个小错误没有发现，改了就过了
H题我看漏了条件，本来是非常简单的bitset。
这些最后导致lyk的C题没有时间调完了。
今天8个签到题。K有一点需要思考。C题比较难写。D题套路没有见过。I是一个很巧妙也非常难的几何构造题。
题解
- C ： 因为数据是随机的。可以暴搜。但是很容易TLE。暴搜的顺序要随机，不能排序！
更加稳定的做法是DP
- D ：压位暴力。但是可以分块优化。将26位分成前面21位和后面5位两部分。块内的转移可以预处理。复杂度O(226) , 块外转移是O(2 21 * 21) . 其实分成16 + 10位更加优秀。注意要先从小到大做一次，标记所有终态的超级也是终态，然后再从大到小做，只要能够转移到必败态就是必胜的。
- E ：我们写了生成函数。其实直接枚举两个质数，然后再枚举一次累加答案，ans=\sum f[i]f[n-i]。以为是单点求值，O(n)即可，不需要fft
- F ：对于精度问题可以取log再exp，也可以用eps判断。结论是：ans=⌊LM / N⌋ 。
- G ： 最大匹配，但是要求最大化的是字典序。这种模型可以把费用设置为1000(10 - x), 费用流。直接用__int128即可
- K ： 三个两两线性无关的向量(a,b,c)要线性相关，当且仅当 b 对 a, c 对 a进行消元并归一化后相同。本来线性相关的一定可以都选。这里的消元指用a的第一个非零位去消b和c的对应位。
补题
- C [lyk,zqq] 那个dp还是很好写的，统计三角形个数可以写n4暴力，我一个小时就写完，调完了
- D [zqq]
- I []