2019年8月

题意有一棵 $N$ 点的树,有 $Q$ 次询问 $(a,b,c,d)$ ,问 $a\rightarrow b$ 与 $c\rightarrow d$ 是否相交。$N,Q\le 100000$ 。题解可以发现两条边相交,就一定存在一条边的最高点在另一条边上,即端点的 $\text{LCA}$ 。所以只用求 $\text{LCA}$ 就行了。第一次写倍增 $\text{LCA}$ ,感觉还是树剖...
题解 图论-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...
题解 动态规划 动态规划-状压DP
省选/NOI-
题意有 $N$ 个人要排队,要求一队的站在一起,共有 $M$ 队。调整队列的方法为让一部分人出队,再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压,用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ,设之前排到了第 $l$ 个人,那么现在要排的是 $[l+1,...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意有 $N$ 个人去执行 $N$ 个任务,每个人执行每个任务有不同的成功率,每个人只能执行一个任务,求所有任务都执行的总的成功率。(直接用题面)$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ,枚举任务 $j$ ,很容易得到方程:$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...
题解 动态规划 动态规划-状压DP
省选/NOI-
题意用 $K$ 个硬币购买 $N$ 个物品。商店不设找零,可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。$N\le 100000 \ , \ K\le 16$ 。题解看到 $K\le 16$ ,状压。用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品;预处理出 $v[i][j]$ 表示硬币 $i$ ,从 $j$ 物品开始买,能买到哪个物品;枚举当前用的硬币 $...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意在一棵 $N$ 个点的树上放 $K$ 个监听器,每个监听器可以监听与它直接相连的节点,但不能监听自己。要求所有节点都被监听,求方案数。$N\le 100000 \ , \ K\le 100$ 。题解真·毒瘤题目。用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了,放了 $i$ 个监听器,$x$ 上放没放监听器,$x$ 有没有被监听到 的方...
题解 动态规划 动态规划-树形DP
NOI/NOI+/CTSC
题意将一棵 $N$ 个点的树上 $K$ 个点染黑,另外的点染白。求黑点两两之间距离和加上白点两两之间距离和的最大值。$N,K\le 2000$ 。题解考虑每一条边的贡献,即为 边权 $\times ($ 一侧的黑点个数 $\times$ 另一侧的黑点个数 $+$ 一侧的白点个数 $\times$ 另一侧的白点个数 $)$ 。用 $f[x][i]$ 表示以 $x$ 为根的子树,黑点有 $i$ ...
题解 动态规划 动态规划-树形DP
省选/NOI-
由于Pjax与自带反垃圾保护的冲突,请在 设置->评论 中关闭反垃圾保护! 否则可能无法评论。推荐使用插件smartspamGithub镜像(更快下载)示例站点Edge[edʒ]n.边缘;棱;角;锋Feature一款棱角分明的主题。Pjax 支持。代码高亮、文章目录支持。使用下载(或clone)后将文件夹命名为 Typecho-Theme-Edge ,然后放入 /usr/themes/...
博客
题意有 $N$ 个小球,每个小球的坐标为 $(x_i,y_i)$ ,即水平为 $x_i$ ,高度为 $y_i$ , 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ,每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数,分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球,求最高分数。$N\le 1000$ 。题解比较容易想到区...
题解 动态规划 动态规划-区间DP
省选/NOI-
题意可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ,可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。字符串长度 $N\le 100$ 。题解设需要处理的字符串为 $S$ ,用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。显然可以从两个字符串拼接而来。枚举断点 $k$ ,$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。也可...
题解 动态规划 动态规划-区间DP
省选/NOI-
最难受的事情莫过于比赛还剩20min,你锁了题,然后叉了自己。锁题有风险,叉人需谨慎。A. Choose Two Numbers题意从两个序列中各选取一个数,要求这两个数的和不属于这两个序列。序列长度 $N\le 200$题解水题,$N^2$ 枚举。#include<bits/stdc++.h> using namespace std; inline int read() {...
题解 比赛-Codeforces
题意给一个长度为 $N$ 的木板染色,木板有初始颜色,要求染成一种颜色。每次可以选择一段连续的格子染色,颜色可以被覆盖。求至少要染多少次。$N\le 50$ 。题解用 $f[l][r]$ 表示将 $[l,r]$ 染成一种颜色的最少次数。当 $S_l=S_r$ 时,可以在染一边时顺便把另一边染了,即 $f[l][r]=\min(f[l+1][r],f[l][r-1])$ 。否则可以枚举中间点 ...
题解 动态规划 动态规划-区间DP
提高+/省选-
题意有 $N$ 座城堡和 $S$ 个玩家,每个玩家有 $M$ 个士兵。能占领城堡要求自己驻扎的兵力严格大于对方的两倍,玩家之间两两都会有独立的城堡争夺,占领第 $i$ 个城堡的收益是 $i$。现在已知 $S$ 个玩家的驻军情况,求如何分配兵力,可以获得最大收益。$S,N\le 100 \ \ \ \ M\le 20000$ 。题解很显然的背包问题,只是需要预处理一下重量。用 $v[i][j]...
题解 动态规划 动态规划-背包DP
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces19 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2