2019-team154-011

从 Trac 迁移的文章

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

原文章内容如下：

== 概述 ==
八月集训第三场
== 总结 ==
== dafu456 ==
选题的故事：今天opentrains挂了，所以比的2011年Warsaw U的题。正如CJB所说，每个队伍差不多都少了一个小时。然而很亏的是，我们少了一个多小时，还是在最开始的时候少的。扫描完题面，发现没有一个平常所说的“签到题”。每一个题，都需要花时间搞（或者搞不出来）。peh开到I题，发现是一个构成三角形的题，这与7月集训我的那道乱搞题有相似之处，但似乎不对。我们一开始提出了假做法，还想了半天，最后发现不对。终于在开场1h20min左右的时候，peh想出了一个乱搞的做法然后就过了。E题树形dp，把题意转述给dzf，他很自信地开始做啦！WA第一发，发现没开long long，WA第二发，发现开的是ULL而题目要输出-1。。。然后我用乱搞做法过G，发现最终做法和zqq一样诶！我们还准备了ABF。对于A题打了表而且找了很久的规律，终于我们发现了对角线上的规律，但是下面一个三角形的规律处于“空”的状态，直到比赛结束才知道原来大家都找了规律，而做法跟找规律并没有关系。B题，dzf很快想出来网络流的建边方法，然而近百万级别的边数，边太多估计跑不过去，也没想到优化方法。但是乌鸦队用cyw费用流就这样过掉了？？？F，整体二分，思路有，稍微难写一点，最后惊险过掉。
遗憾的是，D没开出来。
这套题反映的问题：我好菜。
=== dzf ===
E题就记个子树的size。先爆了int，贪了一下用ULL，却忘记了前面的初始化为-1了。而且没调一次样例，直接踩了《碎碎念》的两个雷~.~。'''用ULL之前应该想想为什么不是LL'''
I题签到题集体shabi，若非乱搞做法是正解的超集，两个小时都不够耗的。实际上用枚举-贪心的思路走一走就好了。
B题我shabi了，想到最小费用最大费用流去了。其实对每段时间贪最大匹配就好。增广成功则题目-1，匹配失败则人员-1，故时间复杂度正确。
F题计划打了个主席树后交给pnh打整体二分。但是'''对主席树不熟'''，实属锅了，还忘记了struct数组的空间问题，对着个360MB的数组注释“90MB”，大言不惭！厚颜无耻！还写了pushDown！该打。最后还要'''把longlong调回int换空间'''。
D题，我想也锅了，前期没读（读了一段），长时间泡着AB。中途是知道要读D的，但心态是“赶紧弄出A之后再读D”，一直拖着。结果过D的队伍数量更多。'''在小卡题恶化成大卡题之前就应该读新一题，以保证掌握更多信息'''
A题，'''被看似很有规律的表迷惑住了，其实应该从公式下手'''

概述

八月集训第三场

总结

dafu456

选题的故事：今天opentrains挂了，所以比的2011年Warsaw U的题。正如CJB所说，每个队伍差不多都少了一个小时。然而很亏的是，我们少了一个多小时，还是在最开始的时候少的。扫描完题面，发现没有一个平常所说的“签到题”。每一个题，都需要花时间搞（或者搞不出来）。peh开到I题，发现是一个构成三角形的题，这与7月集训我的那道乱搞题有相似之处，但似乎不对。我们一开始提出了假做法，还想了半天，最后发现不对。终于在开场1h20min左右的时候，peh想出了一个乱搞的做法然后就过了。E题树形dp，把题意转述给dzf，他很自信地开始做啦！WA第一发，发现没开long long，WA第二发，发现开的是ULL而题目要输出-1。。。然后我用乱搞做法过G，发现最终做法和zqq一样诶！我们还准备了ABF。对于A题打了表而且找了很久的规律，终于我们发现了对角线上的规律，但是下面一个三角形的规律处于“空”的状态，直到比赛结束才知道原来大家都找了规律，而做法跟找规律并没有关系。B题，dzf很快想出来网络流的建边方法，然而近百万级别的边数，边太多估计跑不过去，也没想到优化方法。但是乌鸦队用cyw费用流就这样过掉了？？？F，整体二分，思路有，稍微难写一点，最后惊险过掉。

遗憾的是，D没开出来。

这套题反映的问题：我好菜。

dzf

E题就记个子树的size。先爆了int，贪了一下用ULL，却忘记了前面的初始化为-1了。而且没调一次样例，直接踩了《碎碎念》的两个雷~.~。用ULL之前应该想想为什么不是LL

I题签到题集体shabi，若非乱搞做法是正解的超集，两个小时都不够耗的。实际上用枚举-贪心的思路走一走就好了。

B题我shabi了，想到最小费用最大费用流去了。其实对每段时间贪最大匹配就好。增广成功则题目-1，匹配失败则人员-1，故时间复杂度正确。

F题计划打了个主席树后交给pnh打整体二分。但是对主席树不熟，实属锅了，还忘记了struct数组的空间问题，对着个360MB的数组注释“90MB”，大言不惭！厚颜无耻！还写了pushDown！该打。最后还要把longlong调回int换空间。

D题，我想也锅了，前期没读（读了一段），长时间泡着AB。中途是知道要读D的，但心态是“赶紧弄出A之后再读D”，一直拖着。结果过D的队伍数量更多。在小卡题恶化成大卡题之前就应该读新一题，以保证掌握更多信息

A题，被看似很有规律的表迷惑住了，其实应该从公式下手