contest2 题解
A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合,转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论:对于 $\leq \sqrt n$ 的质数只有 $8$ 个,先状压,然后将其他的数字,如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人,所以对每一类先预处理 $g_{S}...
A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合,转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论:对于 $\leq \sqrt n$ 的质数只有 $8$ 个,先状压,然后将其他的数字,如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人,所以对每一类先预处理 $g_{S}...
A如果长度为 $2$ 特判,否则将第一个数和剩下的数分开。B$B$ 进制下正整数的数根等价于 $\pmod {B-1}$,注意这里 $0$ 对应的答案是 $B-1$。所以答案是 $(k-1)B+x$。C双指针扫出所有相同的段,每段取前 $k$ 大即可。D观察一下发现只需要枚举 $x|n$,然后前缀和预处理+判断所有矩阵是不是全 $0/1$ 矩阵即可。时间复杂度分析一波:先考虑行的贡献,枚举的...
A假设 $a \geq 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 ...
A手玩一下样例,我们从大到小确定每个数:将确定的数挪到序列的最前面,设确定了 $x$ 个数,那么 $x \times x$ 的方格的数都没用了,并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值,所以我们只需要每次取最大值,将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。B可以猜测一下选择方案一定是前面可能有某些增加值的地方,后面值就一直不变了。所以我们先一...