文章

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

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

题意：求 小 X 有 $n$ 种颜色的球，其中第 ii 种颜色的球共有 $ 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 个操作，依次执行，每次给你 xi，你选择一个 阅读更多…

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 上问了出题人两个小时才懂…… 在这里对他细致耐心的讲解表示感 阅读更多…

蒟蒻选手来写题解啦~ 题目链接 首先有一个结论: 对于一个联通块, 经过行动后的颜色其实是按照编号从大到小 DFS 的 DFN 序. 感受一下, 对于节点 $ u $ 操作完后的颜色是编号最大的孩子 $ v $, 对于 $ v $ 的孩子也可以递归理解, 相当于插入一段 DFN 序. 由于是 DFN 阅读更多…

百度之星是由百度公司组织的一年一次的比赛，分为两项赛事，分别是 “程序设计大赛” 和 “开发者大赛”。程序设计大赛针对 (也仅针对) 在校学生 (原因可能是以前的百度之星被谷歌的员工爆破掉了)，而开发者大赛允许已工作选手报名参加。 这篇文章主要介绍” 百度之星程序设计大赛”。 阅读更多…

设简单无向图的 $\rm{EGF}$ 为 $F$ ，简单连通图的 $\rm{EGF}$ 为 $C$ 。 显然有 $F(x)=\sum\limits_{i=0}^{\infty}2^{i\choose2}\frac{x^i}{i!}$ 。 然而现在需要求的是 $G(n)$ ，直接求 $G(n)$ 不好 阅读更多…