Fanyi's Blog

看到一个有趣的算法，能在最坏时间复杂度 \(\mathcal{O}(n)\) 内求出序列第 \(k\) 小。 首先如果是期望线性的话，应该是非常简单的，就是我们直接使用快速排序的分治思想，随机选一个数作为 pivot，把比她小的放前面，比她大的放后面，于是就形成了左右两边，紧接着考虑左边的 size 是否小于 \(k\) 进行分治。 但我们需要的是确定性算法。 首先我们保证每个数是不相同的，这很好保证，只要开个 pair，在每个数后面附上一个 index 以双关键字比较即可。 现在有一个非常有趣的想法，就是我们用一种方法来找到一个 pivot，让这个 pivot 比较居中。我们考虑将序列按照每五个切成片，这样的话如果是一个长度为 \(n\) 的序列，就会被切成 \(\left\lceil \frac{n}{5}\right\rceil\) 片，每片至多 \(5\) 个数，然后我们对这…

Farmer John 有 \(s\) 只奶牛，和 \(n\) 个独立的篱笆，每个篱笆里可以圈养一些奶牛。出于一种奇♂️怪的偏好，Farmer John 把篱笆排成了一排。第 \(i\) 个篱笆圈养的奶牛数量为 \(a_i\)，显然我们有 \(\sum_{i=1}^n a_i=s\)。而且，处于 Farmer John 的癖好，他要求对于每个 \(i\) 都有 \(a_i>0\)。 Bessie 认为一个农场是“幸运的”当且仅当你可以找到一个区间 \([l,r]\)，使得 \(\sum_{i=l}^ra_i=k\)。 而得寸进尺的 Bessie 认为一个农场是“牛逼的”当且仅当不管 Farmer John 怎么安置他的奶牛，该农场都是“幸运的”。 现在有 \(t\,(1\le t\le 10^5)\) 组询问，每组询问给出 \(s, n\) 和…

给一张 \(n\,(3\le n\le 10^5)\) 个点 \(m\,(2\le m\le 2\times 10^5)\) 条边的无向连通图，以及三个正整数 \(a,b,c\)，保证 \(a+b+c=n\)。你需要对每个点染成三种颜色中的一种，使得这三种颜色的点的个数分别为 \(a,b,c\)，且有两种颜色的点构成两个联、连通块。可能无解。 我们先考虑我们这两个连通块的大小应该为多少。我们不妨令 \(a\le b\le c\)，那么我们发现其实只要让 \(a\) 和 \(b\) 是连通块即可。因为如果是 \(c\) 是连通块，那么我们显然可以通过删掉部分节点的方式将其的大小缩小。 考虑到这一点，如果这是一棵树的话，那算法就简单了。我们考虑枚举一条边，如果边两边的 size 分别大于了 \(a\) 和 \(b\)，那就 YES 了。如果找不到的话，那显然就是 NO。 然后我们考虑图的情况，…

告诉你 \(n\)，要你猜一个长度为 \(n\) 的正整数序列 \(\left\{a_i\right\}\)，\(a_i\) 两两不同，且存在 \(0\le l\le 2\times 10^5-n\) 使得 \(a_i\in\left(l,l+n\right]\)。 每次你可以向交互库询问 ? x y（\(x\neq y\)），交互库向你返回 \(\mathrm{lcm}(a_x,a_y)\)。询问次数为 \(n+5000\)，其中 \(3\le n\le 10^5\)。 我们先考虑 \(n\) 比较小的情况，这时候我们可以考虑到我们有那个 \(5000\)，我们考虑 \(n^2\) 次询问。我们考虑利用一个柿子，也就是当 \(\gcd(x,y)=1\) 时，…

给一个长度为 \(n\,(1\le n\le 1000)\) 的正整数序列 \(\left\{c_n\right\}\,(1\le c_i\le 10^9)\)。用该序列一如下方式构造一个括号序列 \(s\)： 求有多少对 \(\left<l,r\right>\) 使得 \(s_{l\sim r}\) 为合法括号序列。 整一个 \(\mathcal{O}(n)\) 的题解吧。 我们分两种情况考虑合法的括号序列： 我们可以定义第一种括号序列是“独立的”，也就是说她不能被分裂成两个合法括号串；而第二种括号序列是“不独立的”，也就是说，她能被分裂成两个合法的括号串。 我们考虑把两种字符串分开考虑。很显然，每个 ')'，只能作为一个独立括号串的右端点，所以我们统计这部分是非常容易的：跑一遍栈，和平时一样，只是批量地压栈和弹栈，记录弹出的 '(' 次数，即是这部分的答案。 对于非独立的情况，我们考虑…

给定一个长度为 \(n\) 的字符串表示一个序列 \(a_i\)，字符串中只有 '+'、'-'，第 \(i\) 个字符为 '+' 表示 \(a_i = 1\)，为 '-' 表示 \(a_i = -1\)。\(q\) 组询问，每组询问给定两个整数 \(l, r\,(1\le l\le r\le n)\)，将 \(a_{l\sim r}\) 单独取出后，求最少删除多少个数字，使得所成长度为 \(m\) 的序列 \(\left\{b_{i}\right\}\) 满足 \(\sum_{i=1}^m(-1)^{i-1}b_i=0\)。 D1 仅要求出最少删除多少个数字，D2 需要求出删除哪些数字（多解输出任意一组即可）。 \(T\) 组数据，\(1\le T\le 10^3, 1\le n, q\le 3\cdot 10^5\)。 先考虑没有多组询问。 窝萌首先发现一个性质，那就是如果有两个连续的…

有 \(T\,(1\le T\le 10^3)\) 组数据，每组给一个长度为 \(k\,(1\le k\le 50)\) 的十进制正整数 \(n\)，其中 \(n\) 在十进制下不存在 \(0\)（同样不存在前导 \(0\)），让你求一个整数 \(m\)，使得 \(m\) 在十进制下为 \(n\) 在十进制下的子序列，且 \(m\) 为非素数（\(1\) 也是非素数）。子序列不要求连续。 窝萌考虑尽量批量解决一些能解决数。 考虑到如果一个数字含有 \(1, 4, 6, 8, 9\)，那么这个数只要保留这一位即可，而其余情况均需保留两位。 如果没有这些数，也就是只有 \(2, 3, 5, 7\)，如果存在两个数字相同，那么只要保留这两个数字就一定被 \(11\) 整除，于是位数大于等于 \(5\) 位的数字都解决了。 然后考虑到只要 \(2\) 和 \(7\)、\(5\) 和 \(7\)…

有 \(n\,(2\le n\le 4\cdot 10^6)\) 个节点，编号 \(1\sim n\)，你一开始在节点 \(n\)，想要到节点 \(1\)。假设你现在在节点 \(x\)，你可以进行以下两种操作： 求有多少种方案到达节点 \(1\)，只要有一次选择的 \(x\) 或 \(z\) 不同就算方案不同。答案对 \(m\) 取模，其中 \(m\in \left(10^8, 10^9\right)\) 且 \(m\) 是素数。 令 \(f_i\) 表示 \(n=i\) 时的答案，我们有： 前一部分表示用减法，后一部分表示用除法。 考虑优化，第一部分直接前缀和，我们直接考虑第二部分。一种很直接的优化是将小于 \(\sqrt{i}\) 的 \(d\) 直接拿出来算，大于 \(\sqrt{i}\) 的 \(d\) 拿出来算贡献， \(f_{k}\) 能转移到 \(f_i\) 的 \(d\)…

高考数学挂了 圆锥曲线最后几步了忘了开根 qaq 这里订正一下 如图，已知 \(F\) 是抛物线 \(y^2=2px\,(p>0)\) 的焦点，\(M\) 是抛物线的准线与 \(x\) 轴的交点，且 \(\left|MF\right|=2\) （1）求抛物线的方程； 解：\(p=2\Rightarrow y^2=4x\) （2）设过点 \(F\) 的直线交抛物线与 \(A\)､\(B\) 两点，斜率为 \(2\) 的直线 \(l\) 与直线 \(MA,\,MB,\,AB\)，\(x\) 轴依次交于点 \(P，Q，R，N\)，且 \(\left|RN\right|^2=\left|PN\right|\cdot\left|QN\right|\)，求直线 \(l\) 在 \(x\) 轴上截距的范围。 解： 设 \(A(a^2,2a),\ B(b^2,2b)\)。有…

嘴里说着退役，不知不觉就真的退役了。 想起来已经两年半了。从弃了文化课来搞 OI，到现在又得滚回去搞文化课，真是一段有意思的经历。 两年前，打字还要看着键盘，然而现在还是不会背键盘；场场模拟赛爆蛋，然而现在还是只会爆蛋。 NOIP2018 初赛直接挂了，险些退役。回想起来那种自闭的感觉确实挺有意思的。 CSP2019 好不容易过了初赛，结果复赛爆炸，Day1T3 写不出来，Day2T1 有被卡常。 考完 CSP 去打 CodeForces，好不容易要上 IM 了，连续几场 fst 直接一夜回到解放前。 后来文化课压力逐渐重了起来，毕竟是要高考了。 不管怎么说，总算是 AFO 了。 还有几篇博客没填完的，就让她们鸽这吧（ 不知道以后再有没有机会打 CF 了： 不知道以后再有没有机会刷洛谷了：