AtCoder 乱做
感觉只会抄题解。。AGC020E首先自己可以想到如果只是要单纯的求一个串的方案数可以区间 dp:观察这个表达式,可以写成f := g | g + f g := '0' | '1' | '(' + f + '*' + 'x' + ')'其中 x 是一个数字,要求 $1$,并且 $f$ 是 $g$ 的一个长度为 $x$ 的循环节。那么就可以根据上面的定义写出 dp 了:设 $f_{l,r},g...
感觉只会抄题解。。AGC020E首先自己可以想到如果只是要单纯的求一个串的方案数可以区间 dp:观察这个表达式,可以写成f := g | g + f g := '0' | '1' | '(' + f + '*' + 'x' + ')'其中 x 是一个数字,要求 $1$,并且 $f$ 是 $g$ 的一个长度为 $x$ 的循环节。那么就可以根据上面的定义写出 dp 了:设 $f_{l,r},g...
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把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back...
A. 树的染色如果确定了某个点的颜色,我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。我们设 $f_v$ 表示钦定 $v$ 是白色,子树内是黑色的点的权值和的最小值。合并子树的时候钦定当前的根是白色,如果儿子 $x$ 和根同色子树和贡献 $a_x$,答案贡献 $f_x$;否则子树和贡献 $f_x$,答案贡献 $a_x$,背包合并即可。复杂度 $O(nm)$。#include <...
E题意有一个随机数生成器,生成 $[0,n-1]$ 之内的数,生成第 $i$ 个数的概率为 $\frac{A_i}{S}$,其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成,求期望生成次数,对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$,答案就是 $\max t_i$ 的...