Ptilopsis_w's little blog

Rainbow Rectangles 先枚举上下边界 up,downup,downup,down，考虑有多少满足条件的 l,rl,rl,r，如果直接枚举 lll 然后算 rrr 的话时间至少是 O(n3log⁡n)O(n^3 \log n)O(n3logn) 的，但是可以倒着枚举上下边界，把加点改成删点，这样的话之前算出来的答案可以转移到现在，时间复杂度 O(n2log⁡n)O(n^2 \log n)O(n2logn) 。 #include <algorithm>#include <cmath>#include <cstdio>#include <iostream>#include <set>#include <vector>using namespace std;#define int long long typedef long long ll;const int N = 2e3+10;const int P = 1e9+7;int n, k, L; ll ans;int x[N], y[N], col[N]; ...

猫 CF311B 首先猫在哪个位置是没有影响的，重要的的是猫开始等的时间。 我们可以让每只猫的 ttt 减去它到起点的距离，也就是人最晚的可以使这只猫不等待的出发时间。 我们将这个时间记为数组 aaa，很明显正好接到 aaa 大的猫也可以接到 aaa 小的猫(只是需要等待)，所以我们将 aaa 从小到大排个序，就可以让每个人接到的猫在 aaa 中是连续的一段，然后就可以 DP 了。 设 f(i,j)f(i,j)f(i,j) 表示前 iii 个人接前 jjj 只猫，且第 iii 个人正好接到第 jjj 只猫的最小等待时间。 DP 方程就比较好列了: f(i,j)=min⁡0≤k<j{f(i−1,k)+∑s=k+1j(aj−ak)}f(i,j) = \min_{0 \le k < j} \left\{ f(i-1,k) + \sum_{s=k+1}^{j}(a_j-a_k) \right\} f(i,j)=0≤k<jmin​{f(i−1,k)+s=k+1∑j​(aj​−ak​)} 前缀和一下，式子就变成了: f(i,j)=min⁡0≤k<j{f(i−1,k)+(j− ...

题目 n≤8n \le 8n≤8，考虑搜索，但是直接爆搜的计算次数最坏在 328=24032^8=2^{40}328=240 级别，无法接受。 考虑平衡一下，使用折半搜索，然后用双指针合并答案，计算次数 2202^{20}220，可以通过。 #include <algorithm>#include <cstdio>#include <iostream>using namespace std;typedef long long ll;const int N = 10;const int SIZE = 1.5e6+10;int n, s, a[N];ll tmp[2][SIZE];int cnt[2], lim;void dfs(int x, ll sum, int type);int main(){ cin >> n >> s; for(int i = 1; i <= n; i++) cin >> a[i]; lim = n/2, dfs(1, 0, 0); ...

squence 考虑静态版本的做法。 只考虑一种单峰，另一种是一样的。 交换次数是对应原数组下标的逆序对个数。 从小到大排序后从两边向中间加数，可以放前面或后面。 贡献是对中间还没有加入的数的逆序对个数，也就是没放的数中 下标比它大的 比 下标比它小的 更多就放前面，否则放后面。 插入一个数，考虑它的影响。 它的下标一定是最大的，肯定放后面，本身不产生贡献。 但在它前面加入且放后面的数贡献+1，且一些放后面的数会改放前面。 对于每个数找到它改放在前面的时刻。 此时没放的数中 下标比它大的 超过 下标比它小的，下标比它小的数不会变化，也就是要找下标比它大的数中第k个值比它大的数的下标。。 写个 bit 维护一下就行了。 #include <algorithm>#include <cstdio>#include <cstring>#include <iostream>#include <vector>using namespace std;const int N = 3e5+10;typedef long long ll;stru ...

环境准备 安装 node.js 和 git。 然后再注册一个 github 账号。 搭建博客 选择目录 随便找一个目录，新建一个文件夹，比如我这里就在 E 盘根目录下新建了一个 blog 文件夹，然后进入这个文件夹，右键，选择 git bash here 打开 git bash。 安装 Hexo 在 git bash 中输入: npm install -g hexo-cli 装好之后是这样： Hexo 初始化和本地预览 初始化并安装所需组件： hexo initnpm install 如果命令执行失败可以尝试科学上网。 执行完之后的样子： 这时候我们就有一个最基础的博客了，可以输入下面的命令在本地预览 hexo generate # 生成页面, 可以缩写为 hexo ghexo server # 在本地启动预览服务器, 可以缩写为 hexo s 这时候在浏览器里打开 http://localhost:4000 ，出现 Hexo 默认主题的页面，本地博客安装成功! 效果图: 添加/修改文章 写文章可以在 Hexo 根目录下的 /source/_posts/ 里写文章，里面有个默 ...

小D的序列 乱搞过的（ 题目给了一个等比数列，我们可以用小学二年级就学过的等比数列求和公式 check 一下每个数作为公比的时候是否与真实的 sum 值相等。时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)。 #include <cstdio>#include <iostream>#include <unordered_set>using namespace std; typedef long long ll;const int N = 2e5+10; int n, p;ll a[N]; ll qpow(ll a, ll b); int main(){ cin >> n >> p; for(int i = 1; i <= n; i++) cin >> a[i]; ll sum = 0; for(int i = 1; i <= n; i++) (sum += a[i]) %= p; for(int i = 2; i & ...

分组 将字符串反转一下，后缀就变成前缀了，然后就可以扔到 trie 树上了，考虑统计子树和，我们就可以知道某一个前缀可以匹配多少个字符串了，然后贪心一手，尽量能匹配的前缀都匹配上就行了。 #include <cstdio>#include <iostream>using namespace std; typedef long long ll;const int N = 1e6+10; namespace Prime { bool vis[N]; int prime[N], pcnt; int d[N]; void getprime(int n) { for(int i = 2; i <= n; i++) { if(!vis[i]) prime[++pcnt] = i, d[i] = i; for(int j = 1; j <= pcnt and i*prime[j] <= n; j++) &# ...

奇数计数 如果 k=1k=1k=1 的话，直接求出序列的异或和，偶数都会两两消掉，所以剩下的就是那个出现了奇数次的数。 如果 k=2k=2k=2 的话，先求出序列的异或和，然后记录一个数组 t[]，如果 aia_iai​ 的第 jjj 位为 111 的话，就令 t[j] ^= a[i]，然后找到 sss 为 111 的某一位，因为 sss 是某两个数异或得到的值，所以 sss 某一位为 111 的话，必定是其中只有一个数这一位为 111 ，此时的 t[j] 即为其中一个数，另一个数就是 s^t[j] 。 #include <cstdio>#include <iostream>using namespace std;int n, k;int s, t[32];int main(){ cin >> n >> k; for(int i = 1, x; i <= n; i++) { cin >> x; s ^= x; for(int j = ...

序列问题 设 f(i,j)f(i,j)f(i,j) 为前 iii 个数中选出了 jjj 个数的最大值，时间复杂度 O(n2)O(n^2)O(n2) 考虑优化一下上面那个东西，如果 Ai>iA_i > iAi​>i, 那么这个数一定无法造成贡献，直接忽略即可。 设 f(i)f(i)f(i) 为将第 iii 个数作为 BBB 序列最后一个数且造成 111 贡献的最大值。 考虑由 f(j)f(j)f(j) 转移至 f(i)f(i)f(i) 的条件： j<ij < ij<i Aj<AiA_j < A_iAj​<Ai​ Ai−Aj≤i−jA_i-A_j \le i-jAi​−Aj​≤i−j 可以将其看作三维偏序问题，使用 CDQ 分治优化 DP, 时间复杂度 O(nlog⁡2n)O(n \log^2 n)O(nlog2n)，但是过不去。 仔细观察条件，发现满足条件 2,3 一定可以满足条件 1，然后就变成一个二维的问题了，可以先按 AiA_iAi​ 排序，然后求一个 i−Aii-A_ii−Ai​ 的最长不下降子序列，其长度即为 ...

树点编号 因为需要保证任意的删除顺序都保证图联通，所以白色黑色分别只能构成一个联通块。 我们直接在树上 dfs 一遍找出子树大小为 aaa 或者 bbb 的一棵子树，将其染成相应的颜色，剩下的部分染成另一个颜色即可，因为每次删除编号绝对值最小的，所以按后序遍历分配编号即可。 #include <cstdio>#include <iostream>#include <vector>using namespace std;struct Rhine_Lab { Rhine_Lab() { freopen("tom.in", "r", stdin); freopen("tom.out", "w", stdout); }};Rhine_Lab Ptilopsis_w;const int N = 1e5+10;int n, a, b, rt;int sub, type;int cnta, cntb; ...