Fanyi's Blog

构造一个 \(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\) 的块，每个块都是的开头都是最大的。这给我们了一个提示，因为这样的东西给了我们一个将构造方法和序列连结起来的桥梁…

有一个 \(n\times n\) 的棋盘（\(n\le 300\)），然后对于每一列，考虑将所有该列纵坐标大于等于 \(a_i\) 的格子全部删掉。在剩余期盼中，问有多少种放车的方案能使每个格子都能被至少一个车攻击到。 首先考虑到这样一件事情，就是如果用 \(\left<l,r,h\right>\) 表示的是 \([l,r]\) 区间内，纵坐标大于 \(h\) 的格子，我们定义一个这样的三元组为一个状态。 然后我们考虑对于每个状态，它里面的格子，如果要合法的话，每一列一定是下面三种中的其中一种： 现在我们考虑 dp，\(f_{t,i,j}\) 表示状态为 \(t\) 的时候，现在有 \(i\) 个 \(2\) 类点，\(j\) 个 \(3\) 类点，那么显然 \(1\) 类点就是 \(r-l+1-i-j\) 个。 然后我们考虑转移，我们考虑 \(t\) 所表示的方格是否完全被分成了两块，…

有 \(n\) 条线 \(m\) 个平衡器，从左往右第 \(i\) 个平衡器连接了 \(x_i,y_i\) 条电线（\(1\le x_i<y_i\le n\)），每个平衡器都有一个状态：向上或向下。考虑一个令牌，从最左边的某一条导线开始，如果在第 \(i\) 个位置，如果他在 \(x_i\) 导线上且平衡器状态向下，那么就到 \(y_i\)，同理如果在 \(y_i\) 且状态向上，则到 \(x_i\)。记 \(k_i\) 表示令牌从导线 \(i\) 开始到无穷远处是他在哪条导线上。 让你构造两种解，每种解用一个字符串表示，表示每个平衡器的状态。第一组解要求所有的 \(k_i\) 相等，第二组接要求至少有两个 \(k_i\) 不相等。无解输出 \(-1\)。 数据范围 \(2\le n\le 5\times 10^4,\,1\le m\le 10^5\)。 一道有趣的构造题。 首先我们考虑…

问存在多少个长度为 \(n\,(2\le n\le 5000)\) 的单调不减序列 \(a\)，满足 \(1\le a_i\le n\)，且对于任意 \(k\,(1\le k<n)\)，都有：对任意大小为 \(k\) 的子集 \(S\) 和大小为 \(k+1\) 的子集 \(T\)，满足 \(\sum_{x\in S}A_x<\sum_{x\in T}A_x\)。答案对大质数 \(m\) 取模。 首先需要发现一个性质，就是如果 \(k=\left\lfloor\frac{n}{2}\right\rfloor\) 的时候满足了，那么其他的 \(k\) 都能满足。为什么呢？首先是对于每个 \(k\)，显然如果满足了 \(\sum_{i=1}^{k+1}a_i\ge \sum_{i=n-k+1}^na_i\)，就满足所有的 \(S\) 和 \(T\) 了。然后如果满足了…

有一段标号从 \(-\infty\) 到 \(+\infty\) 的序列 \(A\)，初始是 \(A_i=0\)。现在有一个人在 \(0\) 位置，有一段操作序列 \(s\)，依次进行操作。 假设 \(i\) 时刻这个人在位置 \(p\)，如果 \(s_i\) 是 '+'，则将 \(A_p\) 加 \(1\)，如果是 '-'，则减 \(1\)；如果是 '<' 则该人左移一格，否则是 '>' 则右移一格。 要求数出 \(s\) 的所有连续子串中最终得到的 \(A\) 与 \(s\) 最终得到相同 \(A\) 序列的个数。 数据范围 \(|s|\le 250000\)。 考虑构造一波类似生成函数的东西 \(f(x)=\sum_{i=-\infty}^{+\infty}A_ix^i\)，另外还有一个指针 \(g\)，开始是 \(g\) 指向 \(0\) 位置，显然初始时 \(f(x)=0\)。…

题意大概就是给你 \(n-1\) 个点集，全集是 \(\{1,2,\dots, n\}\)，现在要从每个点点集中抽出两个点来连边，最终形成一棵树。让你输出方案或判断无解。\(n\) 有 \(10^5\)，所有集合大小之和不超过 \(2\times 10^5\)。 考虑构造，儿子向父亲连边。也就是说，每个集合最后都是儿子 \(\to\) 父亲的一条边，那么我们可以随便选一个点作为跟，其余点肯定对应一个集合，表示这个集合所对应的边，一端是他，另一端是他父亲。其实也就是一个匹配，左边是除了根节点以外的所有点，右边是所有点集。点与点集有边当且仅当这个点在点集中出现。 显然地，如果这个匹配无解那么最终肯定无解，因为根本找不到一个完美的儿子 \(\to\) 父亲的映射。找到匹配之后我们把根加上去，跟前面的连法一样。如果连上之后这张图仍然不连通，那么显然无解，因为两个独立的连通块显然没有生成树。 那如果…

定义一棵树上两个点等价当且仅当以这两个点为根的有根树同构，一棵树的权值定义为这棵树的等价类个数。 给出一棵 \(n\) 个点的树，可以在这棵树基础不断的加叶子，使得最后树的权值最小，求出这个权值，以及满足之前条件的所有树中最小叶子数。 数据范围 \(n\le 100\)。 我们发现其实最终所得的树只有两种，一种是以一条边为中心，左右两边同构，一种是以点为中心，呈放射状分布。 其实这两种都一样，以边为放射状的只要把这条边看成一个点就可以了。 这样我们考虑枚举中心，要求其权值，首先不难发现同构的数量其实就是以中心为根的树的深度。然后我们考虑叶子个数，我们只要想想构造这棵树的过程，其实就是把每一层深度的所有点的儿子数补成相同，那么补完后树的叶子个数就是每层非叶子节点儿子个数的乘积，对于原树来讲就是每层儿子树最多的儿子个数的乘积。 复杂度 \(\mathcal{O}(n^2)\)，开…

有一张 \(n\) 个点 \(m\) 条边的简单无向图，每次选择一个度数小于等于 \(1\) 的点然后将其删除，对于每个 \(k\) 求删去 \(k\) 个点的方案数。\(n\le 100,\,m\le \frac{n\times(n-1)}{2}\)。 首先环上点肯定删不掉，如果一个连通块之间有两个环，那么被两个环夹着的点肯定也删不掉。 接下来我们考虑两件事情，一件事情就是如果一个连通块本身不是一棵树，那么如果它的一部分点能被删掉，那这部分点肯定组成一个森林，每棵树肯定之靠着一个环。外面的点先被删，而环旁边的点是最后被删的，那我们相当于对于每棵树就可以以环旁边那个点为根，然后 dp 上去。这个 dp 很方便，考虑到没两个点只会在其 LCA 上被合并一次，所以这部分的复杂度是 \(\mathcal{O}(n^2)\) 的。 然后我们考虑这个连通块本身就是一棵树的情况，这个情况下其实就是每个…

有一张 \(n\) 个点 \(m\) 条边的无向图，第 \(i\) 条边开通的条件是你已经走过了 \(d_i\) 条边，问 \(1\to n\) 至少需要走多少条边，或输出无解。\(n\le m\le 150,\,0\le d_i\le 10^9\)。 首先有一个 simple 的想法就是枚举路径上的 \(d\) 最大的边，然后先用比该边 \(d\) 小的边满足要求地走 \(d_i\) 步，然后再用 \(d\) 小于等于该边的边走到终点。 我们考虑将边从大到小排序，首先要算出前 \(d_i\) 步能到哪儿，这不难用矩乘，然后是走用小于等于 \(d_i\) 的边走到终点，这一个 bfs 即可解决。 代码在这里