widsnoy's blog

题目链接 很容易想到一个状态表示方法\(f[i][j]\)表示前\(i\)个点，最后一个高度为\(j\)时的最小花费。转移只用考虑上一个点填什么。 但是状态是表示不下的… 如果只有三个点，因为最左和最右不能改，那么中间的调整范围是\([\max (h-1-b,h-3-b),\min (h-1+b,h-3+b)]\)，因为要代价最小，显然只能不调整或者取端点的高度。 yy 一下，发现其实每个点情

题目链接 把时间轴作为一个轴，距离做纵轴。 每个外星人的信息都是一条水平线段。 问题变成选一些竖直线段，使穿过所有的水平线段。 可以发现如果一段直线移动到刚刚穿过最近的一个端点，不会影响穿过的线段，所以启发我们只需要管端点。 区间 dp \(f[l][r]\)表示\(l\)到\(r\)的最优答案。 每次决策只需要考虑最高线段在最高点哪个位置。 注意\(f\)数组要开两倍。 1234567891

题目链接 读入方式很新颖啊 把没人教的科目，只有一个人教的科目，和两个人教的科目状压一下。 设状态\(f[i][s0][s1][s2]\)为当前考虑了前\(i\)人每个科目的状况，还需要的最小花费。 每个人无非选和不选两种决策，记搜一下。 转移从后面一个人转移过来，好像有点诡异。 这道题好像很难正向转移的样子，因为 s2 表示的其实是大于等于 2 人的科目，所以正着转移很难表示旧的 s2。 而

题目链接 Problem 选取一些区间，使其区间交不小于\(k\)。 # Solution 区间交即是选出的区间的\([L-max,R-min]\)。将所有区间按左端点排序，枚举每一个区间(区间的\(r-l >= k\))将其左端点作为\(L-max\)。设之前右端点不小于\(L-max+k\)的区间有\(a\)个，对答案的贡献是\(2^a\)。可以用数据结构(比如支持单点修改和区间查询

题目链接 线段树维护\(\max\), \(sum\) 因为每个数最多被开根\(\log \log a-i\)次，所以直接暴力修改。 当某个区间所有数开根后值不变时不用再修改，即\(0\leq a-i\leq 1\)。 时间复杂度\(\mathjaxcal{O}(m\log n+n\log \log a)\) 123456789101112131415161718192021222324252

发现把数据结构忘得差不多了，赶紧补了一下 贴几篇讲得不错的博客，不打算再写一遍，骗访问量也要按基本法。 ## 主席树 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>using names

新科技 同余最短路 题目链接 先考虑后两种走法能走到的楼层. 按照模数分类, 具体\(f[i]\)表示最小的楼层使\(f[i]\bmod x=i\), 为什么要这样做呢？ 因为能到达的楼层无非就是\(ax+by+cz\) 我们当\(x\text{,}y\)固定时，方案数是\(\left\lfloor\frac{h-x-y}{z}\right\rfloor\) 我们考虑所有\(ax+by\)，都

题目链接 题解 简洁的做法是找出合法串的特点，直接判断。 目的是把串还原成 N 。 因为端点的 V 一定是由 NV 或者 VN 产生的，所以可以直接消掉。 同理对于连续的 V 也可以从端点开始消除成为 1 个 V。 而且连续的 N 一定也是不合法的，数学归纳法可以证明。 对于英文串，只要不单是 V 就一定合法。 中文串额外判断一下左端点是不是 N 。 代码 123456789101112131

题目链接 题目 求一个排列在\(1\)~\(N\)的全排列中的排名。 解析 从第一个数开始考虑，比它小的排列第一个数一定比它小，设为\(k\)个。 后面的数可以乱排，方案数是\(k\times (n-1)!\)。 后面的数同理，不能再用前面出现的数。 每一次都要找比当前数小的数个数，用权值树状数组维护。 时间复杂度\(\mathjaxcal{O}(n\log n)\) 代码 123456789

自己出了一道题，感觉挺有意思的。 题目 一个长度为\(n\)的序列，将每个子序列的权值定义为\(\min(a-l,a_{l+1},...,a-r)\times \max(a-l,a_{l+1},...,a-r)\)。 对于所有长度不小于\(k\)的连续子序列，要你求出一段权值严格次大的子序列。如果不存在这样的子序列，输出最大的权值。 题解 因为总是会有一个数作为最小值，所以直接枚举每个数作为区