2018-Sp37-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(20180911.jpg,500px)]]
== 流水账 ==
前面被G题被约翰一语道破指点迷津。之后一直在想F题，想了半天发现是个找结论，很快A了F，然后三个人讨论B，[[br]]
想好了我上机写，不太顺，加起来A掉花了90min，其中sort相等返回0，re了一发。之后卡K，D，和欧阳想了会K交给欧阳，[[br]]
然后帮约翰想了D的一个细节，其他时间在想J，发现是个傻逼题。D，K都过了之后写J。但是人更傻逼，写的丑陋，输出还有个细节写错了，[[br]]
之后约翰有信心rush C，交给约翰，过了C还剩150s，在结束的之后调试迅速找到了输出的错误，改了之后就过了。

== 总结 ==
=== lqybzx ===


=== Johann ===
这个C把偏序找到以后就很傻逼了。还好rush成功了。[[br]]
python写起来也太麻烦了。[[br]]
=== zx2018  ===
菜啊。[[br]]
== 题解 ==

K:f[i][j]表示前i个数有j个位置异或为1是否可行。另开两个vector分别记录1和0的位置，转移时枚举当前数用几个1去抵消1，几个1新增1。

因为每个位置只需要被转移一次，因此复杂度为n*len*len。转移的时候维护到当前位置的异或和以及前一个转移位置即可输出答案。

== 补题 ==
J：zx2018

E：lqybzx

口糊一个I 不知道对不对，先把所有的三角形按照坐标分成两类，少的一类是第二类。然后相邻的三角形连边。所有 [ 第二类+相邻2个度为1的第一类 ] 打包定成三元组。[[br]]
（不然之后跑二分图匹配也会多一个肯定要变三元组还要难看的余一个），之后跑二分图最大匹配，对于每一个匹配，看周围相邻的4个三角形，没有匹配的直接拉一个变成三元，[[br]]
这里不存在有三个或四个还没有匹配，不然最大匹配可以多1。两个的话，最开始的打包会有用，导致最后每个二元匹配拿一个周围的未匹配应该一定会拿满。[[br]]
无解当且仅当第一类个数>2*第二类个数。[[br]]

流水账

前面被G题被约翰一语道破指点迷津。之后一直在想F题，想了半天发现是个找结论，很快A了F，然后三个人讨论B，[[br]]

想好了我上机写，不太顺，加起来A掉花了90min，其中sort相等返回0，re了一发。之后卡K，D，和欧阳想了会K交给欧阳，[[br]]

然后帮约翰想了D的一个细节，其他时间在想J，发现是个傻逼题。D，K都过了之后写J。但是人更傻逼，写的丑陋，输出还有个细节写错了，[[br]]

之后约翰有信心rush C，交给约翰，过了C还剩150s，在结束的之后调试迅速找到了输出的错误，改了之后就过了。

总结

lqybzx

Johann

这个C把偏序找到以后就很傻逼了。还好rush成功了。[[br]]

python写起来也太麻烦了。[[br]]

zx2018

菜啊。[[br]]

题解

K:f[i][j]表示前i个数有j个位置异或为1是否可行。另开两个vector分别记录1和0的位置，转移时枚举当前数用几个1去抵消1，几个1新增1。

因为每个位置只需要被转移一次，因此复杂度为n*len*len。转移的时候维护到当前位置的异或和以及前一个转移位置即可输出答案。

补题

J：zx2018

E：lqybzx

口糊一个I 不知道对不对，先把所有的三角形按照坐标分成两类，少的一类是第二类。然后相邻的三角形连边。所有 [ 第二类+相邻2个度为1的第一类 ] 打包定成三元组。[[br]]

（不然之后跑二分图匹配也会多一个肯定要变三元组还要难看的余一个），之后跑二分图最大匹配，对于每一个匹配，看周围相邻的4个三角形，没有匹配的直接拉一个变成三元，[[br]]

这里不存在有三个或四个还没有匹配，不然最大匹配可以多1。两个的话，最开始的打包会有用，导致最后每个二元匹配拿一个周围的未匹配应该一定会拿满。[[br]]

无解当且仅当第一类个数>2*第二类个数。[[br]]

附加文件