2021年10月

October 12, 2021

洛谷P3572 [POI2014]PTA-Little Bird

题意从$1$开始,跳到比当前矮的不消耗体力,否则消耗$1$点体力,每次询问有一个步伐限制,求每次最少耗费多少体力数据范围:$2 \le n \le 1000000$题解用$f[i]$表示前$i$个的步数,易得状态转移方程$$ f[i]=\min_{j=i-k}^{i-1}\left\{ \begin{aligned} &f[j] &a[j] > a[i]...
October 12, 2021

洛谷P3492 [POI2009]TAB-Arrays

题意给出两$n \times m$的矩阵,保证每个矩阵内元素互不相同且权值均在$[-10^6,10^6]$之间,请能否把其中一个矩阵通过若干次交换两行或者交换两列的操作变成另外一个矩阵数据范围:$1\le n,m \le 1000$题解结论:任何一行/列中的元素不会变暴力判断即可代码:#include<iostream> #include<cstdio> #inclu...
October 12, 2021

洛谷P3287 [SCOI2014]方伯伯的玉米田

题意有$n$个数,可以进行$k$次操作,每次操作可以选择一个区间让每个数$+1$,求最后最长不下降子序列长度数据范围:$1 \le n \le 10000,1\le k \le 500$题解首先明确一个事实:每次操作的区间的右端点一定是$n$容易证明:这样不会使答案变小,并且如果不这样可能会使答案变小用$f[i][j]$表示第$i$个数已经被操作了$j$次,当前的答案,状态转移方程为$$f[...
October 12, 2021

洛谷P3258 [JLOI2014]松鼠的新家

题意树上操作$u$到$v$的路径上权值$+1$询问每个点的权值数据范围:$2 \le n \le 300000$题解树剖裸题注意每次的终点作为下次的起点,会多$+1$,记得$-1$;最后一次也是,题目有特殊要求代码:#include<iostream> #include<cstdio> using namespace std; #define ls rt<<...
October 12, 2021

洛谷P3084 [USACO13OPEN]Photo G

题意有$n$头奶牛,$m$条约束$(a_i,b_i)$,表示$a_i$到$b_i$间有且仅有一头带斑点的奶牛,求最多可能有多少只斑点奶牛数据范围:$1 \le n \le 200000,1 \le m \le 100000$题解将有且仅有一头拆解为至多一头+至少一头初步思路为差分约束,但明显复杂度过高发现可以$dp$,用$f[i]$表示第$i$头奶牛有斑点的情况下前$i$头奶牛最多有多少斑点...
October 12, 2021

洛谷P3067 [USACO12OPEN]Balanced Cow Subsets G

题意给出$n$个数,从中选出一些,求选出的数能分成相等的两份的方案数数据范围:$2 \le n \le 20$题解对于每个元素,无非$3$种状态:$0$ 不选$-1$ 左$1$ 右但直接搜索复杂度达到$O(3^n)$考虑折半搜索将组合二进制压缩,前半搜索记录下可能的$sum$,后半搜索从前半中找到相等的$sum$(其实是找$-sum$,但是是等价的),则此种选择方案成立由于$sum$较大,需...
October 12, 2021

洛谷P2890 [USACO07OPEN]Cheapest Palindrome G

题意给出小写字母组成的字串,要求增删字母使其变为回文串,增删不同字母的花费不同,求最小花费数据范围:$1 \le L \le 2000$题解用$f[i][j]$表示将区间$[i,j]$修改为回文串的最小花费,显然有$$f[i][i]=0$$当$s[i]=s[i+1]$时有$$f[i][i+1]=0$$因为要从小区间转移到大区间,$f[i][j]$可以从$f[i+1][j]$或$f[i][j-...