2019-team666-0009

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

八月集训第2场

rank:校内24/25 总115/256

== 流水账 ==

开场签到hyw '''A1y16''',yyc '''E1y24'''. 然后开始看榜读题，这时榜上过的人多的是F，看，卡。hyw开始在纸上推式子，yyc提出可以随机化一下取中位数，T了，调了几次参，继续T。yyc调参的时候hyw读B，等yyc调完的时候跟yyc说了一下题意，卡。yyc看J，没看懂题意，于是hyw看J，yyc想B，hyw也没完全弄懂J的题意，开始研究样例并尝试建模。两人各自卡了约40分钟，hyw提出先把所有题看一遍。很快hyw一眼看出G是个之前做过的费用流，跟yyc说了一下，可是两人都不会输出方案，弃。这时剩下的题里H过的最多，两人想H并讨论，发现怎么优化都是O(n^3^q)，开bitset感觉也不是很够，弃。这时两人都比较自闭，yyc提出去调一调F的参，hyw继续想B，很快调参的过程中yyc发现了F的一个神奇的规律，随便交了一发竟然过了，'''F8y219'''. 之后yyc想出了J的构造方法，'''J1y248'''. 这时hyw检查了一遍B的题意，发现读了假题，上机，'''B1y273'''. 最后半小时yyc上机莽一发H题O(n^3^q/64)的做法，hyw想出K但来不及了，H写完网页卡了没交上去（后来Wa on 2）。

== 总结 ==

=== yyc ===

卡题...难受...

这F咋回事啊？黑人问号.jpg

=== tjc  ===


=== hyw  ===

今天主要演了个B题，之所以发现读题错误很晚是因为一开始在想贪心+暴搜剪枝，后来在想状压dp，觉得复杂度无比正确，然而转移需要性质，推了半天没推出来，上厕所的时候突然意识到可能读错题，结果回去看真的读错了qwq

J题是个构造，卡了很久是因为看了题以后直觉这个构造一定是基于某个图论模型的，于是一直考虑建模，事实证明想复杂了，其实有简单而巧妙的构造方法。

cjb说H虽然复杂度有点危险不过很多人都过了而且都一发过了所以就写了，感觉这个经验非常的靠谱，事实证明那个复杂度是能跑过去的

还有K题，是时候复习一下线代了

封榜后一小时可以考虑2+1. 平时训练可以参考实力相近的队过的题。

希望明天打真赛。

=== 题解 ===

A: 直接递归做就行了

B：dfs暴搜

C：dp(*留坑*)

D：

E：签到

F：l*n/m即可，证明不会，数学意义是期望

G：最小费用流，费用用向量组表示

H：bitset暴力搞

I：

J：从起始位置开始，以后每次都只能从之前的下面走

K：枚举第一个基，用它第一个不为0的那一维去消其他所有的向量，然后剩下向量单位化，统计等价类，取最大值，注意特判零向量是属于任何等价类的。

[/wiki/2019-team666 返回]

概述

八月集训第2场

rank:校内24/25 总115/256

流水账

开场签到hyw A1y16,yyc E1y24. 然后开始看榜读题，这时榜上过的人多的是F，看，卡。hyw开始在纸上推式子，yyc提出可以随机化一下取中位数，T了，调了几次参，继续T。yyc调参的时候hyw读B，等yyc调完的时候跟yyc说了一下题意，卡。yyc看J，没看懂题意，于是hyw看J，yyc想B，hyw也没完全弄懂J的题意，开始研究样例并尝试建模。两人各自卡了约40分钟，hyw提出先把所有题看一遍。很快hyw一眼看出G是个之前做过的费用流，跟yyc说了一下，可是两人都不会输出方案，弃。这时剩下的题里H过的最多，两人想H并讨论，发现怎么优化都是O(n³q)，开bitset感觉也不是很够，弃。这时两人都比较自闭，yyc提出去调一调F的参，hyw继续想B，很快调参的过程中yyc发现了F的一个神奇的规律，随便交了一发竟然过了，F8y219. 之后yyc想出了J的构造方法，J1y248. 这时hyw检查了一遍B的题意，发现读了假题，上机，B1y273. 最后半小时yyc上机莽一发H题O(n³q/64)的做法，hyw想出K但来不及了，H写完网页卡了没交上去（后来Wa on 2）。

总结

yyc

卡题...难受...

这F咋回事啊？黑人问号.jpg

tjc

hyw

今天主要演了个B题，之所以发现读题错误很晚是因为一开始在想贪心+暴搜剪枝，后来在想状压dp，觉得复杂度无比正确，然而转移需要性质，推了半天没推出来，上厕所的时候突然意识到可能读错题，结果回去看真的读错了qwq

J题是个构造，卡了很久是因为看了题以后直觉这个构造一定是基于某个图论模型的，于是一直考虑建模，事实证明想复杂了，其实有简单而巧妙的构造方法。

cjb说H虽然复杂度有点危险不过很多人都过了而且都一发过了所以就写了，感觉这个经验非常的靠谱，事实证明那个复杂度是能跑过去的

还有K题，是时候复习一下线代了

封榜后一小时可以考虑2+1. 平时训练可以参考实力相近的队过的题。

希望明天打真赛。

题解

A: 直接递归做就行了

B：dfs暴搜

C：dp(*留坑*)

D：

E：签到

F：l*n/m即可，证明不会，数学意义是期望

G：最小费用流，费用用向量组表示

H：bitset暴力搞

I：

J：从起始位置开始，以后每次都只能从之前的下面走

K：枚举第一个基，用它第一个不为0的那一维去消其他所有的向量，然后剩下向量单位化，统计等价类，取最大值，注意特判零向量是属于任何等价类的。