名字贼长的玩意练习记录

如果你直接从点 1 走过来，不休息，那么在第步时就算上的贡献。后面不管怎么选都可以。一共种情况（以为底数的原因是每一个位置有“休息”或“不休息”两种选择）。
如果不是直接从点 1 不休息地走过来，而是中间休息了一会再走过来，假设在位置才将这种情况的答案加上，那么前面的个位置和后面的个位置你不管怎么选都可以。所以对于每一个一共有种情况。而也有种选法，就一共种情况。

综合一下，最终答案就是。

注意，当时，为负数，但此时，所以不必担心。

1413E 2100

？？？你去跟上面那道题坐一桌。

注：每一次打完之后，后面不管之前的有没有用完，生命都会回复。也就是敌人回复血量的状态可以叠加。

容易发现，当的时候，不管敌人血量多大，每次打他，他回复完血量后血量都会减少。所以一定可以打死敌人。

否则，设目前时刻为。当，也就是的时候，你原来的攻击就啥用都没了。那么可以断言，一次攻击只有在的时候可以被算作有效攻击。此时令。

那么，我们就要在的时间范围内尽量多攻击，也就是每秒都要攻击敌人。一共可以攻击的次数就是。因为时刻也可以攻击他。注意到你要在第次攻击时把它刚好砍死。此时它的血量就是要求的最大血量。计算的话就是你的伤害减去它在第次攻击之前回复的血量。血量的那一项可以用等差数列公式求得。

1360H 2100

简单模拟。记一个最开始的中位数，然后给他赋上初值。给所有要减去的数排一次序。

然后一次同时减去头、尾。分类讨论现在在的哪一边。然后如果新的之前已经消去过了，那么就让它移动（具体方向需分讨），直到这个数没有被消去为止。因为，所以很轻松。

274D 2200

每一行其实是反映了所有的相对大小关系。那么就建一个图，每一行先忽略，然后肯定要从小数连到大数。但是这样边可能过多，所以中间放一个虚点，然后从小数连向虚点，然后从虚点连向大数即可。

最后判断有无环，有环则无解。若无环，则跑拓扑，即可求得答案。

1555E 2100

你硬控我一个中午，直到我想出来了那个性质……

要判断可以从一个线段能够 travel 到另一个线段，其实不需要那么麻烦，只需要将每一个线段的右端点统统，然后判断这两个线段中间有没有空的位置就行了……(* ￣︿￣)

然后首先将所有线段按照权值从小到大排序，然后你要维护一个的区间中所有点都要被覆盖。这个可以用线段树做。

然后双指针维护最小的以为结尾的一个选择的线段区间，使尽量小，这样方差才会尽量小。于是先求出来第一个，然后每一次让自加，然后再让自加直到都被覆盖过一次（若不自加也可以实现的话就不用自加）。

啊啊啊啊啊啊啊啊啊啊啊啊啊我要癫了！！！！！！

1970D 2100, 2600, 3100

这 3 道题，乱搞是正解（Tag 里面都标的是随机化）。所以我们要考虑如何乱搞才能把它搞对。

因为这里的，，所以我们要想一种合理的构造方法，使字符串简单易构造，并且两个字符串合并之后的总子串个数可以在复杂度很小的情况下被求出来。

可以发现，有一种 XOXXXX... 的构造，同时实现上面两种条件。因为 X 和 O 的个数差距非常大，所以答案相同的概率非常低。（经过一个早自习的推导后，）两个长度为的串按顺序合并到一起后的总子串个数为。为了保证式子不出错，字符串长度可以从开始。

然后就可以打的表了。打出所有合法长度之后就可以爽爽爽了。

打表核心代码

map<int, int> mp;
int calc(int x, int y){
    return max(x, y-1)*3-1 + (x)*(y-1);
}
void gen(){
    for(int i=1;i<=1000;i++) len[i] = rrnd(max(5, len[i-1]+7), 30*i);
    vector<int> vct;
    len[0] = 5;
    for(int i=1;i<=1000;i++){
        cerr<<i<<'\n';
        int allflag = 0;
        for(int j=len[i-1]+1;j<=30*i;j++){
            int flag = 1;
            for(int now:vct){
                if(mp[calc(now, j)] | mp[calc(j, now)]){
                    flag = 0; break;
                }
            }
            map<int, int> mp2;
            for(int now:vct){
                if(mp2[calc(now, j)]){
                    flag =0; break;
                }
                mp2[calc(now, j)] = 1;
                if(mp2[calc(j, now)]){
                    flag =0 ;break;
                }
                mp2[calc(j, now)] = 1;
            }
            if(mp[calc(j, j)]) flag = 0;
            if(flag){
                vct.push_back(j);
                len[i] = j;
                allflag = 1;
                for(int now:vct){
                    mp[calc(now, j)] = 1; mp[calc(j, now)] = 1;
                }
                mp[calc(j, j)] = 1; break;
            }
        }
        if(allflag == 0){
            cerr<<"????\n";
            exit(1);
        }
    }
}

765F 3100; 1793F 2600

这道题是 Algorithm-Duel 网站上的每日一题。据说这道题在洛谷上还有一道第三倍经验。黑题喜加一。

总而言之，题目大意就是给你一个序列，有次询问。在下标范围内取两个数，求这两个数的绝对值的最小值。

表面上是，实际上有很多点对都是没用的。比如，有个点，并且，那么实际上这个点对很明显是没用的。我们要做的就是把那些有用的点给拎出来。然后再对这些点求二维偏序求。

我们设如果比优，并且选了就可以不用选，也就相当于严格偏序，就说支配。现在我们要看当选定时，有多少个使得是有用的。这里钦定里面的。

假设我们现在已经定了是有用点。这里要让优，那么肯定就是中值的并且值最小（在此基础上位置最靠右）的点。即。我们要找一个，使得也是有用点，那么就要满足以下限制：

要让不被支配，。
要让不被支配，那么，即。

于是。这样，你的搜索值域范围减半。所以一个点最多个有用的左端点。所以总点对数就一共个。

那么具体怎么搜索呢？搞一个值域、动态开点线段树维护序列下标为的所有值。然后对于，找到最小的使并且取。这个可以在修改线段树时维护。然后搜索（为了搜索是否有使，这种时间复杂度影响小到忽略不计）。

最后，类似二维偏序的，用树状数组维护即可。

406D 2200

这道题容易发现，每一个点的经过的路径都是一个上凸壳。所以可以让这些点从右往左遍历，随时维护上凸壳，将现在的点和栈顶连一条边，这样就会形成一棵由第个点为根的树。找 LCA 即可。

955D 2600

首先，可以先对整个串做一个 KMP。如果有匹配的，就找到一个包含该串的长度为的串，把它劈成两半即可。

否则，就只能把这个串给拆开。枚举劈成两半的左边的长度和右边的长度。根据贪心，我们肯定要找到最早出现的合法位置和最晚出现的合法位置。

解决方案是：我们可以从左到右 KMP，设表示最早以结尾的并且长度向左扩大到之后的结尾位置。不要忘记，最后要从到，每次要让更新，保证不漏。预处理的合法方式反转序列后同理。

然后就枚举，若合法则输出即可。

1467D 2200

我们可以预处理每一个点会被算多少次到答案里。这样就可以直接在线修改查询了。

最开始会设表示你走了步，走到点的方案数。初始设，然后转移直接即可。

但是这样会发现，可能会发现：因为是走步后，走到点的方案数，这个和最终答案是不一样的。最终算贡献的方法应该是，再设表示从点开始再走步，把步数走完的方案数。并且设表示点会被算到答案里的次数。

于是可以得到转移：。现在要做的就是如何算数组。我们发现，从点开始再走步把步数走完，把这个步骤倒过来，其实就是走步后，走到点的方案数。和的定义是一样的。所以，。这道题就做完了。

2072G Div.3 最新最热

这道题可惜了，如果想到拆式子，赛时就可以切掉这道题然后 AK 了。

首先，大于的答案全是，显然。

其次，当时，是 base 意义下的两位数。所以可以拆分，算出所有两位数的答案为：

$\begin{aligned} &\sum_{p=sq+1}^{n} p(n\bmod p) + (n-n\bmod p)/p\\ = &\sum_{p=sq+1}^{n} p(n-\lfloor\frac{n}{p}\rfloor p) + \lfloor \frac{n}{p}\rfloor \\ = &\sum_{p=sq+1}^{n} np-\lfloor \frac{n}{p}\rfloor p^2 + \lfloor \frac{n}{p} \rfloor \\ = &\sum_{p=sq+1}^{n} \lfloor \frac{n}{p} \rfloor (1-p^2) + np \end{aligned}$

然后就可以普通分块做了。预处理的前缀和然后求即可。时间复杂度

最后，当，暴力求即可。复杂度目测。能过就行。

同时，不要忘记判断的边界关系。

60D 2500

远古场 + 每日一题 + 联考出过类似的。

边长互质的三角形的通项公式，。证明看这里。

因为所有的两两不同，所以可以搞一个并查集维护。然后枚举的复杂度设置好上限是能过的。。

1416C 2000

因为这道题出现了异或运算，所以可以尝试一位一位地考虑。

那么就可以先预处理出对于每一位的逆序对个数。具体地说，就是预处理出，如果两个数是一对逆序对，那么是哪一位决定了第一个数大于第二个数。这一位所决定的逆序对数之和。

这个就可以使用 01-Trie + DFS 来解决。在 DFS 的时候，每一个节点有一个零儿子和一儿子。分别代表了这一位选的情况和选的情况。要求出逆序对个数，就需要在 Trie 的 insert 操作时，记录这个状态有哪些数遍历过（即记录一个编号集合）。所以，我们可以双指针扫，左指针遍历，右指针记录有几个编号小于左指针现在正在指向的编号。

然后，扫完之后，求出了这个节点所可以判出来的逆序对数。这也就是当取的这一位为时，这个节点所可以判出来的逆序对数。那么当取的这一位为时的逆序对数肯定就可以求出来。

我们用一个数组来记录当的第位取时的逆序对数。上面操作就是为了记录这个。最后，从高位向低位扫，最优逆序对数就加上，然后当时，的该位取，否则取。

884D 2300

拆开是不好想的所以要把思维逆转想成合并。(ˉ▽ˉ；)…~~（我连这一步都没想出来~~

当时，就是合并果子。一道黄题。而现在可以等于，所以从正常情况来说，肯定是要尽量合并。

但是，有一个问题，就是当为偶数的时候。因为相当于删除一个数，相当于删两个数。最后要把删为，按照上面的方法要先操作。但是肯定是不如先，然后一直优。

所以，当为偶数时，先，然后一直。否则，一直。

1148E 2300

首先，将和排序后，它们的位置可以是一一对应的。因为如果两个石子的路径有交，那么把它换成无交也是可行的。

那么，满足有解的一个必要条件就是：。因为一一对应，并且在的同时也要。

不仅如此，假如有向左移动的已经大于前面向右移动的和，那么也没有解。具体地说，设。当存在使，那么就没有解。

现在有解了。我们维护一个栈，表示想要向右移动的石子的栈。

当，不管。
当，它就想要往右移动。然后就将其 push 进栈内。
否则，就要让他尽量匹配前面的想要往右移动的石子。一直匹配直到这个石子已经向左移动到了为止。若想要往右移动的石子还有距离，那就再把它 push 到栈里面。

当一个答案被记录的时候，那么肯定就会有一个元素被永远的弹出栈。所以就一定。

1051F 2400

题目中明显标明。

于是就可以先建一棵生成树，两个点的距离就是链上的距离。

然后再把不在生成树上的边加进图，然后以这些不在生成树上的点为源点，跑 Dijkstra。最多也就跑次。查询的时候，就先求它们在树上的距离，然后枚举这最多个点，设现在的点为。然后求的最小值。再将其和树上距离取个就是答案。

762C 2100

因为需要在中删除一段连续的段，所以剩下的两段一定就是连续的。

我们可以处理对于串，是的子序列的的前缀的最大长度。对于，的后缀最大长度同理。然后枚举和取即可。

859E 2100

首先，连边，建图。对于每一个连通块，会有 3 种情况：

是一棵树。设其大小为。然后会有种方案数。
有环。这个环你会牵一发而动全身，所以会有种方案数。
有自环。方案数为。

乘起来即可。

985D 2100

今日每日一题。但是昨日的每日一题太难了没写

注意：翻译没有体现出来的一点是：最后一个堆的大小是。

二分答案（即能摆多少堆）。然后对于每一个堆数，计算它能承载的最大沙袋数：

若，则最大沙袋数明显。
否则，取剩下堆数为堆。它肯定是呈一个前面的增长率为，后面的增长率为的一个山峰。那就计算的等差数列和这个山的沙堆个数加起来即可。

1184E 1900, 2100, 2400; 827D 2700

首先求最小生成树。

对于每一条边，分讨：

若该边不为树边，那么取树上的链的边权最大值。如果小于等于这个最大值，这条边就可以被计入最小生成树里。
否则，这条边是树边。对于这条边所在的一个环（算上一条非树边），如果这条边大于边边权，那么这条边就不是树边了。会被替代。所以树边的答案就是所有边边权的最小值。

那么处理方法就是，对于每一条边设置一个，存储它所在的所有环的非树边的权值的。可以在算每一条非树边时，给所有。

这些都可以使用线段树 + 树链剖分实现。