xixike

# Description Luogu 传送门 # Solution 我们直接找是否有等于 3 的等差子序列即可。 假设三个数 ai<aj<aka_i < a_j < a_kai​<aj​<ak​ 形成了等差子序列，那么有 ai+ak=2×aja_i + a_k = 2 \times a_jai​+ak​=2×aj​，所以对于一个 aia_iai​ 对应的 aka_kak​ 只有一个。 因此我们对于每一个 aja_jaj​ 只需要判断一对 ai,aka_i, a_kai​,ak​ 是否在 jjj...

# Description Luogu 传送门 vjudge 传送门 不得不说，洛谷的翻译是真的迷，这里再给出一个翻译： 给你一个长度为 nnn 的数列，让你把这个数列划分成 k+1k + 1k+1 段。 定义一段区间的价值为区间内数字两两异或的和，即 ∑i=lr∑j=i+1r(ai⊕aj)\sum\limits_{i = l}^r\sum\limits_{j = i + 1}^r(a_i \oplus a_j)i=l∑r​j=i+1∑r​(ai​⊕aj​)。 求一种划分方案使得 k+1k + 1k+1...

# Description Luogu 传送门 # Solution 偶然发现这道题所以来做做。 刚开始看完题的时候感觉这只能暴力模拟…… 于是不要脸的看了一眼题解之后，我们可以用一些表达式来表示每头奶牛到达它应该到的位置的时间，从而计算出总共时间。 具体来说，第 nnn 头牛到达其位置所用时间是 sn+tns_n + t_nsn​+tn​，第 n−1n - 1n−1 头牛到达 sns_nsn​ 的时间就是 sn+tn+1s_n + t_n + 1sn​+tn​+1（因为 cown−1cow_{n - 1}cown−1​ 初始坐标比 cowncow_ncown​ 的坐标靠左...

# Description Luogu 传送门 # Solution 非常有意思的一道题。 看到回文子串，首先想到的 manacher 算法。emm…… 但是写了 manacher 之后怎么做呢？ 我们发现，求相交的回文子串非常麻烦，所以直接一波正难则反，用总的回文子串数减去不相交的。 接下来考虑如何求不相交的回文子串。 我们开两个数组 fif_ifi​，gig_igi​。fif_ifi​ 表示以 iii 为开头的回文串有多少个，gig_igi​ 表示以 iii 为结尾的回文串有多少个。 看到标签里的前缀和，我们给 gig_igi​ 做个前缀和存到 sumisum_isumi​ 里，那么...

# 前言 刚开始学 OIOIOI 的时候学过对拍，但是后来基本上没有用过。 （暴力都不会写什么对拍） 临近 CSPCSPCSP 稍微复习了一下，于是写一篇博客记录一下（以后忘了还可以看）。 # 正文 # 方法 # 1. 准备好你需要对拍的程序 a.cpp #include <iostream>#include <cstdio>#include <algorithm>using namespace std;int main(){ long long a, b; cin >> a >> b;...

# Description 洛谷传送门 # Solution KruskalKruskalKruskal 重构树好题。 我们先按照水位 aaa，建 KruskalKruskalKruskal 重构树。具体来讲：按水位从高到低排序，每次选出剩余边中水位最高的一条边插入到树中，这样就建成了一个小根堆。 然后我们再来考虑询问。 对于一个水位线 ppp，若 p<Kruskalp < Kruskalp<Kruskal 重构树上的点 xxx 的水位，那么在以 xxx 为根的子树中，开车是可以随意通行的，对答案没有贡献。 若 p>t[x].depp...

# Description Luogu 传送门 # Solution 首先有一个明显的结论，如果两个子串是 iii 相似，那么它们也一定是 1≤j≤i1 \leq j \leq i1≤j≤i 相似。 所以我们可以通过 SA 把 height 数组求出来，然后从大到小排序，并依次枚举。 每次对两个相邻的后缀进行处理，把它们两个所在的并查集合并。 考虑合并都有哪些操作，回顾一下问题，我们需要计算 kkk 相似的个数及最大权值。 先看个数：由于我们是按 height 数组从大到小枚举的，所以已经在并查集里的子串一定是合法的，所以 ans1+=sizx×sizyans_1 += siz_x...