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贪心删除出现次数最少的数。#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 #d...
A做法一:答案一定是相邻两个的差的最小值。考虑反证法:如果 $[l,r](l+1 < r)$ 是答案,那么中间一定能取到一段小于等于平均数的。做法二:二分答案。首先答案是 $\min_{i,j} \frac{a_i-a_j}{j-i}$,考虑二分最小值,那么相当于对于所有 $j>i$ 要有 $a_i-a_j \geq kj-ki$,也就是 $a_i+k_i \geq a_j+k_...
A我们固定 $s$ ,循环位移所有 $t$,发现答案就是相同的字母对数。而循环位移 $s$ 是本质不变的,所以答案乘个 $n$ 就好了。所以你构造的串中每个字母都要保证是 $s$ 中出现次数最大的,设这样的字母有 $c$ 个,答案显然是 $n^c$。B从高到低位贪心一定是最优的。对于每个点,我们可以通过判断周围点是否存在来确定这个点是否可以取走,每次取走能取的最大/最小后更新周围的点即可。C...
A设第 $i$ 个女生的限制为 $mx_i$,意思是存在一个男生给她 $mx_i$ 的礼物。设第 $i$ 个男生的限制为 $mn_i$,意思是要给所有女生 $mn_i$ 的礼物。设男女生都根据限制大小从小到大排序,首先如果 $mx_n > b_1$ 那么就无解(所有女生至少收到了 $mx_n$ 的礼物,但是第一个女生说她没收到,矛盾了)对于每个女生,我们都要钦定好一个男生送给他礼物,我...