xixike

# Description Luogu 传送门 # Solution 斜率优化 dp 非常好的一道斜率优化，完全理解题目都用了好长时间 QwQ 其实如果你已经完全理解了这道题也不是特别难了。 我们可以选两个下标，然后把经过这两个下标的线全部删掉。 不难发现，交叉的线是没有用的，所以对于上方的一个点，我们只保留它与下方连边中最右边的点即可。 然后这张图就变成了好多不相交的线，这样就可以列出朴素 dp\text{dp}dp 了。 设 fif_ifi​ 表示把前 iii 条弦全部切掉的最小花费，那么有转移方程： fi=min⁡(fj+minlu[j+1]−1×minrv[i]+1)f_i =...

# 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​ 里，那么...