CF 1455 题解
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$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$ 的...
题意给出一个 $n$ 个点的数，边有边权，支持翻转一条边的边权，以及求最长的满足路径上边权异或和是 $0$ 的路径。题解相当于子树翻转，求相同颜色的直径。赛时被卡常做法：直接动态维护直径端点，合并的时候暴力枚举合并。一个比较优秀的做法：转括号序后两个点的距离就是括号匹配后失配的括号数量。先考虑如何快速求区间内失配的括号数量：考虑维护失配的右括号和左括号数量，记为 $a,b$。合并的时候设左儿...