先考虑部分分怎么打。 根据个人习惯，规定下文中「直角蛇」是从最上面一行到达最下面一行。 subtask 2 不妨这样考虑：到达每一行后，都可以通过左右移动，到达下一行的任意一个位置。到达第一行的位置可以任选；从任意位置到达最后一行后，可以再通过左右移动，在任意位置结束。所以答案就是 \[ m^{n+1} \] subtask 1 and 3 这两个子任务都可以用 \(O(nm)\)

区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 \([i,j]\)，最后一个元素的来源会对转移产生影响，所以设 \(f(i,j,0/1)\) 为考虑区间 \([i,j]\)，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单 \[ f(i,j,0) = [a_i < a_{i+1}]

二分图判定 没啥技巧，最难的是把图论模型建起来。 luogu1330 封锁阳光大学 相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。 图可能不连通，取的是每一张二分图的左右边的较小值。 #include<bits/stdc++.h> using namespace std; #define int long long #define ui

欧拉路径 定义 从一个点出发，不重不漏地经过图中每一条边的一条路径，允许重复经过节点。 无向图 首先必须是连通图，其次是两种情况。 所有点的度数是偶数。 恰好存在两个点的度数是奇数。 有向图 要求连通。 所有点的入度等于出度。 恰好存在一个节点入度比出度多 \(1\)，一个节点入度比出度少 \(1\)。

Hankson的趣味题 从质因子的角度考虑。 把 \(a,b,c,d\) 都分解了，对于一个质因子 \(p_i\)，题目给出的条件等价于 \[ \min \Big( e_{p_i} (x) ,e_{p_i} (a)\Big) =e_{p_i}(c) \] \[ \max \Big( e_{p_i}(x),e_{p_i}(b) \Big) = e_{p_i}(d) \] 讨论一下就

考虑如果 \(a\) 能看见 \(b\)，那么从 \(a\) 到 \(b\) 连边。 先从简单的图上开始分析。 考虑在 DAG 上的情况，发现还是不太容易确定。 Part1 不妨先只考虑有向链，这个很简单，最大就是链长（超过 \(3\) 的话），最小是 \(3\)。然而当我们把若干形态的链拼成一张 DAG 时，则会出现一个点到达另一个点的路径不止一条，从而导致很诡异的事情，似乎不太容易找

本文主要放知识点。 质数筛 埃氏筛模板 void prime() { for(int i=2;i<=n;++i) if(!v[i]) { for(int j=i*i;j<=n;j+=i) v[j]=1; // 优化：从i*i开始枚举 } } 线性筛模板 void ora() { for(int

对于 \(K=1\) 的情况，每组里面都不能有冲突，所以从后往前尽可能划分，容易证明这样做是对的。 如何判断冲突？注意到值域不大，可以开一个桶，枚举一个完全平方数 \(k^2\)，判断 \(k^2-x\) 是否出现过即可。完全平方数的个数是 \(O(\sqrt{n})\) 的，所以复杂度为 \(O(n \sqrt{n})\)。 对于 \(K=2\) 的情况，如果我们把有冲突的点连边，那么

[ARC101E] Ribbons on Tree 对于以 \(x\) 为根的子树，如果 \((x,fa_x)\) 的边没有被覆盖，那么说明子树内没有任何一个点与子树外的点匹配。 把这些没有被覆盖的边看作特殊边，那么整棵树就被若干特殊边划分成了若干连通块。我们要求的是不含任何特殊边的匹配方案。 考虑容斥。钦定一个边集 \(S\)，表示 \(S\) 内的边一定是特殊边。根据子集反演，容斥

并查集是一个森林，每棵树表示一个集合，并且这个集合根据某种具有传递性的关系构建起来。 普通并查集关心的信息只有 \(x\) 所在集合的根，\(fa_x\) 表示的仅仅是一个传递性关系，即 \(fa_x\) 与 \(x\) 所在集合的根相同。从任意节点往上跳，都能找到它所在集合的根。 使用路径压缩优化，在向上访问节点时，把路径上所有节点的 \(fa\) 都改为根，那么就能做到单次查询均摊