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...
题意有 $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()...
题意对 $\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$可...
题意有 $n(n\le 5\times 10^5)$ 个人，如果两个人之间所有人的身高都不高于他们，他们就可以互相看见。问有多少对人可以相互看见。题解总感觉之前做过但又找不到，所以还是写下来记录一下。维护一个从大到小的单调栈，当前这个人 $i$ 可以和单调栈中所有 $h_j\le h_i$ 的人 $j$ 以及第一个比他高的人 相互看见。如果身高相同应该合并在一起。#include<bi...
双倍经验：洛谷4568，只需要改数据范围。题意有一个 $n(n\le 10000)$ 点 $m(m\le 50000)$ 边的无向图，可以将其中 $k(k\le 20)$ 条边的边权改成 $0$ ，求 $1\rightarrow n$ 的最短路。题解分层图最短路。将图分为 $k+1$ 层，同一层按给出的边连边；第 $i$ 层与第 $i+1$ 层之间也按给出的边连，但权值为 $0$ 。这样走到...
题意有一个 $m(m\le 20)$ 个点 $e$ 条边的无向图，有 $n(n\le 100)$ 个时刻需要从 $1\rightarrow m$ （保证可以到达）。每个点都有些时刻无法通行，如果更换道路还需要额外交 $k$ 元。求最小花费。题解用 $f[i]$ 表示前 $i$ 个时刻的最小花费，$x$ 表示最短路径。枚举与 $i$ 路径相同的区间起点 $j$ ，可以得到方程：$$f[i]=\...
题意给出 $n(n\le 100)$ 个单词，求一段长度不超过 $1000$ 的情书中出现了多少次这些单词，一句话中只统计一次。题解小清新模拟题，用 map 标记给出的单词以及当前这句话里是否出现过。#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); i...