0103abc 的网站

图不连通肯定不满足条件。下面的分析均基于“图连通”这一条件。 考虑在图中任意选择一棵生成树 $T$，并对其在满足 $1$ 条件的情况下，按照 dfs 顺序贪心的让当前访问到的结点尽可能的上色。此时只需要想办法让其满足 $2$ 条件。然后可以惊喜的发现此时这个生成树上不存在一条边...

可是我还真的不知道这个性质啊/kel 这题太麻森了，交互题不交互.jpg 考虑到图是一张竞赛图，竞赛图有下面的几条性质： 任意一个点入度加上出度为 $n-1$。 任意一张竞赛图缩点后一定为链。 若 $x$ 点的出度大于或等于 $y$ 点的出度，则 $x$ 一定可以到达 $y$。 同样的，若 $x$...

首先树上路径计数一类的问题肯定可以上点分，但是有做法可以做到严格 $O(n)$。 考虑对于树上的一个点 $u$，在其子树点集 $Su$ 中的点 $v$（$v\in Su$）满足 $cu=cv$，则显然 $v$ 只能和 $Su$ 中除了 $u$ 以外的结点做贡献。于是考虑从根节点 $1$ 开始对树做...

感觉这题很聪明，赛时切这题的人是怎么想到的（ 考虑分类 $1$ 的位置：若确定 $1$ 在序列左半边还是右半边，则必然能找出长度 $\le\frac{n}{2}$ 的区间使得该区间正确的和为 $0$，长度 $>\frac{n}{2}$ 的区间使得该区间正确的和为...

暴力可过，所以不写郑洁了！！111 考虑一个经典 dp。设 $f{k,i,j}$ 表示从 $i$ 走到 $j$，且走了 $k$ 步，经过的路径的最大权值的和是多少。显然初始条件：对于每一条边 $u\to v$，且其边权为 $w$，都有 $f{1,u,v}=w$。转移是简单的：枚举中转点 $x$，则...

简单容斥题。考虑到 $\text{lcm}(i,j,k)\ge i+j+k$ 不好做，于是可以求 $\text{lcm}(i,j,k)<i+j+k$ 的不同方案数。因为 $i<j<k$ 所以枚举 $k$，必有 $i+j+k<k+k+k=3k$。也就是说有且仅有下面的两种合法情况：...

简单题，~~但是没想出来~~ 考虑对于每一个不为 $1$ 的数 $i$，若其之前没有访问过，则将所有 $i^k$ 全部标记，并将所有底数为 $i^k$ 的数全部列出。可以将底数全部改为 $i$ 然后同样的修改指数的值。问题变为计算有多少本质不同的二元数对 $(i,j)$ 同时满足下列条件：...

首先套路的，枚举第一条加入的边 $u\to v$，并将其缩为一个点。此时问题变为给定一个有根树，每一次只能从上往下加边，问有多少种不同的加边方法。 然后肯定就是在树上 dfs 遍历每一个结点，然后合并该结点的所有子树信息。设 $f_u$ 表示 $u$...

简单的问题。子序列相关题目考虑在子序列自动机上 dp。套路的，设 $to{i,j}$ 表示 $i$ 后面第一个字符 $j$ 出现的位置，$fi$ 表示当前到 $i$ 位置，可以得到的不同的子序列的数目。则 $to{i,j}$ 显然可以 $O(n)$ 处理，$fi$...

XorForces。每日被 Hack。 首先考虑异或的性质： 壹 若 $x\oplus y=0$，则 $x=y$。 壹.证明 若 $x\oplus y=0$，则 $x$ 和 $y$ 二进制表示下每一位的值都相同，显然只有两个数完全相同时才能有这样的性质。因此得证。 贰 若 $x\oplus...