2017-Sp69-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，看到有人过了B，cjb读了B，上机开始写，写完发现题意不太对，和yzc讨论了下，yzc给了个线段树的做法，cjb上机继续写，之后'''B1y48'''。sub和yzc讨论了I，yzc上机写I，'''I2y68'''。sub给出了E的算法，yzc表示怀疑，上机写了，之后'''E1y102'''。之后集中攻D，yzc上机写了暴力找规律，各种分析推广后终于在3个小时的时候wa了第一发，cjb发现一队过了H，读了H，和sub讨论了之后会做了，之后D一直在调试，三个半小时wa了第二发，cjb上机写H，之后'''H4y261'''，最后终于找到了D的问题，'''D3y278'''。
== 总结 ==
=== chenjb ===
今天打得太sb了...我们这几场都有个问题一直忽略了，就是读题，今天最搞笑的事情就是有很多比较好搞的题目我们都没读过，连榜都不管了死磕D。以后我们开场要先读题，不同于区域赛，没必要开场急着抢题目，每个人都读几个题，这样以后也方便许多，然后我和yzc也不能像以前一样急于丢题意，我在比赛中也要特别注意榜的走向，尽早把题目读完，也好把握题目的类别，今天出D其实得不偿失。
=== oipotato ===
赛后分到锅之后读了两个题直接秒了，可以说是非常搞笑了。最近赛中的读题的确是一个大问题，很梦游？问题很大要引起重视。
=== subconscious  ===
== 题解 ==
 * C：
   * 题意：01串p：pi=[(a*i+b)%n<p],a,n互质，01串q串长m，读入给出，求q在p中匹配数量，n,a,b,p<=1e9,m<=1e6。
   * 题解：设匹配开始位置x，对于q的每一位可以视为对ax的一个区间限制，离线拆分求区间交即可。注意要剔除x>n-m+1的m-1个位置。
 * F：
   * 题意：给定一棵树，删掉一条边再加一条边，求直径的最大值和最小值并输出删的边和加的边。
   * 题解：考虑枚举删掉哪条边，对于删掉后的两棵子树，想要连起来之后直径最大，显然就是将两个直径连起来。若想要最小，显然是直径的中点连起来。于是用树形DP维护每个子树的直径（记录直径的来源）和最深深度（也要记录来源），并记录去掉来源的直径和最深深度。用类似换根操作枚举删掉每一条边，记录答案和删掉的边。于是方案就很容易的可以通过删掉的边的两端用暴力dfs得到了。
 * G：
   * 题意：50个加油站，4000辆车，每辆车只会在[a,b]这个区间选择最便宜的加油站加油，但是如果价钱超过c，就会放弃，要求给加油站定价钱，使得收益最大。
   * 题解：显然取值就在c里面取，f[i][j][k]表示[i,j]里值不小于k的最大收益，有两种决策: f[i][j][k] <- f[i][j][k-1] （不小于k-1可以转移给不小于k) 以及 f[i][j][k]  <- f[i][p-1][k] + f[p+1][j][k]+cnt*q[k].c （枚举最小点的取值与位置，分割区间)，统计cnt可以预处理，也可以单调搜扫一下。
 * J：
   * 题意：一个长度为n的序列，一些位置有初始值。给定m个限制条件，每个限制条件给出一个区间和k个关键点，表示这些关键点的值都比区间内别的值大。求给1-n每个位置分配一个值使得满足限制和初始条件，值域[1,10^9^]，n为100000，m为200000.
   * 题解：用线段树套vector维护覆盖当前线段树区间的限制条件的编号，记录每个点被多少个区间置为关键点，并记录线段树每个区间上的每个限制条件在当前区间存在多少个非关键点，那么显然若区间里确定了值的位置个数达到这个值，就可以在这个区间中将其删去，还要记录每一个限制条件加入了多少个线段树区间，没被删除一次就减1，变为0时说明这个区间所有的非关键点都已经确定了值，于是关键点的值和非关键点的值+1取最大，整个过程类似拓扑排序。若最后确定的值的个数不足n个或取值超过范围则无解。
 * [https://wiki.icpc-camp.org/dreadnought/Warsaw%20U%20Tasks,%20XV%20Open%20Cup%20Onsite Dreadnought]
 * [https://wiki.icpc-camp.org/twsf/Petrozavodsk%20Summer-2015.%20Warsaw%20U%20Tasks,%20XV%20Open%20Cup%20Onsite TheWaySoFar]
== 补题 ==
 * A
 * ~~C~~ by sub
 * ~~F~~ by yzc
 * ~~G~~ by cjb
 * ~~J~~ by yzc
 * K

流水账

开场各自看题，看到有人过了B，cjb读了B，上机开始写，写完发现题意不太对，和yzc讨论了下，yzc给了个线段树的做法，cjb上机继续写，之后B1y48。sub和yzc讨论了I，yzc上机写I，I2y68。sub给出了E的算法，yzc表示怀疑，上机写了，之后E1y102。之后集中攻D，yzc上机写了暴力找规律，各种分析推广后终于在3个小时的时候wa了第一发，cjb发现一队过了H，读了H，和sub讨论了之后会做了，之后D一直在调试，三个半小时wa了第二发，cjb上机写H，之后H4y261，最后终于找到了D的问题，D3y278。

总结

chenjb

今天打得太sb了...我们这几场都有个问题一直忽略了，就是读题，今天最搞笑的事情就是有很多比较好搞的题目我们都没读过，连榜都不管了死磕D。以后我们开场要先读题，不同于区域赛，没必要开场急着抢题目，每个人都读几个题，这样以后也方便许多，然后我和yzc也不能像以前一样急于丢题意，我在比赛中也要特别注意榜的走向，尽早把题目读完，也好把握题目的类别，今天出D其实得不偿失。

oipotato

赛后分到锅之后读了两个题直接秒了，可以说是非常搞笑了。最近赛中的读题的确是一个大问题，很梦游？问题很大要引起重视。

subconscious

题解

C：
- 题意：01串p：pi=[(a*i+b)%n
- 题解：设匹配开始位置x，对于q的每一位可以视为对ax的一个区间限制，离线拆分求区间交即可。注意要剔除x>n-m+1的m-1个位置。
F：
- 题意：给定一棵树，删掉一条边再加一条边，求直径的最大值和最小值并输出删的边和加的边。
- 题解：考虑枚举删掉哪条边，对于删掉后的两棵子树，想要连起来之后直径最大，显然就是将两个直径连起来。若想要最小，显然是直径的中点连起来。于是用树形DP维护每个子树的直径（记录直径的来源）和最深深度（也要记录来源），并记录去掉来源的直径和最深深度。用类似换根操作枚举删掉每一条边，记录答案和删掉的边。于是方案就很容易的可以通过删掉的边的两端用暴力dfs得到了。
G：
- 题意：50个加油站，4000辆车，每辆车只会在[a,b]这个区间选择最便宜的加油站加油，但是如果价钱超过c，就会放弃，要求给加油站定价钱，使得收益最大。
- 题解：显然取值就在c里面取，f[i][j][k]表示[i,j]里值不小于k的最大收益，有两种决策: f[i][j][k] <- f[i][j][k-1] （不小于k-1可以转移给不小于k) 以及 f[i][j][k] <- f[i][p-1][k] + f[p+1][j][k]+cnt*q[k].c （枚举最小点的取值与位置，分割区间)，统计cnt可以预处理，也可以单调搜扫一下。
J：
- 题意：一个长度为n的序列，一些位置有初始值。给定m个限制条件，每个限制条件给出一个区间和k个关键点，表示这些关键点的值都比区间内别的值大。求给1-n每个位置分配一个值使得满足限制和初始条件，值域[1,10⁹]，n为100000，m为200000.
- 题解：用线段树套vector维护覆盖当前线段树区间的限制条件的编号，记录每个点被多少个区间置为关键点，并记录线段树每个区间上的每个限制条件在当前区间存在多少个非关键点，那么显然若区间里确定了值的位置个数达到这个值，就可以在这个区间中将其删去，还要记录每一个限制条件加入了多少个线段树区间，没被删除一次就减1，变为0时说明这个区间所有的非关键点都已经确定了值，于是关键点的值和非关键点的值+1取最大，整个过程类似拓扑排序。若最后确定的值的个数不足n个或取值超过范围则无解。
Dreadnought
TheWaySoFar

补题

A
C by sub
F by yzc
G by cjb
J by yzc
K

附加文件

1.png by chenjb