我们先简化问题，考虑序列上的问题，并且不受K限制。
我们考虑dp，对于给定的序列 v[1],v[2],v[3]...v[n]，我们定义dp[i]表示以i号点为开头的最长lili序列的长 度。然后我们去考虑如何维护这个dp值。对于我们枚举到的i位置，我们去观察这个点可能贡献到哪些lili序 列。对于数列{1，5，2，3，4} 我们考虑第5个位置的值4能贡献到哪几个位置。显然它能对以3位置的2开头 的lili序列，以4位置的3开头的lili序列，以5位置4开头的lili序列有贡献。那么为什么不能对前两个有贡献呢? 因为对于第一个1来说，4不是1后面第一个比它大的。对于第二个5来说，4比5小。我们假设当前位置为x， 值为v[x]。观察它贡献的位置，我们很容易发现其有贡献的序列就是那些开头介于 last 与 x 之间的。Last为x 之前的 离x最近的 值大于等于v[x]的位置。
进而我们可以发现，当前一个点的值可以对一段区间产生贡献，并且贡献的形式都是区间加一，这启发我 们用数据结构去维护这个转移。我们使用线段树，线段树的维护以每个位置开头的dp最大值，按从左往右的 顺序枚举 i 点，对于每个 i 我们可以用单调栈找出其贡献的区间，然后在线段树上实现区间加一，最后去询 问线段树上的前缀[1,i]最大值，这个值就是每个点的dp值。那么同样，我们发现对于有K限制的版本，I 点的dp值就为线段树上询问区间[max(i-k+1,1),i]的区间最大 值，其它并无区别。
此时，对于固定的K，我们已经得到了一个效率为O(nlogn)的做法。但这题要求的是对于每个K都输出其 对应的答案，这个效率显然是不够的，所以我们应该去思考如何优化这个算法。
我们再回过头来看问题，因为其要询问的是对于每个 K ，lili 值大于 W 的点数。而上述步骤中我们求出了 所有点的lili值，这显然浪费了非常多的额外时间。于是我们观察，对于给定的W，若在距离系数为k的情况 下，其lili值满足了条件即大于等于W，那么在距离系数为k+1的情况下也一定满足条件。于是我们就可以想 到二分，如果对于每个点，我能求得使其满足条件的最小的k值，那么对于K∈[k,n]，它也应该满足条件。
那么对于每个点我们可以二分使它满足条件的最小的k，对于二分的一个值mid，去线段树上询问区间 [max(i-mid+1,1),i]的最大值，然后根据这个值与W的关系继续二分。但是这个效率对于每个点是 O(log^2n)，因为有经典的做法，所以我们卡掉了这个效率。我们知道，线段树的本质其实就是在一直二分 区间，那么我们就可以将二分k的这个过程和线段树结合起来，换句话说就是在线段树上做二分来找到这个 最小的k，这个效率对于每个点是O(logn)
关于线段树上二分，我们可以考虑当进入到一个节点的时候，若其右儿子维护的区间max大于等于W，那 说明右儿子中一定存在满足条件的k值，且这个k值一定比左儿子中的k值来的小。如若不然，则观察其左儿 子的max值，若其大于等于W，则进左儿子找答案，若左右儿子的值都小于W，则该点无论如何都不可能对 答案有贡献，此时直接在线段树上直接return即可。
最后我们来考虑树上的版本与序列上的差异。序列上的从左往右按顺序就变成了树上的按dfs序，序列上 的贡献区间的左端点从 x前面离它最近的一个权值大于等于v[x]的点 变成了 x到根路径上第一个权值大于等 于v[x]的点。x到根路径上第一个权值大于等于v[x]的点如何求呢?我们可以采用可撤销单调栈或者倍增，题 解采用了可撤销单调栈，就是在单调栈弹栈的时候不真正的弹掉元素，只是二分一个弹完之后的栈顶位置， 最后就可以直接撤销了。
接下来我们需要考虑一下线段树上维护的信息发生了什么变化。在序列问题上，线段树很自然的可以维护 每个下标位置的dp值，因为这些都是连续的。但是在树上，每个点到根路径上的点的dfs序不是连续的，所 以我们不能去维护dfs序，但是我们可以发现，每个点到根路径上的点的高度是连续的!所以我们可以将线段 树换成维护高度为i的点的dp值，因为在dfs的过程中，每个时刻在lili序列中高度与点是一一对应的。那么我 们只需按上述方法维护答案，然后在dfs过程中进入一个点的时候加上这个点的贡献，然后计算答案，在撤出 这个点的时候减去其在线段树上的贡献，并撤回单调栈即可。
此时我们已经求出了每个点可以贡献的最小k值，然后我们只需要对这些值做一遍前缀和就能得到答案了。 效率:O(nlogn)
C – Cinema
其实就在n*m的网格中，用最少的十字覆盖掉所有格子。• 贪心构造?状压DP.三进制表示行的状态:0表示未覆盖，1表示被覆盖了的，2表示放了十字的。
状态数:3^15 = 14,348,907 ?
去除非法状态:
两个0相邻，两个2相邻，0和2相邻，两个相邻的1边上没有2
m = 15, 状态数~6531, m = 14状态数~3721, m = 10状态数~392
因为T最大有1000，可以离线所有test case, 然后按照m相同的一起dp求解。• 记录状态转移，输出方案。
D – Disgusting Relationship
E – Enigmatic Partition
拆分肯定由三种连续的数构成，比如l, l+ 1, l+ 2. 可以通过枚举!去初始化f(n).
F—Factorio
首先，将每种物品建一个点，将原料向产品连一条有向边，容易将题目转化为一个DAG图，其中边权为合成 公式中原料的系数，点权为合成公式中产品的系数的倒数。
设F(i) = 从根到i所有路径长度之和。其中路径长度是指:路径上的点和边的权值的乘积。 F(i)的实际意义为在理想情况下，i节点与根节点的机器数量之比。
因此，题目所求的瓶颈就是cnt(i)/F(i)最小的那些机器，其中F需要使用高精度，或者注意到点权和边权只有1， 2，1/2，因此也可以使用bitset维护超长整形。
G – Game SET
暴力出奇迹，直接冲!!!三层循环枚举，然后判断。 N≤256,T≤1000
H—Hard String Problem
有n个无限循环的字符串，给出每个循环串的循环节，求这n个串有多少个本质不同公共子串。• 题解
首先需要将每个串处理为最简形式，用其最小循环节的最小循环同构来表示。
对于只有两个无限循环串，求公共子串的问题，我们可以得到一个结论:如果其本质循环节相同，则拥有无
限多个公共子串。否则，公共子串的长度将不会超过长串长度的三倍。
有了引理之后，我们思考如何将其推广到n个串，我们可以选出最短串S_min，求剩余的n-1个串S_i各自和 S_min的公共子串，然后将这些子串集合求交。在求S_min与S_i的公共子串数量时，需要将S_min 以及S_i 都各自翻倍到4|S_i|长度。因此考虑整个过程，S_min最长需要翻倍到4|S_max|，其余每个串则需要翻倍到4|S_i|，然后可以用广义sam 来求这些翻倍过后串的公共子串即可。
J – Jumping Points
可以先考虑两端封闭的简单情况。即
这就是类似在两端拉绳子，拉到不能拉了就最短。
• 折线的转折点，必定在线段的端点处。可以贪心从起点出发，如果看不到某条线段了，那个挡住视线的那个端点肯定是下一个 端点。然后跳到那个端点继续贪心找。知道看到终点。但是这个贪心最坏情况还是O(n^2)的。可以维护上下两个凸壳。复杂度优化成O(n).最后从两端封闭到两端不固定。只要枚举两端上下端点的组合:四种情况。对于每一种情况，两端进行拉成水平的处理即可。
网易有道公司氛围 38人发布
投递美团等公司10个岗位 >