Fanyi's Blog

给一张 \(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 了： 不知道以后再有没有机会刷洛谷了：

构造一个 \(n^3\) 个点的无向图 \(G\)，方法如下： 现在，要你求出 \(G\) 的最大独立集大小膜 \(998244353\) 以后的值。 \(2\le n\le 10^5,1\le m_1,m_2,m_3\le 10^5\) 考虑到是点权是一个大数的幂次，那肯定是选的数越大越好。 考虑如果你知道了图 \(G\) 之后你会怎么做。 首先 \(\left<n,n,n\right>\) 这个点必须得选，然后其跟她连边的点就不能选了。 然后如果一个点已经确定了旁边已经比她大的点都不选了，那么她才会选。 那会不会有两个相邻的点点权相等呢？显然不会。因为相邻的点必须有两个权值相等，那么另外一个肯定相等，这是不合法的。 然后我们就考虑这个过程，就是我们考虑如何判断一个点选不选，那就要看与之相邻的比她大的点选不选，就是如果那些点都是不合法的，那么这个点合法，否则不合法。 我们发现这跟博弈问题…

给出一种生成长度为 \(3n\) 的排列 \(P\) 的方法： 现在要你求出，这样的方式共能生成多少种本质不同的排列 \(A\)，答案对 \(m\) 取模。 \(1\le n\le 2\times 10^3,10^8\le m\le 10^9+7\) 首先我们不难发现这个序列在一定程度上肯定是有单调性的，因为本身这个生成的方式就是一个单调的过程。 我们发现对于一个块 \(\{a,b,c\}\)，如果 \(a>b\)，那 \(b\) 一定是紧跟在 \(a\) 后面的。而如果 \(a<b\)，那么我们不难发现这个快可以分裂成两个，也就是 \(\{a\},\{b,c\}\)，因为 \(b\) 肯定在 \(a\) 之后选。 那么也就是说，我们现在的情况是，有一些长度为 \(1,2,3\) 的块，每个块都是的开头都是最大的。这给我们了一个提示，因为这样的东西给了我们一个将构造方法和序列连结起来的桥梁…