分类:题解

题意给出一个 $N$ 点 $M$ 边的有向图,以及 $K$ 个感兴趣的点,求感兴趣的点两两之间最短路的最小值。$N\le 100000 \ , \ M\le 500000$ 。题解如果建立原点和汇点,把 $K$ 个点分成两组,分别与原点汇点相连,再从原点开始跑到汇点的最短路就是最小值。但这样显然无法涵盖所有情况。所以枚举二进制位,把当前位为 $1$ 的加入第一组,其它的放入第二组。因为两个数...
题解 图论-最短/最长路 图论
NOI/NOI+/CTSC
题意给出一个 $N$ 点 $M$ 边的有向图,并给出最短路径。依次删掉最短路上的每条边,求删边后最短路长度。$N\le 10^5 \ , \ M\le 2\times 10^5$ 。题解朴素的做法可以每删一条边就跑一次 $\text{Spfa}$ ,但这样显然会爆。可以发现不需要每次都更新所有点的最短路。如果删除 $(u,v)$ ,那么最短路一定是 $$1\rightarrow x\righ...
题解 图论-最短/最长路 图论
NOI/NOI+/CTSC
题意给出一个 $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++...
题解 比赛-Codeforces
这是赛后做的。珍爱生命,远离eduA.There Are Two Types Of Burgers题意在你的餐厅里有两种汉堡:牛肉汉堡和鸡肉汉堡。每个牛肉汉堡需要 $2$ 片面包和 $1$ 片牛肉,一个鸡肉汉堡需要 $2$ 片面包和 $1$ 个鸡排。一个牛肉汉堡卖 $h$ 元,一个鸡肉汉堡卖 $c$ 元。你有 $b$ 片面包,$p$ 片牛肉和 $f$ 块鸡排。求最大收益。所有数据 $\le ...
题解 比赛-Codeforces
题意你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次:选择一个有超过一个元素的块(初始时你只有一块,即整个序列)选择两个相邻元素把这个块从中间分开,得到两个非空的块。每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。$n\le 10000...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意有 $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$ 就可以...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意有 $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$ 。然后把...
题解 动态规划 动态规划-单调队列优化DP
提高+/省选-
题意有 $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) \\ ...
题解 动态规划 动态规划-单调队列优化DP
提高+/省选-
题意有 $N$ 个数,可以进行 $K$ 次操作,每次可以选择一个区间,把其中所有数 $+1$ 。求最后最长不降子序列的长度。$N\le 10000 \ , \ K\le 500$ 。题解可以发现,每次选择区间的右端点一定是 $N$ ,否则就可能出现答案减小的情况,而不可能会增加。用 $f[i][j]$ 表示第 $i$ 个数被操作了 $j$ 次 ,前 $i$ 个数的最优情况。可以得到方程:$$...
题解 动态规划 数据结构-树状数组
省选/NOI-
题意一颗 $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}$ ,感觉还是树剖...
题解 图论-LCA 算法-倍增
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划40 动态规划-区间DP8 动态规划-单调队列优化DP4 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP12 动态规划-状压DP12 动态规划-线性DP9 动态规划-背包DP2 图论4 图论-LCA2 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路15 图论-树上差分1 图论-桥1 图论-缩点4 图论-负环3 字符串2 字符串-kmp2 思维题3 数学22 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂3 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵4 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分9 数据结构-线段树1 数据结构-队列1 比赛-Codeforces13 比赛-JX Round1 比赛-NOIp3 算法-二分/三分9 算法-位运算1 算法-倍增2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分3 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索19 算法-模拟3 算法-状态压缩3 算法-贪心4 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2