[IOI2000] 邮局 加强版 题解 考虑动态规划,设 f i , j f_{i,j} fi,j 为经过了 i i i 个村庄,正在建第 j j j 个邮局的最优距离。 以及 w i , j w_{i,j} wi,j 表示区间 [ i , j ] [i,j] [i,j] 内建一个邮局时的距离总和。 a a a 数组表示每个村庄的坐标编号。 朴素版状态转移方程: f
Description: 自从zkysb出了可持久化并查集后…… hzwer:乱写能AC,暴力踩标程 KuribohG:我不路径压缩就过了! ndsf:暴力就可以轻松虐! zky:…… n个集合 m个操作 操作: 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合,是则输出1否则输出0 请注意本题采用强制在
题目链接 [蓝桥杯 2022 省 B] 李白打酒加强版 题目描述 话说大诗人李白,一生好饮。幸好他从不开车。 一天,他提着酒壶,从家里出来,酒壶中有酒 2 2 2 斗。他边走边唱: 无事街上走,提壶去打酒。 逢店加一倍,遇花喝一斗。 这一路上,他一共遇到店 N N N 次,遇到花 M M M 次。已知最后一次遇到的是花,他正好把酒喝光了。 请你计算李白这一路遇到店和
我的代码: #include <iostream>using namespace std;int dp[101][101][101];const int mod = 1e9 + 7; //题中说了,答案要取模int main(){int n, m; //定义遇到店n次,遇花m次cin >> n >> m;dp[0][0][2] = 1; //因为题目中说了初始有2斗
Hotel加强版 题解 很板子的一道长链剖分。 首先应该是很容易想出它的dp方程式的。 我们令 f u , i f_{u,i} fu,i表示在 u u u的子树中,与 u u u距离为 j j j的点的个数, g u , i g_{u,i} gu,i表示在 u u u的子树中,两个离它们 l c a lca lca距离与它们的 l c a lca lca与 u u u距离的差值为 j j
题目 跑 k k k遍方格取数,问能取到的最大价值 分析 按照算法竞赛进阶指南,建边应该是拆点后入点连接出点用两条边,一条容量为1,费用为 a i , j a_{i,j} ai,j,另一条容量为 k − 1 k-1 k−1,费用为0,向右向下的有向边容量为 k k k,费用为0,从 ( 1 , 1 ) (1,1) (1,1)入点开始跑到 ( n , n ) (n,n) (n,n)的出点