Codeforces Round#631解题报告

打的我直接裂开 (菜的一笔) ,还好和队友互相打星,迫使我狗在蓝名。

  • 出题人的英语是体育老师教的?
  • 开场 A 题看不懂
  • B 题被自己的**写法给搞得心态爆炸疯狂 WA2
  • C 题知道怎么写但是细节太多也没时间写了

Gs2gYV.png

A.Dreamoon and Ranking Collection

题意

给出一个人参加 n 场比赛的所有排名,假设他再参加 x 场比赛可以取得 vv 表示 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-imx代表在第 i 位置 后一个序列所需要的数字个数, sum 代表我后面还有多少不同个数字,当summx, 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