OI笔记 | 2022.10 做题记录（一）
- 停课期间的安排
- [NOIP2003 普及组] 麦森数
- [NOIP2004 普及组] FBI 树
- [CSP-S2019 江西] 和积和
- [NOIP2001 普及组] 求先序排列
- [NOIP2001 提高组] 数的划分
- [NOIP2021] 报数
- [NOIP2013 提高组] 积木大赛
- 白头鹰
- [CSP-J2019 江西] 次大值
- 逆序对
其中的 dp 和 模板题 被转移到新的专题中了。
以后每 $10$ 题开一篇文章。
停课期间的安排
[2022-10-12] Ver. 1
针对 10 月的赛前时间安排如下。
文化课
-
停课期间，做 语数英物化生 作业(对于重复性的订正、暂时无意义 如练字等作业 考虑不做)，上 语英物化生 课。
-
晚上 (若有晚自习则晚自习时) 补充 政史地 笔记，对于较难内容可以看MT上的视频 或 问老师。赛后再补做 政史地 的基础题作业。
目标
-
高一：提高二等，普及一等，NOIp 随缘。
-
高二：提高一等，NOIp 一等。
-
省赛以上水平的比赛(如省选)，等当年 NOIp 结束后综合学习情况再议是否备考。大概率不考虑更进一步。
学习清单
考虑学习或练习以下内容：
-
图论： 最小生成树、最短路。【对图论题能够打一些可观的暴力分】
-
数据结构： 线段树、堆、ST表、并查集、(平衡树/treap)、(树状数组)等。
-
数学：乘法逆元、组合数学、(中国剩余定理)、(概率论/期望)。
-
动态规划：线性dp、背包dp、区间dp、(数据结构优化dp)。
-
字符串：Hash、(KMP)。
-
其他：高精、记搜、剪枝、哈希、分治。【各种暴力解法】
至少的刷题强度：
-
一天 $2\sim 3$ 道橙题(从真题里选，限时切掉，不看题解)；
-
一天 $1\sim 2$ 道黄题(在上述内容的题单中选，专题练习，少看题解)；
-
一天 $0\sim 2$ 道绿题(在上述范围内都可尝试做，想不出来直接看题解)。
-
蓝题及以上的题不作安排。如果恰好双倍经验或优化搜索可以调调看。
[NOIP2003 普及组] 麦森数
输出 $2^P - 1$ 的位数和后 $500$ 位数字，其中 $1 \times 10^3< P <3.1\times 10^6$。
题解
第一问是数学推导。由于 $2$ 的幂不可能以 $0$ 结尾， 可知 $2^P-1$ 的位数与 $2^P$ 的位数相同。我们知道 $10^n$ 的位数是 $n + 1$，所以考虑转化： $2^P=(10^{\log_{10}2})^P=10^{P\log_{10}2 }$，故位数为 $P\times \log_{10}2+1$。
第二问是一个高精快速幂，见代码即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct BigInt {
int a[1005];
BigInt() {memset(a, 0, sizeof(a));}
void out() {
int k = 500;
for(int i = 1; i <= 10; i++) {
for(int j = 1; j <= 50; j++) putchar(a[k--] + '0');
putchar('\n');
}
}
BigInt operator * (const BigInt &t) const {
BigInt ret;
for(int i = 1; i <= 500; i++) {
for(int j = 1; j <= 500; j++) {
ret.a[i + j - 1] += a[i] * t.a[j];
ret.a[i + j] += ret.a[i + j - 1] / 10;
ret.a[i + j - 1] %= 10;
}
}
return ret;
}
};
inline ll read() {...}
inline void write(ll x) {...}
BigInt qpow(int p) {
BigInt ret, t;
ret.a[1] = 1; t.a[1] = 2;
while(p) {
if(p & 1) ret = ret * t;
t = t * t;
p >>= 1;
}
return ret;
}
int main() {
int p = read();
write(int(log10(2) * p + 1)); putchar('\n');
BigInt ans = qpow(p); ans.a[1]--;
ans.out();
return 0;
}
[NOIP2004 普及组] FBI 树
我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 $I$ 串，既含 0 又含 1 的串则称为 $F$ 串。
$FBI$ 树是一种二叉树，它的结点类型也包括 $F$ 结点，$B$ 结点和 $I$ 结点三种。由一个长度为 $2^N$ 的 01 串 $S$ 可以构造出一棵 $FBI$ 树 $T$，递归的构造方法如下：
- $T$ 的根结点为 $R$，其类型与串 $S$ 的类型相同；
- 若串 $S$ 的长度大于 $1$，将串 $S$ 从中间分开，分为等长的左右子串 $S_1$ 和 $S_2$；由左子串 $S_1$ 构造 $R$ 的左子树 $T_1$，由右子串 $S_2$ 构造 $R$ 的右子树 $T_2$。
现在给定一个长度为 $2^N$ 的 01 串，请用上述构造方法构造出一棵 $FBI$ 树，并输出它的后序遍历序列。
题解
按照题意模拟即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = (1 << 11) + 1;
bool a[MAX_N];
char tree[MAX_N];
void build_tree(int p, int l, int r) {
bool B = 0, I = 0;
for(int i = l; i <= r; i++) {
if(a[i] == 0) B = 1;
if(a[i] == 1) I = 1;
}
if(B && I) tree[p] = 'F';
else if(B && !I) tree[p] = 'B';
else if(!B && I) tree[p] = 'I';
if(l != r) {
int m = l + ((r - l) >> 1);
build_tree((p << 1), l, m);
build_tree((p << 1) | 1, m + 1, r);
}
}
void print_tree(int p) {
if(tree[(p << 1)]) print_tree((p << 1));
if(tree[(p << 1) | 1]) print_tree((p << 1) | 1);
putchar(tree[p]);
}
int main() {
int n;
cin >> n;
char c;
for(int i = 1; i <= (1 << n); i++) cin >> c, a[i] = (c - '0');
build_tree(1, 1, (1 << n));
print_tree(1);
return 0;
}
[CSP-S2019 江西] 和积和
给定两个下标从 $1$ 到 $n$ 编号的序列 $a_i,b_i$，定义函数 $S(l,r)(1\le l\le r\le n)$ 为：
\[\sum_{i=l}^r a_i\times \sum_{i=l}^r b_i\]请你求出下列式子的值：
\[\sum_{l=1}^n \sum_{r=l}^n S(l,r)\]由于答案可能很大，你只需要给出答案模 $10^9+7$ 后的结果。
数据范围：$3\le n\le 5\times 10^5$ , $1\le a_i,b_i\le 10^9$。
题解
这题主要是式子有点难推，推了一个小时才推出来。另外取模如果取模不当的话分数会比暴力还低。
首先用 $sa$，$sb$ 存前缀和，于是得到以下式子：
\[ans=\sum_{l=1}^n \sum_{r=l}^n [(sa[r]-sa[l-1])(sb[r]-sb[l-1])]=\\ \sum\limits_{l=1}^n \sum\limits_{r=l}^n(sa[r]sb[r]+sa[l-1]sb[l-1]-sa[r]sb[l-1]-sa[l-1]sb[r])\]利用这个式子可以拿到 $70$ 暴力分。
继续考虑如何只枚举左端点。我们用 $smul$ 存 $sa[i]sb[i]$ 的前缀和，这样式子中 $\sum\limits_{r=l}^n(sa[r]sb[r])$ 的部分可以 $O(1)$ 解决 。再用 $ssa$ 存 $sa$ 的前缀和， $ssb$ 存 $sb$ 的前缀和，这样式子中 $\sum\limits_{r=l}^n (sa[r]sb[l-1]+sa[l-1]sb[r])$ 也可以 $O(1)$ 解决。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAX_N = 5e5 + 5;
ll sa[MAX_N], sb[MAX_N], smul[MAX_N], ssa[MAX_N], ssb[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), x;
ll ans = 0;
for(int i = 1; i <= n; i++) {
x = read();
sa[i] = (sa[i - 1] + x) % MOD;
ssa[i] = (ssa[i - 1] + sa[i]) % MOD;
}
for(int i = 1; i <= n; i++) {
x = read();
sb[i] = (sb[i - 1] + x) % MOD;
ssb[i] = (ssb[i - 1] + sb[i]) % MOD;
smul[i] = (smul[i - 1] + (sa[i] * sb[i]) % MOD) % MOD;
}
for(int i = 1; i <= n; i++) {
ans = (ans + smul[n] - smul[i - 1]) % MOD;
ans = (ans + (n - i + 1) * (sa[i - 1] * sb[i - 1] % MOD)) % MOD;
ans = (ans - (sa[i - 1] * (ssb[n] - ssb[i - 1]) % MOD) % MOD + MOD) % MOD;
ans = (ans - (sb[i - 1] * (ssa[n] - ssa[i - 1]) % MOD) % MOD + MOD) % MOD;
}
write(ans);
return 0;
}
[NOIP2001 普及组] 求先序排列
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。
题解
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
void p(string a, string b) {
if(a.size() <= 0 || b.size() <= 0) return;
char root = b[b.size() - 1];
int k = a.find(root);
putchar(root);
p(a.substr(0, k), b.substr(0, k));
p(a.substr(k + 1), b.substr(k, a.size() - k - 1));
}
int main() {
string a, b;
cin >> a >> b;
p(a, b);
return 0;
}
[NOIP2001 提高组] 数的划分
将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：$n=7$，$k=3$，下面三种分法被认为是相同的。
$1,1,5$;
$1,5,1$;
$5,1,1$.
问有多少种不同的分法。
题解
考虑数据范围较小，可以直接暴力搜索。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, ans;
inline ll read() {...}
inline void write(ll x) {...}
void dfs(int p, int sum, int l) {
if(p == k) {
if(sum == n) ans++;
return;
}
for(int i = l; i + sum <= n; i++) dfs(p + 1, sum + i, i);
}
int main() {
n = read(), k = read();
dfs(0, 0, 1);
cout << ans;
return 0;
}
另外本题还有递推的思路。递推式：$dp_{i,j}=dp_{i-1,j-1}+dp_{i-j,j}$。
[NOIP2021] 报数
报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 $7$ 的倍数，或十进制表示中含有数字 $7$，就必须跳过这个数，否则就输掉了游戏。
在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z 闲得无聊玩起了这个报数游戏。但在只有两个人玩的情况下计算起来还是比较容易的，因此他们玩了很久也没分出胜负。此时小 z 灵光一闪，决定把这个游戏加强：任何一个十进制中含有数字 $7$ 的数，它的所有倍数都不能报出来！
形式化地，设 $p(x)$ 表示 $x$ 的十进制表示中是否含有数字 $7$，若含有则 $p(x) = 1$，否则 $p(x) = 0$。则一个正整数 $x$ 不能被报出，当且仅当存在正整数 $y$ 和 $z$ ，使得 $x = yz$ 且 $p(y) = 1$。
例如，如果小 r 报出了 $6$ ，由于 $7$ 不能报，所以小 z 下一个需要报 $8$；如果小 r 报出了 $33$，则由于 $34 = 17 \times 2$，$35 = 7 \times 5$ 都不能报，小 z 下一个需要报出 $36$ ；如果小 r 报出了 $69$，由于 $70 \sim 79$ 的数都含有 $7$，小 z 下一个需要报出 $80$ 才行。
现在小 r 的上一个数报出了 $x$，小 z 想快速算出他下一个数要报多少，不过他很快就发现这个游戏可比原版的游戏难算多了，于是他需要你的帮助。当然，如果小 r 报出的 x 本身是不能报出的，你也要快速反应过来小 r 输了才行。
由于小 r 和小 z 玩了很长时间游戏，你也需要回答小 z 的很多个问题。
题解
首先筛出来不合法的数。我这里采用的是枚举 $7$ 在数字中出现的位置来构造不合法的数，然后把它的倍数筛掉。类似于埃氏筛法，我们知道如果枚举到某个数时它已经被筛掉了，可以直接跳过它。
然后注意预处理一下每个数的后继让其为 $O(1)$，而不能每次询问都向后查找出后继，后者会 TLE。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e7 + 3;
bool f[MAX_N];
int nxt[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void init() {
int p = 1, q = MAX_N / 10;
for(int i = 1; i <= 7; i++) {
for(int m = 0; m < p; m++) {
for(int n = 0; n < q; n++) {
int t = n * (p * 10) + 7 * p + m;
if(f[t]) continue;
for(int i = 1; i * t <= MAX_N; i++) f[i * t] = 1;
}
}
p *= 10;
q /= 10;
}
int t = MAX_N - 2;
for(int i = MAX_N - 3; i >= 1; i--) {
if(f[i]) nxt[i] = -1;
else nxt[i] = t, t = i;
}
}
int main() {
init();
int T = read();
while(T--) {
int x = read();
write(nxt[x]);
putchar('\n');
}
return 0;
}
[NOIP2013 提高组] 积木大赛
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 $n$ 的大厦，大厦可以看成由 $n$ 块宽度为 $1$ 的积木组成，第 $i$ 块积木的最终高度需要是 $h_i$。
在搭建开始之前，没有任何积木（可以看成 $n$ 块高度为 $0$ 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 $[l, r]$，然后将第 $L$ 块到第 $R$ 块之间（含第 $L$ 块和第 $R$ 块）所有积木的高度分别增加 $1$。
小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。
题解
对于本题我们可以纯粹模拟贪心水过，但是复杂度过高，不太优秀。
考虑使用递推： 考虑用 $f_i$ 表示考虑到第 $i$ 块积木时的操作次数，那么如果 $h_i \le h_{i - 1}$， 那么在搭好第 $i-1$ 块时顺带就能搭好第 $i$ 块积木，所以 $f_i=f_{i-1}$。否则，只需在搭好第 $i-1$ 块所用次数的基础上加上多余高度即可，所以 $f_i = f_{i - 1} + (h_i - h_{i - 1})$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100005;
int a[MAX_N], f[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), ans = 0;
for(int i = 1; i <= n; i++) a[i] = read();
f[1] = a[1];
for(int i = 2; i <= n; i++) {
if(a[i] <= a[i - 1]) f[i] = f[i - 1];
else f[i] = f[i - 1] + a[i] - a[i - 1];
}
write(f[n]);
return 0;
}
白头鹰
白头鹰作为美丽国的国鸟，每天都会进行数学演算的工作。
今天，他得到了3个整数$a, b, p$，其中$p$是一个质数，以及一个函数$f(x, y)$。
函数$f(x,y)$如下定义：
-
令整数$v = ab + xy$。
-
如果$v$是$p$的倍数，则$f(x, y) = 1$。
-
否则，令整数$u = ax + by$，$f(x, y) = u * inv_p(v) \% p$。其中$inv_p(v)$表示$v$在模$p$意义下的乘法逆元。
白头鹰获得了一个整数$k$，且需要计算一下式子：
\[f(f(...f(f(f(k, k-1), k-2), ..., 2), 1)\]对于$100\%$的数据：$2 \leq p \leq 10^{9}+7, 1 \leq a, b \leq min(p-1, 10^{5}), 2 \leq k \leq 10^{18}$。
题解
首先我们要弄清楚逆元怎么求。
乘法逆元可定义为 $ax\equiv 1(\bmod p)$ 的解。这个方程等价为 $ax+py=1$，如果 $p$ 为质数，它等价为 $ax+py=\gcd(a,p)$，形成了 exgcd 的标准形式。所以容易写出：
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {x = 1, y = 0; return;}
exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - (a / b) * y;
}
inline ll inv(ll v, ll p) {
ll x, y;
exgcd(v, p, x, y);
return (x % p + p) % p;
}
本题的时间复杂度主要来自于 $k$ 的值。对于比较小的 $k$，可以直接计算答案，复杂度为 $O(k\log v)$。此外，打表观察发现当 $k \ge a+ 1$ 时，答案总是不变的，所以我们加一句 if(k > a + 1) k = a + 1; 再注意一下每一步取模（防止爆 long long）即可过此题。这个规律怎么证明暂时不懂。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, p, k;
inline ll read() {...}
inline void write(ll x) {...}
void exgcd(ll a, ll b, ll &x, ll &y) {...}
inline ll inv(ll v, ll p) {...}
inline ll f(ll x, ll y) {
ll v = (a * b % p + x * y % p) % p;
if(v % p == 0) return 1;
ll u = (a * x % p + b * y % p) % p;
return u * inv(v, p) % p;
}
int main() {
a = read(), b = read(), p = read(), k = read();
if(k > a + 1) k = a + 1;
ll t = f(k, k - 1);
for(int i = k - 2; i >= 1; i--) t = f(t, i);
write(t);
return 0;
}
[CSP-J2019 江西] 次大值
给出 $n$ 个正整数。求出
\[a_i \bmod a_j (1 \le i,j \le n \wedge i \neq j)\]的所有结果中的严格次大值是多少。
题解
考虑排序后使用函数 unique 去重，可知答案为 $\max(a_{n-2}, a_{n} \bmod a_{n-1}) $。
这是因为： 最大值一定为 $a_{n-1}$ （$a_{n-1} \bmod a_{n}=a_{n-1}$）。
并且有
-
$a_{n-2}=a_{n-2}\bmod a_{n-1}<a_{n-1}$；
-
$a_{n}\bmod a_{n-1} < a_{n-1}$。
可以证明，其他结果都比这两种结果更小。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10;
int a[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
sort(a + 1, a + n + 1);
n = unique(a + 1, a + n + 1) - a - 1;
write(max(a[n - 2], a[n] % a[n - 1]));
return 0;
}
逆序对
给定一段正整数序列，求出其中逆序对的个数。逆序对定义为序列中 $a_i>a_j$ 且 $i<j$ 的有序对。
题解
我们在做归并排序的时候顺带把答案统计一下。也就是若合并时出现左半部分当前指向的数 $a_i$ $>$ 右半部分当前指向的数 $a_j$ 的情况，那么 $mid\to r$ 的每一个数都可以与 $a_j$ 构成逆序对，所以对答案有 $mid - i + 1$ 的贡献。
时间复杂度： $O(n\log n)$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 10;
int a[MAX_N], tmp[MAX_N];
ll ans;
inline ll read() {...}
inline void write(ll x) {...}
void merge(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
merge(l, mid);
merge(mid + 1, r);
int i = l, j = mid + 1;
for(int k = l; k <= r; k++) {
if(a[i] <= a[j] && i <= mid || j > r) tmp[k] = a[i++];
else ans += mid - i + 1, tmp[k] = a[j++];
}
for(int k = l; k <= r; k++) a[k] = tmp[k];
}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
merge(1, n);
write(ans);
return 0;
}
- 上一篇 OI笔记 | 线性 DP 专题
- 下一篇 OI笔记 | 入门数学模板
♥