B. Back to School '24 P2 - Cheating
题目描述
有 \(N\) 道题，第 \(i\) 道题的分值为 \(A_i(A_1\le A_2\le \dots\le A_N)\)，有 \(M\) 个学生，初始时分数均为 \(0\)。每次会让分数最低的 \(B_i\) 个同学获得 \(A_i\) 分，若有多个分数相同的学生，则让编号更小的学生获得 \(A_i\) 分。求最终每个学生的分数。
思路
由于 \(A_1\le A_2\le \dots \le A_N\)，所以让一些学生获得 \(A_i\) 分后，一定比其他学生分都高，因此这些学生的分数一定是递增的。每次对一段区间加 \(A_i\) 即可。
时空复杂度均为 \(O(N+M)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000005;
int n, m, a[MAXN];
ll sum[MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
int pos = 0;
for(int i = 1, x; i <= n; ++i) {
cin >> x;
sum[pos + 1] += a[i];
sum[min(m + 1, pos + x + 1)] -= a[i];
if(pos + x > m) {
sum[1] += a[i], sum[pos + x - m + 1] -= a[i];
}
pos = (pos + x > m ? pos + x - m : pos + x);
}
for(int i = 1; i <= m; ++i) {
cout << (sum[i] += sum[i - 1]) << " ";
}
return 0;
}
D. Back to School '24 P4 - Candidates
题目描述
有 \(N\) 个 \(K\) 元组，我们将对其从大到小进行排序，有一个长度为 \(K\) 的排列 \(A\)，代表排序时第 \(i\) 个关键字为 \(A_i\)。现在给出排序后的结果，求出字典序最小的 \(A\)。
思路
显然第一关键字中 \(N\) 个元组必须单调不升。假如第一关键字为 \([3,2,2,1,1,1]\)，那么这将会把数列分成三段，因为第一关键字已经确定不同段间的顺序，所以之后就不需要管断点了。
使用优先队列和拓扑排序求解即可。
空间复杂度 \(O(NK)\)，时间复杂度 \(O(NK\log K)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001, MAXK = 300001;
int n, k, p[MAXN], cnt[MAXK];
bool flag[MAXN];
vector<int> a[MAXN], ans;
vector<bool> vis[MAXK];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> p[i];
}
for(int i = 1; i <= n; ++i) {
a[i].resize(k + 1);
for(int j = 1; j <= k; ++j) {
cin >> a[i][j];
}
}
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 1; i <= k; ++i) {
vis[i].resize(n + 1);
for(int j = 1; j < n; ++j) {
if(a[p[j]][i] >= a[p[j + 1]][i]) {
cnt[i]++;
vis[i][j] = 1;
}
}
if(cnt[i] == n - 1) {
pq.push(i);
}
}
for(; !pq.empty(); ) {
int x = pq.top();
pq.pop();
ans.emplace_back(x);
for(int i = 1; i < n; ++i) {
if(a[p[i]][x] > a[p[i + 1]][x] && !flag[i]) {
flag[i] = 1;
for(int j = 1; j <= k; ++j) {
if(!vis[j][i]) {
vis[j][i] = 1;
cnt[j]++;
if(cnt[j] == n - 1) {
pq.push(j);
}
}
}
}
}
}
if(ans.size() != k) {
cout << -1;
}else {
for(int x : ans) {
cout << x << " ";
}
}
return 0;
}
E. Back to School '24 P5 - Snitching
题目描述
有 \(N\) 个学生，第 \(i\) 个学生指责学生 \(A_i\)。你要按顺序采访区间 \([l,r]\) 中的学生，并找到第一个被指责 \(k\) 次的学生。如果没有人被指责 \(k\) 次，输出 \(-1\)。
思路
使用根号分治。
很容易发现这里 \(r\) 无关紧要，只需找到 \(l\) 后第一个出现 \(k\) 次的学生并判断是否 \(\le r\) 即可。
我们对查询的 \(l\) 从大到小处理。对于 \(k\le \sqrt N\) 的查询，我们令 \(nxt_i\) 表示下一个出现 \(i\) 次的元素位置，每次在开头加入元素时，先用 vector 记录下来，再把 \(\sqrt N\) 以内的 \(nxt_i\) 用 vector 记录的信息全部更新。
对于 \(k> \sqrt N\) 的查询，至多有 \(\sqrt N\) 个数会出现 \(k\) 次，暴力枚举即可。
空间复杂度 \(O(N+Q)\)，时间复杂度 \(O((N+Q)\sqrt N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500001, B = 708, MAXQ = 500001;
struct query {
int l, r, k, id;
}s[MAXN];
int n, q, a[MAXN], cnt[MAXN], nxt[B + 1], ans[MAXQ];
vector<int> ve, pos[MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
cnt[a[i]]++;
}
for(int i = 1; i <= n; ++i) {
if(cnt[i] > B) {
ve.emplace_back(i);
}
}
for(int i = 1; i <= q; ++i) {
cin >> s[i].l >> s[i].r >> s[i].k;
s[i].id = i;
}
sort(s + 1, s + q + 1, [](const query &a, const query &b) -> bool {
return a.l < b.l;
});
for(int i = 1; i <= B; ++i) {
nxt[i] = n + 1;
}
for(int i = q, j = n; i >= 1; --i) {
for(; j >= 1 && j >= s[i].l; --j) {
pos[a[j]].emplace_back(j);
for(int k = 1; k <= min(B, int(pos[a[j]].size())); ++k) {
nxt[k] = min(nxt[k], pos[a[j]][pos[a[j]].size() - k]);
}
}
if(s[i].k <= B) {
ans[s[i].id] = (nxt[s[i].k] <= s[i].r ? a[nxt[s[i].k]] : -1);
}else {
int ret = n + 1;
for(int x : ve) {
if(pos[x].size() >= s[i].k) {
ret = min(ret, pos[x][pos[x].size() - s[i].k]);
}
}
ans[s[i].id] = (ret <= s[i].r ? a[ret] : -1);
}
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}