在讨论《求问NOIP》回复：

cu ball @[Water__Problem](luogu://user/549623)

在文章《NOIP 有啥必知道的 9 个 trick》发表评论：

啥必知道的 trick，看看你中了几条

考虑单个连通块，容易发现只要它不存在欧拉回路，就一定无解。 这是因为，如果一个连通块有若干个存在欧拉回路的子图，则它们一定呈环状。假设原图无欧拉回路，那么这些子图一定由一些链串联起来，这些链就导致原图一定是无解的。如果一个连通块连一个这样的子图都没有，那更不用说。 考虑多个连通块的情形，我们发现只要有一个连通块无解整个…

**环形问题很容易想到回路**。 考虑**建立图论模型**（技巧点 1），我们将 $[0,2^n-1]$ 中的所有数作为节点，然后向他们能够转移到的节点连边，边权是 $0/1$，分别代表向末尾添加 $0/1$。设当前节点为 $x$，则它连向的节点编号为 `(x #include #include #include #i…

在文章《NOI 2024 游记》发表评论：

《In Rainbows》《Ants From Up There》好评

在讨论《问，关于CF》回复：

求问各位大佬，这个是 CF 自身的问题还是网络问题？

看到异或，考虑 01-trie。 小乔先选的情况，相当于枚举 $n$ 个数，对于每个数找其最大异或值的最小值。这个可以用 01-trie 轻松解决。 小蓝先选的情况，相当于枚举 $n$ 个数，对于每个数找其最小异或值的最大值。同样可以使用 01-trie，但需要注意不能和自己异或，于是需要在之前标记**独属于**当前…

在文章《题解：[ABC413E] Reverse 2^i》发表评论：

%%%

在文章《[ABC416E] Development 題解》发表评论：

/se

在文章《题解：AT_abc417_d [ABC417D] Takahashi's Expectation》发表评论：

orz

比较具有启发性的树形 dp。 若按照常规的做法，按照 dfs 序转移，则第一个要求容易实现，但第二个是不好实现的。 考虑转换角度，我们不妨令 $dp_i$ 表示节点 $i$ 所在深度，且当前深度选的点权最大值。这样按照深度转移，则第二个要求容易实现。那么第一个呢？对于每个节点 $i$，它当然从上方深度的最大值转移而来。…

看到前缀，考虑使用 trie，先把所有字符串扔到里面去。 然后发现要求方案数，于是考虑 dp，在本题中自然想到在 trie 上 dp 了。 具体而言，我们观察到 trie 有一种很好的性质：对于 trie 上的某个节点 $u$，$u$ 的子树内所有叶子节点所对应的字符串都有根节点到 $u$ 这条路径所对应的前缀。 这个…

> 本文摘自 [可持久化数据结构](https://www.cnblogs.com/XOF-0-0/p/18919848) 这种众数题又不带修首先考虑主席树吧。 但我们目前还不知道怎么使用它，先放着。 考虑刻画一个合法区间的形态：若一个区间内有 $tot$ 个「目标众数」（即严格大于区间长度一半向上取整的数），则必定有…

不要 `#define int long long`，否则可能导致 MLE。

考虑一种暴力的匹配方式：每当在 $a$ 中匹配到 $b_1$，就向后枚举匹配 $b_2,b_3,...,b_m$。 容易发现，若第一次匹配失败了，则后面的匹配都不可能成功，因此暴力匹配即可。 题目需要找两个，于是用一个 $cnt$ 数组记录每个 $b_i$ 在 $b_{i+1}$ 之前出现的次数。若匹配成功且至少有一个…

只有询问无修改，于是考虑莫队维护 $b_i$。 容易发现对于每个 $b_i$，它可以匹配的 $a_i$ 总是一个从 $1$ 开始的连续区间。采用贪心的思想，我们对于每个 $b_i$，我们尽量选择最大的那个 $a_i$，称其为它的「最佳位置」。 对于这种连续区间，我们考虑使用线段树维护之。维护三个信息： - 答案 $an…

在文章《题解：P3968 [TJOI2014] 电源插排》发表评论：

@__yabnto__ 就是你维护了左右最长连续空插排才能依据它维护 mx 和 m

区间问题，优先考虑线段树，$O(q \log n)$ 的时间复杂度可以承受。 具体的，我们维护五条信息： - 区间内被使用插排个数 $used$。 - 区间内的左端最长连续空插排 $lmx$。 - 区间内的右端最长连续空插排 $rmx$。 - 区间内的最长连续空插排 $mx$。 - 区间内的最长连续空插排的中间位置 $…

在讨论《【求助】为什么B图一定选最大团？》回复：

@[_Ansheng_](luogu://user/1496240) 是这样的。

RT，若 $B$ 去掉最大团中的一个人，使得 $A$ 图中有两个人能加进来（假设原本 $A$ 图中一个都选不了），这样显然更优啊。 但是这种情况是否存在呢？如果存在，是否需要每个 $B$ 中的最大团都需要讨论一遍？求 dalao 解答 qwq。

对于有关环的无向图问题，自然往双连通方面思考。 容易发现一个点双连通分量（下文简称 V-DCC）中至多有一个简单环。 这是因为，若有多个简单环，则必定存在割点。 于是我们直接在每个 V-DCC 里边统计即可。 进一步可以发现，若一个 V-DCC 满足边数与点数相等，则它里面的所有边都是答案。 统计点数是简单的。如何统计…

在无向图中，对于每一个简单环， 都会产生两种不同的走法，即走环的「上侧」或「下侧」。（可自行画图理解） 因为本题保证了是点仙人掌，于是设两点间的路径上有 $n$ 个环，则答案即为 $2^n$。 不难想到缩点形成一棵树，这样就可以简单地使用树上差分统计贡献了。 时间复杂度是 $O(q \log n)$ 的。[实现](ht…

在讨论《CSP-J押题》回复：

@[xujunlang2011](/user/738893) 折磨牛！！！

在讨论《听灌多》回复：

巨佬太强了！

在讨论《申请降黄》回复：

河南拔智齿。

在讨论《这个水平能进noip吗》回复：

IOI 2026 预备队员。

注意 dfs 参数顺序。

在讨论《【求助】关于时间复杂度》回复：

@[EasonLiang](/user/392626) 所以巨佬可以解释下为什么是 $O(n^2)$ 的吗 qwq。

有没有大佬帮忙分析一下这个程序的时间复杂度啊 qwq。个人感觉是 $O(n)$ 的，但超时了两个点。 题目是 P7912。 ```cpp #include #include using namespace std; const int N=2e5+5; int n,tot,a[N]; struct Node{ int…

在讨论《LCA #11 WA 求调》回复：

@[General0826](/user/1351126) 拜谢 /bx/bx/bx