文章

题目传送门 qwq 发现并不需要求出期望，之需要求出所有方案的和即可。考虑 $\rm{DP}$ ： 设 $f(i,j)$ 表示选出的 $m$ 张牌中有 $i$ 张是强化牌，一共打出了 $j$ 张强化牌时所有方案的倍率和。 设 $g(i,j)$ 表示选出的 $m$ 张牌中有 $i$ 张是攻击牌，一共打 阅读更多…

题目传送门 qwq 设 $f(S)$ 表示考虑过的集合为 $S$ 的方案数。 如果当前的最大独立集为 $A$ ，$B$ 代表所有与 $A$ 集合中的点有边相连的点的集合，那么当前状态下 $S=A\cup B$ 。 设 $P_u$ 表示与 $u$ 距离不超过 $1$ 的点集。 考虑转移，首先确定一点 阅读更多…

题目传送门 qwq 设 $sum=\sum_{i}w_i,kill=\sum_{i 被杀死了}w_i$ ，则当前杀死猎人 $k$ 的概率为： $$ P=\frac{w_k}{sum-kill}\ $$ 然后很显然，假设一次可以选择的猎人集合并非活着的猎人集合而是全集，但是如果选到了被杀了的猎 阅读更多…

题目链接 难点是 n 个装置围成了一个环，导致了 DP 的后效性。 解决办法就是在状态中记录两个值（本质就是暴力枚举）： 1. 第一个选的设施的位置 2. 因为前面设施的选择，导致从某一个设施往后都不能选。 状态是 $f[i][j][l]$表示前 $i$个设施，第一个选的设施的位置是 $j$，因为前 阅读更多…

注：本题解为转载题解，内容大意为洛谷题解中的头篇题解，但该文章内容全部为本人自己总结所写，题解原网址，之所以要写本篇题解是为了加深理解。 Problem’s Website 洛谷 P1072 Problem’s Main Idea $n$个询问，每个询问给定 $a_0, a_ 阅读更多…

题意： 小 X 有 $n$ 种颜色的球，其中第 $i$ 种颜色的球共有 $ a_i$ 个，同色的球无法区分。定义第 $l \sim r$ 种颜色的混乱度 $f(l, r)$为：将第 $l \sim r$ 种颜色的所有球排成一排，总共的方案数对 $p$ 取模后的值。小 X 想请你帮忙计算下列式子的值： 阅读更多…

在残量网络跑 SCC, 考虑边 $ (x, y) $ 或者点 $ x, y$ 可行边: 要求 $ (x,y) $ 是匹配边或 $ (x,y) $是非匹配边，但 $ x $ 和 $ y $ 处在同一个 SCC 中。 必经边: 要求 $ (x,y) $ 是匹配边且 $ x $ 和 $ y $ 不在同一 阅读更多…

前言 有一类 DP 的转移是带有数据结构特征的，针对这一点，我们可以使用合适的数据结构来优化转移。 可能这么干说着不好理解，下面会给出两道题目来详细说明。 例子 1.【arc073f】Many Moves 题目大意： 你有两个整数 $a$ 和 $b$ 。 现在 $n$ 个操作，依次执行，每次给你 $ 阅读更多…

Sasha Circle (CF549E) 题目大意 平面上有两个点集，点集大小分别为 $n,m(n,m\leq 10^4)$，所有的点都在整点处，且坐标的绝对值不超过 $C(C\leq 10^4)$。求一个圆将两个点集隔开。 引理 1. 整点集的凸包大小上限为 $O(C^\frac{2}{3})$ 阅读更多…

题目链接 题目简述 给定一个点带权的树，用观测半径为 $r$的摄像头放在节点处，要求覆盖的点的点权和尽量大。求这个最大值。 前言 本题是洛谷 2018 年 8 月 3 号的一场比赛 (链接) 的 T2。 我在 QQ 上问了出题人两个小时才懂…… 在这里对他细致耐心的讲解表示感谢 阅读更多…