这是赛后做的。珍爱生命，远离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)]]$$#...
题意一个机器人从 $N$ 点 $M$ 边有向图的 $1$ 出发，每秒可能有 $3$ 种行为：留在原地沿边去下一个城市自爆，自爆后不能再行动求 $T$ 秒后的行为方案数。$N\le 30 \ , \ M\le 100 \ , \ T\le 10^6$ 。题解只考虑行为 $2$ ，可以用矩阵快速幂来实现，初始的图 $^T$ 就是答案。对于行为 $1$ ，相当于每个点都有个自环。对于行为 $3$ ...
题意有一棵 $N$ 点的树，有 $Q$ 次询问 $(a,b,c,d)$ ，问 $a\rightarrow b$ 与 $c\rightarrow d$ 是否相交。$N,Q\le 100000$ 。题解可以发现两条边相交，就一定存在一条边的最高点在另一条边上，即端点的 $\text{LCA}$ 。所以只用求 $\text{LCA}$ 就行了。第一次写倍增 $\text{LCA}$ ，感觉还是树剖...
题意要从一个 $N$ 点 $M$ 边的有向图的 $1\rightarrow N$ ，每秒可以走 $2^k$ 条边（$k$ 是任意自然数），求最少要花多少秒。$N\le 50 \ , \ M\le 10000$ 。题解用一个 bool 数组 $s[i][j][p]$ 表示能否走 $2^p$ 条边从 $i\rightarrow j$ ，可以通过倍增预处理出所有情况。这样就得到了所有能在 $1s$...
题意给出 $N,A,B$ ，求 $N_0$ 的最值，使得 $\lfloor N^A+N^B \rfloor = \lfloor {N_0}^A+{N_0}^B \rfloor$ 。有 $T$ 组数据，答案为每组数据中 $\max N_0 - \min N_0$ 的和。输入方式请看原题。$4\le N\le 5 \ , \ 5\le A,B\le 10 \ , \ T\le 5\times 1...
题意有 $N$ 张卡片，使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格，如果跳到就输了，求跳到终点的方案数。$N\le 24 \ , \ M\le 2$ 。题解用 $cnt[i]$ 表示当前走到的格子，很容易想出状压方程：$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\n...
题意有 $N$ 个人要排队，要求一队的站在一起，共有 $M$ 队。调整队列的方法为让一部分人出队，再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压，用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ，设之前排到了第 $l$ 个人，那么现在要排的是 $[l+1,...
题意有 $N$ 个人去执行 $N$ 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。（直接用题面）$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ，枚举任务 $j$ ，很容易得到方程：$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...