0103abc 的网站

观察样例可得答案要么为 $0$ 要么是 $2$ 的若干次幂的形式。 考虑若存在两个箱子 $i,j$ 满足 $ai<aj<bi<bj$ 则 $i,j$ 两个箱子不能被放在同一个栈内。一个暴力的方法是直接枚举所有这样的二元组 $(i,j)$，这两个元素不能同属一个栈，因此直接扩展域并查集把...

考虑用一个二元组 $(u,i)$ 来维护状态，表示当前在车站 $u$ 的 $i$ 号线上。一个暴力的做法是直接建出整张图然后跑 dijk，但是时间复杂度明显爆炸了。 注意到导致边的数量爆炸的原因主要是换乘，因此考虑优化这个部分。在某个车站从线路 $x$ 换到线路 $y$ 的代价固定为...

为了方便，这里把 $A$ 数组降序排序。 设在某一时刻当前还没有被弹出的 $A$ 集合内最大的元素为 $Aj$，则之后插入一个不属于 $A$ 的数 $x$ 时必须满足 $x>Aj$。证明考虑如果插入了一个数 $x<Aj$ 且 $x\not\in A$ 则以后想要把 $Aj$ 弹出来之前必须先弹出来...

为啥有黑来着。 有经典结论：竞赛图三元环数量为 $\binom n3-\sum\limits{i=1}^n\binom{\degi}{2}$，其中 $\degi$ 表示 $i$ 点的出度。最大化三元环的数量即最小化 $\sum\limits{i=1}^n\binom{\degi}2$ 也就是最小化...

题目中给的东西其实就是要求排列对应的坐标点落在大圆和小圆之间求排列的数量。记 $fi$ 表示满足 $x^2+i^2<n^2$ 的 $x\in[0,2n)\cap\mathbb N$ 的数量，$gi$ 表示满足 $x^2+i^2\le 4n^2$ 的 $x\in[0,2n)\cap\mathbb N$...

是人类能做的题吗，，，感谢 gpt 姐姐帮我理解这个题。 题目就是统计有多少张 $n$ 个点的，最小点覆盖恰好为 $k$ 的有标号简单无向图，答案对 $2$ 取模。 有经典结论：任意 $n$ 个点的无向图中最小点覆盖大小和最大独立集大小的和为 $n$。因此问题等价于统计最大独立及大小恰好为...

警察局 $S$ 的数量很少，因此猜测最终做法的时间复杂度中带一个 $2^S$。记 $cnti$ 表示如果 $i$ 集合内的警察局都可以覆盖到的格子的数量（不包含警察局本身所在的格子），然后考虑 dp，设 $fi$ 表示只能分配给集合 $i$ 中警察局的格子的数量，转移显然就是...

套路的考虑把括号串放到二维平面上考虑，记 的权值为 $1$， 的权值为 $-1$，权值数组为 $wi$，前缀和数组为 $Si$，则括号串可以看作是一条过 $(i,Si)$ 点的折线。则此时路径最低点到起点的纵坐标高度差就是无法匹配的右括号...

部分内容参考了该题解。 大的来了。 题目的条件可以看作是存在整数 $l$ 满足 $3l\le k$ 且前 $2l$ 个数构成回文串，因此问题可以看作是统计长度不超过 $n$ 的序列中存在一个足够短的偶数长度回文前缀的序列数量。 考虑 dp，设 $fi$ 表示长度为 $2i$...