打的我直接裂开 ~~(菜的一笔)~~ ,还好和队友互相打星,迫使我狗在蓝名。
- 出题人的英语是体育老师教的?
- 开场 A 题看不懂
- B 题被自己的**写法给搞得心态爆炸疯狂 WA2
- C 题知道怎么写但是细节太多也没时间写了
[](https://imgchr.com/i/Gs2gYV)
<!--more-->
# A.Dreamoon and Ranking Collection
## 题意
给出一个人参加 `n` 场比赛的所有排名,假设他再参加 `x` 场比赛可以取得 `v` ,`v` 表示 `1~v` 的所有排名他都取得过,求最大的 `v`
## 题解
难在题意了,数据范围比较小直接暴力枚举就行
## 代码
```cpp
#include<bits/stdc++.h>
typedef long long ll;
#define int ll
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
int a[MAXN];
void solve(){
int n, x;
cin >> n >> x;
for(int i = 1;i <= n;i++){
int t;
cin >> t;
a[t]++;
}
int ans = a[1] + 1;
for(int i = 1;i <= 205;i++){
if(a[i] == 0){
if(x == 0)
break;
else
x--;
}
ans = i;
}
cout << ans << endl;
memset(a, 0, sizeof(a));
}
signed main() {
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
```
# B.Dreamoon Likes Permutations
## 题意
求有多少种把一个序列从中间断开,得到两个从 `1` 开始的序列的方法
## 题解
前一个序列用一个 `set` 维护,在第 `i` 个位置时 `set` 中最大的元素等于 `i` 并且 `set.size() == i` 则代表在第 `i` 位置,前一个序列满足条件。
后一个序列维护一个后缀最大值 `mx`, 后缀元素个数 `sum` ,后缀总共元素 `num = n-i`,`mx`代表在第 `i` 位置 后一个序列所需要的数字个数, `sum` 代表我后面还有多少不同个数字,当`sum`, `mx`, `num` 都相等时代表此时后序列满足条件。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> P;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
int a[MAXN], cnt[MAXN];
set<int> S, S1;
vector<P> ans;
void solve(){
int n;
cin >> n;
int sum = 0, mx = -1;
for(int i = 1;i <= n;i++){
cin >> a[i];
cnt[a[i]]++;
if(cnt[a[i]] == 1)
sum++;
S1.insert(-a[i]);
}
//S.insert(-a[1]);
mx = *S1.begin();
mx = -mx;
for(int i = 1;i <= n;i++){
S.insert(-a[i]);
cnt[a[i]]--;
if(cnt[a[i]] == 0){
S1.erase(-a[i]);
sum--;
}
mx = *S1.begin();
mx = -mx;
auto it = S.begin();
int tt = *it;
if(-tt == i && S.size() == i){
int num = n - i;
if(sum == num && num == mx && sum == mx){
ans.push_back(P(i, n-i));
}
}
}
cout << ans.size() << endl;
for(int i = 0;i < ans.size();i++)
cout << ans[i].first << " " << ans[i].second << endl;
S.clear();
S1.clear();
ans.clear();
memset(cnt, 0, sizeof(cnt));
}
signed main() {
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
/*
1
6
1 2 3 1 2 3
1
6
3 5 1 2 4 1
*/
```
# C.Dreamoon Likes Coloring
## 题意
有m种颜色涂一个长度为 `n` 的方块,每种颜色涂连续 $L_i$ 块,构造出使得所有方块都被涂色且每种颜色至少涂了一个方块的方法,方块上的颜色只记录最后一次涂的颜色
## 题解
贪心,每次尽量往前染色
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> P;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
int a[MAXN], ans[MAXN];
void solve(){
int n, x, sum = 0;
cin >> n >> x;
for(int i = 1;i <= x;i++){
cin >> a[i];
sum += a[i];
}
if(sum < n){
cout << -1 << endl;
return ;
}
int pos = 1;
sum -= n;
for(int i = 1;i <= x;i++){
if(a[i] + pos - 1 > n){
cout << -1 << endl;
return ;
}
if(sum >= a[i] - 1){
sum -= a[i] - 1;
a[i] = 1;
} else {
a[i] -= sum;
sum = 0;
}
ans[i] = pos;
pos += a[i];
}
for(int i = 1;i <= x;i++)
cout << ans[i] << " ";
}
signed main() {
int T;
T = 1;
while(T--){
solve();
}
return 0;
}
```
# 待补
D, E
Codeforces Round#631解题报告