Archie 这是一道主席树的题目 为什么这么说呢？因为根据推导，每个人的相对位置不变才是最优解 那么就涉及到每个人的位置位于1区间第几大了 当然每个人分开处理是可以的，不过一个权值线段树可以很好的帮助我们查询并且利用等差数列的性质来快速计算. #include<iostream> #include<cstdio> #inc…

这只是个结论题 我们都知道对于n个点的图，可以构成的无根树种类是$n^{n-2}$，既然是有根图，那就规定一个n，答案就是$n^{n-1}$ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include&l…

小结论：我们只要把所有的都异或起来就是最小的 $a \oplus b\lt a+b$ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namesp…

P4555 [国家集训队]最长双回文串 显然可以想到用manacher 然后统计一下每个位置开头和结尾的最长子序列 但是怎么更新？边跑mancher边更新每一个位置太慢了 那就到最后递推更新呗。 #include<iostream> #include<cstdio> #include<cstring> #incl…

P2375 [NOI2014] 动物园 暴力怎么做，暴力是不是，kmp求next数组然后递归硬求。 考虑优化吧，首先，递归多少层完全可以记忆化，不，是直接预处理。 然后怎么跳？考虑我们已经处理完i点，跳到了j处，现在多了个i+1，怎么办？ 是不是接着上一个跳就行？因为j的位置顶多移动一，如果j和i+1相等的话 这样就成了$O(n)$了 #inclu…

P4302 [SCOI2003]字符串折叠 Jennie 注意，这个题之所以写成带$()$的形式，不是为了解释说明，而是你最后输出的格式。 然后就是水的一批的区间dp #include<iostream> #include<cstdio> #include<cstring> #include<cmath&g…

P4552 [Poetize6] IncDec Sequence [Lisa](https://www.luogu.com.cn/problem/P4552) 从差分的方向考虑这个问题。那么显然只要考虑大于0的和小于零的。 那么最少的操作次数就是两类的和绝对值较大的。那么种类呢？从差分角度来想，后面的全是零了，那么只取决于第一个数是多少，那么剩下多…

P5785 [SDOI2012]任务安排 介绍 这个题我们分析一波P5785 [SDOI2012]任务安排 首先这个s很讨厌，不过我们可以把每一个批次的s的影响扔到后面去，对后面的产生而不是前面，然后写出dp方程 $f_i=f_j+s\times (sum_n-sumc_j)+sumt_i\times(sumc_i-sumc_j)$ 然后把只带 $…

Jennie 这东西叫01BFS 为了省事，我们决定每次把推了干草堆的放后面，没推的放前面。 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<deque> #include<…

Lisa 用所有路径的长度的和除以所有路径的种类就可以了. #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #def…