CodeForces 1221F Choose a Square
题意大概就是有 \(n\) 个点，每个点其坐标 \(x_i,y_i\) 与权值 \(c_i\)，其中 \(1\le n\le 5\cdot 10^5,0\le x_i,y_i\le 10^9,-10^6\le c_i\le 10^6\)。 让你选一个正方形，该正方形的左下角及右上角必须在 \(y=x\) 这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边权。输出所获的最大权值及其选择正方形的左下角 \(x_1,y_1\) 及右上角 \(x_2,y_2\)，要求 \(0\le x_1=y_1\le x_2=y_2\le 2\cdot 10^9\)。 其实就是让你选两个数 \(l,r\)，左下角为 \((l,l)\)，右上角为 \((r,r)\)。 我们考虑一个点是否在正方形内。 我们发现对于第 \(i\) 个点，若…
造一棵树
帮人造了几组数据。 其实就是造了一棵树。 记录一下以备后用。
UVa11600 Masud Rana
题目大意就是有 \(n\,(n\le 30)\) 个点的无向完全图，有 \(m\,\left(m\le \frac{n\times (n-1)}{2}\right)\) 条道路上没有怪兽，其他道路都有怪兽。 一个人一开始在 \(1\) 号点，每次会随机选择一条路走并把这条路上的怪兽全部杀完。 问期望走多少步才能让这 \(n\) 个点之间都存在没有怪兽的路径。 按照国际惯例，多组数据，\(T\le 100\)。 一看网上的题解，为什么都是 \(\mathcal{O}(2^n)\) 的啊，为什么暴力都能过啊。 当然先声明一下，下面说的复杂度多不太准确，比如说 \(\mathcal{O}(2^n)\)，实际上可能说的是 \(\mathcal{O}(2^n\times n)\) 或是 \(\mathcal{O}(2^n\times n^2)\)，但考虑到这道题对于这种算法的复杂度数据范围放的很宽，…
CodeForces VP 记录
感觉 tf 的时候还是打几场 VP 好…… 加*号的是当场过掉的，这样以后复习可以用。 题意好难翻译啊，那就不翻译了吧。 反正直接模拟就可以了。 代码：58555087 题目大意是给你一个长度为 \(n(n\le 10^5)\) 的严格递增的正整数序列 \(\{E\}\)，让你求 \(i<j<k\) 使得 \(E_k-E_i\le U\) 且 \(\eta=\frac{E_k-E_j}{E_k-E_i}\) 最大。 考虑到严格递增应该是单调性问题。 显然如果 \(i\) 和 \(k\) 固定，那么 \(\eta\) 与 \(E_j\) 负相关，于是 \(i=j-1\)。 然后考虑枚举 \(i\) 算 \(k\)，直接把上面的 \(E_k\) 去掉即可：…
新坑
决定开个新坑，刷一些 CF 上的 dp 题。 现在做了几题： 10 [2019.8.5]忽然发现 stoxielinhanorz 怎么什么题都做过啊，果然是神仙…… [2019.8.6]大家快看这里有个叫 pufanyi 的沙雕自闭了： 果然他是个菜鸡…… [2019.9.21]文化课真香……感觉好久没做题了…… 有 \(n\) 个国际象棋棋手，他们先两两比赛，实力强的会有 \(p\) 的概率打败实力弱的（\(p\) 从头至尾都是相同的），然后赢得把边连向败的。然后再把每个强连通分量的抠出来继续做，知道所有人都有一个唯一的排名。求共期望下棋多少盘。 我们令 \(f_i\) 表示有 \(i\) 名棋手的答案，我们考虑转移。 我们有： 其中 \(g_{i,j}\) 表示从 \(i\) 个点中选出 \(j\) 个点而这 \(j\) 个点均被另外 \(i-j\) 个点打败的概率，\(s_i\)…
AGC006F Blackout
我们有一个 \(N\) 行 \(N\) 列的矩阵。第 \(i\) 行第 \(j\) 列的格子表示为 \((i,j)\)。 开始时，有 \(M\) 个格子是黑色，其他格子都是白色。特别地，开始时格子 \((a_1,b_1),(a_2,b_2),\cdots,(a_M,b_M)\) 是黑色。 スヌケ君会按照以下的规则尽可能多的将白色格子涂成黑色： 请计算出当再也没有白色格子能被涂黑时，黑色格子的个数。 \(1\le N,M\le 10^5;1\le a_i,b_i\le N\)。 按照套路，我们应该把行和列看成点，即有 \(1\sim N\) 个点，每个格子 \((x,y)\) 可以看成是 \(x\to y\) 的一条有向边。如果存在边 \((x,y)\) 与边 \((y,z)\)，就连边 \((z,x)\)，询问最终有几条边。 我们将每个弱连通分量分开考虑。 我们考虑什么时候不能加边了，…
ARC068F Solitaire
将 \(1\sim n\) 顺序加入双端队列（每次可加头可加尾），再删除（每次可删头可删尾），求有多少种删除序列，使得 \(1\) 是第 \(k\) 个被删的。 \(k\le n\le 2000\) 根据套路这种计数类题我们应该考虑什么样的序列满足性质。 我们考虑我们是如何构造这段序列的。 一开始，我们将 \(1\sim n\) 的排列放入双端队列中，那应该是这样的： 然后我们考虑取出后哪些数是可以放在 \(1\) 前面的： 大概就应该是上图红色和蓝色的（当然分成两段的可能是红色而不是绿色）。 于是我们发现 \(1\) 前面的序列（包括 \(1\)）可以划分为两个单调递减的子序列（\(1\) 划给与他相邻的那个序列，反正他是最小的）： 我们发现如果是这样的话，与 \(1\) 相邻颜色序列的末尾一定是 \(1\)，另一个子序列的末尾（即最小值）一定比绿色序列中的最大值要大。 于是我们就可以…
AGC005C Tree Restoring
青木君特别喜欢数列和树，他觉得它们是世界上最美妙的事物。 有一天，神仙给了青木君一个长度为 \(n\) 的整数数列 \(a\)。这让青木君特别想构造一棵美妙树。 美妙树的每条边长度都为 \(1\)。而且美妙树有一个最重要的性质：对于每一个点 \(i(1\le i\le n)\)，在树中离它距离最远的点与它的距离应恰好等于 \(a_i\)。 青木君想了想就秒掉了这题，他决定考考你：对于一个给定的序列，是否存在一棵美妙树？ \(2\le n\le 100,1\le a_i\le n−1\) 首先根据这个序列我们可以很方便地求出直径。 然后我们把树的直径上的点删掉，即 \(l, l-1, l-2, \cdots, mid, mid + 1, \cdots, l - 1, l\)，如果不存在那么一定是 impossible。 然后还有就是不可能出现 \(a\) 比直径中点小的点，把它判掉就过了此题…
ARC068E Snuke Line
原题链接 有一趟列车有 \(M+1\) 个车站，从 \(0\) 到 \(M\) 编号。有 \(N\) 种商品，第 \(i\) 种只在编号 \([l_i,r_i]\) 的车站出售。一辆列车有一个预设好的系数 \(d\)，从 \(0\) 出发，只会在 \(d\) 的倍数车站停车。对于 \(d\) 从 \(1\) 到 \(M\) 的列车，求最多能买到多少种商品。 \(1\le N \le 3\times 10^5;1\le M\le 10^5;1\le l_i\le r_i\le M\)。 我们考虑对于每个 \(d\)，如果区间 \([l_i,r_i]\) 有 \(r_i-l_i+1\ge d\)，那么显然它一定会被覆盖，我们直接统计答案。 我们考虑 \(r_i-l_i+1<d\) 的情况，显然它只会被覆盖一次，所以我们只要求这些区间与这些点的交点个数即可。 于是我们由长度从小到大枚举区间，放入…
ARC080E Young Maids
原题链接 题意大概就是给你一个排列 \(p\)，你每次可以找到 \(p\) 中相邻两个数并将其移至另一个初始为空的队列的开头，让最终 \(p\) 的字典序尽量小。 过程大概就是这样： 由于字典序大小是从前往后决定的，所以我们考虑从前往后确定这个序列，也就是将题意中的过程倒着做。 我们考虑在某一状态下，选择的两个数在原序列中是 \(p_l,p_r\)，那么再次之前的选择中，不可能出现选择的数为 \(p_{a_l},p_{a_r}\) 使得 \(a_l<l<a_r\) 或 \(a_l<r<a_r\)。 于是我们发现倒着考虑是，选择 \(p_l,p_r\) 时就是把序列分成了 \([1,l-1],[l+1,r-1],[r+1,n]\) 这 \(3\) 段，这 \(3\) 段相互独立。 我们考虑怎样的 \(<l,r>\) 是合法的。显然就是…