\(\texttt{E F}\) 忘（不）记（会）写了。
A Yet Another Dividing into Teams 题解
题目大意
有一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)，将他们分为若干组，使得每一组没有两个数的差为 \(1\)，使分的组数尽可能少。
解题思路
排完序后对于任意 \(1\le i< n\) 均有 \(a_i\) 与 \(a_{i+1}\) 最接近，所以若存在 \(a_{i+1}-a_i=1\) 则必定要分成两组，否则一组。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 1;
sort(a + 1, a + n + 1);
for(int i = 2; i <= n; i++) {
if(a[i - 1] + 1 == a[i]) {
ans = 2;
break;
}
}
cout << ans << "\n";
}
return 0;
}
B1 & B2 Books Exchange 题解
题目大意
有 \(n\) 个小朋友每人手里有一本书，给定一个排列 \(a\)，表示每一轮第 \(i\) 个小朋友会把书给 \(a_i\)。求每个小朋友的书会在几轮后回到自己手里。
解题思路
暴搜寻找即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int t, n, a[N];
inline int dfs(int cur, int x, int y) {
if(y == x && cur != 0) {
return cur;
}
return dfs(cur + 1, a[x], y);
}
int main() {
ios::sync_woth_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
cout << dfs(0, i, i) << " ";
}
cout << "\n";
}
return 0;
}
C1 & C2 Good Numbers 题解
题目大意
给定 \(n\)，求不小于 \(n\) 的最小数 \(x\)，使得 \(x\) 可以分解成不同的 \(3\) 的幂之和。其中 \(C2\) 的数据规模更大。
解题思路
我们只需要算出 \(3^i\) 的前缀和 \(s_i\)，然后从大到小判断是否要选 \(3^i\) 作为 \(x\) 的一部分，如果 已选数字之和加上 \(s_{i-1}\le x\) 那么说明当前 \(3^i\) 不用选。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int n, ans, sum[105], a[105];
inline int solve(long long x) {
int ans = 0;
for(int i = 38; i >= 1; i--) {
if(ans + sum[i - 1] >= x) {
continue;
} else {
ans += a[i];
}
}
if(ans < x) {
ans += 1;
}
return ans;
}
signed main() {
sum[0] = 1;
a[0] = 1;
long long cnt = 3;
for(int i = 1; i <= 100 && sum[i - 1] <= INF; i++) {
sum[i] = sum[i - 1] + cnt;
a[i] = cnt;
cnt *= 3;
}
int t;
cin >> t;
while(t--) {
cin >> n;
cout << solve(n) << "\n";
}
return 0;
}
D1 & D2 Too Many Segments 题解
题目大意
给定 \(n\) 个区间，要求删除最少数量的区间，使得每个点被覆盖的次数不超过 \(k\)，求方案。
解题思路
我们首先要做的事情就是能够计算出当前点 \(x\) 处被几条线段覆盖的问题。我们需要先将所有线段按左端点排序，用差分维护线段结束，然后枚举每条线段，每枚举一个线段我们就让 \(cnt+1\)， 表示当前点 a[i].l 有 \(cnt\) 个线段覆盖，同时 sum[a[i].r]--，表示线段在 a[i].r 在这里结束。当我们在判断当前点 a[i].l 被几条线段覆盖时，还需要去掉右端点已经小于 a[i].l 的线段，这样就得到了当前点 a[i].l 有 \(cnt\) 个线段覆盖。然后判断 \(cnt>k\)，如果 \(cnt>k\) 说明需要去掉线段，我们优先去掉右端点最大的线段。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k;
int sum[N], cnt, pos;
vector<int> ans;
priority_queue<pair<int, int> > p;
struct node {
int l, r, id;
} a[N];
inline bool cmp(node x, node y) {
if(x.l == y.l) {
return x.r > y.r;
}
return x.l < y.l;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r;
a[i].id = i;
}
sort(a + 1, a + 1 + n, cmp);
for(int i = 1; i <= n; i++) {
p.push(make_pair(a[i].r, a[i].id));
cnt++;
sum[a[i].r]--;
while(pos < a[i].l) {
cnt = cnt + sum[pos];
pos++;
}
if(a[i].l != a[i + 1].l) {
while(cnt > k) {
while(!p.empty() && p.top().first < a[i].l) {
p.pop();
}
ans.push_back(p.top().second);
sum[p.top().first]++;
p.pop();
cnt--;
}
}
}
cout << ans.size() << "\n";
for(int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << "\n";
return 0;
}