2020-team10-003

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team10 返回]

== Rank和提交情况 ==
[[Image(standing3.png,1000px)]] 

Solved: 4/12

== 流水账 ==

by fr

开场40min我才到。。。之前lxy先切了L，然后发现B也是签到于是跟我说了题意。我5分钟就推出(n&m)==m然后秒出了3^logn^的做法，然后去想子集卷积，想完了直接上机子去写结果样例没过。1.5h左右lzh到了跟我说只用做一次FWT，然后我改了之后还是过不去样例。这时候lxy想出了G然后上去切了，我继续想B，大概2h的时候样例过了，但是交上去WA on 1。同时lzh想出I，我下去换lzh上，静态调错（然而没发现错误）。2h30min我再次上去开始疯狂对拍，结果拍了N组数据都没错。期间还交了好几次WA。因为除了BGI这三道题以外其他题都只有1、2个队过，所以lxy和lzh在通览别的题目。大概3h多时我发现我的read没有返回值（但是本机竟然能返回正确的x）！！！然后补上，结果一发过了。但是现在并没有别的题可以上去写，于是就有了长达30min的空机。。。大概3h30min左右lxy和lzh定下来写H，但我对C有了一点类似于模拟费用流的贪心思路于是开始分头行动。3h50min左右lzh开始写H的（我也不知道为什么）特别长的区间DP，结果样例很久也没过，4h多的时候过了样例，交了一发WA on 2。换我开始写C，写了20min左右交了一发也WA on 2。然后我们就轮着看题改题，但是全都WA on 2。大概4h50min时我发现我的做法假了（没考虑“反悔”的情况）。但是剩10min显然改不了了。lzh继续调H，然而最后也没过去。。。最后就4题gg了，而且成为了AC题数相同罚时最长的队伍（因为B）


== 个人小结 ==

lzh：缺勤一个半小时，I 题没拍就交wa了一发，最后 H 写得太细不知道哪里锅了。。包括昨天训练也有一题会正解连wa不止，还要提高代码实现能力。

lxy：队友开始没来心情有点异常，贡献了全场唯一一个L的wa，后面人来齐刚好打完了g（也wa几遍呜呜呜），别的就还好，和队友完成了一些题的思路。战略上一些失误，我还把e不相交漏掉了，一并道歉。

fr：本场两大罪行：迟到40min，read没返回值！！！还有就是对FWT的理解还不够深刻（仅限与会打板子），以及构造贪心反例的能力较弱。最后1.5h没和队友站在一起做H而是单打独斗想C也是战略问题。

== 题解 ==
A:

B:组合数是奇数等价于(n&m)==m，因此使用子集卷积即可（fr）

C:首先排序，然后给每个数减d*(i-1)来去掉d的限制（注意如果减成负数要直接加到0），设f[i][j]为前i个点且最后一个点不大于j的最小代价，画图可知该DP每一行的状态都是一个斜率减小直到为0的折线。用堆维护断点即可。（fr）

D:

E:由于圆不相交，所以只需判断每个圆是否堵住通道即可。离线后用线段树+扫描线维护[px,py]的连通性（fr）

F:

G:我写了个栈维护，遇到与上一个点不同就弹出，画图磕发现不会相交（lxy）

H:区间dp板子（lzh）

I:贪心乱搞一下就可以了，注意特殊情况的特判（lzh）

J:

K: 

L:简单贪心（lxy）

[/wiki/2020-team10 返回]

Rank和提交情况

Solved: 4/12

流水账

by fr

开场40min我才到。。。之前lxy先切了L，然后发现B也是签到于是跟我说了题意。我5分钟就推出(n&m)==m然后秒出了3^logn的做法，然后去想子集卷积，想完了直接上机子去写结果样例没过。1.5h左右lzh到了跟我说只用做一次FWT，然后我改了之后还是过不去样例。这时候lxy想出了G然后上去切了，我继续想B，大概2h的时候样例过了，但是交上去WA on 1。同时lzh想出I，我下去换lzh上，静态调错（然而没发现错误）。2h30min我再次上去开始疯狂对拍，结果拍了N组数据都没错。期间还交了好几次WA。因为除了BGI这三道题以外其他题都只有1、2个队过，所以lxy和lzh在通览别的题目。大概3h多时我发现我的read没有返回值（但是本机竟然能返回正确的x）！！！然后补上，结果一发过了。但是现在并没有别的题可以上去写，于是就有了长达30min的空机。。。大概3h30min左右lxy和lzh定下来写H，但我对C有了一点类似于模拟费用流的贪心思路于是开始分头行动。3h50min左右lzh开始写H的（我也不知道为什么）特别长的区间DP，结果样例很久也没过，4h多的时候过了样例，交了一发WA on 2。换我开始写C，写了20min左右交了一发也WA on 2。然后我们就轮着看题改题，但是全都WA on 2。大概4h50min时我发现我的做法假了（没考虑“反悔”的情况）。但是剩10min显然改不了了。lzh继续调H，然而最后也没过去。。。最后就4题gg了，而且成为了AC题数相同罚时最长的队伍（因为B）

个人小结

lzh：缺勤一个半小时，I 题没拍就交wa了一发，最后 H 写得太细不知道哪里锅了。。包括昨天训练也有一题会正解连wa不止，还要提高代码实现能力。

lxy：队友开始没来心情有点异常，贡献了全场唯一一个L的wa，后面人来齐刚好打完了g（也wa几遍呜呜呜），别的就还好，和队友完成了一些题的思路。战略上一些失误，我还把e不相交漏掉了，一并道歉。

fr：本场两大罪行：迟到40min，read没返回值！！！还有就是对FWT的理解还不够深刻（仅限与会打板子），以及构造贪心反例的能力较弱。最后1.5h没和队友站在一起做H而是单打独斗想C也是战略问题。

题解

A:

B:组合数是奇数等价于(n&m)==m，因此使用子集卷积即可（fr）

C:首先排序，然后给每个数减d*(i-1)来去掉d的限制（注意如果减成负数要直接加到0），设f[i][j]为前i个点且最后一个点不大于j的最小代价，画图可知该DP每一行的状态都是一个斜率减小直到为0的折线。用堆维护断点即可。（fr）

D:

E:由于圆不相交，所以只需判断每个圆是否堵住通道即可。离线后用线段树+扫描线维护[px,py]的连通性（fr）

F:

G:我写了个栈维护，遇到与上一个点不同就弹出，画图磕发现不会相交（lxy）

H:区间dp板子（lzh）

I:贪心乱搞一下就可以了，注意特殊情况的特判（lzh）

J:

K:

L:简单贪心（lxy）

附加文件

• standing3.png by longxy