OI笔记 | 2022 国庆假期刷题记录
连续子段的差异
给出一个包括 $N$ 个元素的整数数组 $A$，包括 $A$ 本身在内，共有 $\frac{N(N+1)}{2}$个非空子段。例如：$1 3 2$的子段为$1,3,2,1 3, 3 2, 1 3 2$。在这些子段中，如果最大值同最小值的差异不超过$K$，则认为这是一个合格的子段。给出数组$A$和$K$，求有多少符合条件的子段。例如：$3 5 7 6 3$，$K = 2$，符合条件的子段包括：$3, 5, 7, 6, 3 ,3 5 ,5 7 ,7 6 ,5 7 6$，共$9$个。
题解
如果暴力枚举每一个子段并求最大值与最小值，时间复杂度为 $O(n^2)$，难以接受。
有两种能 AC 的解法，下面把区间 $[l, r]$ 内的最大值记作 $Max(l,r)$，最小值记作 $Min(l,r)$。
ST表 + 二分
考虑如何优化我们的枚举。
我们枚举子段的每一个左端点 $l$。容易看出单调性：随着右端点 $r$ 的增大，差值 $d=Max(l,r)-Min(l,r)$ 不减，这让我们想到二分答案。
利用二分，容易找到最大的合法(即使得 $d \le k$)的 $r_0$，则 $r$ 取 $[l,r_0]$ 的每一个数都是合法的，故答案直接加上 $(r_0-l+1)$ 即可。
然而这种方式需要能够 $O(1)$ 求 $d$ (也就是 RMQ 问题)。由于个人不会写线段树，又是静态数组，就用ST表来写了。
时间复杂度：$O(n\log n)$。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005, MAX_LOG = 17;
int n, k, ans;
int a[MAX_N], log_2[MAX_N];
int fMin[MAX_N][MAX_LOG], fMax[MAX_N][MAX_LOG];
// 初始化ST表
void init_log() {
log_2[1] = 0;
log_2[2] = 1;
for(int i = 3; i <= MAX_N; i++) log_2[i] = log_2[i / 2] + 1;
}
void init_st() {
for(int i = 1; i <= n; i++) fMin[i][0] = fMax[i][0] = a[i];
for(int j = 1; j <= MAX_LOG; j++) {
for(int i = 1; i + (1 << (j - 1)) - 1 <= n; i++) {
fMax[i][j] = max(fMax[i][j - 1], fMax[i + (1 << (j - 1))][j - 1]);
fMin[i][j] = min(fMin[i][j - 1], fMin[i + (1 << (j - 1))][j - 1]);
}
}
}
// 利用ST表求区间最值
int Max(int l, int r) {
int len = log_2[r - l + 1];
return max(fMax[l][len], fMax[r - (1 << len) + 1][len]);
}
int Min(int l, int r) {
int len = log_2[r - l + 1];
return min(fMin[l][len], fMin[r - (1 << len) + 1][len]);
}
int main() {
init_log();
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
init_st();
for(int i = 1; i <= n; i++) {
//二分答案
int l = i - 1, r = n + 1;
while(l < r - 1) {
int mid = (l + r) >> 1;
if(Max(i, mid) - Min(i, mid) > k) r = mid;
else l = mid;
}
ans += l - i + 1;
}
cout << ans;
return 0;
}
单调队列
考虑单调队列也可以维护一段连续区间内的最大值或最小值，容易找到对于每一个左端点的最大合法右端点 $r_0$，时间复杂度更优，为 $O(n)$。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50003;
int a[MAX_N];
deque<int> o, p; // o : min; p : max
int main() {
int n, k, ans = 0, r = 1;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
while(!o.empty() && o.front() < i) o.pop_front();
while(!p.empty() && p.front() < i) p.pop_front();
while(r <= n) {
while(!o.empty() && a[o.back()] >= a[r]) o.pop_back();
while(!p.empty() && a[p.back()] <= a[r]) p.pop_back();
o.push_back(r);
p.push_back(r);
if(a[p.front()] - a[o.front()] > k) break;
r++;
}
ans += r - i;
}
cout << ans;
return 0;
}
N的倍数
一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。
[SPJ] 输出任意一种解。
题解
如果找到两个前缀和 $sum_i$ 和 $sum_j$，满足 $sum_i\equiv sum_j(\bmod \ N)$ ，则区间 $[i+1,j]$ 是一组可行解。
之前做过类似的数学题，不过那个是统计有多少组同余然后用组合数来算。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 50005;
int a[MAX_N], cnt[MAX_N];
int main() {
ll n, sum = 0;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
sum += a[i];
if(cnt[sum % n] || sum % n == 0) {
cout << i - cnt[sum % n] << endl;
for(int k = cnt[sum % n] + 1; k <= i; k++) {
cout << a[k] << endl;
}
return 0;
}
cnt[sum % n] = i;
}
cout << "No Solution";
return 0;
}
三角形
10.03模拟赛B组T1，考场暴力做法 $30pts$。
给定三条边长 $a$, $b$, $c$ 。给定 $m$ 个可用的单位线段（长度为 $1$），你可以将它们中的若干个拼接到每条边上（当然也可以不接）。
求有多少种拼接方案使得这三条边能构成三角形。
思路
考虑问题的反面，即有多少种拼接方案，使得这三条边构不成三角形。用总方案数减去这部分即可。
如何计算总方案数
思考：如果不考虑能否构成三角形，总的拼接方案有多少种。
根据分类加法原理，总方案数 $=$ 不拼接单位线段的方案数 $+$ 用尽 $1$ 条单位线段的方案数 $+$ $\dots$ $+$ 用尽 $m$ 条单位线段的方案数。
其中对于用尽 $i$ 个单位线段的方案数，使用凑元素的隔板法，方案数为 $\binom{i+2}{2} = \frac{(i+1)(i+2)}{2}$。
所以共有 $\sum\limits_{i=0}^m \frac{(i+1)(i+2)}{2}$ 种拼接方案。
如何计算构不成三角形的方案数
构不成三角形的充要条件是：存在最长边，它大于或等于其余两边之和。
假设 $max_len$ 为最长边，其余两边为 $len_1$ 与 $len_2$，我们往最长边上加上 $k$，可知 $k \in [0, m]$。
对于每一个 $k$，如果加上它后能构成三角形，则它对答案没有贡献。
如果加上它后 不能构成三角形，我们再考虑 往剩余两边上能加多少长度，使得仍然不能构成三角形。这个最大可加数会等于 剩余可用的单位线段个数 $(m-k)$ 与 最长边与其余两边之和的差距 $(max_len+k-len_1-len_2)$ 中较小的那一个。于是将答案减去 最大可加数对应的方案数 即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c, m;
inline ll read() {...}
inline void write(ll x) {...}
inline ll count(ll x) {return (x + 1) * (x + 2) / 2;}
ll diff(ll max_len, ll len1, ll len2) {
ll ret = 0;
for(int k = 0; k <= m; k++) {
if(len1 + len2 > max_len + k) continue;
ret += count(min(m - k, max_len + k - (len1 + len2)));
}
return ret;
}
int main() {
a = read(), b = read(), c = read(), m = read();
ll ans = 0;
for(ll i = 0; i <= m; i++) ans += count(i);
ans -= diff(a, b, c) + diff(b, c, a) + diff(c, b, a);
write(ans);
return 0;
}
[NOIP2016 普及组] 回文日期
注：本题为水题，贴到Blog上是因为觉得自己写的比较漂亮。
题目描述
用 $8$ 位数字表示一个日期，前 $4$ 位代表年份，接下来 $2$ 位代表月份，最后 $2$ 位代表日期。
给出两个用上述方法表示的日期，计算它们之间有多少个真实存在的日期的表示是回文的。
[注] 闰年的判断标准(满足一种即可)：
- 这个年份是 $4$ 的整数倍，但不是 $100$ 的整数倍；
- 这个年份是 $400$ 的整数倍。
题解
可以枚举这两个日期中的所有日期，逐一判断是否回文。这种方法更清晰，且由于日期是真实的，所以枚举范围并不大。
也可以考虑枚举后四位(只有 $366$ 种可能)，考虑以它为后四位构造的回文数是否在给定范围之内，这样枚举范围小了很多。
我写的是前者，使用结构体来保存日期，感觉这样封装起来舒服很多。高精写到结构体里也是这个道理。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct date {
int y, m, d;
bool operator != (const date &t) const {
return y != t.y || m != t.m || d != t.d;
}
void read() {
string s;
getline(cin, s);
y = (s[0] - '0') * 1000 + (s[1] - '0') * 100 + (s[2] - '0') * 10 + (s[3] - '0');
m = (s[4] - '0') * 10 + (s[5] - '0');
d = (s[6] - '0') * 10 + (s[7] - '0');
}
bool palin() {
return (y / 1000 == d % 10) && (y / 100 % 10 == d / 10) && (y / 10 % 10 == m % 10) && (y % 10 == m / 10);
}
date next_date() {
int lim = months[m];
if(m == 2 && (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) lim++;
if(m == 12 && d == 31) return (date){y + 1, 1, 1};
else if(d < lim) return (date){y, m, d + 1};
else return (date){y, m + 1, 1};
}
};
int main() {
int ans = 0;
date l, r;
l.read(), r.read();
for(date i = l, r = r.next_date(); i != r; i = i.next_date()) if(i.palin()) ans++;
cout << ans;
return 0;
}
[JRKSJ R6] Eltaw
给你 $k$ 个长为 $n$ 的序列 $a_{1\dots k,1\dots n}$，有 $q$ 次询问，每次询问给出一个区间 $[l,r]$，要求出 $\displaystyle\max_{i=1}^k\sum_{j=l}^ra_{i,j}$，即求出所有序列中区间 $[l,r]$ 的和的最大值。
对于 $100\%$ 的数据，$1\le n,k,q\le5\times 10^5$，$1\le n\times k\le 5\times10^5$，$1\le l\le r\le n$，$0\le a_{i,j}\le 10^9$。
题解
赛时骗了 $50pts$ 的部分分，然后赛后看了题解，居然就是用 map 优化暴力。
其实还挺有意思的。这题之所以可以暴力，是因为数据范围中 $ 1\le n×k\le 5×10^5 $ 。这决定了：
-
空间不可能会爆。可以用二维
vector或 一维数组 存。 -
如果 $n < k$，由于区间总数只有 $\frac{n(n+1)}{2}$，如果我们用
map存下已经计算过的区间，真正的计算最大值操作不超过 $O(n^2)$ 级别，每次都是 $O(k)$，处理询问 $O(1)$，所以复杂度 $O(n^2k + q)$。 -
如果 $n \ge k$，则每次暴力计算导致的复杂度 $O(qk)$ 并不大。总的复杂度 $O(nk+qk)$。
似乎这种思想叫根号分治？
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> sum;
map<pair<ll, ll>, ll> ans;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), k = read(), q = read();
sum.resize(k + 2);
for(int i = 1; i <= k; i++) {
sum[i].resize(n + 2);
for(int j = 1; j <= n; j++) {
ll tmp = read();
sum[i][j] = sum[i][j - 1] + tmp;
}
}
for(int i = 1; i <= q; i++) {
ll l = read(), r = read();
if(!ans[{l, r}]) {
ll tmp = -1;
for(int j = 1; j <= k; j++) tmp = max(tmp, sum[j][r] - sum[j][l - 1]);
ans[{l, r}] = tmp;
}
write(ans[{l, r}]);
putchar('\n');
}
return 0;
}
- 上一篇 OI笔记 | 2022.9 做题记录
- 下一篇 OI笔记 | 线性 DP 专题
♥