2019-team154-002

从 Trac 迁移的文章

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

原文章内容如下：

== 概述 ==

七月集训第二场

== 流水账 ==
=== dafu456 ===
我是演员，专打假赛。

（我打假赛不要紧，297过G就行了）

还有几个暴力题没时间做（手动无奈）。

=== dzf ===
开场花了点时间拍题目传给外网的詹哲远（当时还没刷出pdf），回过头来CD已经被一血，估计是签到题，决定在dafu写D时'''D1(13)'''我看C。想到最长路去了还翻了翻板子，才突然发现是层次图，跑一趟队列就好'''C1(32)'''。发现E被一血了，读了一下要求每条边被包含在MST中要删除的最少边，直觉认为是有关生成树的特殊结论，跳过了。詹哲远远程打H，我和dafu讨论了一下F认为只用一个人handle，又交换了下I的意见，都可做，最后我把FI塞进代码队列，dafu研究G，哲远静态DEBUG'''H2(79)'''然后扛起了E。写F的时候两次坐标变换错位了，调了一会'''F1(93)'''，写I发现漏了循环节只完整出现一次的情况，幸好准备数据有反映'''I1(149)'''，dafu开始写G，这是他的噩梦。G卡了一发，考虑到代码较复杂，而E题思路做法都成熟了，让哲远先E'''E1(209)'''。机器回到G，我口胡了一组数据，才发现输入极其恶心，dafu继续受罪。场上突发过K如喝水，我读了一下题尝试构造尽量短的线段，发现十字无解，倒转一下思路尝试构造尽量长的线段，最终发现要将线段分组贪心'''K1(237)'''。机器再次回到G，重构代码（虽然我也不熟悉这种题w_w），扫描法用了最暴力的分类讨论，ctrl-cv写代码法，很无脑简单，但是出bug风险大，于是路上加上了一堆assert弥补；最后找了一会“=”写成“==”的BUG，过了几组数据提交RE，这时詹哲远已经在场，提出删除assert，'''G4(297)'''。


=== A ===
对一颗树指定点权，其中点权大于零的可覆盖距离不大于点权的附近点。覆盖所有点，并使点权和最小。
=== B ===
4X4棋盘，两人轮流下黑白子，给出初态和末态特征求可能的最终局面数。
棋盘很小，直接暴力。
=== C ===
无向图找到一条最长路，路径要求节点度数严格递增。
按照度数对点排序，依次松弛。
=== D ===
对一个数反复操作：每个数位的平方求和。问最终能否变成1.
第一次操作后数的最大值很小，于是用set判循环。
=== E ===
无向图对每一条边求至少删掉多少条边后此边可以出现在MST上。
对每条边(u,v)只保留边权更小的边，考虑最少的删边使(u,v)不连通，即最小割。
=== F ===
给出一个迷宫的size和递归式的构造方法，求从起点走m步之后的坐标。
确认目标位置属于递归的哪个部分，递归之后做对应的坐标变换。
=== G ===
两条折线求围成的多边形数量和面积。
扫描一遍，将y轴方向的线段看做事件。分类讨论两条折线的y轴走势。
=== H ===

=== I ===
类似循环小数的尾循环，求数串的循环节p和开始循环位k，使k+p最小。
发现倒着做答案不变，直接套用kmp。留意循环节仅出现一次的情况。
=== J ===
判断一个无向图是否满足任意割出的两个点集（点数都是n/2）都有完美匹配。
霍尔婚配定理+乱搞？
=== K ===
给出一条链（仅有平行x轴、平行y轴走向），任意地更改每条线段的长度，使得链不自相交。
原边长无意义。令连续的同向线段分为一组（连续定义为不被反方向线段分隔），令最后一个元素尽量大，前面的元素为1。这样对于每一组走向都不会发生碰撞。
=== L ===
对p个有向图移动棋子，求p个图的棋子都到达终点时最小代价。代价包含边权、所停留点的点权。

概述

七月集训第二场

流水账

dafu456

我是演员，专打假赛。

（我打假赛不要紧，297过G就行了）

还有几个暴力题没时间做（手动无奈）。

dzf

开场花了点时间拍题目传给外网的詹哲远（当时还没刷出pdf），回过头来CD已经被一血，估计是签到题，决定在dafu写D时D1(13)我看C。想到最长路去了还翻了翻板子，才突然发现是层次图，跑一趟队列就好C1(32)。发现E被一血了，读了一下要求每条边被包含在MST中要删除的最少边，直觉认为是有关生成树的特殊结论，跳过了。詹哲远远程打H，我和dafu讨论了一下F认为只用一个人handle，又交换了下I的意见，都可做，最后我把FI塞进代码队列，dafu研究G，哲远静态DEBUGH2(79)然后扛起了E。写F的时候两次坐标变换错位了，调了一会F1(93)，写I发现漏了循环节只完整出现一次的情况，幸好准备数据有反映I1(149)，dafu开始写G，这是他的噩梦。G卡了一发，考虑到代码较复杂，而E题思路做法都成熟了，让哲远先EE1(209)。机器回到G，我口胡了一组数据，才发现输入极其恶心，dafu继续受罪。场上突发过K如喝水，我读了一下题尝试构造尽量短的线段，发现十字无解，倒转一下思路尝试构造尽量长的线段，最终发现要将线段分组贪心K1(237)。机器再次回到G，重构代码（虽然我也不熟悉这种题w_w），扫描法用了最暴力的分类讨论，ctrl-cv写代码法，很无脑简单，但是出bug风险大，于是路上加上了一堆assert弥补；最后找了一会“=”写成“==”的BUG，过了几组数据提交RE，这时詹哲远已经在场，提出删除assert，G4(297)。

A

对一颗树指定点权，其中点权大于零的可覆盖距离不大于点权的附近点。覆盖所有点，并使点权和最小。

B

4X4棋盘，两人轮流下黑白子，给出初态和末态特征求可能的最终局面数。

棋盘很小，直接暴力。

C

无向图找到一条最长路，路径要求节点度数严格递增。

按照度数对点排序，依次松弛。

D

对一个数反复操作：每个数位的平方求和。问最终能否变成1.

第一次操作后数的最大值很小，于是用set判循环。

E

无向图对每一条边求至少删掉多少条边后此边可以出现在MST上。

对每条边(u,v)只保留边权更小的边，考虑最少的删边使(u,v)不连通，即最小割。

F

给出一个迷宫的size和递归式的构造方法，求从起点走m步之后的坐标。

确认目标位置属于递归的哪个部分，递归之后做对应的坐标变换。

G

两条折线求围成的多边形数量和面积。

扫描一遍，将y轴方向的线段看做事件。分类讨论两条折线的y轴走势。

H

I

类似循环小数的尾循环，求数串的循环节p和开始循环位k，使k+p最小。

发现倒着做答案不变，直接套用kmp。留意循环节仅出现一次的情况。

J

判断一个无向图是否满足任意割出的两个点集（点数都是n/2）都有完美匹配。

霍尔婚配定理+乱搞？

K

给出一条链（仅有平行x轴、平行y轴走向），任意地更改每条线段的长度，使得链不自相交。

原边长无意义。令连续的同向线段分为一组（连续定义为不被反方向线段分隔），令最后一个元素尽量大，前面的元素为1。这样对于每一组走向都不会发生碰撞。

L

对p个有向图移动棋子，求p个图的棋子都到达终点时最小代价。代价包含边权、所停留点的点权。