打的我直接裂开 ~~(菜的一笔)~~ ，还好和队友互相打星，迫使我狗在蓝名。 - 出题人的英语是体育老师教的？ - 开场 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