标签:算法-差分

Codeforces Round #572 (Div. 2) 题解题意给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ,求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。题解利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数,那么答案就是 $\sum_{i=1}^\infty g(i)$ 。先把序列从小到大排序,这样...
题解 动态规划 算法-差分
NOI/NOI+/CTSC
题意有 $N$ 天,每天剩余教室为 $R_i$ 个。有 $M$ 个人要借教室,从 $S_i$ 借到 $T_i$ 。问能否满足所有人,如果不行则输出第一个不满足的人。$N,M\le 10^6$ 。题解本来还想写线段树查询最小值的,然后发现二分+差分就能解决。做法就是二分答案,然后差分修改后验证是否有 $<0$ 的。#include<bits/stdc++.h> using ...
题解 算法-二分/三分 算法-差分
提高+/省选-
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问,求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ,询问数 $M\le 50000$ 。...
题解 数据结构-树链剖分 算法-差分
NOI/NOI+/CTSC
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问,求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ,询问数 $M\l...
题解 数据结构-树链剖分 算法-差分
NOI/NOI+/CTSC
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA4 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集1 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces19 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2