### 奇环树的定义 > 一棵树+一条边 ### 无向奇环树 $n$ 个点 $n$ 条边，联通。 ### 有向奇环树 :::info[外向奇环树] 每个点恰好一条入边，形态上就是一个环出出发走到链 ::: :::info[内向奇环树] 每个点恰好一条出边，形态上就是任意点出发都能走到环中 ::: ### 奇环树的处理…

## T2 ### 思路 首先可以证明三个点的各自路径必然有一个交汇点。 然后根据贪心，肯定会优先选择最远的两个点，剩下一个再考虑，所以就是直径+一条链。 ```cpp #include using namespace std; const int N = 2e5 + 10; int n, s, x, y, z, le…

## T1 ### 思路 我挂了QWQ。成唐人了多考虑了一种情况。 首先可以发现，如果选的数字为一奇一偶，那么获得的数字就会比两数之和小一，否则得到的数就等于两数之和。所以后手肯定尽量会选一奇一偶，而先手则需要尽快的奇数或偶数用光。发现先手全部选取奇数时速度相当的快，先后手各操作一次后会减三，而偶数加一，而但是如果都选…

## T1 ### 思路 差分约束+倍增LCA秒了。 ```cpp #include using namespace std; const int N = 1e5 + 10; int n, k, fa[N][30], dep[N], sum[N], u[N], v[N]; vector E[N]; void dfs1(…

## T1 ### 思路 裸的树的直径。 ```cpp #include using namespace std; const int N = 5e5 + 10; int n, len, d1[N], d2[N], ans; vector > E[N]; void dfs(int x, int fa) { for(in…

在讨论《【新版个人中心、相似工单】25 年 10 月更新》回复：

qp

## A ### 思路 貌似我的最屎山'^' 我的思路就是先考虑顺序遍历一遍整个括号序列，先进行正常的括号匹配，同时把路上碰到的问号塞进一个队列里面，如果一个右括号出现了没有左括号可以匹配的情况，就把队头拿出来和它匹配。这个过程中要顺便统计剩余的未匹配的左括号数量，做一个后缀最小值，然后再顺序遍历一遍，并统计当新添加的…

## A ### 思路 没啥思路，就是按照题目说的来。 ```cpp #include #define int long long using namespace std; const int N = 1e4 + 10; int n, k, sum = 1; string p, s[N], d[N]; signed m…

## T1 ### 思路 送分题，抬走。 直接杀掉 $m-1$ 个区间，使这些区间的和最大。 时间复杂度 $O(n\log n)$ ```cpp #include using namespace std; const int N = 1e5 + 10; int m, s, c, a[N], ans; int main(…

这难度不合理啊C ## A ### 思路 ~~看到 $n$，原地爆炸；~~ ~~看到 $q$，直接起飞。~~ 为何 $q$ 这么小啊。 于是邪恶的复杂度就来了：$O(q\sqrt{n}\log n)$。我们可以先分块，然后对于块内直接排序，查询时二分就行了。 ```cpp #include #define int lo…

## T1 ### 思路 对于每一个数，先全部放进去，直接升序排序，然后如果其贡献为负数（包括对其他数的加成）就直接杀掉。 ```cpp #include #define int long long using namespace std; const int N = 1e6 + 10; int n, k, a[N],…

## T1 ### 思路 直接把 $b$ 对 $a$ 做差后直接差分，算其中的正数的和。 ```cpp #include using namespace std; const int N = 2e5 + 10; int n, a[N], b[N], ans; int main() { ios::sync_with_st…

在文章《题解：P11526 [THUPC 2025 初赛] Imyourfan》发表评论：

tql把我也看得不会生产阳光了

## A ### 思路 其实就是一个逆序对。 ```cpp #include using namespace std; const int N = 1e5 + 10, MOD = 1e8 - 3; int n, t[N], w[N], ans; struct Node { int x, y; bool operator…

## A ### 思路 首先发现，无论你如何翻转，逆序对的奇偶性是不变的，并且当且仅当其逆序对数量为偶数时才是有可能的，所以可以直接算逆序对。 ```cpp #include #define int long long using namespace std; const int N = 1e6 + 10; int T…

## A ### 思路 相比其他人相对诡异。 因为是一个三角形，所以左边那个纵向的边界直接一维差分维护，但是右边那条斜边非常不好搞，所以直接化斜为直，把一条一条的斜边“拉直”，也可以理解为翻转 $45$ 度后再看的矩形。然后也同样可以用差分维护。 ```cpp #include #define int long lon…

## A ### 思路 可以把一条边的字符串拆成一个一个的点与一条一条的边，只包含 $1$ 个字符。然后先考虑第二问。首先可以发现为了字典序最小，我们必须要求走的每一步都是最小的，即如果你当前走了 $d$ 步，则你来自的那条边的字符必须是能走到的所有可能中最小的，否则就没有继续搜下去的必要。然后第一问，其实就是加了长度…

## T1 ### 思路 首先区间 DP 是显然的。但是转移时出了问题：很明显直接转移会算重复，于是我们考虑去重。我们发现对于右边那颗子树，不妨稍微缩小一点，把 $dp_{k,j}$ 改为 $dp_{k+1,j-1}$。这个东西就能保证因为两边不对称，就杀掉了重复。（口胡 ```cpp #include #define…

## T1 ### 思路 好想，直接倍增 LCA，看到 $c_i$ 那么小那不就直接状压吗？ ```cpp #include using namespace std; const int N = 1e6, M = 21; int n, q, c[N], sum[N][M], fa[N][M], dep[N]; vect…

## T1 ### 记录 预估 $100pts$，实际 $100pts$。 ### 思路 竟然还有送分题😲 首先发现无解非常朵好判，就是类似 `a->b,b->c,a->c` 之类的，就是去除重边后，做并查集，去除重边后如果有边连接的两点在同一块内，则无解，否则合并这两个块。最后对块的数量做阶乘即为答案。 ```cp…

## A ### 思路 非常好想，直接二分长度哈希统计即可。 ```cpp #include #define int long long using namespace std; const int N = 20010, mul = 20013, MOD = 998244353; int n, k, a[N]; int…

在讨论《求问CSP-S GD小道消息真实性》回复：

~~wow，【】~~

在讨论《坐标 HN，-S初赛85pts有救吗》回复：

/bx

T3MLE了我心态炸了😭😭😭😭😭😡😡😡😡😡 ## T1 ### 记录 $100pts$ ### 思路 竟然还有小学数学。 第一眼看到这个式子： $$\sum_{i=2}^{n}\frac{1}{u(i)v(i)}$$ 其中 $u(i)$ 是大于 $i$ 的最小质数，$v(i)$ 是不大于 $i$ 的…

## A ### 记录 完了我是唐龙，分层图写了1.5h😡，然后发现发现我是乐子。 $100pts$ ### 思路 你写后会发现发现，对于两个位置之间，随你怎么连（$1$ 连 $1$，$2$ 连 $2$ 和 $1$ 连 $2$，$2$ 连 $1$ 无论怎么样都是可以和两边相接），既然有这么好的性质，那么就好些多了：直…

## A ### 记录 $84pts$ 但是 Vjudge 当前弧优化没写/ll ### 思路 首先，欧拉路径还是很明显的。但是要求每条边要从两个方向各走一遍。那么不就是把它拆成有向边再跑欧拉路径吗？~~披着无向图标签的有向图~~ ```cpp #include using namespace std; const i…

## T1 ### 记录 $100pts$ 为什么是蓝题为什么是蓝题为什么是蓝题为什么是蓝题 ### 思路 首先考虑一半对一半的情况，考虑把 `G` 组的权值设为 $1$，把 `H` 组的权值设为 $-1$，按照位置把同学排序后对权值做前缀和，因为是一半 `G`，一半 `H`，所以在这种情况下的“公平区间”的权值和即为…

## A ### 思路 还是挺板子的一道缩点题，边权转点权做法相当丰富，可以直接缩点后弄到一个节点上，也可以把一条边拆分成两条边，中间的节点存边权。然后整体上还是很想缩点模板的。复杂度为 $O(n+m)$。 ### 代码 ```cpp #include #define int long long using names…

## A ### 思路 分层图板子（我因为建边和建成小根堆而死掉了），就是分 $k + 1$ 层，代表使用了几次（第一层表示没使用），然后在各层的终点找最小值就行了。 ### 代码 ```cpp #include using namespace std; const int N = 2e4 + 10, K = 40;…

在讨论《洛谷网校秋季课程报名指南》回复：

qp