A fresh start.

题意有 $n(\le 5\times 10^5)$ 个区间,要从中选出 $m(\le 2\times 10^5)$ 个区间,要求存在一个点被覆盖了 $m$ 次,求最大区间长度与最小区间长度差值 的最小值。题解贪心,将所有区间按长度从小到大排序,答案一定是一段连续的区间。所以可以用线段树维护覆盖的次数,然后尺取法不断取被覆盖次数最大为 $m$ 的一段并更新答案。需要离散化预处理。需要注意区间长...
题解 数据结构-线段树
省选/NOI-
题意给出一个 $1..n(\le 10^5)$ 的全排列,有 $m(\le 10^5)$ 次操作,每次把 $[l,r]$ 中的数升序或降序排列。最后询问第 $q$ 个数是多少。题解只有最后一次询问,所以可以把操作离线处理。先考虑对一个 $0/1$ 串进行操作。升序排序就是把所有的 $1$ 挪到后面,降序就是挪到前面,可以用线段树解决。可以二分答案 $mid$ ,然后将 $< mid$ ...
题解 算法-二分/三分 数据结构-线段树
省选/NOI-
题意有 $n(\le 18)$ 只绿猪,位置在 $(x_i,y_i)$ 。每次可以从 $(0,0)$ 发射一只小鸟,开口向下的抛物线上的猪会被消灭。问至少要发射多少只小鸟。题解容易想到暴力的状压。用 $f(S)$ 表示消灭集合 $S$ 中的绿猪需要多少只小鸟,预处理出经过 $i,j$ 两只猪的抛物线可以消灭的猪 $s[i][j]$,枚举不在 $S$ 中的两只猪 $i,j$ ,方程式为:$$\...
题解 动态规划 动态规划-状压DP
提高+/省选-
DarkBzoj提交地址题意有 $N(\le 2000)$ 个农民, 他们住在 $N$ 个不同的村子里. 这 $N$ 个村子形成一棵树。每个农民初始时获得 $X$ 的钱。每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民。对于每个农民给定一个值 $v_i$, 求:最少需要多少次操作, 使得每个农民最终拿到的钱 $\geq$ 给定的值。题解有个结论:每条边最...
题解 动态规划 动态规划-树形DP
DarkBzoj提交地址:因为没有SPJ,所以需要特殊处理答案如下:if (ans) printf("%.10f",ans); else puts("0");题意某个公司有 $n(\le 5\times 10^5)$ 个人, 上下级关系构成了一个有根树,其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒...
题解 动态规划 动态规划-树形DP
题意给一个数字串 $s(|s|\le 10)$ 和正整数 $d(\le 1000)$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除(可以有前导 $0$)。题解$|s|$ 较小,考虑状压。用 $f(S,i)$ 表示下标集合 $S$ 内的数都用过了,当前数 $\equiv i\pmod d$ 。每次枚举一个不在 $S$ 的数 $j$ 加入转移,方程式为:$$f(S,i)\rightar...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意给一个 $n(\le 15)$ 个点 $m$ 条边的无向连通图(不存在自环或重边),每条边有一个边权,要求割掉若干条边,使 $1$ 到 $n$ 只有 $1$ 条路径(不经过重复点),问割掉的边权和最小是多少。题解可以发现最后图的形态一定是一条链,链上可能挂了若干个连通块,要最大化图的边权和。$n$ 比较小,考虑状压。用 $f(S,i)$ 表示目前链上的终点为 $i$ ,加入的点集为 $S...
题解 动态规划 动态规划-状压DP
NOI/NOI+/CTSC
题意有一棵 $n(\le 3\times 10^5)$ 个点的树和 $m(\le 3\times 10^5)$ 条路径,可以把一条边的边权改为 $0$ ,求所有路径长度最大值的最小值。题解求最大的最小值,可以二分答案 $mid$ 。可以发现如果路径的长度 $> mid$ ,那么路径上一定有一条边要被修改。所以修改的这条边需要覆盖所有长度 $> mid$ 的路径,并且边权要 $\g...
题解 数据结构-树链剖分 图论-LCA 图论-树上差分
省选/NOI-
由于一些玄学的原因,BZOJ最近上不去了。不过我从某群里得知可以通过它原来解析的IP地址访问,于是便有了这篇文章。查询BZOJ原来的IP地址,随便百度一下就出来了,如这个,可以看到历史解析为 61.187.179.132修改host,加上一行:61.187.179.132 www.lydsy.com然后就可以访问啦
笔记
题意自己去看吧太长了我懒得总结了题解可以发现,对一段路使用了加速器,那么在区间终点下车的乘客旅行时间都会 $-1$ 。所以可以预处理出每个点下车的人数 $q[i]$ 。预处理出最开始每个点的到达时间 $arr[i]$ 和 每个点最后到达的旅客时间 $last[i]$ 。如果使用加速器后能让下一段路的起点 $i$ 提前开车,即满足 $arr[i]-1<last[i]$ ,那么在下一段路的...
题解 算法-模拟 算法-贪心
提高+/省选-
题意一个圆的方程为 $x^2+y^2=r^2$ ,给出 $r$ ,问圆上有多少个点的坐标都是整数。题解可以用勾股定理的通解:$$x=d\dfrac{v^2-u^2}{2} \ , \ y=duv \ , \ r=d\dfrac{v^2+u^2}2$$枚举 $d$ ,就可以得到 $u^2+v^2$ ,再枚举 $u$ 就可以统计答案了。不过这样算出来的是第一象限内的解,所以最后答案要 $\tim...
题解 数学
省选/NOI-
题意有 $n(\le 150000)$ 个建筑需要修复,每个建筑有修复耗时 $t1$ 以及修复完成的截止时间 $t2$ ,问最多能修复多少个建筑。题解贪心。先把所有建筑按照截止时间排序,然后依次处理各个建筑。如果当前建筑还能修就修,否则就从之前修过的建筑里找到耗时最多的,如果比当前建筑的耗时多就替换掉。需要用堆维护。#include<bits/stdc++.h> using n...
题解 算法-贪心
提高+/省选-
我是傻逼,赛后D题加了一行就过了。。。A.Distinct Digits题意给出 $l,r(\le 10^5)$ ,求 $x\in [l,r]$ ,要求 $x$ 各数位均不同。题解数据范围小,直接暴力判断。#include<bits/stdc++.h> using namespace std; inline int read() { char ch=getchar()...
题解 比赛-Codeforces
题意对 $\forall i\in [1,n]$ ,求下式对 $123456789$ 取模的值$$\sum_{j=1}^n a_{\lfloor \frac{i}{j} \rfloor}\times b_{i \ \mathrm{mod} \ j}$$$n\le 10^5 \ , \ a_i,b_i\le 10^9$题解A了这题再随便打了下T3的暴力就rk18了。中途还突然把时限放宽到 $2...
题解 数学 算法-分块
题意求$$\sum_{i=1}^n k \ \mathrm{mod} \ i$$$n,k\le 10^9$题解经典的数值分块问题。原式可以化为:$$n\times k - \sum_{i=1}^n i\times \lfloor \dfrac{k}{i} \rfloor$$问题就转化为求 $\sum_{i=1}^n i\times \lfloor \dfrac{k}{i} \rfloor$可...
题解 数学 算法-分块
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces19 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2