错题列表：
#1Playlist
#2分数线划定
#3Made Up
#4图书管理员
#1Playlist
我们来介绍滑动窗口的写法：
1、使用一个滑动窗口k[l,r)在歌曲列表中移动。
2、同时利用一个unordered_set S来检测窗口中的歌曲是否有重复。如果窗口右端的歌曲在窗口内没有重复，那么就将其加入到窗口中并继续尝试扩大窗口；
3、否则，就将窗口左端的歌曲移出窗口，并尝试缩小窗口。
4、在这个过程中，不断更新并最终得到无重复歌曲序列的最大长度。
我们来看一下标程：
using namespace std;
int main() {ios::sync_with_stdio(0), cin.tie(0);int n;cin >> n;vector<int> A(n);for (int &a : A) cin >> a;set<int> S;int ans = 0;for (int l = 0, r = 0; l < n; S.erase(A[l++])) {// r = maxᵣ{A[l,r)无重复元素}while (r < n && !S.count(A[r])) S.insert(A[r++]);ans = max(ans, r - l); // 更新最大的无重复歌曲序列长度}printf("%d\n", ans);return 0;
}
#2分数线划定
我们先来看一下题目：
直接来看一下我的代码：
#include <bits/stdc++.h>
using namespace std;
struct person{int num, pen;// 编号， 笔试成绩bool operator<(const person & one)const { // 重载运算符if(pen != one.pen) return one.pen < pen;else return one.num > num;}
};
int main() {ios::sync_with_stdio(false),cin.tie(0);int n, m;cin >> n >> m;vector<person> people(n);for(int i = 0; i < n; i++) cin >> people[i].num >> people[i].pen;sort(people.begin(),people.end());m = m * 3 / 2;int numline = people[m - 1].pen;cout << numline <<' ';int peo = 0;for(int i = 0;i < n; i++)if(people[i].pen < numline) break;else peo++;cout << peo << '\n';for(int i = 0; i < peo; i++) cout << people[i].num << ' ' <<people[i].pen << '\n';return 0;
}很简单。
#3Made Up
这个只能用线性遍历，用一个新的cnt数组：把方案数存起来。
因为
保证输入都小于N，不然查不到吗。
【分析】
1.所有数字范围都在[1,N]内，可以新建一个数组Cnt，其中Cnt[b]代表Bc=b出现的次数，其中c∈C。
2.遍历数组A，将A中每个元素a在Cnt中对应的值Cnt[a]相加，得到最终的结果。
#include <bits/stdc++.h>
using namespace std;
int main() {ios::sync_with_stdio(false), cin.tie(0);int N;cin >> N;vector<int> A(N), B(N), C(N), Cnt(N);// 减1是因为在C++中，数组索引从0开始，而题目中的数组索引从1开始for (int& a : A) cin >> a, a -= 1;for (int& b : B) cin >> b, b -= 1;// 计算每个元素b（B[c]）在数组C中出现的次数，结果存储在Cnt数组中for (int& c : C) cin >> c, c -= 1, Cnt[B[c]] += 1;long long ans = 0;// 计算A数组中每个元素a在Cnt数组中的对应值的和，即答案for (int a : A) ans += Cnt[a]; printf("%lld\n", ans);return 0;
}#4图书管理员
#include <bits/stdc++.h>
using namespace std;
int main() {ios::sync_with_stdio(false), cin.tie(0);int n, q;cin >> n >> q; // 书的数量和读者的数量map<int, int> S; // 后缀: 包含此后缀的最小编码for (int i = 0, a; i < n; i++) {cin >> a; // 图书的编码后缀: 2123->3, 23, 123, 2123for (int e = 10;; e *= 10) {int f = a % e;if (!S.count(f)) S[f] = a;S[f] = min(S[f], a);if (f == a) break;}}for (int i = 0, l, a; i < q; i++) {cin >> l >> a;printf("%d\n", S.count(a) ? S[a] : -1);}return 0;
}map就是映射，int映射到int，就是代表的意思。
