在与机房大佬们的合作下，rk89，rating+=140。题解代码中省略的程序头：#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define ha 1000000007
#define ui unsigned int
#de...
题意给出黑点白点各 $n(\le 100)$ 个，要求一个黑点连接一个白点，并且所有线段都不相交。题解所有线段不相交 $\rightarrow$ 两两连最近的点 。那么把距离变成负数就是KM算法裸题了，但这道题有个神奇的坑点：如果在 find() 里更新顶标的偏移值 d ，就会T；而改在外面更新就A了。我也不知道为什么，看来以后得改下KM算法的写法了。#include<bits/std...
Codeforces Round #572 (Div. 2) 题解题意给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ，求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。题解利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数，那么答案就是 $\sum_{i=1}^\infty g(i)$ 。先把序列从小到大排序，这样...
A.Keanu Reeves题意题解显然答案最多为 $2$ 。如果本来就不一样多，答案就是 $1$ ；否则把第一个数划出去即可，答案为 $2$ 。#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch&l...
赛前，ljq：不得了，6个人开黑，上紫稳了啊。10+min过去，大家都A了2道，ljq：这场怕不是要AK。最后辣鸡C题，毁我青春。不过还是得怪做题策略有问题，如果直接跳过C去做DE应该都能A掉，这次就算是用rating买教训了。A.Pens and Pencils过水已略B.Rooms and Staircases题意我相信过不了多久洛谷上就会有翻译了题解可以发现答案一定是从某一端出发，到达...
题意有 $n(\le 50)$ 个人用 $m(\le 50)$ 张卡牌玩游戏。第一局由玩家 $1$ 坐庄抽卡，如果卡上的数字是 $x$ ，那么从他的位置数第 $x$ 的人就被处决。第二局就由被处决的人的后一个人坐庄，以此类推，最后剩下的玩家获得胜利。求每个玩家的胜率。题解概率DP，用 $f[i][j]$ 表示还剩 $i$ 个人，从坐庄的人往后数第 $j$ 个人的胜率。如果只剩 $1$ 个人，...
2019-10-12 题解 动态规划
提高+/省选-
题意要求构造一个长度为 $n(\le 10^{15})$ 的 $0/1$ 环形序列，满足任意连续 $m(2\le m \le 5)$ 个数的和不超过 $k$ 。求方案数。题解$m$ 比较小，可以状压。可以发现答案其实就是把一个状态往后推 $n$ 次，最后回到自己的方案数。两个状态之间的转移关系 $s[i][j]$ 可以提前预处理出来，然后把 $s$ 看成一个矩阵，合法状态 $i$ 对答案的贡...
题意一棵 $n(\le 50000)$ 个点的树，有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守，军队可以同时移动，每小时移动 $1$ 单位长度。问至少要多久才能满足条件，无解输出 -1（没有）。题解答案显然满足单调性，所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)如果军队 $i$ 在根节点...
A.SwapSort题意题解先离散化，然后第 $i$ 位把 $i$ 换过来就行了。#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1...
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$ ...