写在前面
比赛地址：https://codeforces.com/contest/1884
捏吗我不会容斥，我是飞舞。
A
\(k\le 10\)，于是直接枚举 \(x\sim x+20\) 检查即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool check(int x_, int k_) {
int ret = 0;
while (x_) ret += x_ % 10, x_ /= 10;
return (ret % k_ == 0);
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int x = read(), k = read();
for (int i = x; i <= x + 20; ++ i) {
if (check(i, k)) {
printf("%d\n", i);
break;
}
}
}
return 0;
}
B
发现每次从询问 \(i\rightarrow i + 1\) 时均是把末尾的一堆 1 前移，操作次数等于末尾的 1 的个数。
于是模拟该过程，记录当前末尾的一堆 1 的数量和其中最左侧的 1 的位置即可。当无法前移时无解。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, num;
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
scanf("%s", s + 1);
LL ans = 0;
int cnt = 0, last = n + 1;
for (int i = n; i; -- i) {
while (last != 0 && s[last - 1] != '0') ++ cnt, -- last;
if (last == 0) {
printf("-1 ");
continue;
}
-- last;
ans += cnt;
printf("%lld ", ans);
}
printf("\n");
}
return 0;
}
C
考虑枚举作为 \(\min\{ a \}\) 的位置 \(i\)，设作为 \(\max\{ a \}\) 的位置为 \(j\)。发现当某次操作同时覆盖了 \(i, j\) 时这次操作对答案无贡献，仅覆盖 \(i\) 时贡献为负，则当 \(i\) 确定时，最优的操作方案一定是选择没有覆盖 \(i\) 的所有操作，仅需检查其中所有位置的最大值即可。
再手玩一下发现，当固定 \(i\) 时，没有覆盖 \(i\) 的操作要么是右端点小于 \(i\) 要么是左端点大于 \(i\)，即当把操作分别按照右端点升序和左端点升序排序时，有贡献的操作分别是其中的一段前缀和一段后缀。于是分别对这两种情况进行扫描线，枚举 \(i\) 的同时枚举有贡献的操作并维护贡献，求覆盖区域中的最大值。线段树区间加+区间最大值维护即可。
注意先离散化，离散化时不仅要把每次操作的端点 \(l, r\) 加进去，\(l-1\) 和 \(r+1\) 也要加进去（可能作为 \(\min\{ a \}\) 的位置 \(i\)）。
总时间复杂度 \(O(n\log n)\) 级别，由于离散化了 \(4\times n\) 级别的点，所以还有个 4 的常数。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n, m;
struct Opt {
int l, r;
} opt[2][kN];
int datanum, data[kN << 1];
int ans[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
namespace Seg {
#define ls (now_<<1)
#define rs (now_<<1|1)
#define mid ((L_+R_)>>1)
const int kNode = kN << 2;
int maxa[kNode], tag[kNode];
void Pushup(int now_) {
maxa[now_] = std::max(maxa[ls], maxa[rs]);
}
void Pushdown(int now_) {
maxa[ls] += tag[now_], maxa[rs] += tag[now_];
tag[ls] += tag[now_], tag[rs] += tag[now_];
tag[now_] = 0;
}
void Build(int now_, int L_, int R_) {
maxa[now_] = 0, tag[now_] = 0;
if (L_ == R_) {
maxa[now_] = 0, tag[now_] = 0;
return ;
}
Build(ls, L_, mid), Build(rs, mid + 1, R_);
Pushup(now_);
}
void Modify(int now_, int L_, int R_, int l_, int r_, int val_) {
if (l_ <= L_ && R_ <= r_) {
maxa[now_] += val_;
tag[now_] += val_;
return ;
}
if (tag[now_]) Pushdown(now_);
if (l_ <= mid) Modify(ls, L_, mid, l_, r_, val_);
if (r_ > mid) Modify(rs, mid + 1, R_, l_, r_, val_);
Pushup(now_);
}
int Query(int now_, int L_, int R_, int l_, int r_) {
if (l_ <= L_ && R_ <= r_) return maxa[now_];
if (tag[now_]) Pushdown(now_);
int ret = 0;
if (l_ <= mid) ret = std::max(ret, Query(ls, L_, mid, l_, r_));
if (r_ > mid) ret = std::max(ret, Query(rs, mid + 1, R_, l_, r_));
Pushup(now_);
return ret;
}
#undef ls
#undef rs
#undef mid
}
bool cmp0(Opt fir_, Opt sec_) {
return fir_.r < sec_.r;
}
bool cmp1(Opt fir_, Opt sec_) {
return fir_.l < sec_.l;
}
void Init() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
opt[0][i].l = opt[1][i].l = read();
opt[0][i].r = opt[1][i].r = read();
data[i] = opt[0][i].l;
data[n + i] = opt[0][i].r;
data[2 * n + i] = std::max(1, opt[0][i].l - 1);
data[3 * n + i] = std::min(opt[0][i].r + 1, m);
}
std::sort(data + 1, data + 4 * n + 1);
datanum = 0;
for (int i = 1; i <= 4 * n; ++ i) {
if (data[i] != data[i - 1]) ++ datanum;
data[datanum] = data[i];
}
for (int i = 1; i <= n; ++ i) {
opt[0][i].l = opt[1][i].l = std::lower_bound(data + 1, data + datanum + 1, opt[0][i].l) - data;
opt[0][i].r = opt[1][i].r = std::lower_bound(data + 1, data + datanum + 1, opt[0][i].r) - data;
}
std::sort(opt[0] + 1, opt[0] + n + 1, cmp0);
std::sort(opt[1] + 1, opt[1] + n + 1, cmp1);
}
void Solve() {
int p = n;
Seg::Build(1, 1, datanum);
for (int i = datanum; i; -- i) {
while (1 <= p && opt[1][p].l > i) {
Seg::Modify(1, 1, datanum, opt[1][p].l, opt[1][p].r, 1);
-- p;
}
ans[i] = Seg::maxa[1];
}
p = 1;
Seg::Build(1, 1, datanum);
for (int i = 1; i <= datanum; ++ i) {
while (opt[0][p].r < i && p <= n) {
Seg::Modify(1, 1, datanum, opt[0][p].l, opt[0][p].r, 1);
++ p;
}
ans[i] = std::max(ans[i], Seg::maxa[1]);
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
Solve();
int maxans = 0;
for (int i = 1; i <= datanum; ++ i) maxans = std::max(maxans, ans[i]);
printf("%d\n", maxans);
}
return 0;
}
D
妈的容斥杀我。
这复杂度显然是给调和级数跑的，一个显然的想法是取补集求 not good 对的数量，然后考虑枚举公因数 \(i\)，求 \(i\) 可以整除的数对的个数。
为了不重不漏考虑枚举数对的 \(\gcd\)，记 \(f_{i}\) 表示 \(\gcd = i\) 的数对的数量，记 \(\operatorname{cnt}_i\) 为数值 \(i\) 的出现次数，\(s_i\) 为 \(i\) 的倍数的数量，则显然有：
\[f_i = \dfrac{s_i\left( s_i - 1 \right)}{2} - \sum_{k\ge 2} f_{k\times i}
\]
然后考虑原数列中是否出现过作为某对数的 \(\gcd\) 的 \(i\) 则答案即：
\[\dfrac{n\times (n - 1)}{2} - \sum_{\operatorname{cnt}_i\not= 0} f_i
\]
当然也可以考虑有哪些数对的 \(\gcd\) 没有在原数列中出现过，答案即：
\[\sum_{\operatorname{cnt}_i=0} f_{i}
\]
总时间复杂度是调和级数 \(O(n\ln n)\) 级别，代码采用了第一种计算答案的方法。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, a[kN], cnt[kN];
LL ans, f[kN];
bool vis[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) cnt[i] = f[i] = vis[i] = 0;
for (int i = 1; i <= n; ++ i) a[i] = read(), ++ cnt[a[i]], vis[a[i]] = 1;
for (int i = n; i; -- i) {
LL num = f[i] = 0;
for (int j = 1; i * j <= n; ++ j) {
num += cnt[i * j];
f[i] -= f[i * j];
vis[i * j] |= vis[i];
}
f[i] += num * (num - 1) / 2ll;
}
ans = 1ll * n * (n - 1) / 2ll;
for (int i = 1; i <= n; ++ i) if (vis[i]) ans -= f[i];
printf("%lld\n", ans);
}
return 0;
}
写在最后
学到了什么：
- C：贡献形式为 \(\max - \min\) 形式时，如果某次操作会给这两个位置以同样的影响则该操作无贡献。
- D：枚举公因数以记录贡献，并减去公因数的倍数的贡献。