Kruskal4668

摘要： D 考虑枚举两个区间最终的 \(\text{MEX}\)，发现固定 \(\text{MEX} = x\) 时，所有 \(< x\) 的数都要被包含，所有 \(=x\) 的数都不能被包含。合法区间 \((l, r)\) 相当于一个二维平面上的矩形，求其面积即可。 时间复杂度 \(O(n)\)。 #in 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

摘要： Cycle 困难图论题。 结论 \(1\)：如果一张竞赛图存在环，那么一定存在三元环。 证明： 取环上连续的三个点 \(a\to b\to c\)，根据竞赛图的性质，\(a, c\) 之间必然存在一条边： 若 \(a\to c\)，那么我们可以把 \(a\to b \to c\) 直接替换为 \(a 阅读全文

该文被密码保护。 阅读全文

摘要： Minimum Path 神仙分层图题。 不要考虑原式的实际含义，我们直接对整个式子考虑，设 \(e_{\max}\) 为最大边，\(e_{\min}\) 为最小边： \[\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} 阅读全文

摘要： 下 Niz 唐题，出题人少玩点原神吧。 Sol.1 Xor Hashing 给每个数字随机赋权，然后找到序列中所有值为 \(1\) 的位置 \(p_i\)，维护指针 \(j\) 从 \(p_i\) 一直扫到 \(p_{i + 1}\)，记录 \(p_i\sim j\) 之间的最大权值。那么要以 \( 阅读全文

摘要： DZY Loves Chinese II 【警告】：该题解的结论有误，等我有时间了再来修/kk 一道喵喵哈希题。 对于连通性问题，可以考虑对原图建出 DFS 树，然后对于不同的边采取不同的处理方式。在本题中，如果需要把原图割开，那么至少需要存在一条树边，使得经过它的非树边全都被割开，且它自己被割开。 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

摘要： 叶子的染色 谁家绿题这么难啊？ 结论 \(1\)：对于任意非叶子节点 \(u, v\)，以 \(u\) 为根求得的最优解与以 \(v\) 为根求得的最优解相同。即根的选择不影响答案。 证明： 考虑调整法，假设我要从 \(u\) 换根到它的一个儿子 \(v\)，进行分类讨论： 当根节点 \(u\) 有 阅读全文

摘要： T 形覆盖 场上没有注意到转化，对着基环树和树的部分暴力图论建模，爆肝 3h 大分讨以 7.88KB 的代码成功通过。 Sol.1 暴力分讨 下文中，我们称 T 形的中心为黑点，其余格子为白点。 从部分分做法开始想，当 \(\min dis\le 2\) 的时候： 容易发现，有影响的结构有三种： 切 阅读全文

摘要： Koala and Notebook 神秘题。 最小化数字的条件可以拆成： 先最小化数字长度。 在此基础上，最小化字典序。 直接建长度的最短路 DAG，然后在 DAG 上贪显然是不对的，因为对于长度不同的两个数字我们没办法判断接哪个更优秀。于是考虑一个图论建模的常用技巧：拆边。我们把 \(w\) 的 阅读全文

摘要： 粉碎 旧题新写。 结论 \(1\)：对于两张能同时存在的花色相同的牌 \(i, j(i < j)\)，若不存在 \(i < k <j\) 使得 \(a_i = a_k = a_j\)，则一定能将 \(1\sim j\) 全部删掉。 证明是简单的，如果 \(i, j\) 能同时存在（即 \(i\) 不 阅读全文

摘要： Divide 神仙题。 一个显然的想法是我们把人按照某种顺序排序，之后根据有序的性质进行 DP。但是你发现本题中“有序”这个性质根本用不上，我们需要找到另一种性质构造排列使其能够直接 DP。 注意到把人按照 \(w_i\) 排序后，若最后一个人和第一个人的和 \(\bm{w_n+w_1\ge m}\ 阅读全文

摘要： 猜数游戏 赛时大脑获得了犯困 debuff，成功宕机，11:30 才想出了这题。 看上去比较像交互最优化题，可以考虑一下对策略进行 DP。注意到一段区间的答案只与其长度有关，而与其具体对应的下标区间无关，因此定义 \(dp_{i}\) 表示长度为 \(i\) 的区间所需的最少询问花费。 因为我们的一 阅读全文

该文被密码保护。 阅读全文

摘要： Power Tree 简单题，场上大概写了 50min。 Sol.1 树形 DP 对所有数变 \(0\) 的条件进行刻画，把子树的条件画在序列上。具体而言，我们求出树的中序遍历，选择一个节点等价于将其子树的区间 \([l, r]\) 分离出来，即在 \(l - 1, l\) 之间与 \(r, r+1 阅读全文

该文被密码保护。 阅读全文