这次我只过了三道，D题因为最后统计答案时越界而 Wrong answer on pretest 12 ，结束后把两个 n 改成 n-k+1 就过了，我真是傻逼。代码都是考场代码，所以很丑，凑合看吧。A. Hotelier题意有 $10$ 个房间，客人可能从左边或右边进来，进来后给客人安排最近的房间。可能有人离开。给出 $N$ 个操作，要求输出操作后每个房间是否有人。$N\le 10^5$题解...
题意把 $N$ 个数分成 $M$ 段，要求每段和的方差尽可能小，求最小值。$N\le 3000$ 。题解我这个辣鸡的错误解法方程还是比较容易想到的，用 $f[i][j]$ 表示当前是第 $i$ 段，分到第 $j$ 个数的最优解，方程为：$$f[i][j] = \min_{k=0}^{j-1} (f[i-1][k] + \sum_{p=k+1}^j M\times (X_p - \overli...
题意有 $N$ 个工厂，每个工厂与第 $1$ 个工厂的距离为 $X_i$，有成品 $P_i$ 件。需要修建一些仓库，在每个工厂修建的成本为 $C_i$ 。修建完成后要将成品全部运到仓库里，且只能往序号较大的工厂里运输。运输的成本为 $P_i\times (X_j-X_i)$ 。求成本的最小值。$N\le 10^6$ 。题解用 $f[i]$ 表示最后在 $i$ 修仓库的最小成本，枚举上一次修仓...
题意农场主养了 $M$ 只猫，它们会到 $N$ 座山上去玩，在 $T_i$ 的时候下山。农场主雇了 $P$ 个员工，员工可以在不同的时刻从第 $1$ 座山出发去接猫。求所有猫等待时间和的最小值。$N,M\le 10^5 \ , \ P\le 100$ 。题解用 $t_i$ 表示接第 $i$ 只猫的最早出发时间，显然 $t_i = T_i - D_{H_i}$ ，然后将所有猫按照 $t_i$ ...
2021.11.18更新：“最长路径 $+1$ 就是答案”有误，因为对于 $M_2$ 的情况，两点间的距离其实可以是无穷大的。但强连通分量中就不会有这种情况，因为点之间两两互通，所以它们之间的距离也就有上限。题意有 $N$ 个数和 $M_1+M_2$ 种关系。前 $M_1$ 种关系 $(x,y)$ 表示 $S_x+1=S_y$ ，后 $M_2$ 种关系表示 $S_x\le S_y$ 。求最多...
题意有 $N$ 个重量为 $1,2,3$ 的砝码，以知部分砝码之间的重量关系。给出砝码 $A,B$ ，要求另外选出两个砝码 $C,D$，使得 $A+B > , = , < C+D$ ，求三种情况的方案数。$4\le N\le 50$ 。题解可以先预处理出砝码之间差值的范围。令 $S_i$ 为 $i$ 砝码的重量，用 $mx[i][j]$ 表示 $S_i-S_j$ 的最大值，$mn...
题意在 $N$ 点 $M$ 边的有向无环图中选出最多的点，要求这些点两两之间不能有路径相连。$N\le 200$ ，$M\le 30000$ 。题解路径可达的关系可以通过 $\text{Floyd}$ 传递闭包处理。剩下的问题即转化为：选出最多的点，要求这些点两两没有连边。如果把每个点分裂成两个点，形成二分图，就是标准的最大独立集问题。最大独立集 $= N - $ 最小点覆盖（最大匹配）。#...
题意给出一个 $N\times N$ 的矩形，每个格子染有 $0..5$ 这 $6$ 种颜色。每次操作可以把左上角格子所在的同色联通块全部染成一种颜色，求把所有格子染成一种颜色至少需要多少种操作？$N\le 8$ 。多组数据，组数 $T\le 20$ 。题解朴素的搜索为每次枚举要染的颜色，染色后继续搜索直到染完。退出的条件为某次染色没有新增的格子。期望得分30。#include<bit...
题意给出一个 $A\times B$ 的矩阵，要求求出一个子矩阵，满足子矩阵中最大值和最小值的差值最大。$A,B\le 1000$ 。题解先对每行用单调队列求出最大/最小值，记录在 $maxx[],minx[]$ 中。然后对这两个数组的每列用单调队列再求出最大/最小值，即可得到答案。#include<bits/stdc++.h>
using namespace std;
in...
题意多重背包问题。题解单调队列优化多重背包。$$f[i][j] = \max_{k=0}^{num[i]} f[i-1][j-k\times c[i]]+k\times w[i]$$令 $a = j \mod c[i] \ , \ b = \lfloor \dfrac{j}{c[i]} \rfloor $ ：$$f[i][j] = \max_{k=b-num[i]}^{b} \{f[i-1]...
题意有 $N$ 个格子，每个格子有权值。最开始每次只能跳 $d$ 格，可以通过改进跳 $d-g..d+g$ 格。求满足能获得最少 $k$ 权值的最小的 $g$ 。$N\le 500000$ 。题解可以对 $g$ 二分答案，然后进行验证。令 $f[i]$ 为前 $i$ 个格子可以获得的最大权值，转移方程式为：$$f[i] = \max_{j=1}^{i-1} f[j]+s[i] \ (d-g\...
双倍经验：洛谷2034 选择数字题意从一个数列中选出一些数，要求不能有超过 $k$ 个连续的数，求这些数的最大和。数列长度 $N\le 100000$ 。题解令 $f[i]$ 表示前 $i$ 个数的最优解，$sum[i]$ 表示前缀和，转移方程式为：$$f[i] = \max_{j=i-k}^i f[j-1] + sum[i] - sum[j]$$$$f[i] = \max_{j=i-k}^...
题意给出一个 $N$ 点 $M$ 边的有向图，令 $1\rightarrow N$ 的最短路长度为 $d$ ，求 $1\rightarrow N$ 的长度不超过 $d+k$ 的路径条数。多组数据。 $N\le 100000$ ，$M\le 200000$ 。题解先跑一次反向最短路，记 $i\rightarrow n$ 的最短路长度为 $dis[i]$ 。用 $d(i,j)$ 表示 $i\ri...
题意给出 $N$ 个砝码，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和，求能凑出的 $\le C$ 的重量最大值。$N\le 1000,C\le 2^{30}$ 。题解每个砝码的质量至少等于前面两个砝码的质量的和所以 $N\le 30$ 。。。所以爆搜就行了，拿个前缀和优化剪枝，如果剩下的都能取就直接取完。#include<bits/stdc+...