2020-team1-002

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 7/11  dirt: 42%
rank: 34 (现场榜unknown)
[[Image(Rank.png,800px)]]

== 流水账 ==
开场继续Grammy顺开Oscar倒开，Oscar表示IJK都不好做，Grammy感觉自己大概会做A，两人决定先跟榜。
Grammy看完B感觉好像没想法，回去写A，Oscar跟着榜切，B1Y12，D1Y33，24min时，Grammy交了一发A，wa on test 4，找了一会没找到错接下了H的题意，给出了H的一个做法扔给了Oscar写，自己回去查A的错。H1Y41，11分钟后Grammy又交了一发A，wa on test10（一脸迷惑）。
接下来的一个半小时，Oscar G1Y83，I1Y132，Grammy则不断的在wa A，wa了4次后他终于意识到这题他的贪心fix不动了，他改成了dp，最终A6Y132。Oscar K1Y158。
Grammy提出了一个F的结论，看起来很对，他写完交上去T了，之后Oscar给出了一个hack的数据，这个做法去世了。Oscar提出了一个很对的做法，但是要写一个吉司机线段树。Grammy决定去想想其他题，他给了一个C的做法，被Oscar叉掉了，于是他又fix了一下，这个做法现在看起来对了，于是他冲上去写了。很快写完并且通过了样例后，转移条件的判断被Oscar造的数据叉了。接下来一个多小时两人就在  fix做法  和  造新的数据卡掉转移的判断方法   中间反复横跳，比赛结束了也没fix完（
== 总结 ==
2h构造一场空，DS不会见祖宗
贪心dp分不清，hack自己第一名
（Grammy一己之力吃下全队所有罚时）
== 题解 ==
A:
B:
C:
D:
E:
F: 预处理显然（bushi） 后面就是两边同时for到最近的根递归。复杂度T(总)=T(大)+T(小)+O(小)，解得O(nlogn)，但是非常难想到
另一种想法是预处理以后每次找到pos对应区间的左端点<=当前根&&pos>=当前根打个标记L，找到pos对应区间的右端点<=当前根&&pos>=当前根打个标记R，再把所有被打上两个标记的位置加入候选根队列。复杂度显然O(nlogn)，但是非常难写（还没写，会写的，在鹿上了，咕咕咕）
G:
H:
I:
J:
K:

[/wiki/2020-team1 返回]

概述

solved: 7/11 dirt: 42%

rank: 34 (现场榜unknown)

流水账

开场继续Grammy顺开Oscar倒开，Oscar表示IJK都不好做，Grammy感觉自己大概会做A，两人决定先跟榜。

Grammy看完B感觉好像没想法，回去写A，Oscar跟着榜切，B1Y12，D1Y33，24min时，Grammy交了一发A，wa on test 4，找了一会没找到错接下了H的题意，给出了H的一个做法扔给了Oscar写，自己回去查A的错。H1Y41，11分钟后Grammy又交了一发A，wa on test10（一脸迷惑）。

接下来的一个半小时，Oscar G1Y83，I1Y132，Grammy则不断的在wa A，wa了4次后他终于意识到这题他的贪心fix不动了，他改成了dp，最终A6Y132。Oscar K1Y158。

Grammy提出了一个F的结论，看起来很对，他写完交上去T了，之后Oscar给出了一个hack的数据，这个做法去世了。Oscar提出了一个很对的做法，但是要写一个吉司机线段树。Grammy决定去想想其他题，他给了一个C的做法，被Oscar叉掉了，于是他又fix了一下，这个做法现在看起来对了，于是他冲上去写了。很快写完并且通过了样例后，转移条件的判断被Oscar造的数据叉了。接下来一个多小时两人就在 fix做法 和 造新的数据卡掉转移的判断方法 中间反复横跳，比赛结束了也没fix完（

总结

2h构造一场空，DS不会见祖宗

贪心dp分不清，hack自己第一名

（Grammy一己之力吃下全队所有罚时）

题解

A:

B:

C:

D:

E:

F: 预处理显然（bushi） 后面就是两边同时for到最近的根递归。复杂度T(总)=T(大)+T(小)+O(小)，解得O(nlogn)，但是非常难想到

另一种想法是预处理以后每次找到pos对应区间的左端点<=当前根&&pos>=当前根打个标记L，找到pos对应区间的右端点<=当前根&&pos>=当前根打个标记R，再把所有被打上两个标记的位置加入候选根队列。复杂度显然O(nlogn)，但是非常难写（还没写，会写的，在鹿上了，咕咕咕）

G:

H:

I:

J:

K:

附加文件