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$ 的...