Fanyi's Blog

感觉已经濒临 AFO 了。 题解中的翻译大部分来自网上，如果有侵权行为请联系我。 查看题解 PDF

声明：本游记的所有内容均是在 CSP 结束之后写的。 都高二了，第一次正式出去玩，第一次写游记。 上午信心赛，然后 yk 就放了场 Day2，窝打到自闭了。 啥我 T2 打了个奇怪的贪心过了？？？旺仔和 zyy 竟然 T1 同时没开大数组同一个数组海星…… 听说如果这场把 RP 用光会导致 CSP 爆 0，窝怕不是药丸。 高二老年选手第一次参加NOIPCSP，是不是晚了点。 路上好多人都在奶今年原题大战。 先去学车想围观一下考场，然而不让进。 和daifucong住一个房间，感觉酒店环境一般，但也还算过得去。 听说那叫“维也纳三好酒店”，名字不错。 晚上 daifucong 勾引我打 cs1.6，尝试下然鹅被卡巴基佬删了，听说 dfc 那个也被 360 删了。 然后开始无所事事。 dfc 给我讲了 pkuwc2019 的 D1T1，然后我想了好久是不是药丸…… 自闭后开始背板，然鹅还没开始…

题意大概就是有 \(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\) 个点，若…

帮人造了几组数据。 其实就是造了一棵树。 记录一下以备后用。

题目大意就是有 \(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)\)，但考虑到这道题对于这种算法的复杂度数据范围放的很宽，…

感觉 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\)…

我们有一个 \(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)\)，询问最终有几条边。 我们将每个弱连通分量分开考虑。 我们考虑什么时候不能加边了，…

将 \(1\sim n\) 顺序加入双端队列（每次可加头可加尾），再删除（每次可删头可删尾），求有多少种删除序列，使得 \(1\) 是第 \(k\) 个被删的。 \(k\le n\le 2000\) 根据套路这种计数类题我们应该考虑什么样的序列满足性质。 我们考虑我们是如何构造这段序列的。 一开始，我们将 \(1\sim n\) 的排列放入双端队列中，那应该是这样的： 然后我们考虑取出后哪些数是可以放在 \(1\) 前面的： 大概就应该是上图红色和蓝色的（当然分成两段的可能是红色而不是绿色）。 于是我们发现 \(1\) 前面的序列（包括 \(1\)）可以划分为两个单调递减的子序列（\(1\) 划给与他相邻的那个序列，反正他是最小的）： 我们发现如果是这样的话，与 \(1\) 相邻颜色序列的末尾一定是 \(1\)，另一个子序列的末尾（即最小值）一定比绿色序列中的最大值要大。 于是我们就可以…

青木君特别喜欢数列和树，他觉得它们是世界上最美妙的事物。 有一天，神仙给了青木君一个长度为 \(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\) 比直径中点小的点，把它判掉就过了此题…