本篇博客还在持续更新润色中～
STL - map
题单 🧑🏻💻
| 题目来源 | 题目名称 | 题目链接 | 备注 | 难度 |
|---|---|---|---|---|
| AtCoder - ABC 109B | Shiritori | 链接🔗 | map基础题 | 🟢 |
| HDU - 2648 | Shopping | 链接🔗 | map基础题 | 🟢 |
| AtCoder - ABC 118B | Foods Loved by Everyone | 链接🔗 | map基础题 | 🟢 |
| AtCoder - ABC 116B | Collatz Problem | 链接🔗 | map基础题 | 🟢 |
| Codeforces 1399C | Boats Competition | 链接🔗 | 思维 + map | 🟡 |
| AtCoder - ABC 114D | 756 | 链接🔗 | map + 数论 | 🟡 |
| AtCoder - ABC 111C | //// | 链接🔗 | map排序 | 🟡 |
题解 🚀
Shiritori
题目信息 📚
【题目名称】AtCoder ABC 109B - Shiritori
【题目描述】
Takahashi is practicing shiritori alone again today.
Shiritori is a game as follows:
- In the first turn, a player announces any one word.
- In the subsequent turns, a player announces a word that satisfies the following conditions:
- That word is not announced before.
- The first character of that word is the same as the last character of the last word announced.
In this game, he is practicing to announce as many words as possible in ten seconds.
You are given the number of words Takahashi announced, $N$, and the $i$-th word he announced, $W_i$, for each $i$.
Determine if the rules of shiritori were observed, that is, every word announced by him satisfied the conditions.
【输入】
The input is given from Standard Input in the following format:
$N$
$W_1$
$W_2$
$\vdots$
$W_N$
【输出】
If every word announced by Takahashi satisfied the conditions, print Yes; otherwise, print No.
【数据范围】
- $N$ is an integer satisfying $2 \leq N \leq 100$.
- $W_i$ is a string of length between $1$ and $10$ (inclusive) consisting of lowercase English letters.
【输入样例1】
4
hoge
english
hoge
enigma【输出样例1】
No【输入样例2】
9
basic
c
cpp
php
python
nadesico
ocaml
lua
assembly【输出样例2】
Yes【输入样例3】
8
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaa
aaaaaaa【输出样例3】
No【输入样例4】
3
abc
arc
agc【输出样例4】
No【原题链接】
https://atcoder.jp/contests/abc109/tasks/abc109_b
题目解析 🍉
【题目分析】
利用 map<string, int> 存储当前单词数组，然后进行查询即可。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int main() {
cin >> n;
string w;
char pre;
map<string, int> mp; // map存储单词序列
for (int i = 1; i <= n; i++) {
cin >> w;
mp[w]++;
if (mp[w] > 1 || (pre != w[0] && i != 1)) {
cout << "No" << endl;
return 0;
}
pre = w.back(); // pre记住上个单词的结尾
}
cout << "Yes" << endl;
return 0;
}Shopping
题目信息 📚
【题目名称】HDU 2648 - Shopping
【题目描述】
Every girl likes shopping, so does dandelion. Now she finds the shop is increasing the price every day because the Spring Festival is coming. She is fond of a shop which is called “memory”. Now she wants to know the rank of this shop’s price after the change of everyday.
【输入】
Multiple test cases, please process to the End Of File.
One line contians a number $n ( n \le 10000)$, stands for the number of shops.
Then n lines, each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.) stands for the name of the shop.
Then a line contians a number $m (1 \le m \le 50)$, stands for the days .
Then m parts , every parts contians $n$ lines , each line contians a number $s$ and a string $p$ , stands for this day ,the shop p’s price has increased $s$.
【输出】
Contains $m$ lines ,In the ith line print a number of the shop “memory” ‘s rank after the ith day.
We define the rank as :If there are t shops’ price is higher than the “memory” , than its rank is $t+1$.
【输入样例】
3
memory
kfc
wind
2
49 memory
49 kfc
48 wind
80 kfc
85 wind
83 memory【输出样例】
1
2【原题链接】
https://vjudge.net/problem/HDU-2094
题目解析 🍉
【题目分析】
C++ STL容器 map 的经典使用。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, p;
string s;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
while (cin >> n) {
// 读入店铺
map<string, int> mp;
for (int i = 1; i <= n; i++) {
cin >> s;
mp[s] = 0;
}
// m天数据
cin >> m;
for (int i = 1; i <= m; i++) {
// 读入一天的数据
for (int j = 1; j <= n; j++) {
cin >> p >> s;
mp[s] += p;
}
// 输出当前排名
int cnt = 1;
for (auto t: mp) {
if (t.second > mp["memory"]) cnt++;
}
cout << cnt << endl;
}
}
return 0;
}Foods Loved by Everyone
题目信息 📚
【题目名称】AtCoder ABC 118B - Foods Loved by Everyone
【题目描述】
Katsusando loves omelette rice. Besides, he loves crème brûlée, tenderloin steak, and so on, and believes that these foods are all loved by everyone.
To prove this hypothesis, he conducted a survey on $M$ kinds of foods and asked $N$ people whether they like these foods or not.
The $i$-th person answered that he/she only likes the $A_{i1}$-th, $A_{i2}$-th, …, $A_{iK_i}$-th food.
Find the number of foods liked by all the $N$ people.
【输入】
Input is given from Standard Input in the following format:
$N$ $M$
$K_1$ $A_{11}$ $A_{12}$ … $A_{1K_1}$
$K_2$ $A_{21}$ $A_{22}$ … $A_{2K_2}$
$\vdots$
$K_N$ $A_{N1}$ $A_{N2}$ … $A_{NK_N}$
【输出】
Print the number of the foods liked by all the $N$ people.
【数据范围】
All values in the input are integers.
- $1 \leq N, M \leq 30$
- $1 \leq K_i \leq M$
- $1 \leq A_{ij} \leq M$
For each $i$ $(1 \leq i \leq N)$, $A_{i1}, A_{i2}, …, A_{iK_i}$ are distinct.
【输入样例1】
3 4
2 1 3
3 1 2 3
2 3 2【输出样例1】
1【输入样例2】
5 5
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4【输出样例2】
0【输入样例3】
1 30
3 5 10 30【输出样例3】
3【原题链接】
https://atcoder.jp/contests/abc118/tasks/abc118_b
题目解析 🍉
【题目分析】
利用 map 统计每种食物有多少人喜欢即可。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, k, t;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> m;
map<int, int> mp; // mp[i]=t 表示第i种食物有t个人喜欢
for (int i = 1; i <= n; i++) {
cin >> k;
for (int j = 1; j <= k; j++) {
cin >> t;
mp[t]++;
}
}
// 遍历map，查看每种食物是否被所有人喜欢
int cnt = 0;
for (auto t: mp) {
if (t.second == n) cnt++;
}
cout << cnt << endl;
return 0;
}Boats Competition
题目信息 📚
【题目名称】Codeforces 1399C - Boats Competition
【题目描述】
There are $n$ people who want to participate in a boat competition. The weight of the $i$-th participant is $w_i$. Only teams consisting of two people can participate in this competition. As an organizer, you think that it’s fair to allow only teams with the same total weight.
So, if there are $k$ teams $(a_1,b_1), (a_2,b_2), \ldots, (a_k,b_k)$, where $a_i$ is the weight of the first participant of the $i$-th team and $b_i$ is the weight of the second participant of the $i$-th team, then the condition $a_1+b_1 = a_2+b_2 = \cdots = a_k+b_k = s$, where $s$ is the total weight of each team, should be satisfied.
Your task is to choose such $s$ that the number of teams people can create is the maximum possible. Note that each participant can be in no more than one team.
You have to answer $t$ independent test cases.
【输入】
The first line of the input contains one integer $t$ $(1 \leq t \leq 1000)$ — the number of test cases. Then $t$ test cases follow.
The first line of each test case contains one integer $n$ $(1 \leq n \leq 50)$ — the number of participants. The second line of the test case contains $n$ integers $w_1, w_2, \ldots, w_n$ $(1 \leq w_i \leq n)$, where $w_i$ is the weight of the $i$-th participant.
【输出】
For each test case, print one integer $k$: the maximum number of teams people can compose with the total weight $s$, if you choose $s$ optimally.
【输入样例】
5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2【输出样例】
2
3
4
1
2【提示】
In the first test case of the example, we can reach the optimal answer for $s=6$. Then the first boat is used by participants 1 and 5, and the second boat is used by participants 2 and 4 (indices are the same as weights).
In the second test case of the example, we can reach the optimal answer for $s=12$. Then the first 6 participants can form 3 pairs.
In the third test case of the example, we can reach the optimal answer for $s=3$. The answer is 4 because we have 4 participants with weight 1 and 4 participants with weight 2.
In the fourth test case of the example, we can reach the optimal answer for $s=4$ or $s=6$.
In the fifth test case of the example, we can reach the optimal answer for $s=3$. Note that the participant with weight 3 can’t use the boat because there is no suitable pair for him in the list.
【原题链接】
https://codeforces.com/problemset/problem/1399/C
题目解析 🍉
【题目分析】
题目的数据范围非常小，因此可以采用「枚举」总重量 s 的方式，判断每一个合法的 s 能够组成多少队伍，取答案最大值即可。
判断过程可以使用 map 桶思想计数，也可以采用「贪心 + 双指针」算法。
【C++ 代码】枚举 + map ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
int n, w[N];
// 枚举 + 统计
void solve_1() {
cin >> n;
unordered_map<int, int> mp;
// 输入权重数组w，并统计每个权重出现的次数
for (int i = 1; i <= n; i++) {
cin >> w[i];
mp[w[i]]++;
}
// 枚举可能的权重之和s（最少为1+1=2，最大为n+n=2n，因为w<=n）
// 枚举s后，问题被简化成：对于数组w，有多少队伍的和为s
int maxteams = 0;
for (int s = 2; s <= 2 * n; s++) {
int teams = 0; // 对于当前权重和s，能满足的队伍数存入teams中
// 对权重i枚举，看i和s-i是否均出现在w中
for (int i = 1; i <= s / 2; i++) {
if (mp[i] && mp[s - i]) {
if (i == s - i)
teams += mp[i] / 2;
else
teams += min(mp[i], mp[s - i]);
}
}
if (teams > maxteams) maxteams = teams;
}
cout << maxteams << endl;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve_1();
}
return 0;
}【C++ 代码】枚举 + 贪心 + 双指针 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
int n, w[N];
// 枚举 + 双指针
void solve_2() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
sort(w + 1, w + n + 1);
// 枚举可能的权重之和s（最少为1+1=2，最大为n+n=2n，因为w<=n）
// 枚举s后，问题被简化成：对于数组w，有多少队伍的和为s
int maxteams = 0;
for (int s = 2; s <= 2 * n; s++) {
int teams = 0; // 对于当前权重和s，能满足的队伍数存入teams中
// 权重数组排序经过排序后为升序，故可以使用双指针，统计共有多少对权重和为s
int i = 1, j = n;
while (i < j) {
if (w[i] + w[j] == s) {
i++, j--, teams++;
} else if (w[i] + w[j] < s) {
i++;
} else {
j--;
}
}
maxteams = max(maxteams, teams);
}
cout << maxteams << endl;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve_2();
}
return 0;
}756
题目信息 📚
【题目名称】AtCoder ABC 114D - 756
【题目描述】
You are given an integer $N$. Among the divisors of $N!$ ($=1 \times 2 \times \ldots \times N$), how many Shichi-Go numbers are there?
Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.
When a positive integer $A$ divides a positive integer $B$, $A$ is said to be a divisor of $B$. For example, $6$ has four divisors: $1, 2, 3$, and $6$.
【输入】
Input is given from Standard Input in the following format:
$N$
【输出】
Print the number of the Shichi-Go numbers that are divisors of $N!$.
【数据范围】
- $1 \leq N \leq 100$
- $N$ is an integer.
【输入样例1】
9【输出样例1】
0There are no Shichi-Go numbers among the divisors of $9! = 1 \times 2 \times \ldots \times 9 = 362880$.
【输入样例2】
10【输出样例2】
1There is one Shichi-Go number among the divisors of $10! = 3628800$: $32400$.
【输入样例3】
100【输出样例3】
543【原题链接】
https://atcoder.jp/contests/abc114/tasks/abc114_d
题目解析 🍉
【题目分析】
本题考察数论中的算数基本定理与质因数分解。
算术基本定理/唯一分解定理：当 $n >= 2$ 且 $n$ 为整数时，$n = p_1^{a_1} \times p_2 ^ {a_2} \times \ldots \times p_k^{a_k}$，$p_1,p_2,\ldots,p_k$ 均为质数。
$n$ 共有 $(a_1 + 1) \times (a_2 + 1) \times \ldots \times (a_k + 1)$ 个 divisors（即选若干个或不选 $p_1$，选若干个或不选 $p_2$，… ，选若干个或不选 $p_k$。全选即得到 $n$，全不选得到 $1$）
有了以上基础，我们就可以将题目中的 $N!$ 进行质因数分解，统计每个质因子出现次数。
若想构成 75 个divisors 的数，则必须为：
- $3 * 5 * 5 = 75$ → $p_1^{2} * p_2^{4} * p_3^{4}$
- $3 * 25 = 75$ → $p_1^{2} * p_2^{24}$
- $5 * 15 = 75$ → $p_1^{4} * p_2^{14}$
- $1 * 75 = 75$ → $p_1^{74}$
因此只需分别统计以上四类情况即可。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
map<int, int> mp;
vector<int> v;
// 对x进行质因数分解，并将结果存入map中
void prime_factorization(int x) {
for (int i = 2; i <= x / i; i++) {
while (x % i == 0) {
mp[i]++;
x /= i;
}
}
if (x > 1) mp[x]++;
}
// 在vecotr中搜索有几个数满足v[i]>=x
int s(int x) {
int cnt = 0;
for (int i = 0; i < v.size(); i++) {
if (x <= v[i]) cnt++;
}
return cnt;
}
int main() {
cin >> n;
// 对n!进行质因数分解
for (int i = 1; i <= n; i++) prime_factorization(i);
// 将质因子出现的次数放入vector中进行排序
for (auto t: mp) v.push_back(t.second);
sort(v.begin(), v.end());
// 对75进行分解
// 75 = 75 = 3 * 25 = 5 * 15 = 3 * 5 * 5
// 即拥有75个divisors的数x，可以分解为：x = a1^74 / x = a1^2 * a2^24 / x = a1^4 * a2^14 / x = a1^2 * a2^4 * a3^4
int cnt = 0;
cnt += s(74);
cnt += s(24) * (s(2) - 1);
cnt += s(14) * (s(4) - 1);
cnt += s(4) * (s(4) - 1) / 2 * (s(2) - 2);
cout << cnt << endl;
return 0;
}////
题目信息 📚
【题目名称】AtCoder ABC 111C - ////
【题目描述】
A sequence $a_1, a_2, …, a_n$ is said to be /\/\/\/ when the following conditions are satisfied:
- For each $i = 1, 2, …, n - 2$, $a_i = a_{i+2}$.
- Exactly two different numbers appear in the sequence.
You are given a sequence $v_1, v_2, …, v_n$ whose length is even. We would like to make this sequence /\/\/\/ by replacing some of its elements.
Find the minimum number of elements that need to be replaced.
【输入】
The input is given from Standard Input in the following format:
$n$
$v_1$ $v_2$ $\ldots$ $v_n$
【输出】
Print the minimum number of elements that needs to be replaced.
【数据范围】
- $2 \leq n \leq 10^5$
- $n$ is even.
- $1 \leq v_i \leq 10^5$
- $v_i$ is an integer.
【输入样例1】
4
3 1 3 2【输出样例1】
1The sequence $3, 1, 3, 2$ is not /\/\/\/, but we can make it /\/\/\/ by replacing one of its elements: for example, replace the fourth element to make it $3, 1, 3, 1$.
【输入样例2】
6
105 119 105 119 105 119【输出样例2】
0The sequence $105, 119, 105, 119, 105, 119$ is /\/\/\/.
【输入样例3】
4
1 1 1 1【输出样例3】
2The elements of the sequence $1, 1, 1, 1$ are all the same, so it is not /\/\/\/.
【原题链接】
https://atcoder.jp/contests/abc111/tasks/arc103_a
题目解析 🍉
【题目分析】
统计奇数位以及偶数位上所有数字出现的次数（map），从大到小排序（将 map 的 key:value 键值对存入 vector<pair<int, int>> 中，自定义 sort 参数实现按 value 排序），然后贪心即可。
PS：注意奇数位和偶数位上最多出现的数字可能相同，此时需要考虑选择出现次数第二多的情况。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, v[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
// 读入数据，并且统计奇数位、偶数位数字出现个数，存入m1, m2中
map<int, int> m1, m2;
for (int i = 1; i <= n; i++) {
cin >> v[i];
if (i & 1) m1[v[i]]++;
else m2[v[i]]++;
}
// 将map中的键值对存入vector<pair<int, int>>中，实现按照value排序
vector<PII> v1, v2;
for (auto t: m1) v1.push_back({t.first, t.second});
for (auto t: m2) v2.push_back({t.first, t.second});
// 匿名函数替换cmp
sort(v1.begin(), v1.end(), [](auto a, auto b) { return a.second > b.second; });
sort(v2.begin(), v2.end(), [](auto a, auto b) { return a.second > b.second; });
// 取出奇数位、偶数位出现次数最多的数字以及出现次数
int id1 = v1[0].first, cnt1 = v1[0].second;
int id2 = v2[0].first, cnt2 = v2[0].second;
// 分类讨论 + 贪心
int ans = 0;
if (id1 != id2) { // 奇数、偶数位置出现次数最多的数字不同
ans = n - cnt1 - cnt2;
} else { // 奇数、偶数位置出现次数最多的数字相同
if (v1.size() == 1 && v2.size() == 1)
ans = n / 2;
else if (v1.size() >= 2 && v2.size() >= 2) { //
ans = min(n - cnt1 - v2[1].second, n - cnt2 - v1[1].second);
} else if (v1.size() >= 2 && v2.size() == 1) {
ans = n - cnt2 - v1[1].second;
} else if (v1.size() == 1 && v2.size() >= 2) {
ans = n - cnt1 - v2[1].second;
}
}
cout << ans << endl;
return 0;
}***
题目信息 📚
【题目名称】 -
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
【原题链接】
题目解析 🍉
【题目分析】
【C++ 代码】
