这场 Div. 3 难度高于平时。
A
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n;
scanf("%lld", &n);
int cnt = n / 4;
n %= 4;
if (n) ++cnt;
printf("%lld\n", cnt);
}
return 0;
}
B
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[3010][3010];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%1lld", &a[i][j]);
for (int i = 1; i <= n; i += m, puts(""))
for (int j = 1; j <= n; j += m)
printf("%lld", a[i][j]);
}
return 0;
}
C
clist 评分 \(1112\)。
维护 \(26\) 个字母的前缀和，然后计算给定区间两个字符串每一个字母的差的和，除以 \(2\) 就是答案。
时间复杂度为 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
char s[N], t[N];
int box[N][26], bb[N][26];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, q;
scanf("%lld%lld%s%s", &n, &q, s + 1, t + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j)
box[i][j] = box[i - 1][j], bb[i][j] = bb[i - 1][j];
++box[i][s[i] - 'a'], ++bb[i][t[i] - 'a'];
}
while (q--) {
int l, r;
scanf("%lld%lld", &l, &r);
int sum = 0;
for (int i = 0; i < 26; ++i)
sum += abs(box[r][i] - box[l - 1][i] - bb[r][i] + bb[l - 1][i]);
printf("%lld\n", sum >> 1);
}
}
return 0;
}
D
clist 评分 \(1420\)。
问题转化为求下列表达式的值：
\[\large \sum\limits_{x=1}^{n-2}\sum\limits_{y=1}^{n-x-y}[xy+x(n-x-y)+y(n-x-y)\le n] \]其中 \([statments]\) 为艾弗森括号，若 \(statments\) 的值为 \(\texttt{true}\) 则 \([statments]\) 的值为 \(1\)，否则为 \(0\)。
然后发现后面表达式是一个调和级数的形式，也就是说总的有效的答案数为 \(n\log n\) 级别。
因此直接暴力枚举即可。时间复杂度为 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
char s[N], t[N];
int box[N][26], bb[N][26];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, x, cnt = 0;
scanf("%lld%lld", &n, &x);
for (int i = 1; i < x; ++i) {
for (int j = 1; j < x - i; ++j) {
int remain = (n - i * j) / (i + j);
if (i * j >= n)
break;
remain = min(remain, x - i - j);
if (remain > 0)
cnt += remain;
}
}
printf("%lld\n", cnt);
}
return 0;
}
E
clist 评分 \(1615\)。
令 \(check(l,r)\) 表示 \(l\sim r\) 一段区间是否满足条件。
因此可以开始推式子：
\(\large \sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \sum\limits_{x=i}^j \sum\limits_{y=x}^j [check(x,y)]\)
\(\large \sum\limits_{x=1}^n \sum\limits_{y=x+1}^n \sum\limits_{i=1}^x \sum\limits_{j=y}^n [check(x,y)]\)
发现 \(check(x,y)\) 已经和后面的 \(i\)，\(j\) 没有关系了，把 \(check(x,y)\) 提到前面。
\(\large\sum\limits_{x=1}^n\sum\limits_{y=x+1}^n([check(x,y)]\sum\limits_{i=1}^x\sum\limits_{j=y}^n 1)\)
\(\large\sum\limits_{x=1}^n\sum\limits_{y=x+1}^n[check(x,y)]\times x\times(n-y+1)\)
然后根据括号的套路，将 \(1\) 看作 \(1\)，\(0\) 看作 \(-1\) 跑一边前缀和。
把 \(x\) 从 \(n\) 到 \(1\) 倒着枚举，令 \(S_i\) 表示 \(i\) 的前缀和。则计算左端点是 \(x\) 对答案造成的总贡献就是所有满足 \(y>x\) 且 \(S_y=S_{x-1}\) 的 \(x\times(n-y+1)\)。把 \(x\) 提取出来，后面的 \(n-y+1\) 和 \(x\) 没有关系可以直接扔到一个 map 里算答案。
时间复杂度为 \(O(n\log n)\)。如果使用 gp_hash_table 一类哈希表可以做到理论 \(O(n)\)。一定一定记得取模。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100, mod = 1e9 + 7;
char s[N];
int sum[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; ++i)
if (s[i] == '1') sum[i] = sum[i - 1] + 1;
else sum[i] = sum[i - 1] - 1;
int res = 0;
map<int, int> mp;
for (int x = n; x; --x) {
res += mp[sum[x - 1]] * x % mod;
mp[sum[x]] += (n - x + 1);
mp[sum[x]] %= mod;
res %= mod;
}
printf("%lld\n", res % mod);
}
return 0;
}
F
clist 评分 \(1996\)。
不是这明显是虚高啊！这不比 E 简单？
首先考虑一个 \(O((n+k)\log n)\) 的暴力。开一个堆来维护当前 \(n\) 个元素的值。每一次从堆里取出当前值最大的元素，并将这个元素的值更新重新放回堆里。
然后看到每一次取出堆里最大的元素，因此可以发现答案一定存在一个阈值 \(p\)，其中选取的数一定全部 \(\ge p\)。更具体的说：值 \(>p\) 的可以选取的数一定全部选取，值 \(<p\) 的可以选取的数一定全都不选取。值 \(=p\) 的数会选取一部分。
容易发现 \(p\) 具有单调性，因此考虑二分答案。计算 \(p\) 是否在 \(k\) 次以内可以取完可以使用等差数列求和。注意一下恰好为 \(p\) 的边界情况即可。时间复杂度为 \(O(n\log n)\) 可以通过。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100, mod = 1e9 + 7;
int a[N], b[N];
int calc(int shouxiang, int gongcha, int xiangshu) {
int moxiang = shouxiang - gongcha * (xiangshu - 1);
return (shouxiang + moxiang) * xiangshu / 2;
}
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, k;
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; ++i)
scanf("%lld", &b[i]);
int l = 0, r = 1e9, best = 0;
while (l <= r) {
int mid = l + r >> 1;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] >= mid)
cnt += (a[i] - mid) / b[i] + 1;
}
if (cnt >= k)
best = mid, l = mid + 1;
else
r = mid - 1;
}
int sum = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] >= best + 1) {
int p = (a[i] - (best + 1)) / b[i] + 1;
sum += calc(a[i], b[i], p);
k -= p;
}
}
sum += k * best;
printf("%lld\n", sum);
}
return 0;
}
G
clist 评分 \(2384\)。
好逆天一题。考虑随机赋权哈希。
容易发现给出的问题即为一个大小为 \(n\) 的简单环。从 \(a\) 到 \(b\)（\(a\neq b\)）的不同简单路径数量一定为 \(2\)。把她放到一个圆上考虑，即为选取一段优弧或者劣弧并将其覆盖。对于这样的一组 \(a\)，\(b\)，考虑在整数范围内随机赋权 \(p\)，并让 \(a\) 和 \(b\) 的点权全都异或上 \(p\)。然后跑一边前缀哈希。此时可以惊人的发现，若两个不同的区间所对应的权相同，那么她们一定位于同一个可选块内！！因此只需要找出最长的连续可选块，然后此时贪心的让这一段区间不被覆盖，设这段长度为 \(p\) 则最优答案为 \(n-p\)。时间复杂度为 \(O(n)\)。
#include <iostream>
#include <cstdio>
#include <random>
#include <map>
#define int long long
const int N = 500100, mod = 1e9 + 7;
int val[N];
std::mt19937_64 mt;
std::uniform_int_distribution<int> qwq(1, 400000000000000000);
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 0; i <= n; ++i)
val[i] = 0;
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%lld%lld", &a, &b);
int t = qwq(mt);
val[a] ^= t, val[b] ^= t;
}
std::map<int, int> mp;
int mx = 0;
for (int i = 1; i <= n; ++i)
mx = std::max(mx, ++mp[val[i] ^= val[i - 1]]);
printf("%lld\n", n - mx);
}
}