君の脈で踊りたかった

October 16, 2019

洛谷P2513/HAOI2009 逆序对数列

题解求$1 \sim n$的全排列中逆序对数为$k$的数量数据范围:$n,k \le 1000$题解用$f[i][j]$表示$1 \sim i$的全排列中逆序对数为$j$的数量考虑将$i$插入$1 \sim i-1$的数列中。因为$i$比该数列中所有数都大,所以$i$放在哪里都能产生贡献,贡献的范围为$i-1$(放在首位)$\sim 0$(放在末位),可得状态转移方程$$f[i][j]=\s...
October 16, 2019

洛谷P1776 宝物筛选

题意多重背包数据范围:$0 \le w \le 4 \cdot 10^4,1 \le n \le 100$题解设$w$为价值,$v$为体积,$c$为数量多重背包的状态转移方程为$$f[i][j]=\max(f[i-1][j-kv]+kw)$$其中$k \in [1,c]$由于$i$一定从$i-1$转移而来,所以第一维可以去掉$$f[j]=\max(f[j-kv]+kw)$$但是这样$dp$的...
October 16, 2019

洛谷P2569/SCOI2010 股票交易

题意略数据范围:$0 \le w,t \le 2000,1 \le p \le 2000,1 \le bp_i \le ap_i \le 1000,1 \le as_i,bs_i \le p$题解算法:动态规划用$f[i][j]$表示第$i$天持有$j$股股票,前$i$天的最大收益首先,若从第$i$天开始买股票,有$$f[i][j]=-ap_i \cdot j$$其中$j \in [0,as...
October 15, 2019

洛谷P3616 富金森林公园

题意对于一个数列,有$2$种操作:$1 \ x$ 询问$\ge x$的连续段的个数$2 \ i \ x$ 将$a_i$的值修改为$x$数据范围:$1 \le n,m \le 200000,1 \le a_i,x \le 10^9$题解首先对于一个询问考虑:将$\ge x$的数定义为$1$,$< x$的数定义为$0$;那么一个段的构成应为$$011 \dots 110$$即一个$01$+...
October 14, 2019

CF1244E Minimizing Difference

题意给出$n$个数,每次操作可以选择一个数$+1$或$-1$,求$k$次操作后最小极差数据范围:$2 \le n \le 10^5,1 \le k \le 10^{14}$题解为了减小极差,每次肯定是选择最大值$-1$或最小值$+1$,所以先排个序为了快速转移,可以将$a[i]$变为$a[i+1]$(对于前半部分)或将$a[i]$变为$a[i-1]$(对于后半部分);而当$k$值不足以进行一...
October 14, 2019

CF1244C The Football Season

题意求解$$ \left\{ \begin{aligned} & wx+dy=p \\ & x+y \le n \\ & x,y\ge 0 \end{aligned} \right. $$的一组解$(x,y)$数据范围:$2 \le n \le 10^{12},1 \le p \le 10^{17},1 \le d < w...
October 13, 2019

洛谷P3848/TJOI2007 跳棋

题意略数据范围:$1 \le n \le 100$题解数据范围较小,可直接$dfs$越过连续$1$为int nx=x+v[i][0],ny=y+v[i][1],cnt=1; for(;nx>=1 && nx<=n && ny>=1 && ny<=n && a[nx][ny];nx+=v[i][0],ny+...
October 13, 2019

洛谷P2572/SCOI2010 序列操作

题意对于一个$01$序列,有$5$种操作:$0 \ a \ b$ 把$[a,b]$区间内的所有数全变成$0$$1 \ a \ b$ 把$[a,b]$区间内的所有数全变成$1$$2 \ a \ b$ 把$[a,b]$区间内的所有数全部取反$3 \ a \ b$ 询问$[a,b]$区间内总共有多少个$1$$4 \ a \ b$ 询问$[a,b]$区间内最多有多少个连续的$1$对于每个询问,输出答...
October 13, 2019

洛谷P3287/SCOI2014 方伯伯的玉米田

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

洛谷P4163/SCOI2007 排列

题意给一个数字串$s$和正整数$d$, 统计$s$有多少种不同的排列能被$d$整除数据范围:$s$的长度$\le 10,1 \le d \le 1000$题解直接计算整除的较为麻烦,可以状压使用过的数$d$并记录当前数模$d$的余数,再来表示方案数用$f[i][j]$表示选用过的数状态压缩为$i$,当前余数为$j$易得状态转移方程$$f[i|(1<<j)][(k*10+a[j])...