打的我直接裂开 (菜的一笔) ，还好和队友互相打星，迫使我狗在蓝名。
- 出题人的英语是体育老师教的？
- 开场 A 题看不懂
- B 题被自己的**写法给搞得心态爆炸疯狂 WA2
- C 题知道怎么写但是细节太多也没时间写了
A.Dreamoon and Ranking Collection
题意
给出一个人参加 n 场比赛的所有排名，假设他再参加 x 场比赛可以取得 v ，v 表示 1~v 的所有排名他都取得过，求最大的 v
题解
难在题意了，数据范围比较小直接暴力枚举就行
代码
#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 都相等时代表此时后序列满足条件。
代码
#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$ 块，构造出使得所有方块都被涂色且每种颜色至少涂了一个方块的方法，方块上的颜色只记录最后一次涂的颜色
题解
贪心，每次尽量往前染色
代码
#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