Uesugi1

摘要： link 第一次遇到这个套路，不看题解真看不懂这个条件是干什么用的 /ll。 这个条件能转化为原图存在 \(k+1\) 染色的方案。 初始 \(1\) 个点子图必定存在 \(k+1\) 染色。考虑 \(i\) 个点的导出子图，找到其中 \(d\le k\) 的点 \(u\)，则除去点 \(u\) 的 阅读全文

摘要： 感觉不算很难。 首先边双中显然存在定向方案使其中的点互相可达。 发现缩完点双后就是一棵树，\(u\to v\) 的限制就是 \(bl_u\to lca\) 这条链上的边连向父亲，\(lca\to bl_v\) 连上连向子节点，其中 \(bl\) 表示为所在的边双编号。而这是简单的，树上差分记录一下被 阅读全文

摘要： 第一道单位根反演。还挺牛的。只是为什么但凡推导中换一步都推不出来啊 /wq，等到推式子功力足够深厚才能做到这种题吧 /yun。 单位根反演的式子形如： \[[x|n]=\frac{1}{x}\sum_{i=0}^{x-1}\omega_{x}^{ni} \] \(x|n\) 显然，原式 \(=\fr 阅读全文

摘要： 不考虑 \(c\) 是简单的，容易转化为格路计数，路径价值为每一步权值之积。 枚举起点 \((1,i)/(i,1),i>1\) 因为不能走到另外的第一行/第一列的元素，所以 \((1,i)\) 先走到 \((2,i)\)，\((i,1)\) 先走到 \((i,2)\)，\((x,y)\) 到 \(( 阅读全文

摘要： 做的第一道 \(\min-\max\) 容斥题。 题目相当于求所有集合第 \(E(min_k S)\) 其中 \(min_k S\) 表示 \(S\) 中物品出现时间的第 \(k\) 小。 这种形式跟拓展 \(\min-\max\) 容斥的形式完全一致。 \[E(min_k S)=\sum_{T\s 阅读全文

摘要： 不合法就是序列 \(\max\) 前面存在 \(a_i>a_j,j\in[i+1,i+k]\)，这个限制不好计数，跟 \(a_i\) 在序列中的相对大小有关，也跟位置有关。 考虑总情况 - 合法情况。 要返回正确的最大值，则 \(\max\) 前面的部分不能提前推出，明显是要对这种序列计数。 \(f 阅读全文

摘要： 千山鸟飞绝，万径人踪灭。 孤舟蓑笠翁，独钓寒江雪。 题目中本质不同独立集表述不清，实际上含义是若存在两独立集分别在 \(u,v\) 为根，无标号时，树的结构与节点染色情况相同，则记为一种。 要去除换根后相同的情况不好处理。考虑能否去除此限制，貌似是套路 /yiw。以重心 \(u\) 为根，若以 \( 阅读全文

摘要： 这也太 hard 了，如何想到这个双射 /wq。 对于 \(P\) 恰好 \(i\) 个上升对，\(P^-\) 恰好 \(j\) 个上升对计数记作 \(f_{i,j}\)。不妨考虑计数 \(P\) 至少 \(i\) 个上升对，\(P^-\) 至少 \(j\) 个上升对 \(g_{i,j}\)。 \[ 阅读全文

摘要： 这篇文章中有讲基础的卡特兰数。 因为 OI 中的习惯，本文用 \((n,m)\) 表示平面直角坐标系上 \(x=m,y=n\) 的点。 单线限制 根据卡特兰数，考虑拓展。 · 每次向上或向右，从 \((0,0)\) 走到 \((n,m)\) 不越过 \(A:y=x+k\) 的方案数。 将向上走视作 阅读全文

摘要： 我咋感觉这玩意标记跟矩阵完全不是一个难度的呢。这个套路应该不会再考了，不过还是整理一下。 先看一个问题引入： 给定一个序列 \(a\) 有两种操作，支持以下操作。 \(i\in[l,r],a_i\to a_i+x\)，即区间加 查询 \(\sum_{i=l}^r b_i\) 每轮操作后 \(i\in 阅读全文