2020-team1-035

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 6/12  dirt: 33%
rank: 71
[[Image(Rank.png,800px)]]

== 流水账 ==
前期签完到就开始卡题，Emmy开场就冲了A，他一直担心min_25会T，Grammy觉得不可能T，然后他冲了一发TLE，表示这题是某国外算法，但是他没带板子（不久后py到了Tony的板子）。E的题意没注意到一个很重要的限制，H的题意以为是在端点不相交也不会做。中期三人卡三题，结果中间很长一段时间机位上没有人，到了还有一个半小时的时候，几个题意的问题都解决了，同时还开出了其他题，手上握着很多很多题，但是机时显然是写不完了，Grammy先上去把H写了，然后Emmy上去写F，本来觉得至少还能冲一题，但是Emmy wa了，然后就没有然后了。
== 总结 ==
555，看错3个题有点毒瘤, 机时利用严重不足
Grammy: 状态有点迷，感觉有点整场梦游的感觉。中期机时浪费的太严重了，三个人卡三道题，而且中期卡的很多题题意都读错了。赛后测了一下C和E需要的时间，似乎挺少的。
Sakuya: 要不是赛后oscar造了组数据把我叉了我就绝望得不想改这道题了555。还是要提高我自己的代码能力，毕竟我嘴出来的题不会有人帮我写。
== 题解 ==
A: 对所有质数p(3<=p<=n/2)，把p的倍数互相配对，如有多余留一个2p；再把多余的这些和2拿出来互相配对，此时最多剩一个2。然后推式子，筛区间质数个数。
B: FWT
C: ci-=d*i，分组，每组中贡献中位数，逆序则合并
D: 
E: 圆不交，转化为竖直线段问题，扫描线+线段树
F: dp算出每种逆序对数时只用前两个操作的答案，枚举k使得操作数>k的时候不断用第三个操作直到剩余操作数<k，然后解方程。分数类会被卡T
G: 随便连，相交则交换
H: 区间dp
I: 每次把前一半翻转到后面，判一下大小关系，不行就-1再翻转。注意特判10的幂（10->9+1,100->090->99,1000->0990->999）
J: 搞一搞连通性，想法是优化建图，连一连然后求强连通分量，待验证
K: 容斥+插头dp，每次塞入一个1*2或2*1，其余视为空格，1*2可以直接转移，2*1用一个向下的插头
L: 排序取前一段之和与最后一个的最大值

[/wiki/2020-team1 返回]

概述

solved: 6/12 dirt: 33%

rank: 71

流水账

前期签完到就开始卡题，Emmy开场就冲了A，他一直担心min_25会T，Grammy觉得不可能T，然后他冲了一发TLE，表示这题是某国外算法，但是他没带板子（不久后py到了Tony的板子）。E的题意没注意到一个很重要的限制，H的题意以为是在端点不相交也不会做。中期三人卡三题，结果中间很长一段时间机位上没有人，到了还有一个半小时的时候，几个题意的问题都解决了，同时还开出了其他题，手上握着很多很多题，但是机时显然是写不完了，Grammy先上去把H写了，然后Emmy上去写F，本来觉得至少还能冲一题，但是Emmy wa了，然后就没有然后了。

总结

555，看错3个题有点毒瘤, 机时利用严重不足

Grammy: 状态有点迷，感觉有点整场梦游的感觉。中期机时浪费的太严重了，三个人卡三道题，而且中期卡的很多题题意都读错了。赛后测了一下C和E需要的时间，似乎挺少的。

Sakuya: 要不是赛后oscar造了组数据把我叉了我就绝望得不想改这道题了555。还是要提高我自己的代码能力，毕竟我嘴出来的题不会有人帮我写。

题解

A: 对所有质数p(3<=p<=n/2)，把p的倍数互相配对，如有多余留一个2p；再把多余的这些和2拿出来互相配对，此时最多剩一个2。然后推式子，筛区间质数个数。

B: FWT

C: ci-=d*i，分组，每组中贡献中位数，逆序则合并

D:

E: 圆不交，转化为竖直线段问题，扫描线+线段树

F: dp算出每种逆序对数时只用前两个操作的答案，枚举k使得操作数>k的时候不断用第三个操作直到剩余操作数

G: 随便连，相交则交换

H: 区间dp

I: 每次把前一半翻转到后面，判一下大小关系，不行就-1再翻转。注意特判10的幂（10->9+1,100->090->99,1000->0990->999）

J: 搞一搞连通性，想法是优化建图，连一连然后求强连通分量，待验证

K: 容斥+插头dp，每次塞入一个1*2或2*1，其余视为空格，1*2可以直接转移，2*1用一个向下的插头

L: 排序取前一段之和与最后一个的最大值

附加文件