20联赛集训day9 题解
A考虑枚举右端点，维护所有左端点的答案：只需要处理出 $pre_i$ 表示 $i$ 前面第一个和它一样的位置，每次让 $(pre_i,i]$ 加上 $w$，$(pre_{pre_i},pre_i]$ 减去 $w$ 即可。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi firs...
A考虑枚举右端点，维护所有左端点的答案：只需要处理出 $pre_i$ 表示 $i$ 前面第一个和它一样的位置，每次让 $(pre_i,i]$ 加上 $w$，$(pre_{pre_i},pre_i]$ 减去 $w$ 即可。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi firs...
A如果长度为 $2$ 特判，否则将第一个数和剩下的数分开。B$B$ 进制下正整数的数根等价于 $\pmod {B-1}$，注意这里 $0$ 对应的答案是 $B-1$。所以答案是 $(k-1)B+x$。C双指针扫出所有相同的段，每段取前 $k$ 大即可。D观察一下发现只需要枚举 $x|n$，然后前缀和预处理+判断所有矩阵是不是全 $0/1$ 矩阵即可。时间复杂度分析一波：先考虑行的贡献，枚举的...