题意简述n个房间，有一只老鼠可能出现在任意一个房间，并且老鼠在第i个房间出现时，下一秒就会运动到第ai个房间。需要放陷阱确保老鼠不管在哪里出现都会被抓。在第i个房间放陷阱成本ci，输出最少需要多少成本完成题目要求（vjudge翻译）（又是蒯的） 思路框架我们把$i$向$a_i$连边，就得到了老鼠的走 ...

题意简述给定一个序列a，长度。定义一个区间[l,r]的得分为这段区间内不同的数的个数。请你将这个序列划分成k(段，使得每段的分数加起来最大。 思路设dp[j][i]表示前i个分成了j段的最大得分和，d(l,r)表示[l,r]内不同的数个数，那么（这里不知为啥公式爆了，看图凑合一下），其中p枚举前面的 ...

题意简述给定一个长度为n(的序列a，还有两个人。第一个人会选择一对相邻的逆序对交换，第二个人会抛硬币（假设是完全等概率的）决定是交换一对相邻逆序对还是交换一对相邻顺序对（顺序对，即不是逆序对的一对数）。求期望多少步排好序。 思路设逆序对数为x，若x为偶数，答案为2x，否则答案为2x-1。 具体思路设 ...

（PS：洛谷上5789是加强版，3758是可以dp水过的原版）（本文讲最优做法，能通过加强版的） 题意简述有$n$个点$m$条边的无向图，你有一个机器人，从点$1$开始走。每次可以：停留在原地，自爆（就不能继续走了），选一个相邻的点继续走。边珂以重复经过。问你走$k$步有多少种情况。答案对$2017 ...

题意简述T组数据。每次给定n，求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\phi(gcd(i,j))$n<=10^7，T<=5000。 （用T根号n的算法就能过了） 思路框架把gcd换掉，然后用[SDOI2008]仪仗队（洛谷 bzoj）的 ...

题意简述给定一颗$n<=20000$个点的树，点带点权，不超过$2^{60}$。还有$Q<=200000$个询问，每次询问两个点之间路径上的最大异或和。 思路$B[i][k]$表示从$i$往上$2^k$个节点组成的线性基。$LCA$的时候线性基合并就珂以了。带三个log，两个是$log2 ...

题意简述给你一个数字字符串$S$，长度为$n<=1e5$。有一个$int$范围内的质数$P$和$Q<=1e5$次询问，每次询问一个区间$[l,r]$中，$S$的多少个子串（不一定不同）是$P$的倍数。 比如$S=”007”$，它有6个子串，分别是$\{0,0,00,07,007\}$，这 ...

题意简述给你一颗n<=1e5个节点树，1e5次询问，每次给你(l,r,z)，求[l,r]区间内每个数和z在树上LCA的深度的和。对201314取膜。 注：根节点深度是1。 思路框架(x,y)的LCA深度就是，把x到根点权+1，然后询问根到y点权和多少。 那么我们相当于，把[l,r]每个点到根点 ...

题意简述一个$n\times m$的矩阵，每个位置珂能是粉色（0表示）或者是蓝色（1表示），然后你珂以对同一行里连续一段长度的区间染上一种颜色（覆盖型），你能染$t$次，每次不限长度。求你染到的正确的颜色的个数最多是多少。 思路框架$f[i][j]$表示前$i$行染$j$次最大染色个数。$g[i][ ...

题意简述给定一个$n<=1e5$，构造一颗$2n$个节点的数。其中，点$i$和$i+n$上都带点权$i$，并且满足：对于$1<=i<=n$，$i$到$i+n$的路径上（包括两端点），所有点权的异或和为$i$。 举例：i=3，构造图如下：其中，4,5,6的点权分别是1,2,3。不难验 ...