题意用 $K$ 进制串 $S_i$ 表示 $N$ 个不同的单词。每个单词出现了 $W_i$ 次，不存在某个进制串是另一个的字串。求处理后全文的最短长度，以及此情况下最长 $S_i$ 的最短长度。题解编码方式显然是一棵 $K$ 叉哈夫曼树，先补 $0$ 直到 $(N-1)\equiv 0\pmod {(K-1)}$ ，然后每次选 $K$ 个点合并成一个点直到只剩 $1$ 个点即可。要求最长的 ...
四倍经验（1蓝2紫1黑）：P3620，SP1553，P1484，P1792题意将 $N$ 个办公楼两两配成 $K$ 对，要求这 $K\times 2$ 栋楼相异。所有办公楼在一条直线上，配对的两栋楼之间需要连接电缆，求电缆长度的最小值。$N\le 100000$ 。题解显然，配对相邻的两栋楼是最优的。将边看成点来考虑，题目即转化成：在 $N$ 个点中选 $K$ 个不相邻的点，使得点权最小。每...
题意需要用双端队列实现 $N$ 个数的排序。依次处理每一个数，每次只能将数放在队首或队尾，或新建一个队列。求需要的最少双端队列数。$N\le 200000$ 。题解将原数列排序，可以得到 新数列对应原序列下标 的序列。如：原序列下标序列$[3,6,0,9,6,3]$$[1,2,3,4,5,6]$$[0,3,3,6,6,9]$$[3,1,6,2,5,4]$可以发现只有下标序列的一段满足先递减再...
终于把这道一直85分懒得搞的题过了。题意最开始有 $n$ 只蚯蚓，每秒把最长的那条蚯蚓砍成两段，比例为 $p:(1-p)$ 。同时所有蚯蚓每秒增加 $q$ 的长度。求每 $t$ 秒最长的蚯蚓长度，以及 $m$ 秒后排名为 $k\times t$ 的蚯蚓长度。$n\le 10^5 \ , \ m\le 7\times 10^6$题解先对所有蚯蚓长度从大到小排序。将蚯蚓队列、$p$ 和 $(1-...
题意给出一个基环森林，求所有基环树的直径之和。点数 $N\le 10^6$ 。题解思想先考虑求一个基环树的直径。设 $\text{f[i]}$ 是 $i$ 向环外延伸的最长距离，直径有两种情况：不经过环，答案为环的子树直径，即 $\mathrm{max}(\text{f[x]}+\text{f[y]}+w)$ ，其中 $x,y$ 是子树中两点，$w$ 是两点距离。经过环，则答案为 $\mat...
题意求 $N$ 点无向图的最小生成树，满足 $1$ 号节点度数 $\le s$ 。$N\le 30$ 。题解思想考虑构造一个以 $1$ 号节点为根的树，则 $1$ 号节点必须与子树中所有连通块相连。记录去掉 $1$ 号节点后的连通块个数，即 $1$ 号节点的最小度数，为 $tcnt$ 。（题目保证有解即 $tcnt\le s$）对每个连通块分别求出最小生成树，这样就得到了除 $1$ 号节点外...
题意$n\times n$ 的格点中站了 $n$ 个人，要让他们站在一排，求最少的移动次数。$n\le 100000$ 。题解选择第几排显然是取所有人 $y$ 坐标的中位数最优。移动到相应位置显然，按照 $x$ 的坐标顺序安排这一排内的顺序是最优的，所以先对 $x_i$ 进行第一次排序。但这样还是需要移动到不同位置，于是处理 $x_i-i$ ，这样就相当于移动到同一位置了，取中位数即可。代码...
题意给出两组点，求两组点间的最近点对。每个组中点数 $N\le 1000$ ，坐标 $x,y\le 10^9$ 。题解按 $x$ 坐标分治，并且对分别属于左右块的点对单独处理。注意数组需要开两倍。#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
c...
题意在 $[0,m]$ 中选一个数，使得它经过给定的 $n$ 个 &、|、^ 操作后得到的数最大。$2\le m\le 10^{9} \ , \ 2\le n\le 10^{5}$ 。题解所有数都 $\le 2^{30}$ ，而且修改都只涉及二进制的修改，所以对每一位进行贪心。用 $s_0$ 代表最初全为 $0$ 的数在操作后每一位的值；用 $s_1$ 代表最初全为 $1$ 的数在操...
题意给出 $n$ 个数，求逆序对个数。其中 $n\le 500000$ ，每个数 $\le 999,999,999$ 。题解数的范围很大，所以直接用树状数组肯定不行。但事实上我们只关心数之间的顺序，所以排序后用 $\text{ord[]}$ 记录顺序即可。#include<bits/stdc++.h>
#define ll long long
using namespace s...
题意从 $m$ 部电影中选出 $1$ 部给 $n$ 个人看。每部电影的配音和字幕都使用的不同的语言，每个人只掌握一种语言，用 $1\le id\le 10^{9}$ 的数表示不同语言。对于选出来的电影，如果某人能听懂配音，他会非常高兴；如果能看懂字幕，他会比较高兴。问：选择哪部电影，使得非常高兴的人最多；如果一样多，应使比较高兴的人最多。$n,m\le 200000$ 。题解显然可以对每部电...
题意给出一个 $5\times 5$ 的 $0/1$ 矩阵，每次点击某一个点会改变自身及上下左右的状态。求把矩阵全部变为 $1$ 的最少步数。多组数据，组数 $N\le 500$ 。题解考虑逐行递推，如果上一行 $(i,j)$ 是 $0$ ，那么就需要点击当前行的 $(i+1,j)$ 。最后校验最后一行是否全为 $1$ 即可。但第 $1$ 行没有上一行，所以我们需要枚举第 $0$ 行的状态，...
题意定义图的连通数是每个点可以到达的点数之和，求一个有向图的联通数。其中点数 $N\le 2000$ 。题解显然直接用 $\text{Floyd}$ 传递闭包是不现实的，于是我直接照题解用了bitset。用 bitset $\text{s[i]}$ 表示 $i$ 与 $N$ 个点的连通情况。直接双重循环枚举用 | 合并起来即可。需要注意自己和自己也要算，但给出的矩阵是不算的，所以需要写在后面...
题意给出一个无向图，有下列操作：$(1,a,b)$ ，查询 $a\rightarrow b$ 路径上桥的数量$(0,a,b)$ ，删除边 $(a,b)$ 。保证无论航线如何被破坏，任意时刻任意两点都能够相互到达。其中点数 $N\le 30000$ ，边数 $M\le 100000$ ，操作数 $Q\le 40000$ 。题解显然，桥的数量就是缩完点后两点间的树上距离，动态询问树上距离显然就是...
题意给出一个有向图，有边权 $w_i$ 和点权 $s_i$ 。要求找一个环，使 $\dfrac{\sum s_i}{\sum w_i}$ 最大。其中点数 $N\le 1000$ ，边数 $M\le 5000$ 。题解$0/1$ 分数规划。设当前二分值为 $mid$ ，题目即为$$\dfrac{\sum s_i}{\sum w_i} > mid$$$$\sum (s_i-mid\time...