2019-team666-0010
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2019-team666 返回]
== 概述 ==
八月集训第3场
rank:校内25/26
== 流水账 ==
开场连着看了五六题都没有什么思路。第一个讨论的是C，讨论出做法后yyc上去写，T了。期间hyw给出I的做法，Wa了，hyw很快想到反例，发现这个做法假了。期间yyc提出E找个重心就好了，并给出了I的做法，于是'''I4y121'''（前面挂了几次文件输入），'''E4y150'''。写I的时候yyc说G可以随机化，写E的时候hyw说B是个很明显的费用流，给出了建图方法，喊yyc上去写，并且说F可以二分+主席树，这样我们手里有四个题，yyc写B，自己开始查yyc的C。B题后来T了，这时hyw觉得F可能来不及写，G可以放到最后莽一发，BC把握大一点，于是两人轮流上机调B和C。最后两题都没调出来，期间G写了一次随机化Wa了，F没来得及写。
== 总结 == （泥萌倒是写总结鸭）
=== yyc ===
泥萌为什么都做过原题...做题太犹豫了，应该及时把卡在毒瘤题上的队友拉出来的...
=== tjc ===
（被台风吹跑了）
=== hyw ===
tjc说前期签到一些题不能想复杂，确实是这样……这场的话其实D,G,E,I都有简单做法。后期保B和C题，是因为我确信B除了费用流没有别的做法，后来知道可以网络流/匈牙利，算是积累了点经验，特别是动态加边的技巧。
UPD1.后来B题：EK Tle 16, 用cyw的Dij费用流似乎没卡过去, Tle 16, 我瞎几把优化了一下Tle on 21。zkw费用流学了一下，Wa5。（照着zkw博客打的，没查出错在哪，洛谷上90分，留坑）。改成网络流可以过。
~~C题是个大细节题，这次卡在这题上吃了很大教训，这种题要不要放后期硬扛还是要考虑一下。~~
UPD2. 就是上次那个电阻题...几乎一毛一样（七月第三场的E）。罪过罪过。
F题可以整体二分，这方面要去补一下。我想的是二分+主席树，没写是当时我和yyc都比较怂，主席树以前写的比较少，以后还是要多写几次。
D和G题是没做过这样的题，一个是反着处理一个是考虑补图，要学会反向思维。
A和J当时因为手里已经有四个题就没开，A这个模型很有意思可以学习，J题感觉如果当时深入想了应该能想出来，思维深度还是不够。
=== 题解 ===
A：设选择的位置上下左右各有a,b,c,d个格子，每次可以使得其中一个数减小，就是nim游戏，转化成a xor b xor c xor d=0,a+c=n-1,b+d=m-1求方程有几组解，设dp[i][0/1][0/1]表示考虑到第i位，(a+c)和(b+d)分别有没有进位，且a xor c=b xor d的方案数，数位dp即可。
B：法一：直接费用流，dij费用流或许能过，zkw费用流听说能过，反正我都没过。法二：网络流，动态加边，先连好题到汇、人和题的边，然后每一次给源和人之间连一条边，跑最大流，最多跑t/r次，加起来统计答案。（77ms）
法三：依然是动态加边，每次给连边的时候，一个人只给他分配一道题，一道题只给分配一个人，在二分图上跑匈牙利，统计答案。（类似法二）
C：和上次的一道电阻题类似（七月第三场, Gym102059E），每次取一个度为2的点u，设两条边为u->v和u->w，若u->v和v->w没有被标记过就更新u的两端点，每次执行del(u,v),del(u,w),add(v,w)，并将v->w这条边标记为不在多边形上。
D：反着做，每次加边跑queue-optimized-bellman-ford就过了？
E：不是重心的点肯定是-1，否则就把各个点到它距离加起来就好了
F：
G：考虑补图，每个补图上的边把它的两个端点删掉，由于团大小大于2/3*n，删的边要么是团和非团之间的边，要么是非团点之间的边，所以这样删完团里的点一定大于n/3，任选n/3个输出即可
H：
I：先把所有木棒按长度排序，从小到大加入木棒，这样第i根就是最大的木棒，然后要从已经加入的里面找两根长度大于它，遍历所有颜色，加边的时候维护每种颜色目前最长的一根棒的长度，找两个和最大木棒颜色不同的颜色，把最大值加起来和最大的那根比较，合法输出，一直不合法则无解。
J：可以用min(siz[v],n-siz[v])*w算每条边的贡献，也可以直接做，见Runespoor的题解吧[/wiki/2019-team666 返回]
概述
八月集训第3场
rank:校内25/26
流水账
开场连着看了五六题都没有什么思路。第一个讨论的是C，讨论出做法后yyc上去写，T了。期间hyw给出I的做法，Wa了，hyw很快想到反例，发现这个做法假了。期间yyc提出E找个重心就好了，并给出了I的做法，于是I4y121（前面挂了几次文件输入），E4y150。写I的时候yyc说G可以随机化，写E的时候hyw说B是个很明显的费用流，给出了建图方法，喊yyc上去写，并且说F可以二分+主席树，这样我们手里有四个题，yyc写B，自己开始查yyc的C。B题后来T了，这时hyw觉得F可能来不及写，G可以放到最后莽一发，BC把握大一点，于是两人轮流上机调B和C。最后两题都没调出来，期间G写了一次随机化Wa了，F没来得及写。
== 总结 == （泥萌倒是写总结鸭）
yyc
泥萌为什么都做过原题...做题太犹豫了，应该及时把卡在毒瘤题上的队友拉出来的...
tjc
（被台风吹跑了）
hyw
tjc说前期签到一些题不能想复杂，确实是这样……这场的话其实D,G,E,I都有简单做法。后期保B和C题，是因为我确信B除了费用流没有别的做法，后来知道可以网络流/匈牙利，算是积累了点经验，特别是动态加边的技巧。
UPD1.后来B题：EK Tle 16, 用cyw的Dij费用流似乎没卡过去, Tle 16, 我瞎几把优化了一下Tle on 21。zkw费用流学了一下，Wa5。（照着zkw博客打的，没查出错在哪，洛谷上90分，留坑）。改成网络流可以过。
C题是个大细节题，这次卡在这题上吃了很大教训，这种题要不要放后期硬扛还是要考虑一下。
UPD2. 就是上次那个电阻题...几乎一毛一样（七月第三场的E）。罪过罪过。
F题可以整体二分，这方面要去补一下。我想的是二分+主席树，没写是当时我和yyc都比较怂，主席树以前写的比较少，以后还是要多写几次。
D和G题是没做过这样的题，一个是反着处理一个是考虑补图，要学会反向思维。
A和J当时因为手里已经有四个题就没开，A这个模型很有意思可以学习，J题感觉如果当时深入想了应该能想出来，思维深度还是不够。
题解
A：设选择的位置上下左右各有a,b,c,d个格子，每次可以使得其中一个数减小，就是nim游戏，转化成a xor b xor c xor d=0,a+c=n-1,b+d=m-1求方程有几组解，设dp[i][0/1][0/1]表示考虑到第i位，(a+c)和(b+d)分别有没有进位，且a xor c=b xor d的方案数，数位dp即可。
B：法一：直接费用流，dij费用流或许能过，zkw费用流听说能过，反正我都没过。法二：网络流，动态加边，先连好题到汇、人和题的边，然后每一次给源和人之间连一条边，跑最大流，最多跑t/r次，加起来统计答案。（77ms）
法三：依然是动态加边，每次给连边的时候，一个人只给他分配一道题，一道题只给分配一个人，在二分图上跑匈牙利，统计答案。（类似法二）
C：和上次的一道电阻题类似（七月第三场, Gym102059E），每次取一个度为2的点u，设两条边为u->v和u->w，若u->v和v->w没有被标记过就更新u的两端点，每次执行del(u,v),del(u,w),add(v,w)，并将v->w这条边标记为不在多边形上。
D：反着做，每次加边跑queue-optimized-bellman-ford就过了？
E：不是重心的点肯定是-1，否则就把各个点到它距离加起来就好了
F：
G：考虑补图，每个补图上的边把它的两个端点删掉，由于团大小大于2/3*n，删的边要么是团和非团之间的边，要么是非团点之间的边，所以这样删完团里的点一定大于n/3，任选n/3个输出即可
H：
I：先把所有木棒按长度排序，从小到大加入木棒，这样第i根就是最大的木棒，然后要从已经加入的里面找两根长度大于它，遍历所有颜色，加边的时候维护每种颜色目前最长的一根棒的长度，找两个和最大木棒颜色不同的颜色，把最大值加起来和最大的那根比较，合法输出，一直不合法则无解。
J：可以用min(siz[v],n-siz[v])*w算每条边的贡献，也可以直接做，见Runespoor的题解吧