信息奥赛复盘｜2023多校新生周赛九（2023.11.19）
比赛信息 📚
时间：2023 年 11 月 19 日 18:00 - 21:00
竞赛链接：（仅ZJNU内网登录）
ACM集训队讲解视频：/
个人情况 ✍️
本周个人排名：8/28
AC情况：9/19
比赛时间：2023.11.19（18：00 - 21:00）
T1 字符串签到题 ✅
T2 凯撒密码签到题 ✅
T3 求解最小公倍数 ✅
T4 找到二段性 → 二分 ✅
T5 简单思维 + 模拟 ✅
T6 树的涂色问题 ❌
T7 本场耗时最长的题目，赛时陷入了思维误区，未能AC ❌（补题时发现思维漏洞）
T8 该题属于经典的「感觉平常做过类似的题，但赛场上就是做不出的题」 ❌（赛后通过暴力法理清思路，寻找优化方法，发现需要补充「同余」相关数学知识）
总体来看，这次周赛难度相对较低，有不少简单题。若是能在赛时做出T7会更圆满，继续加油 😀
题目列表 🧑🏻💻
| 题目名称 | 难度 |
|---|---|
| T1 - Strings with the Same Length | 🟢 |
| T2 - ROT N | 🟢 |
| T3 - Snack | 🟢 |
| T4 - Buy an Integer | 🟢 |
| T5 - Brick Break | 🟢 |
| T6 - Coloring Edges on Tree | 🟡 |
| T7 - Double Factorial | 🟡 |
| T8 - Rem of Sum is Num | 🟡 |
题解 🚀
A - Strings with the Same Length
题目信息 📚
【题目描述】
Given are strings $s$ and $t$ of length $N$ each, both consisting of lowercase English letters.
Let us form a new string by alternating the characters of $S$ and the characters of $T$, as follows: the first character of $S$, the first character of $T$, the second character of $S$, the second character of $T$, $…$, the $N$-th character of $S$, the $N$-th character of $T$. Print this new string.
【输入】
Input is given from Standard Input in the following format:
$N$
$S$ $T$
【输出】
Print the string formed.
【数据范围】
$1 \leq N \leq 100$
$|S| = |T| = N$
$S$ and $T$ are strings consisting of lowercase English letters.
【输入样例1】
2
ip cc【输出样例1】
icpc【输入样例2】
8
hmhmnknk uuuuuuuu【输出样例2】
humuhumunukunuku【输入样例3】
5
aaaaa aaaaa【输出样例3】
aaaaaaaaaa【题目来源】
题目解析 🍉
【题目分析】
字符串签到题。
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
string s1, s2, s;
int n;
cin >> n;
cin >> s1 >> s2;
// 逐个添加
for (int i = 0; i < n; i++) s = s + s1[i] + s2[i];
cout << s << endl;
return 0;
}B - ROT N
题目信息 📚
【题目描述】
We have a string $S$ consisting of uppercase English letters. Additionally, an integer $N$ will be given.
Shift each character of $S$ by $N$ in alphabetical order (see below), and print the resulting string.
We assume that A follows Z. For example, shifting A by $2$ results in C (A $\to$ B $\to$ C), and shifting Y by $3$ results in B (Y $\to$ Z $\to$ A $\to$ B).
【输入】
Input is given from Standard Input in the following format:
$N$
$S$
【输出】
Print the string resulting from shifting each character of $S$ by $N$ in alphabetical order.
【输入样例1】
2
ABCXYZ【输出样例1】
CDEZAB【输入样例2】
0
ABCXYZ【输出样例2】
ABCXYZ【输入样例3】
13
ABCDEFGHIJKLMNOPQRSTUVWXYZ【输出样例3】
NOPQRSTUVWXYZABCDEFGHIJKLM【数据范围】
- $0 \leq N \leq 26$
- $1 \leq |S| \leq 10^4$
- $S$ consists of uppercase English letters.
【题目来源】
题目解析 🍉
【题目分析】
凯撒密码签到题。
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int n;
string s;
cin >> n; cin >> s;
for (int i = 0; i < s.size(); i++) {
cout << (char) ((s[i] - 'A' + n) % 26 + 'A');
}
return 0;
}C - Snack
题目信息 📚
【题目描述】
Takahashi is organizing a party.
At the party, each guest will receive one or more snack pieces.
Takahashi predicts that the number of guests at this party will be $A$ or $B$.
Find the minimum number of pieces that can be evenly distributed to the guests in both of the cases predicted.
We assume that a piece cannot be divided and distributed to multiple guests.
【输入】
Input is given from Standard Input in the following format:
$A$ $B$
【输出】
Print the minimum number of pieces that can be evenly distributed to the guests in both of the cases with $A$ guests and $B$ guests.
【数据范围】
- $1 \leq A, B \leq 10^5$
- $A \neq B$
- All values in input are integers.
【输入样例1】
2 3【输出样例1】
6【输入样例2】
123 456【输出样例2】
18696【输入样例3】
100000 99999【输出样例3】
9999900000【题目来源】
题目解析 🍉
【题目分析】
求解最小公倍数。
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
LL a, b;
cin >> a >> b;
// 输出最小公倍数
cout << a * b / __gcd(a, b) << endl;
return 0;
}D - Buy an Integer
题目信息 📚
【题目描述】
Takahashi has come to an integer shop to buy an integer.
The shop sells the integers from $1$ through $10^9$. The integer $N$ is sold for $A \times N + B \times d(N)$ yen (the currency of Japan), where $d(N)$ is the number of digits in the decimal notation of $N$.
Find the largest integer that Takahashi can buy when he has $X$ yen. If no integer can be bought, print $0$.
【输入】
Input is given from Standard Input in the following format:
$A$ $B$ $X$
【输出】
Print the greatest integer that Takahashi can buy. If no integer can be bought, print $0$.
【数据范围】
- All values in input are integers.
- $1 \leq A \leq 10^9$
- $1 \leq B \leq 10^9$
- $1 \leq X \leq 10^{18}$
【输入样例1】
10 7 100【输出样例1】
9【输入样例2】
2 1 100000000000【输出样例2】
1000000000【输入样例3】
1000000000 1000000000 100【输出样例3】
0【输入样例4】
1234 56789 314159265【输出样例4】
254309【提示】
For Sample #1:
The integer $9$ is sold for $10 \times 9 + 7 \times 1 = 97$ yen, and this is the greatest integer that can be bought. Some of the other integers are sold for the following prices:
- $10: 10 \times 10 + 7 \times 2 = 114$ yen
- $100: 10 \times 100 + 7 \times 3 = 1021$ yen
- $12345: 10 \times 12345 + 7 \times 5 = 123485$ yen
For Sample #2:
He can buy the largest integer that is sold. Note that input may not fit into a $32$-bit integer type.
题目解析 🍉
【题目分析】
发现二段性 → 二分
【C++代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL A, B, X;
// 返回x的位数，如123共有3位数字
LL d(LL x) {
string s = to_string(x);
return s.size();
}
int main() {
cin >> A >> B >> X;
// 设定二分区间
LL l = 1, r = 1e9;
// 二分
while (l < r) {
LL mid = l + r + 1 >> 1;
if (A * mid + B * d(mid) <= X)
l = mid;
else
r = mid - 1;
}
// 判断是否有解（X能否购买整数1）
if (A + B > X) cout << 0 << endl; // 无解
else cout << l << endl; // 有解
return 0;
}E - Brick Break
题目信息 📚
【题目描述】
We have $N$ bricks arranged in a row from left to right.
The $i$-th brick from the left $(1 \leq i \leq N)$ has an integer $a_i$ written on it.
Among them, you can break at most $N-1$ bricks of your choice.
Let us say there are $K$ bricks remaining. Snuke will be satisfied if, for each integer $i$ $(1 \leq i \leq K)$, the $i$-th of those brick from the left has the integer $i$ written on it.
Find the minimum number of bricks you need to break to satisfy Snuke’s desire. If his desire is unsatisfiable, print -1 instead.
【输入】
Input is given from Standard Input in the following format:
$N$
$a_1$ $a_2$ $…$ $a_N$
【输出】
Print the minimum number of bricks that need to be broken to satisfy Snuke’s desire, or print -1 if his desire is unsatisfiable.
【数据范围】
- All values in input are integers.
- $1 \leq N \leq 200000$
- $1 \leq a_i \leq N$
【输入样例1】
3
2 1 2【输出样例1】
1【输入样例2】
3
2 2 2【输出样例2】
-1【输入样例3】
10
3 1 4 1 5 9 2 6 5 3【输出样例3】
7【输入样例4】
1
1【输出样例4】
0【提示】
For Sample #1:
If we break the leftmost brick, the remaining bricks have integers $1$ and $2$ written on them from left to right, in which case Snuke will be satisfied.
For Sample #2:
In this case, there is no way to break some of the bricks to satisfy Snuke’s desire.
【题目来源】
题目解析 🍉
设定计数器 cnt=1，不断向后查找当前 cnt 是否存在并且累加 cnt 即可。
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, a[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
// 设定计数器cnt，不断向后查找当前cnt是否存在即可
int cnt = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == cnt) cnt++;
}
// 输出答案
if (cnt == 1) cout << -1 << endl;
else cout << n - cnt + 1 << endl;
return 0;
}F - Coloring Edges on Tree
题目信息 📚
【题目描述】
Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$-th edge connects Vertex $a_i$ and Vertex $b_i$.
Consider painting the edges in $G$ with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.
【输入】
Input is given from Standard Input in the following format:
$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
【输出】
Print $N$ lines.
The first line should contain $K$, the number of colors used.
The $(i+1)$-th line $(1 \le i \le N-1)$ should contain $c_i$, the integer representing the color of the $i$-th edge, where $1 \le c_i \le K$ must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.
【数据范围】
- $ 2 \le N \le 10^5$
- $ 1 \le a_i \lt b_i \le N$
【输入样例1】
3
1 2
2 3【输出样例1】
2
1
2【输入样例2】
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8【输出样例2】
4
1
2
3
4
1
1
2【输入样例3】
6
1 2
1 3
1 4
1 5
1 6【输出样例3】
5
1
2
3
4
5【题目来源】
题目解析 🍉
【题目分析】
【C++代码】deque + map ✅
【C++代码】dp ✅
G - Double Factorial
题目信息 📚
【题目描述】
For an integer $n$ not less than $0$, let us define $f(n)$ as follows:
- $f(n) = 1$ (if $n \lt 2$)
- $f(n) = n f(n-2)$ (if $n \geq 2$)
Given is an integer $N$. Find the number of trailing zeros in the decimal notation of $f(N)$.
【输入】
Input is given from Standard Input in the following format:
$N$
【输出】
Print the number of trailing zeros in the decimal notation of $f(N)$.
【数据范围】
$0 \leq N \leq 10^{18}$
【输入样例1】
12【输出样例1】
1【输入样例2】
5【输出样例2】
0【输入样例3】
1000000000000000000【输出样例3】
124999999999999995【提示】
For Sample #1:
$f(12) = 12 × 10 × 8 × 6 × 4 × 2 = 46080$, which has one trailing zero.
For Sample #2:
$f(5) = 5 × 3 × 1 = 15$, which has no trailing zeros.
【题目来源】
题目解析 🍉
【题目分析】
末尾0只可能由因子 5 和 2 构成，又 2 的数量远大于 5，因此只需要查询 $f(n)$ 有多少个因子 5 存在即可。
- 包含1个因子5的个数：$floor(f(n) / (5*2))$
- 包含2个因子5的个数：$floor(f(n) / {(5 * 5 * 2)})$
- 包含3个因子5的个数：$floor(f(n) / {(5 * 5 * 5 * 2)})$
- …
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
int main() {
cin >> n;
if (n & 1) cout << 0 << endl; // n为奇数，无因子5和2
else { // n为偶数，计算因子5的个数
// p=10、50、250、1250...
LL p = 10, cnt = 0;
while (n >= p) {
cnt = cnt + n / p;
p *= 5;
}
cout << cnt << endl;
}
return 0;
}H - Rem of Sum is Num
题目信息 📚
【题目描述】
Given are a sequence of $N$ positive integers $A_1, A_2, \ldots, A_N$, and a positive integer $K$
Find the number of non-empty contiguous subsequences in $A$ such that the remainder when dividing the sum of its elements by $K$ is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.
【输入】
Input is given from Standard Input in the following format:
$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$
【输出】
Print the number of subsequences that satisfy the condition.
【数据范围】
- All values in input are integers.
- $1 \leq N \leq 2\times 10^5$
- $1 \leq K \leq 10^9$
- $1 \leq A_i \leq 10^9$
【输入样例1】
5 4
1 4 2 3 5【输出样例1】
4【输入样例2】
8 4
4 2 4 2 4 2 4 2【输出样例2】
7【输入样例3】
10 7
14 15 92 65 35 89 79 32 38 46【输出样例3】
8【提示】
For Sample #1:
Four sequences satisfy the condition: $(1)$, $(4,2)$, $(1,4,2)$, and $(5)$.
For Sample #2:
$(4,2)$ is counted four times, and $(2,4)$ is counted three times.
【题目来源】
题目解析 🍉
【题目分析】
官方题解：https://img.atcoder.jp/abc146/editorial.pdf
通过暴力法理清思路，需要优化的公式为（s 为a 的前缀和数组）：
$$
(s[i] - s[j]) \bmod k= i - j
$$
然后用同余公式，修改方程：
$$
s[i] - s[j] = k*t + i - j
$$
$$
(s[i] - i) - (s[j] - j)= k*t
$$
$$
(s[i] - i) \bmod k = (s[j] - j) \bmod k
$$
在预处理时，可以令 a[i]--，这样就可以把公式优化为：
$$
s[i] \bmod k = s[j] \bmod k
$$
PS：本题有区间长度限制，$i - j <= k-1$
【C++代码】暴力法（TLE） ❌
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, k, a[N], s[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i]; // 求前缀和数组
}
// 暴力法
LL cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if ((s[i] - s[j]) % k == i - j) cnt++;
}
}
cout << cnt << endl;
return 0;
}【C++代码】前缀和 + 同余 + map + 队列 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, k, a[N], s[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
// 预处理，求前缀和数组
a[i]--;
s[i] = (s[i - 1] + a[i]) % k;
}
LL cnt = 0;
map<LL, LL> mp; // 构建一个map
queue<LL> q; // 维护一个长度为k的队列
q.push(0);
mp[0]++;
for (int i = 1; i <= n; i++) {
q.push(s[i] % k);
if (q.size() > k) {
LL tmp = q.front();
mp[tmp]--;
q.pop();
}
cnt += mp[s[i] % k]++;
}
cout << cnt << endl;
return 0;
}
