A [CTSC2010]星际旅行我们考虑每次旅行收益一样，提示我们这题很可能可以贪心。然后考虑每个点有 $H_i \ge deg_i$ ，可以发现这正好是从 $1$ 出发遍历所有点然后回到 $1$ 的代价，于是我们先考虑终点在 $1$ ，直接把这个代价减掉，得到新的 $H_i$ 。此时能够增加答案的方法就是选择相邻的两个点把他们的 $H$ 同时减少 $1$ ，然后路径上就是进行一次左右横跳，会让答案增加 $2$ 。 这个过程显然是可以贪心做的（因为一个点）把 $H$ 留着匹配上面的收益和往下匹 ...

A 大佬的难题首先这题本身是一个裸的三维数点，直接做复杂度 $O(n\log^2 n)$ ，虽然各种卡常导致看起来随机数据是可以进 2.5 的，但是终测性能太差还是卡掉了！ 我们考虑一个容斥。我们考虑对三个序列两两求一次二维偏序问题，这个问题复杂度显然是 $O(n\log n)$ 的。然后考虑对于一对 $i,j$ ，设满足偏序关系的维度数是 $k$ 。如果 $k = 0,k = 3$ ，它的贡献显然都是 $3$ ，也就是三次求二维偏序都把它算进去了。如果 $k = 1,k = 2$ ，那么它的贡 ...

A 哈密顿回路被阴间到了，给了一个 $G{i,j} < G{i,k} + G_{k,j}$ 的没用条件看了很久发现确实没用，最后暴搜一下就跑过去了。。 我们折半搜索一下，具体来说，对于 $n = 14$ ，我们搜出 $1$ 出发的所有点的个数为 $7$ 的路径，再搜出所有 $1$ 出发点的个数为 $8$ 的路径，然后拼起来即可。复杂度大概是一个和 $\binom{13}{6}$ 有关的东西。 写完后试了试，发现跑的非常慢。这里写一下我的优化方法： 由于最后只需要合并一次，不需要开 set ...

A 圆圈游戏一道优秀的扫描线题。 我们考虑没有相交和包含，提示我们可以通过包含的关系建立出一棵树，一个点的儿子就是它极大的包含的圆。 如果能够建立出这个树，那么我们可以在树上做一个非常 trival 的 $dp$ 解决问题。转移就是枚举选不选这个点。 我们考虑怎么建立这个树。考虑从左往右进行扫描，到达一个圆的左端点的时候就加入这个圆，到达右端点的时候删掉他。我们考虑在删掉一个圆的时候找出它的父亲。 如果这个圆右端点向上引一条切线，考虑讨论一下这个切线碰到的第一段弧。如果这段弧是一个上圆弧，显然我 ...

A Training相当于是要求保留的非树边和尽量大。 我们考虑所有边 $(u,v)$ ，如果距离为奇数，显然这条边必删。 如果距离为偶数，那么加入后会存在一个奇环。但是如果有两个相交的奇环，那么它们拼起来的大环的大小就是两个环长度和减去共有的部分乘二，这是个偶环。 所以我们相当于需要加入若干个点对，使得两两路径之间无交。 事实上这题还在 CERC 中出现过一个无权值的版本，那个问题由于路径权值是 $1$ ，可以证明局部最优等价于全局最优，因此 $dp$ 更加容易，但在这里行不通。 由于每个点度 ...

6.11 模拟赛A Game我们考虑所有人的初始情况是一样的，所以可以逐一确定每个人的做任务情况。 所以有了一个朴素的想法，我们设 $dp[i][j]$ 表示前 $i$ 个人，一共已经做了 $j$ 个任务，这种情况下最小的天数是多少。不难发现，如果我们可以算出 $f(k-j,t)$ 表示一共 $k-j$ 的体力值，一共用 $t$ 天最多做多少任务的话，就可以直接 $O(nm^2)$ 解决问题。 这个东西看起来需要一个 $O(km^2)$ 的转移，但是事实上我们可以算出 $pd[i][j]$ 表示 ...

A 树考虑先化一下第一个式子，那么就是 \sum_{u\in A} d_u + \binom{|A|}{2} - \sum_{u \in A}\sum_{v \in A} [\text{u 是 v 祖先} ,w_u \le w_v] + \sum_{u\in B} \sum_{v \in B} [\text{u 是 v 祖先},w_u< w_v]然后我们不考虑 $\binom{|A|}{2}$ 。 可以猜测这个式子有特殊含义，所以把第一部分也加进这里面来统计，具体来说，我们把这个 $\sum_ ...

Topcoder 12505 CharacterBoard我们考虑如果能够枚举长度，那么每个字符对应回原串的位置就是固定的了，这样我们就可以直接 $26$ 的剩下字符个数次方得到答案。 但是事实上字符串的长度可能到达 $10^9$ ，这么考虑肯定是不行的。但是仔细想一想会发现，对于多数长度，你的 $n \times m \le 100$ 个字符根本不会有冲突。而有冲突的长度，必然是某两个字符之间差距的约数。因此我们直接枚举每两个字符之间的差距，然后枚举这个差距的约数，然后单独计算这些长度即可。剩 ...

A 宝石开场看错题 1.5h ，一直以为不能拿连续 $k$ 个宝石，然后发现 15pts 都不会，直接导致 T3 暴力都没打。。 我们考虑找出第一个位置，使得这个位置的颜色在之前出现过了，那么如果想继续往后选择，就必须把这个位置丢掉。我们一直重复找这种位置的过程，知道找到了第 $k+1$ 个，此时我们就只会在前面的东西种选择 $k$ 个扔掉。具体来说，对于每个出现了大于等于 $2$ 次的颜色我们只会保留最大的。 由于 $k$ 很小，我们可以考虑暴力做上面那个过程。每次之需要找到后面第一个重复出现 ...

懒得卡空间了！ 我们考虑对于一段区间来说，在全局加 $x$ 后，长度为 $l$ 的段的最优答案是啥。不难发现是 $lx + b$ ，其中 $b$ 为长度为 $l$ 段的和的最大值。因此我们可以对每个 $l = 1\sim n$ ，求出一条直线，然后对这个直线求一个凸包就可以做询问在全局加 $x$ 的情况下的和了。 然后考虑区间询问怎么办。首先我们可以把区间询问拆成 $O(\log n)$ 个线段树节点。然后对每个节点，我们维护出最大的后缀和，最大的前缀和，最大的区间本身子段，以及区间的和。之需要 ...