题意求 $N\times M$ 的矩阵中最大的 $0/1$ 相间的长方形和正方形面积。$N,M\le 2000$ 。题解悬线法，把是否是障碍物的判断改成相邻格子是否相同即可。#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
...
题意有两个序列 $a,b$ ，可以把 $b$ 中相邻的数交换，使得 $\sum (a_i-b_i)^2$ 最小。问最少要交换几次？题解可以发现最小的情况就是 $a,b$ 中数字的大小顺序相同，所以离散化后建立 $a$ 中大小在 $b$ 的对应关系 $s$ ，求 $s$ 的逆序对个数即可。#include<bits/stdc++.h>
#define ha 99999997
us...
题意给出一个 $N$ 点 $M$ 边的有向图，以及 $K$ 个感兴趣的点，求感兴趣的点两两之间最短路的最小值。$N\le 100000 \ , \ M\le 500000$ 。题解如果建立原点和汇点，把 $K$ 个点分成两组，分别与原点汇点相连，再从原点开始跑到汇点的最短路就是最小值。但这样显然无法涵盖所有情况。所以枚举二进制位，把当前位为 $1$ 的加入第一组，其它的放入第二组。因为两个数...
题意给出一个 $N$ 点 $M$ 边的有向图，并给出最短路径。依次删掉最短路上的每条边，求删边后最短路长度。$N\le 10^5 \ , \ M\le 2\times 10^5$ 。题解朴素的做法可以每删一条边就跑一次 $\text{Spfa}$ ，但这样显然会爆。可以发现不需要每次都更新所有点的最短路。如果删除 $(u,v)$ ，那么最短路一定是 $$1\rightarrow x\righ...
题意给出一个 $N$ 点 $M$ 边的有向图，要从 $1\rightarrow D$ 。每条边上有限速，如果限速为 $0$ 则需要按照上一条边的速度走。求最短用时。$N\le 150$ 。题解给朴素的最短路加上一维，用 $dis[x][s]$ 表示在节点 $x$ ，当前速度为 $s$ 的最短用时。然后跑 $\text{Spfa}$ 即可。tips: 对 double 进行 memset 时最...
题意给出一个 $N$ 点无向图，至少有两个连通块。求连接两个连通块的方案，使得新连通块的直径最小。$N\le 150$ 。题解先用 $\text{Floyd}$ 跑最短路，然后可以算出从每个点出发的最远距离，然后枚举两个不连通的点连上即可得到答案。但有可能出现连接的两个点不是直径两端的情况，这时原来连通块的直径就是这个新连通块的直径，所以需要取最大值。#include<bits/std...
rk800，终于上蓝啦A.Optimal Currency Exchange题意卢布兑美元为 $a:1$ ，兑欧元为 $b:1$ 。美元面值最少为 $1$ ，欧元为 $5$ 。要把 $N$ 卢布尽量兑换出去，求最少剩下多少。$N\le 10^8 \ , \ 30\le a,b\le 100$题解水题，枚举某种货币用了几张即可。我还sb的T了一次。#include<bits/stdc++...
这是赛后做的。珍爱生命，远离eduA.There Are Two Types Of Burgers题意在你的餐厅里有两种汉堡：牛肉汉堡和鸡肉汉堡。每个牛肉汉堡需要 $2$ 片面包和 $1$ 片牛肉，一个鸡肉汉堡需要 $2$ 片面包和 $1$ 个鸡排。一个牛肉汉堡卖 $h$ 元，一个鸡肉汉堡卖 $c$ 元。你有 $b$ 片面包，$p$ 片牛肉和 $f$ 块鸡排。求最大收益。所有数据 $\le ...
题意你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：选择一个有超过一个元素的块（初始时你只有一块，即整个序列）选择两个相邻元素把这个块从中间分开，得到两个非空的块。每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。$n\le 10000...
题意有 $N$ 块矩形土地，面积为 $W_i\times H_i$ 。可以购买单个土地，价格为面积；也可以将多个土地合并起来买，价格为 $\max W\times \max H$ 。要将所有土地买下来，求最小花费。$N\le 50000$ 。题解对于两块土地 $i,j$ ，如果 $H_i\le H_j,W_i\le W_j$ ，那么买 $j$ 的时候顺便把 $i$ 带上就行了，$i$ 就可以...
题意有 $N$ 个商店，每个商店在 $X_i$，有 $F_i$ 个物品，价格为 $C_i$ 元。如果车上有 $P$ 个物品，每单位距离的运输费用为 $P^2$ 。从 $1\rightarrow E$，要求买 $M$ 个物品，求最小花费。$N,E\le 500 \ , \ X_i\le E$ 。题解先把 $E$ 看成一个商店，各项属性为 $X_i=E \ , \ F_i=C_i=0$ 。然后把...
题意有 $N$ 个区间 $[L_i,R_i]$，求最长的连续的一段，使得段内的温度可能不降。$N\le 10^6$ 。题解连续一段 $i..j$ 的终止条件是 $R_j < L_i$ ，所以要使得队头的 $L$ 尽可能大，用单调队列维护 $L$ 的递减序列即可。因为要求连续，所以把队列末尾退队时需要记录最后一个的位置，并把当前元素放入。#include<bits/stdc++.h...
题意有 $N$ 个点，从 $1$ 开始跳，跳到高度比当前矮的点免费，否则消耗 $1$ 。有 $M$ 次询问，每次给出最长能跳的距离，求跳到 $N$ 的最小花费。$N\le 10^6 \ , \ M\le 25$ 。题解用 $f[i]$ 表示跳到 $i$ 的最小花费，则$$f[i]=\min_{i-j\le q} \begin{cases} f[j] \ (H_j > H_i) \\ ...
题意有 $N$ 个数，可以进行 $K$ 次操作，每次可以选择一个区间，把其中所有数 $+1$ 。求最后最长不降子序列的长度。$N\le 10000 \ , \ K\le 500$ 。题解可以发现，每次选择区间的右端点一定是 $N$ ，否则就可能出现答案减小的情况，而不可能会增加。用 $f[i][j]$ 表示第 $i$ 个数被操作了 $j$ 次 ，前 $i$ 个数的最优情况。可以得到方程：$$...
题意一颗 $N$ 点的树，有 $M$ 组查询 $(i,j,k)$ ，询问 $i\rightarrow j$ 所有节点深度的 $k$ 次方和。$N,M\le 300000 \ , \ K\le 50$ 。题解因为 $K$ 很小，所以每个点的所有权值都可以预处理出来。本来想写树剖的，但其实树上差分就够了。$$ans=v[i]+v[j]-v[lca(i,j)]-v[fa[lca(i,j)]]$$#...