比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18786128
开题 + 补题情况
很菜的一把，就开了三个签到题，1001 Lucas 定理花了好久才看出来，明明前两周 CF div3 才遇到过，1010 那么明显的曼哈顿距离拆绝对值想了八百年才想出来，明明寒假集训才学过的，真的感觉自己基础太不牢固了，很多很基本的东西用不好。
1005 – 修复公路
非常明显的并查集，答案就是连通块个数 \(-1\)。
点击查看代码
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int N = 3e5 + 9;
int a[N], fa[N];
int root(int x) {
return (fa[x] == x) ? x : fa[x] = root(fa[x]);
}
void merge(int u, int v) {
fa[root(u)] = root(fa[v]);
}
void solve()
{
int n;std::cin >> n;
for(int i = 1;i <= n;i ++) {
std::cin >> a[i];
}
for(int i = 1;i <= n;i ++) {
fa[i] = i;
}
for(int i = 1;i <= n;i ++) {
if(i - a[i] > 0) {
merge(i, i - a[i]);
}
if(i + a[i] <= n) {
merge(i, i + a[i]);
}
}
int sum = 0;
for(int i = 1;i <= n;i ++) {
sum += (root(i) == i);
}
std::cout << sum - 1 << '\n';
}
1001 – 数列计数
乘积为奇数，那就是每一项都是奇数，运用 Lucas 定理，一个组合数 \(C_n^m\) 为奇数，当且仅当 \(n \& m = m\)。
若我们先忽略掉题目给的 \(L_i\) 的限制，则答案为 \(2^{sum_i}\)，\(sum_i\) 为 \(a_i\) 中为 \(1\) 的位数，很好理解，也就是对于这些位，\(b_i\) 可以取 \(0\) 也可以取 \(1\)，总的组合数。
但是题目有一个 \(L_i\) 的限制，这个如何考虑呢？
- 如果 \(L_i \geq a_i\)，则无需考虑。
- 如果 \(L_i < a_i\)，那么我们从高位到低位考虑。
- 如果 \(a_i\) 这一位为 \(1\)，但是 \(L_i\) 这一位为 \(0\)，则我们减掉第 \(i\) 位右边所有 \(a_i\) 为 \(1\) 的位的组合数，相当于就是减掉了这一位取 \(1\) 的情况，因为此时大于了 \(L_i\)，不合法；如果 \(a_i\) 这一位。
- 如果 \(a_i\) 这一位为 \(0\)，但是 \(L_i\) 这一位为 \(1\)，则我们直接跳出循环，因为后面的答案都是合法的。
对每一个数的答案乘起来就是最终答案了。
点击查看代码（省略了取模类）
const long long M = 998244353;
using Z = ModNum<M>;
const int N = 2e5 + 9;
void solve()
{
int n;std::cin >> n;
std::vector<i64> a(n), l(n);
for(auto &i : a)std::cin >> i;
for(auto &i : l)std::cin >> i;
Z ans(1);
Z t(2);
for(int i = 0;i < a.size();i ++) {
int sum = 0;
for(int j = 0;j < 32;j ++) {
if(a[i] & (1 << j)) {
sum ++;
}
}
Z tmp;
tmp = t.Pow(sum);
if(l[i] < a[i]) {
for(int j = 31;j >= 0;j --) {
if(a[i] & (1 << j))sum --;
int x = (a[i] >> j & 1);
int y = (l[i] >> j & 1);
if(x == 1 && y == 0) {
tmp -= t.Pow(sum);
}
if(x == 0 && y == 1) {
break;
}
}
}
ans *= tmp;
}
std::cout << ans << '\n';
}
1010 – 选择配送
寒假集训的时候才学过的东西，竟然想了这么久，真的不应该。
对曼哈顿距离拆掉绝对值，可以得到 \((x_1, y_1)\)，\((x_2, y_2)\) 的曼哈顿距离为：
- \(\max((x_1 – y_1) – (x_2 – y_2),(x_1 + y_1) – (x_2 + y_2),(x_2 – y_2) – (x_1 – y_1),(x_2 + y_2) – (x_1 + y_1))\)。
对 \(x_2 – y_2\) 和 \(x2 + y_2\) 各自维护一下最大最小值，然后对每个待选点查询一下即可。
点击查看代码
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int N = 2e5 + 9;
struct Node {
i64 x, y;
};
void solve()
{
int n, m;std::cin >> n >> m;
std::vector<Node> a(n), b(m);
for(auto &[x, y] : a) {
std::cin >> x >> y;
}
for(auto &[x, y] : b) {
std::cin >> x >> y;
}
i64 admx = -inf64, admi = inf64, demx = -inf64, demi = inf64;
for(int i = 0;i < n;i ++) {
admx = std::max(admx, a[i].x + a[i].y);
admi = std::min(admi, a[i].x + a[i].y);
demx = std::max(demx, a[i].x - a[i].y);
demi = std::min(demi, a[i].x - a[i].y);
}
i64 ans = inf64;
for(auto &[x, y] : b) {
i64 tmp = -inf64;
tmp = std::max(tmp, x + y - admi);
tmp = std::max(tmp, admx - (x + y));
tmp = std::max(tmp, x - y - demi);
tmp = std::max(tmp, demx - (x - y));
ans = std::min(ans, tmp);
}
std::cout << ans << '\n';
}
来源链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18786128
没有回复内容