2019-team666-0016

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

[[Image(Submissions.jpg,1000px)]]

== 流水账 ==

开场打印题耽误了几分钟，然后tjc签了L和I，'''L2y16''','''I1y20'''，三人yy了一波A的构造方法，'''A1y33'''。然后tjc开出D，'''D2y67'''，期间hyw给出了H、F的真做法和K的假做法，yyc给出了J的做法。yyc修正了一下hyw的H的做法后上机，'''H2y88'''，hyw上机写J的dp，一开始wa，在机上调了一段时间修正了算法，喜提Tle。这时tjc和yyc讨论出K和G的正解，tjc写K，'''K2y157'''，yyc写G，'''G1y199'''。hyw等到机位，思考了一下写F还是改J，最后选择写F，'''F1y237'''，这时tjc看出C是个欧拉回路，找了个板子就上机写了，'''C1y269'''。hyw试图写个Trie优化一下J的时间常数，最后Mle，没有调完。

== 总结 == 


=== yyc ===


=== tjc  ===

D分类讨论后应先冷静下来再写题，注意细节

K感觉见过这个套路

G想出性质后不会做，抱了yyc大腿

C欧拉回路一遍过好感动。。。

=== hyw  ===

是新学期的第一场训练！感觉打出了新学期的感觉呀！

感觉这场出了J题稍微卡了一卡以外，好多题都基本一遍过，wa的题也很快改完，这场应该是我们队打的最顺利的一场？

J题T的时候我挺自闭的，好在当时头脑清醒地选择了F，最后F一遍过，爽。现在看来如果一个题没有把握改对的话开有把握的新题是明智的。

全场我比较在意的是G题，队友想出dfs树维护连通性的做法，感觉还是挺巧妙的。

=== 题解 ===

A：原串1多新串填0,0多填1，一样多设原串第一个字符为b，则新串第一个字符为!b，其余字符为b。

B：

C：先缩小n，数的前n-1位向后n-1位连边，跑欧拉回路。

D：分类讨论：min(r,c)=1，min(r,c)=2，其他。

E：

F：贪心，假设A能做出n题，则把B的前n题用时从大到小排序，然后从大到小考虑每道题，如果当前题位置之后有之前扫到的题则跳过，否则尽可能的扎气球延长当前题的结束时间。最后判断B能否按时做出第n道题即可。

G：

H：先全填1，判断是否满足条件，不能则输出-1。然后从前往后贪心改，把所有限制条件在左端点标记一下，扫到一个点就把这个点开始的限制条件加进线段树，每把一个1改成-1相当于区间-2，用线段树维护区间最小值。

I：奇偶性。

J：状压+dp，设dpi,j表示处理到第i个串，子序列mask为j的最长长度。

K：随便找一棵生成树，然后从叶子往根贪心。

L：枚举答案，贪心判可行性。

[/wiki/2019-team666 返回]

概述

流水账

开场打印题耽误了几分钟，然后tjc签了L和I，L2y16,I1y20，三人yy了一波A的构造方法，A1y33。然后tjc开出D，D2y67，期间hyw给出了H、F的真做法和K的假做法，yyc给出了J的做法。yyc修正了一下hyw的H的做法后上机，H2y88，hyw上机写J的dp，一开始wa，在机上调了一段时间修正了算法，喜提Tle。这时tjc和yyc讨论出K和G的正解，tjc写K，K2y157，yyc写G，G1y199。hyw等到机位，思考了一下写F还是改J，最后选择写F，F1y237，这时tjc看出C是个欧拉回路，找了个板子就上机写了，C1y269。hyw试图写个Trie优化一下J的时间常数，最后Mle，没有调完。

总结

yyc

tjc

D分类讨论后应先冷静下来再写题，注意细节

K感觉见过这个套路

G想出性质后不会做，抱了yyc大腿

C欧拉回路一遍过好感动。。。

hyw

是新学期的第一场训练！感觉打出了新学期的感觉呀！

感觉这场出了J题稍微卡了一卡以外，好多题都基本一遍过，wa的题也很快改完，这场应该是我们队打的最顺利的一场？

J题T的时候我挺自闭的，好在当时头脑清醒地选择了F，最后F一遍过，爽。现在看来如果一个题没有把握改对的话开有把握的新题是明智的。

全场我比较在意的是G题，队友想出dfs树维护连通性的做法，感觉还是挺巧妙的。

题解

A：原串1多新串填0,0多填1，一样多设原串第一个字符为b，则新串第一个字符为!b，其余字符为b。

B：

C：先缩小n，数的前n-1位向后n-1位连边，跑欧拉回路。

D：分类讨论：min(r,c)=1，min(r,c)=2，其他。

E：

F：贪心，假设A能做出n题，则把B的前n题用时从大到小排序，然后从大到小考虑每道题，如果当前题位置之后有之前扫到的题则跳过，否则尽可能的扎气球延长当前题的结束时间。最后判断B能否按时做出第n道题即可。

G：

H：先全填1，判断是否满足条件，不能则输出-1。然后从前往后贪心改，把所有限制条件在左端点标记一下，扫到一个点就把这个点开始的限制条件加进线段树，每把一个1改成-1相当于区间-2，用线段树维护区间最小值。

I：奇偶性。

J：状压+dp，设dpi,j表示处理到第i个串，子序列mask为j的最长长度。

K：随便找一棵生成树，然后从叶子往根贪心。

L：枚举答案，贪心判可行性。

附加文件