2020-team1-072

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 10/14  dirt: 64%
rank: 24
[[Image(Rank.png,800px)]]
== 总结 ==
除了Grammy不会做F，Hwa了很久，好像没有什么带问题
可能Grammy需要去更积极地看题，或者Oscar早点把A丢给Grammy，这样有概率能再多个A
噢I题Oscar会后半部分，Sakuya会前半部分，但是他们没有交流，如果多交流有可能能多个I？
快进到能AK
== 题解 ==
A: 枚举左端点L，找最近的右端点R
细节和corner case特别多，讲一下主要的几个：
（1） 若不存在l<=K且r>=m-K的人，直接不来；
（2） 若有[i,i]的区间，直接不来；
（3） 若存在l<=K且r>=m-K的人，一定要让他看见，即选定的区间[L,R]要满足 L<=r或R>=l
（4） 若R<=K，要往后跳直至>=K或者不在任何一个l<=K的[l,r]内
（5） R要往后跳至[L,R]不被人完整包含（反正会对K取min）
B: 分数规划
C: 分治可持久化并查集
D: f[n][j]为n个物品中从小到大排名为j的物品先手选到的概率系数，n^2^DP即可
E: 枚举一维，另外两维有用的限制在二维平面上是随x增加y减小的，用set维护这些限制点，multiset维护相邻点之间的最大R
F: dp，mxr[i]表示l<=i的限制中的max r，mnr[i]表示l>=i的限制中的min r，设f[i]表示在i放了点，只考虑包含了i的限制和l>=i的限制，能不能有合法解，那么f[i]=1当且仅当在区间 [ max(mxr[i]+1,i+1), mnr[i+1] ] 内存在f[j]=1，初始化f[4n-1]=1，然后可以O(n)去预处理和dp上述过程
G: 贪心的选，从a枚举到c，看如果选上当前位置i后面的第一个a，子序列能不能凑到k的长度
H: 数据生成器分段可逆，倒着贪心，初始cur=m，满足cur>=ai+1就可以选上，否则如果i=cur则必然劝说。注意z1>z2时第一段的最后一个a可能大于z2，导致无法还原回来，因此需要记录每段结束后的a值。
I: 把数竞中的经典构造（2k+1，k）以及（2k，k）的情况弄出来，其它情况就把原本的构造排成一个列表，然后k个k个地取
J: 对bi>0，考虑第1天，如果ai=1，那么那个i色人看不到i色人，因此知道了自己是i色人，因此至多会在第1天自杀
第2天，如果ai=2，那么所有i色人都只看到1个i色人，并且知道如果只有1个i色人则他至多会在第1天自杀，因此这些i色人知道了i色人不止1个，因此他们自己是i色人，因此至多会在第2天自杀
第3天，如果ai=3，那么所有i色人都只看到2个i色人，并且知道如果只有2个i色人则他们至多会在第2天自杀，因此这些i色人知道了i色人不止2个，因此他们自己是i色人，因此至多会在第3天自杀
归纳可得，bi>0时所有i色人都至多会在第ai天自杀
对于bi=0，没有任何信息。
但如果岛上除了一个颜色以外所有人都自杀了，那么剩下的那种颜色人就知道了自己是那种颜色(不妨设为j)，所以他们会在第min(max(ai)+1,aj)(i!=j)天自杀。
K: 对hi>m，可以先打一打，等到自己剩1血了再打死，因此可以视为血量没有上限后所有hi变为min(hi,m)
由于初始为m，ti<=hi的都可以贪心取掉
剩余的按k1*a+k2*b排序贪心能取就取（k1，k2从-1枚举到1，9种情况取最优）
L: 因为所有数字在[1,K]之间，要求最长上升子序列长度<K，首先长度一定<=K，若存在为K的一定是1~K，所以f[i][j]表示当前处理到位置i，凑出了1~j，最少要删多少个数，每个位置f[i]和f[i-1]只有a[i]和a[i-1]的值不同，所以数组可以只开一维
M: 换根dp，处理一大坨东西
N:

[/wiki/2020-team1 返回]

概述

solved: 10/14 dirt: 64%

rank: 24

总结

除了Grammy不会做F，Hwa了很久，好像没有什么带问题

可能Grammy需要去更积极地看题，或者Oscar早点把A丢给Grammy，这样有概率能再多个A

噢I题Oscar会后半部分，Sakuya会前半部分，但是他们没有交流，如果多交流有可能能多个I？

快进到能AK

题解

A: 枚举左端点L，找最近的右端点R

细节和corner case特别多，讲一下主要的几个：

（1） 若不存在l<=K且r>=m-K的人，直接不来；

（2） 若有[i,i]的区间，直接不来；

（3） 若存在l<=K且r>=m-K的人，一定要让他看见，即选定的区间[L,R]要满足 L<=r或R>=l

（4） 若R<=K，要往后跳直至>=K或者不在任何一个l<=K的[l,r]内

（5） R要往后跳至[L,R]不被人完整包含（反正会对K取min）

B: 分数规划

C: 分治可持久化并查集

D: f[n][j]为n个物品中从小到大排名为j的物品先手选到的概率系数，n2DP即可

E: 枚举一维，另外两维有用的限制在二维平面上是随x增加y减小的，用set维护这些限制点，multiset维护相邻点之间的最大R

F: dp，mxr[i]表示l<=i的限制中的max r，mnr[i]表示l>=i的限制中的min r，设f[i]表示在i放了点，只考虑包含了i的限制和l>=i的限制，能不能有合法解，那么f[i]=1当且仅当在区间 [ max(mxr[i]+1,i+1), mnr[i+1] ] 内存在f[j]=1，初始化f[4n-1]=1，然后可以O(n)去预处理和dp上述过程

G: 贪心的选，从a枚举到c，看如果选上当前位置i后面的第一个a，子序列能不能凑到k的长度

H: 数据生成器分段可逆，倒着贪心，初始cur=m，满足cur>=ai+1就可以选上，否则如果i=cur则必然劝说。注意z1>z2时第一段的最后一个a可能大于z2，导致无法还原回来，因此需要记录每段结束后的a值。

I: 把数竞中的经典构造（2k+1，k）以及（2k，k）的情况弄出来，其它情况就把原本的构造排成一个列表，然后k个k个地取

J: 对bi>0，考虑第1天，如果ai=1，那么那个i色人看不到i色人，因此知道了自己是i色人，因此至多会在第1天自杀

第2天，如果ai=2，那么所有i色人都只看到1个i色人，并且知道如果只有1个i色人则他至多会在第1天自杀，因此这些i色人知道了i色人不止1个，因此他们自己是i色人，因此至多会在第2天自杀

第3天，如果ai=3，那么所有i色人都只看到2个i色人，并且知道如果只有2个i色人则他们至多会在第2天自杀，因此这些i色人知道了i色人不止2个，因此他们自己是i色人，因此至多会在第3天自杀

归纳可得，bi>0时所有i色人都至多会在第ai天自杀

对于bi=0，没有任何信息。

但如果岛上除了一个颜色以外所有人都自杀了，那么剩下的那种颜色人就知道了自己是那种颜色(不妨设为j)，所以他们会在第min(max(ai)+1,aj)(i!=j)天自杀。

K: 对hi>m，可以先打一打，等到自己剩1血了再打死，因此可以视为血量没有上限后所有hi变为min(hi,m)

由于初始为m，ti<=hi的都可以贪心取掉

剩余的按k1*a+k2*b排序贪心能取就取（k1，k2从-1枚举到1，9种情况取最优）

L: 因为所有数字在[1,K]之间，要求最长上升子序列长度

M: 换根dp，处理一大坨东西

N:

附加文件