A.Equalize Prices Again过水已略。B.Social Network题意题解用一个队列维护显示的消息，再开个 map 记录是否在队列中即可。#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
whil...
题意环上有 $m(\le 10^9)$ 个点，有 $n(\le 2\times 10^5)$ 个人可以从 $l_i\rightarrow r_i$ 。对于所有的 $i\in [1,n]$ ，询问如果第 $i$ 个人必须选且为起点，至少要选多少人才能绕完一圈。题解首先断环成链。容易想到贪心，每次选 $l_i\le $ 当前的 $r$ ，$r_i$ 最大的 $i$ 作为下一步。一步一步跳是 $O...
题意有一个长为 $n(\le 256)$ 的数组 $a$ ，第 $i$ 个数有权值 $b_i$ 。从中选取 $K$ 个点 $c_j$ ，把 $a$ 上的数都移过去，代价为 $\sum (a_i-c_j)^2\times b_i$ 。求最小代价。题解非常暴力的DP。用 $f[i][j]$ 表示前 $i$ 个数选了 $j$ 个点，其中第 $i$ 个点选的最小代价。预处理选取 $i,j$ 后 $(...
题意给出一个 $n(\le 10^5)$ ，求集合 $\{1,2,...,n\}$ 的满足：若 $x$ 在集合中，则 $2x$ 和 $3x$ 不能出现在集合中 的子集个数。题解可以构造一个矩形，横向依次 $\times 3$ ，纵向依次 $\times 2$ ，如下图所示：1 3 9 27 81 243
2 6 18 54 162 486
4 12 36 108 324 972在这个矩形中选...
题意有 $n(\le 5\times 10^5)$ 个区间，要从中选出 $m(\le 2\times 10^5)$ 个区间，要求存在一个点被覆盖了 $m$ 次，求最大区间长度与最小区间长度差值 的最小值。题解贪心，将所有区间按长度从小到大排序，答案一定是一段连续的区间。所以可以用线段树维护覆盖的次数，然后尺取法不断取被覆盖次数最大为 $m$ 的一段并更新答案。需要离散化预处理。需要注意区间长...
题意给出一个 $1..n(\le 10^5)$ 的全排列，有 $m(\le 10^5)$ 次操作，每次把 $[l,r]$ 中的数升序或降序排列。最后询问第 $q$ 个数是多少。题解只有最后一次询问，所以可以把操作离线处理。先考虑对一个 $0/1$ 串进行操作。升序排序就是把所有的 $1$ 挪到后面，降序就是挪到前面，可以用线段树解决。可以二分答案 $mid$ ，然后将 $< mid$ ...
题意有 $n(\le 18)$ 只绿猪，位置在 $(x_i,y_i)$ 。每次可以从 $(0,0)$ 发射一只小鸟，开口向下的抛物线上的猪会被消灭。问至少要发射多少只小鸟。题解容易想到暴力的状压。用 $f(S)$ 表示消灭集合 $S$ 中的绿猪需要多少只小鸟，预处理出经过 $i,j$ 两只猪的抛物线可以消灭的猪 $s[i][j]$，枚举不在 $S$ 中的两只猪 $i,j$ ，方程式为：$$\...
DarkBzoj提交地址题意有 $N(\le 2000)$ 个农民, 他们住在 $N$ 个不同的村子里. 这 $N$ 个村子形成一棵树。每个农民初始时获得 $X$ 的钱。每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民。对于每个农民给定一个值 $v_i$, 求：最少需要多少次操作, 使得每个农民最终拿到的钱 $\geq$ 给定的值。题解有个结论：每条边最...
DarkBzoj提交地址：因为没有SPJ，所以需要特殊处理答案如下：if (ans) printf("%.10f",ans);
else puts("0");题意某个公司有 $n(\le 5\times 10^5)$ 个人, 上下级关系构成了一个有根树，其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒...
题意给一个数字串 $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...
题意给一个 $n(\le 15)$ 个点 $m$ 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 $1$ 到 $n$ 只有 $1$ 条路径（不经过重复点），问割掉的边权和最小是多少。题解可以发现最后图的形态一定是一条链，链上可能挂了若干个连通块，要最大化图的边权和。$n$ 比较小，考虑状压。用 $f(S,i)$ 表示目前链上的终点为 $i$ ，加入的点集为 $S...
题意有一棵 $n(\le 3\times 10^5)$ 个点的树和 $m(\le 3\times 10^5)$ 条路径，可以把一条边的边权改为 $0$ ，求所有路径长度最大值的最小值。题解求最大的最小值，可以二分答案 $mid$ 。可以发现如果路径的长度 $> mid$ ，那么路径上一定有一条边要被修改。所以修改的这条边需要覆盖所有长度 $> mid$ 的路径，并且边权要 $\g...
由于一些玄学的原因，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...