2019-team666-0003

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
七月集训第三场
签到题开的有点晚，上来tjc发现L可做写了一发L，20多分钟开出H后hyw上机写了两次都没写对，换yyc写D，检查后本来想上机写但是看yyc快写好了又拖了一会儿，'''H1Y62'''. yyc继续写D，WA了两发发现算法不对，换tjc写L，'''L1y80'''. yyc和hyw讨论I的解法，假了2次，看了榜以后yyc写F，hyw和tjc讨论出I，这时F题WA了，tjc上机写I，'''I3Y120'''. 这时tjc又开出E，'''E1Y152'''. yyc很快改完F，'''F2Y163'''. 这时yyc打算先莽一波B，期间开出A，发现A是个LCT，yyc开始写A，tjc和hyw开出G，hyw上机写G，中间因为dp边界条件判断不对错了一次，'''G2Y256'''. 最后时刻tjc想出J但是来不及写了，全员自闭调A，没有调出来。
== 总结 ==
=== yyc ===
不会写代码*2,做题时还是该仔细想一想对不对，而且就算错了也要好好想一想解决方法，其实D的问题很好解决(UPD:已解决，做法是对的，只是程序有点bug)。
=== tjc  ===
L开场看错题写麻烦了，第一次想出G这种难度的dp题，同时第一次想出来的题>写出来的题，好起来了啊...
看错题计数器++
=== hyw  ===
继续是背锅的一天，开场状态很糟导致H题1个小时才过，I题也是思维很乱，感谢队友帮我冷静下来理清了思路。后期头脑清醒了一点但依旧卡了好几道不可做的题，K题想出n3做法但是没去深入想优化，C题卡了一会儿没有头绪，B、D都很快给出做法不过都假了。感觉今天写代码的状态恢复了一点但是思维还是不在线，加上开场签到不顺压力就很大，以后面对逆风开局可能还是要冷静一点。以及dp这块出了点大锅，边界条件也没注意，还得找时间再练一下。
以及感觉有题好写而且稳而且很多队都过的时候应该先写，比如今天的H，当时应该坚持一下早点换队友下来把它写掉。
补题后UPD：A题有坑，小心n=1,Q=0的情况（否则会疯狂wa on 43）
=== 题解 ===
A：拆点后LCT维护，由于每棵splay中颜色是相同的，直接边access边修改即可
B：建图+缩点+性质+2sat
C：dp，f(i,j)=前i个位置后面接j个'H'满足条件的概率，g(i,j)=后i个位置前面接j个'R'满足条件的概率，枚举分界点后推式子合并fg
D：拓扑排序判环。然后根据每条边的约束条件修改每一个人实际的[l,r]，转化成经典贪心问题，对每个l在覆盖l的区间里面找r最小的即可。
E：贪心，能合并就合并 强化版：zjoi2016 电阻网络
F：
G：dp，f(i,j,k,l)=前i个位置删去j个已选、加入k个未选、末尾连续l个位置未选的最小花费 例题：bzoj5359
H：暴力
I：爆搜SG 例题：cf850C
J：枚举区间最小值+分组+二分+堆维护
K：直接区间dp是n3的，发现可以从(1,n)向(i,i)做一个n2的dp，转化成坐标平面上(1,n)到(i,i)的最长路，注意到一共只有O(n)条带权边，分层转移（水平边和竖直边分别存并排序，按列编号顺序dp，树状数组维护行的信息）
L：预处理+复杂度分析
M：凸优化 例题：1.APIO2014 序列分割;2.LR10 yanQval的生成树

[/wiki/2019-team666 返回]

概述

七月集训第三场

签到题开的有点晚，上来tjc发现L可做写了一发L，20多分钟开出H后hyw上机写了两次都没写对，换yyc写D，检查后本来想上机写但是看yyc快写好了又拖了一会儿，H1Y62. yyc继续写D，WA了两发发现算法不对，换tjc写L，L1y80. yyc和hyw讨论I的解法，假了2次，看了榜以后yyc写F，hyw和tjc讨论出I，这时F题WA了，tjc上机写I，I3Y120. 这时tjc又开出E，E1Y152. yyc很快改完F，F2Y163. 这时yyc打算先莽一波B，期间开出A，发现A是个LCT，yyc开始写A，tjc和hyw开出G，hyw上机写G，中间因为dp边界条件判断不对错了一次，G2Y256. 最后时刻tjc想出J但是来不及写了，全员自闭调A，没有调出来。

总结

yyc

不会写代码*2,做题时还是该仔细想一想对不对，而且就算错了也要好好想一想解决方法，其实D的问题很好解决(UPD:已解决，做法是对的，只是程序有点bug)。

tjc

L开场看错题写麻烦了，第一次想出G这种难度的dp题，同时第一次想出来的题>写出来的题，好起来了啊...

看错题计数器++

hyw

继续是背锅的一天，开场状态很糟导致H题1个小时才过，I题也是思维很乱，感谢队友帮我冷静下来理清了思路。后期头脑清醒了一点但依旧卡了好几道不可做的题，K题想出n3做法但是没去深入想优化，C题卡了一会儿没有头绪，B、D都很快给出做法不过都假了。感觉今天写代码的状态恢复了一点但是思维还是不在线，加上开场签到不顺压力就很大，以后面对逆风开局可能还是要冷静一点。以及dp这块出了点大锅，边界条件也没注意，还得找时间再练一下。

以及感觉有题好写而且稳而且很多队都过的时候应该先写，比如今天的H，当时应该坚持一下早点换队友下来把它写掉。

补题后UPD：A题有坑，小心n=1,Q=0的情况（否则会疯狂wa on 43）

题解

A：拆点后LCT维护，由于每棵splay中颜色是相同的，直接边access边修改即可

B：建图+缩点+性质+2sat

C：dp，f(i,j)=前i个位置后面接j个'H'满足条件的概率，g(i,j)=后i个位置前面接j个'R'满足条件的概率，枚举分界点后推式子合并fg

D：拓扑排序判环。然后根据每条边的约束条件修改每一个人实际的[l,r]，转化成经典贪心问题，对每个l在覆盖l的区间里面找r最小的即可。

E：贪心，能合并就合并 强化版：zjoi2016 电阻网络

F：

G：dp，f(i,j,k,l)=前i个位置删去j个已选、加入k个未选、末尾连续l个位置未选的最小花费 例题：bzoj5359

H：暴力

I：爆搜SG 例题：cf850C

J：枚举区间最小值+分组+二分+堆维护

K：直接区间dp是n3的，发现可以从(1,n)向(i,i)做一个n2的dp，转化成坐标平面上(1,n)到(i,i)的最长路，注意到一共只有O(n)条带权边，分层转移（水平边和竖直边分别存并排序，按列编号顺序dp，树状数组维护行的信息）

L：预处理+复杂度分析

M：凸优化 例题：1.APIO2014 序列分割;2.LR10 yanQval的生成树