题意给出一个 $n(\le 1000)$ 点 $m(\le 10^6)$ 边的有向图，求 $1\rightarrow n$ 的边权积最小的路径。题解因为需要松弛所以不能取模，如果直接乘起来又会爆。不过 $\log(a\times b)=\log(a)+\log(b)$ ，可以改为求边权为 $\log(w)$ 的最短路。在最短路过程中记录 $y$ 的上一个点 $lst[v]$ 以及两点之间的真...
题意有 $n(\le 5\times 10^5)$ 个四维空间点，坐标为 $(x_i,y_i,z_i,q_i)$ 。要求点对 $(i,j)$ 满足：$$x_i-x_j=y_i-y_j=z_i-z_j=q_i-q_j$$求 $j-i$ 的最小值及 $i+j$ 的最大值。题解题意即要求两点的 $x-y,y-z,z-q$ 相等。直接拿个 map 就能水过去。#include<bits/std...
题意有一个长为 $n(\le 10000)$ ，高为 $m(\le 1000)$ 的游戏场景。玩Flappy Bird，在位置 $i$ 点一下会上升 $x_i$ ，否则会下降 $y_i$ ，手速极快每秒可以点多下。有 $k$ 个位置有管道，其中空隙的范围为 $[L_i,H_i]$ 。可以从位置 $0$ 的任意高度出发，问至少要点几次才能到位置 $n$ ？如果无法到达，最多能跨过多少个管道？题...
题意给一个 $n(\le 5\times 10^5)$ 点 $m(\le 5\times 10^5)$ 边的有向无环图，求一个拓扑序满足拓扑序的前缀最大值最少/最多。题解最大的情况比较容易想到，从当前能走的点中选编号最小的点即可，用堆维护。至于最小的情况，直接选最大的点拓展会喜提46分。很容易想到这种方法的问题所在，如果很小的一个点连着一个很大的点，把这两个都选了有可能最优。考虑对贪心进行优...
题意有一棵 $n(\le 100004)$ 个点的树，从根节点出发。节点 $x$ 能放梅花，仅当其所有子节点 $y$ 上都放了 $w_y$ 朵梅花。对于 $\forall i\in [1,n]$ ，如果要在 $i$ 上放 $w_i$ 朵梅花，则至少需要在过程中准备多少梅花？题解可以发现对于节点 $x$ ，一定是按某种顺序遍历所有子节点 $y$ 放上梅花，而且不同的顺序得到的答案也不相同。考虑...
省略的程序头：#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
#define pii pair<int,int>
#defi...
题意有 $n(\le 100)$ 个软件可以安装，每个软件会占 $w_i$ 的磁盘空间，价值为 $v_i$ ，每个软件都有至多一个依赖。剩余磁盘空间为 $m(\le 500)$ ，问安装软件的价值最大值。题解环上的软件必须要全装才有收益，所以先缩点。然后把 $0$ 看成树根，并将它与无依赖的软件连边。剩下的就是标准的树形背包问题，只是注意当前枚举的软件一定会安装，否则无法安装子树上的软件。#...
语文阅读题题意有 $n(\le 4000)$ 对夫妻，还有 $m(\le 20000)$ 对此前的交往关系（都是在这 $2n$ 个人之间）。如果某对夫妻吵架，那么他们都会找此前交往的人复合，然后又一对夫妻被拆散……如果某对夫妻吵架，发生上述过程后可以组成新的婚姻关系，那么就称该婚姻不稳定；否则稳定。询问每个婚姻是否为稳定婚姻。题解先考虑吵架后丈夫的行为，可以发现关系的传递是 男 $\righ...
题意给出一个长度为 $n(\le 2\times 10^6)$ 的数列，有 $m(\le 2\times 10^6)$ 次询问，求 $[l,r]$ 之间有多少个出现了两次及以上的数。题解和 HH的项链 差不多，只是要求出现两次。所以把树状数组维护的值修改一下，变成只有出现了两次才更新节点的权值。先预处理出每种数字下一次和下下次出现的位置 $nxt[]$ 和 $nxt2[]$，并把所有数字出现...
A.Yet Another Dividing into Teams略B.Books Exchange题意题解把关系连边后，可以发现一定是形成若干个环，那么 $O(n)$ 搜索一遍即可。#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch...
当时比赛的时候没做出来这题，做了 洛谷3586 才知道这题的做法。题意有 $N(\le 3\times 10^5)$ 张卡，卡上有数字 $A_i(\le n)$ 。$\forall k$ ，问：每次取 $k$ 张数字互不相同的卡，能取多少次。题解记录每个数字出现的次数为 $s_i$ ，问题就转化为：每次选 $k$ 个正数 $-1$ ，最多操作多少次。然后就可以直接用 洛谷3586 的结论了（...
题意给出一个长度为 $n(\le 10^6)$ 的全 $0$ 序列，要求支持以下操作：单点修改给出 $(c,s)$ ，每次取 $c$ 个正数 $-1$ ，问能否操作 $s$ 次。题解先考虑操作 $2$ 。设 $\geq s$ 的数有 $x$ 个，这些数每次都可以取，此外还需要 $(c-x)$ 个数。设 $< s$ 的数的和为 $sum$ ，如果 $sum < (c-s)\time...
题意有 $n(\le 1000)$ 个人，每个人有分数 $s[i]$ 。有 $S$ 组限制 $(A,B)$ ，要求 $s[A] > s[B]\times k$ 或 $s[A] > s[B]\times \frac{1}{k}$ ，如果不满足则 $A$ 需要女装。已知 $t$ 个人的初始分数。求最大的 $T$ ，使得限制变为 $s[A] > s[B]\times (k-T)$...
题意略（太复杂了不想写）题解令 $f[i]$ 为不大于 $x$ 的最大斐波那契数，那么 $x$ 的父亲节点就是 $x-f[i]$ 。斐波那契数列的第 $58$ 项刚好小于 $10^{12}$ ，所以预处理前 $58$ 个就行了。求两个节点的 $\text{LCA}$ 可以用一种类似树剖的方法，不断地取 $u$ 和 $v$ 中的较大值跳到父节点，直到 $u$ 和 $v$ 相等。层数最多只有 $...
题意给出一个 $n(\le 2\times 10^5)$ 点的树。从 $C$ 出发，先到 $A$ 和 $B$ 中较近的点，然后到另一个点。求可能的路径最大值。题解$A\rightarrow B$ 这段路径是肯定要走的，然后还有一段 $\max_c (\min (AC,BC))$ 。显然 $AB$ 是直径，然后从 $A,B$ 出发分别 $\text{dfs}$ 一次求出距离即可。#includ...