AGC039E Pairing Points
题意在环上分布着 $2n$ 个点，保证对于任意一个六元组 $(a,b,c,d,e,f)$，线段 $ab,cd,ef$ 三点不交于一线。还给出了一个 $2n \times 2n$ 的矩阵 $A$。现在你要讲这 $2n$ 个点两两配对，满足以下条件：每一对点之间都连线，以交点为点，所有交点之间的线段为边，构成的图是一棵树如果配对 $(u,v)$，必须满足 $A_{u,v} = 1$$n \leq...
题意在环上分布着 $2n$ 个点，保证对于任意一个六元组 $(a,b,c,d,e,f)$，线段 $ab,cd,ef$ 三点不交于一线。还给出了一个 $2n \times 2n$ 的矩阵 $A$。现在你要讲这 $2n$ 个点两两配对，满足以下条件：每一对点之间都连线，以交点为点，所有交点之间的线段为边，构成的图是一棵树如果配对 $(u,v)$，必须满足 $A_{u,v} = 1$$n \leq...
题意有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。题解显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪...
A贪心填。先尽量填竖着的再填横着的。因为这样最多会浪费 $1$ 个，所以达到了答案的上界。求出上界判断是否 $\leq$ 即可。B枚举一个位置 $i$，前面只保留 $0$ 后面只保留 $1$，判断是否合法即可。C首先第一步横着走还是竖着走都是一样的。我们设第一步横着走。那么横着走只可能用奇数位置的 $c_i$，竖着走只可能用偶数位置的 $c_i$。枚举总共有几段，然后贪心选择最小的即可。注意...
A$g(x)$ 实际是求原数和去除后缀 $0$ 后的数的比值，发现第一个不同的值一定会在 $10^x$ 达到，所以答案就是字符串长度。B我们先假设走了 $m$ 步，并且都是走第一种，那么相当于就是走了 $\frac{m(m+1)}{2}$，发现将第 $i$ 个位置改成第二种操作会减少 $i+1$，我们先找到最小的 $m$ 满足 $\frac{m(m+1)}{2} \geq x$ ，设 $r=...
A. 树的染色如果确定了某个点的颜色，我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。我们设 $f_v$ 表示钦定 $v$ 是白色，子树内是黑色的点的权值和的最小值。合并子树的时候钦定当前的根是白色，如果儿子 $x$ 和根同色子树和贡献 $a_x$，答案贡献 $f_x$；否则子树和贡献 $f_x$，答案贡献 $a_x$，背包合并即可。复杂度 $O(nm)$。#include <...