信息奥赛复盘｜2023多校新生周赛二（2023.11.5）
比赛信息 📚
时间：2023 年 11 月 5 日 18:00 - 21:00
竞赛链接：http://10.7.95.2/contest/1310/problems（仅ZJNU内网登录）
ACM集训队讲解视频：/
个人情况 ✍️
本周个人排名：8/28
AC情况：4/8
比赛时间：2023.11.5（18：00 - 21:00）
T1 字符串签到题，但是看错了题面细节，WA了好几发，发现”adjacent”后 AC ✅
T2 进制转换，K进制转换为十进制，累乘展开即可 ✅
T3 数学思维 + 前缀和 + 二分 ✅
T4 求若干区间重叠情况，考场上不会写离散化，未能 AC ❌ （补题时发现此题算法非常精妙，值得记录）
T5 赛时仅有1人通过，直接放弃 ❌
T6 全场花了最长时间的题，一直在纠结列出所有情况的暴力法会严重超时，后来在草稿纸上演算时，突然发现规律，勉强 AC ✅
T7 赛时仅有1人通过，直接放弃 ❌
T8 赛时想出分割思路，但是不知道怎么实现 ❌（补题时发现DFS可以实现在n个数中选择k个的操作，使用DFS成功AC ✅）
总体来看，这次周赛算是正常发挥，题目的质量也比较高（均来自AtCoder ABC）若是能在赛时做出T4或T8会更圆满，继续加油 😀
题目列表 🧑🏻💻
| 题目名称 | 难度 |
|---|---|
| T1 - typo | 🟢 |
| T2 - Base K | 🟢 |
| T3 - Long Sequence | 🟢 |
| T4 - Online games | 🟡 |
| T5 - LEQ | 🔴 |
| T6 - FG operation | 🟡 |
| T7 - Distance on Large Perfect Binary Tree | 🔴 |
| T8 - Select Mul | 🟡 |
题解 🚀
A - typo
题目信息 📚
【题目描述】
You are given two strings $S$ and $T$. Determine whether it is possible to make $S$ and $T$ equal by doing the following operation at most once:
- choose two adjacent characters in $S$ and swap them.
Note that it is allowed to choose not to do the operation.
Constraints
- Each of $S$ and $T$ is a string of length between $2$ and $100$ (inclusive) consisting of lowercase English letters.
- $S$ and $T$ have the same length.
【输入】
Input is given from Standard Input in the following format:
$N$
$S$ $T$
【输出】
If it is possible to make $S$ and $T$ equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.
【输入样例1】
abc
acb【输出样例1】
Yes【输入样例2】
aabb
bbaa【输出样例2】
No【输入样例3】
abcde
abcde【输出样例3】
Yes【题目来源】
题目解析 🍉
【题目分析】
T1 字符串签到题，注意题面 “at most once” 和 “adjacent” 的条件即可。
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
if (s == t) cout << "Yes" << endl;
else {
s += '-', t += '-'; // 防止类似s = abcd, t = abce的情况发生时，最后一位没有字符交换
for (int i = 0; i < s.size() - 1; i++) {
// 当前字符不一样，交换s[i]与s[i+1]
if (s[i] != t[i]) {
swap(s[i], s[i + 1]);
// 交换后验证结果
if (s != t) cout << "No" << endl;
else cout << "Yes" << endl;
return 0;
}
}
}
return 0;
}B - Base K
题目信息 📚
【题目描述】
You are given integers $A$ and $B$, in base $K$.
Print $A \times B$ in decimal.
For base-$K$ representation, see Wikipedia’s article on Positional notation.
【输入】
Input is given from Standard Input in the following format:
$K$
$A$ $B$
【输出】
Print the answer.
【输入样例1】
2
1011 10100【输出样例1】
220【输入样例2】
7
123 456【输出样例2】
15642【数据范围】
$2 \leq K \leq 10$
$1 \leq A,B \leq 10^5$
$A$ and $B$ are in base-$K$ representation.
【题目来源】
题目解析 🍉
【题目分析】
T2 进制转换，K进制转换为十进制，累乘展开即可
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
LL k, s1 = 0, s2 = 0;
string a, b;
cin >> k;
cin >> a >> b;
// 累乘法进制转换
for (int i = 0; i < a.length(); i++) s1 = s1 * k + a[i] - '0';
for (int i = 0; i < b.length(); i++) s2 = s2 * k + b[i] - '0';
// 输出结果
cout << (LL) s1 * s2 << endl;
return 0;
}C - Long Sequence
题目信息 📚
【题目描述】
We have a sequence of $N$ positive integers: $A=(A_1,\dots,A_N)$.
Let $B$ be the concatenation of $10^{100}$ copies of $A$.
Consider summing up the terms of $B$ from left to right. When does the sum exceed $X$ for the first time?
In other words, find the minimum integer $k$ such that:
$\displaystyle{\sum_{i=1}^{k} B_i \gt X}$.
【输入】
$N$
$A_1$ $\ldots$ $A_N$
$X$
【输出】
Print the answer.
【数据范围】
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq X \leq 10^{18}$
- All values in input are integers.
【输入样例1】
3
3 5 2
26【输出样例1】
8【输入样例2】
4
12 34 56 78
1000【输出样例2】
23【题目来源】
题目解析 🍉
【题目分析】
数学题，利用取模运算 + 前缀和 + 二分即可得到答案。
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N], s[N], n, sum, X;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据，并求前缀和、sum
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] += s[i - 1] + a[i];
sum += a[i];
}
cin >> X;
// 对X进行处理
LL cnt = X / sum;
X = X % sum;
// 二分
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (s[mid] - s[0] > X)
r = mid;
else
l = mid + 1;
}
cout << l + cnt * n << endl;
return 0;
}D - Online games
题目信息 📚
【题目描述】
There is an online game with $N$ registered players.
Today, which is the $10^{100}$-th day since its launch, the developer Takahashi examined the users’ login history. It turned out that the $i$-th player logged in for $B_i$ consecutive days from Day $A_i$, where Day $1$ is the launch day, and did not log in for the other days. In other words, the $i$-th player logged in on Day $A_i$, $A_i+1$, $\ldots$, $A_i+B_i-1$, and only on those days.
For each integer $k$ such that $1\leq k\leq N$, find the number of days on which exactly $k$ players logged in.
【输入】
Input is given from Standard Input in the following format:
N
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$
【输出】
Print $N$ integers with spaces in between, as follows:
$D_1$ $D_2$ $\cdots$ $D_N$
Here, $D_i$ denotes the number of days on which exactly $k$ players logged in.
【数据范围】
- $1 \leq N \leq 2\times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
- All values in input are integers.
【输入样例1】
3
1 2
2 3
3 1【输出样例1】
2 2 0【输入样例2】
2
1000000000 1000000000
1000000000 1000000000【输出样例2】
0 1000000000题目解析 🍉
【题目分析】
本题题面抽象后，就是分析若干区间的重叠情况。
可以把每个区间进行离散，只记录起点与终点，如区间 [4, 8] 离散为：
- pair{4, +1} → 起点，坐标为4
- pair{8, -1} → 终点，坐标为8
将所有点放入 vector 中进行排序。
设定一个 cnt 变量记录当前区间重合数，然后两点两点逐段分析。
- 若
v[i].second == 1，说明有一个区间开始，重叠数 +1 - 若
v[i].second == 0，说明有一个区间结束，重叠数 -1
本题思路非常精妙，值得学习。
【C++代码】点排序法 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int ans[N], n, s, e;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
vector<pair<int, int>> v;
for (int i = 1; i <= n; ++i) {
cin >> s >> e;
// 将一个区间离散为起点和终点
v.push_back({s, +1});
v.push_back({s + e, -1});
}
// 对所有点排序
sort(v.begin(), v.end());
// 从第1个点开始，不断对相邻两点v[i],v[i+1]进行处理
int cnt = 0; // cnt记录当前重合的区间数量
for (int i = 0; i < v.size() - 1; i++) { // 共有v.size()个点，v.size()-1段
cnt += v[i].second; // cnt根据当前点类别改变，如当前点为起点，说明有一个新区间加入；反之，有一个区间结束
ans[cnt] += v[i + 1].first - v[i].first; // 记录v[i]和v[i+1]之间的区间重叠情况
}
// 输出答案
for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
return 0;
}E - LEQ
题目信息 📚
【题目描述】
Given is a sequence of $N$ integers: $A = (A_1, A_2, \dots, A_N)$.
Find the number of (not necessarily contiguous) subsequences $A’=(A’_1,A’_2,\ldots,A’_k)$ of length at least $2$ that satisfy the following condition:
- $A’_1 \leq A’_k$.
Since the count can be enormous, print it modulo $998244353$.
Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.
【输入】
Input is given from Standard Input in the following format:
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
【输出】
Print the number of (not necessarily contiguous) subsequences $A’=(A’_1,A’_2,\ldots,A’_k)$ of length at least $2$ that satisfy the condition in Problem Statement.
【数据范围】
$2 \leq N \leq 3 \times 10^5$
$1 \leq A_i \leq 10^9$
All values in input are integers.
【输入样例1】
3
1 2 1【输出样例1】
3【输入样例2】
3
1 2 2【输出样例2】
4【输入样例1】
3
3 2 1【输出样例1】
0【输入样例2】
10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501【输出样例2】
830【题目来源】
题目解析 🍉
官方题解传送门：https://atcoder.jp/contests/abc221/tasks/abc221_e/editorial
本题需要的知识点：子序列 + 离散化 + 树状数组 + 快速幂 + 求逆元
- 子序列
- $n$ 个元素组成的序列，其子序列个数有：$2^n$
- $n$ 个元素组成的序列中，下标为 $[i, j]$ 的区间，其子序列个数为：$2^{j - i + 1}$
- $n$ 个元素组成的序列中，下标为 $[i, j]$ 的区间，若保留
a[i],a[j]，其子序列个数为：$2^{j - i - 1}$
- 离散化
- 由于
a数组的值域较大，故需要进行离散化
- 由于
- 树状数组
- 利用数状数组维护
- 快速幂
- 使用经典快速幂模版即可
- 求逆元
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10, M = 998244353;
LL n, a[N], tr[N];
vector<LL> tmp;
// 离散化查询
LL findi(LL x) {
return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin() + 1;
}
// 快速幂
LL quick_power(LL base, LL power) {
LL res = 1;
while (power) {
if (power & 1) res = res * base % M;
power >>= 1;
base = base * base % M;
}
return res;
}
// 树状数组模版
int lowbit(int x) { return x & -x; }
void update(int x, LL c) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] = (tr[i] % M + c % M) % M;
}
LL query(int x) {
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res = (res % M + tr[i] % M) % M;
return res;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], tmp.push_back(a[i]);
// 离散化
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
LL cnt = 0;
for (int i = 1; i <= n; i++) {
// 查询离散化后下标
int id = findi(a[i]);
// 计算项
LL t = quick_power(2, i - 1) % M;
cnt = (cnt % M + t * query(id) % M) % M;
// 费马小定理：若a、p互质，且p为质数，则a的逆元为a^(p-2)
// 单点更新（利用费马小定理求解逆元）
update(id, quick_power(quick_power(2, i), M - 2));
}
cout << cnt << endl;
return 0;
}F - FG operation
题目信息 📚
【题目描述】
We have a sequence of $N$ integers between $0$ and $9$ (inclusive): $A=(A_1, \dots, A_N)$, arranged from left to right in this order.
Until the length of the sequence becomes $1$, we will repeatedly do the operation $F$ or $G$ below.
- Operation $F$: delete the leftmost two values (let us call them $x$ and $y$) and then insert $(x+y)%10$ to the left end.
- Operation $G$: delete the leftmost two values (let us call them $x$ and $y$) and then insert $(x\times y)%10$ to the left end.
Here, $a%b$ denotes the remainder when $a$ is divided by $b$.
For each $K=0,1,\dots,9$, answer the following question.
Among the $2^{N-1}$ possible ways in which we do the operations, how many end up with $K$ being the final value of the sequence?
Since the answer can be enormous, find it modulo $998244353$.
【输入】
Input is given from Standard Input in the following format:
$N$
$A_1$ $\dots$ $A_N$
【输出】
Print ten lines.
The $i$-th line should contain the answer for the case $K=i-1$.
【数据范围】
$2 \leq N \leq 10^5$
$0 \leq A_i \leq 9$
All values in input are integers.
【输入样例1】
3
2 7 6【输出样例1】
1
0
0
0
2
1
0
0
0
0【输入样例2】
5
0 1 2 3 4【输出样例2】
6
0
1
1
4
0
1
1
0
2【题目来源】
题目解析 🍉
【题目分析】
思路1：deque + map 模拟
显然，如果序列长度为 $N$，则会得到 $2^{N-1}$ 个不同的序列。由于 $N$ 的取值范围，如果模拟整个过程（如下面所示），显然会 TLE
- 序列1，先F再F：(2,7,6) → (9,6) → (5)
- 序列2，先F再G：(2,7,6) → (9,6) → (4).
- 序列3，先G再F：(2,7,6) → (4,6) → (0).
- 序列4，先G再G：(2,7,6) → (4,6) → (4).
经过思考，发现最终结果的范围是 [0, 9]，存在大量重复。如上述序列2和序列4的结果均为4，那么在下一次操作时，这两个序列衍生出的四个序列，结果是完全一样的，因此可以合并。
也就是说，我们只需要维护一个map（key值为0～9，value值为对应结果出现的次数），每一轮都更新一下map，更新N-1轮，就能得到最终答案。时间复杂度为 $O(10 * (N-1))$
PS：使用 STL 中的 deque 双端队列，可以方便的实现头尾插入、删除。
思路2：dp
在阅读官方题解后，发现上述思路其实可以用dp实现
dp[i][j] 表示前 $i$ 个数字，各种操作后，以 $j$ 结束的数量。
因此统计 dp[N][0] ~ dp[N][9] 即可。
官方dp题解传送门：AtCoder 220D
【C++代码】deque + map ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL M = 998244353;
LL a[N], n, tmp;
deque<LL> dq;
LL add_mod(LL num1, LL num2) {
return (num1 % M + num2 % M) % M;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> tmp;
dq.push_back(tmp);
}
// 加入前两个元素
unordered_map<LL, LL> cur, next;
LL t1 = dq.front();
dq.pop_front();
LL t2 = dq.front();
dq.pop_front();
cur[t1 * t2 % 10]++;
cur[(t1 + t2) % 10]++;
while (!dq.empty()) {
t1 = dq.front();
dq.pop_front();
for (auto it: cur) {
next[it.first * t1 % 10] = add_mod(next[it.first * t1 % 10], it.second);
next[(it.first + t1) % 10] = add_mod(next[(it.first + t1) % 10], it.second);
}
cur.clear();
for (auto it: next) {
cur[it.first] = it.second;
}
next.clear();
}
for (int i = 0; i <= 9; i++) {
cout << cur[i] % M << endl;
}
return 0;
}【C++代码】dp ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 998244353;
LL n, a[N], dp[N][15];
LL add_mod(LL a, LL b) { return (a % M + b % M) % M; }
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
// 设定dp初始值
memset(dp, 0, sizeof dp);
dp[1][a[1]] = 1;
// dp[i][k]表示操作前i个数字后，以k结束的数量
for (int i = 2; i <= n; i++) {
// 取出当前元素
int t = a[i];
// 通过上一层0～9(dp[i-1][0]~dp[i-1][9])，更新这一层的0～9
for (int j = 0; j < 10; j++) {
dp[i][(t * j) % 10] = add_mod(dp[i][(t * j) % 10], dp[i - 1][j]);
dp[i][(t + j) % 10] = add_mod(dp[i][(t + j) % 10], dp[i - 1][j]);
}
}
// 输出答案
for (int i = 0; i < 10; i++) cout << dp[n][i] % M << endl;
return 0;
}G - Distance on Large Perfect Binary Tree
题目信息 📚
【题目描述】
We have a tree with $2^N-1$ vertices.
The vertices are numbered $1$ through $2^N-1$. For each $1\leq i \lt 2^{N-1}$, the following edges exist:
- an undirected edge connecting Vertex $i$ and Vertex $2i$,
- an undirected edge connecting Vertex $i$ and Vertex $2i+1$.
There is no other edge.
Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.
Find the number, modulo $998244353$, of pairs of vertices $(i, j)$ such that the distance between them is $D$.
【输入】
Input is given from Standard Input in the following format:
$N$ $D$
【输出】
Print the answer.
【数据范围】
$2 \leq N \leq 10^6$
$1 \leq D \leq 2\times 10^6$
All values in input are integers.
【输入样例1】
3 2【输出样例1】
14【输入样例2】
14142 17320【输出样例2】
11284501【题目来源】
题目解析 🍉
【题目分析】
【C++代码】✅
H - Select Mul
题目信息 📚
【题目描述】
You are given an integer $N$. Consider permuting the digits in $N$ and separate them into two positive integers.
For example, for the integer $123$, there are six ways to separate it, as follows:
- $12$ and $3$,
- $21$ and $3$,
- $13$ and $2$,
- $31$ and $2$,
- $23$ and $1$,
- $32$ and $1$.
Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer $101$ into $1$ and $01$. Additionally, since the resulting integers must be positive, it is not allowed to separate $101$ into $11$ and $0$, either.
What is the maximum possible product of the two resulting integers, obtained by the optimal separation?
【输入】
Input is given from Standard Input in the following format:
N
【输出】
Print the maximum possible product of the two integers after separation.
【数据范围】
$N$ is an integer between $1$ and $10^9$ (inclusive).
$N$ contains two or more digits that are not $0$.
【输入样例1】
123【输出样例1】
63【输入样例2】
1010【输出样例2】
100【输入样例3】
998244353【输出样例3】
939337176题目解析 🍉
【题目分析】
- 思路1：DFS + 贪心
- 思路2: 全排列暴力
【C++代码】DFS + 贪心 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 15;
LL n, ans = 0, m1, m2;
vector<PII> v;
// dfs，从v中选择goal位数字作为m1，剩下v.size()-goal位数字作为m2，不断比较m1*m2
void dfs(LL cur, LL goal) {
// 当前选择的数字位数已经到goal位
if (cur == goal) {
m1 = 0, m2 = 0;
// v[i].second是每一个可选数字的标志位
for (int i = 0; i < v.size(); i++) {
if (v[i].second == 0) m2 = m2 * 10 + v[i].first; // 0表示当前数字没有被选中，需要加入m2
else m1 = m1 * 10 + v[i].first; // 1表示当前数字被选中，需要加入m1
}
if (m1 * m2 > ans) ans = m1 * m2;
return;
}
// dfs作选择的模版，类似于全排列（不过标记数组b被集成到了v[i].second）
for (int i = 0; i < v.size(); i++) {
if (v[i].second == 0) {
v[i].second = 1;
dfs(cur + 1, goal);
v[i].second = 0;
}
}
}
bool cmp(PII a, PII b) {
return a.first > b.first;
}
int main() {
cin >> n;
// 将当前数字n逐位分解，放入v中
string s = to_string(n);
// {1, 0}表示分解的数字为1，0表示该数字当前未被选中
for (int i = 0; i < s.size(); i++) v.push_back({s[i] - '0', 0});
// 对v从大到小排序，保证之后的两个乘数是最大的（如选中数字1、3、5，则一定是以531作为乘数，结果最大）
sort(v.begin(), v.end(), cmp);
// 数字n共有 k = s.size() 位，可以分解为 1位 * (k-1)位，2位 * (k-2)位..
// 对于 i位 * (k-i)位 的情况，只需从v中选i个数字作为m1，选另外(k-i)个数字作为m2，不断比较m1*m2即可
for (int i = 1; i <= s.size() / 2; i++) {
dfs(0, i); // 0表示当前在v选中0位数字，i表示需要在v中选中i位数字
}
cout << ans << endl;
return 0;
}【C++代码】全排列法 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, ans = 0;
vector<int> v;
int main() {
cin >> n;
string s = to_string(n);
sort(s.begin(), s.end());
do {
// 对于每一个全排列，分割方式均有s.size-1种
for (int i = 1; i <= s.size() - 1; i++) {
// 构造m1，m2
LL m1 = 0, m2 = 0;
for (int j = 0; j < i; j++) m1 = m1 * 10 + s[j] - '0';
for (int j = i; j < s.size(); j++) m2 = m2 * 10 + s[j] - '0';
if (m1 * m2 > ans) ans = m1 * m2;
}
} while (next_permutation(s.begin(), s.end()));
cout << ans << endl;
return 0;
}
