Codeforces Round#632解题报告

Codeforces Round#632解题报告

场上20分钟写完 $A$,$B$ 直接下机,最后最后过了 $C$ ,补题时也是 $BUG$层出,菜刀不行

Snipaste_20200410_130558.png

A.Little Artem

题意

有白格子(W)相邻的黑格子(B)的数目==有黑格子相邻的白格子的数目+1

题解

一个角落的出现一个W,其余全为B,那么有白格子相邻的黑格子的数目恒为2,且有黑格子相邻的白格子的数目1

代码

#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;
void solve(){
    int n, m;
    cin >> n >> m;
    cout << "W";
    for(int i = 1;i <= n;i++){
        for(int j = 1; j<= m;j++){
            if(i == 1 && j == 1)
                continue;
            else
                cout << "B";
        }
        cout << endl;
    }
}
signed main() {
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

B.Kind Anton

题意

给一个 $a$ 数组,一个 $b$ 数组。其中 $a$ 数组只含有 $-1、0、1$ 。有一种操作 $a_j=a_j + a_i(i<j)$,问是否能够通过这种操作(不限次数)使 $a$ 数组与 $b$ 数组相等

题解

遍历 $a$ 数组,如果$b_i > a_i$,则 $ai$ 就看当前有没有 $1$,如果$a_i > b_i$,就找 $a_i$ 当前有没有 $-1$

代码

#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;
map<int, int > c;
int a[MAXN], b[MAXN];
void solve(){
    int n, m, x;
    c.clear();
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++){
        cin >> b[i];
    }
    for(int i = 1;i <= n;i++){
        if(b[i] > a[i] && c[1] == 0){
            cout << "NO" << endl;
            return ;
        } else if(b[i] < a[i] && c[-1] == 0) {
            cout << "NO" << endl;
            return ;
        }
        c[a[i]]++;
    }
    cout << "YES" << endl;
    
}
signed main() {
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

C.Eugene and an array

题意

给定一个长度为 $n$ 的数组 $a_i$ 问,能在 $a_i$ 中取出多少子集 $b_i$ 且 $b_i$ 的所有子集和均不为 $0$

题解

以 $i$ 位置为该子集的右端点, 记录前缀和,如果 $i$ 位置的前缀和在 $pos$ 位置出现过则代表从 $pos+1$ 的位置开始到 $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;
map<int, int> mp;

void solve() {
    int n;
    cin >> n;
    int pos = 0, ans = 0, x, sum = 0;
    mp[0] = 1;
    for(int i = 1;i <= n;i++){
        cin >> x;
        sum += x;
        if(mp[sum])
            pos = max(pos, mp[sum]);
        ans += (i - pos);
        mp[sum] = i+1; //pos+1
    }
    cout << ans << endl;
}

signed main() {
    int T;
    T = 1;
    //cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

D.Challenges in school №41

题意

一堆小孩有的朝左有的朝右,每次可以选择一对,或者多对面对面的小孩,让他们朝向相反,当没人任何小孩面对面时游戏结束,问你能否在 $k$ 轮内结束这个游戏并输出每一轮有多少个小孩左转,分别是几号。

题解

游戏结束时,小孩的终态一定为 $LLLLL...RRRR$, $n \leq 3000$,所以可以 $n^2$ 的统计最多需要 $sum$ 次(一次转一对)能让小孩全都转完,同时统计一共循环了 $cnt$ 轮(一次转多对)

当 $cnt \leq k$ && $k \leq sum$ 时能完成游戏。然后贪心的去分配这 $k$ 次取值即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> P;
const int MAXN = 3e6 + 5;
const int INF = 0x3f3f3f3f;
vector<int> ans[MAXN];
char s[30005];
void solve() {
    int n, k;
    //scanf("%d %d",&n, &k);
    //getchar();
    //scanf("%s", s);
    cin >> n >> k >> s;
    //cout << s << endl;
    int cnt = 1;
    while(1){
        bool flag = true;
        for(int i = 0;i < n-1;i++){
            if(s[i] == 'R' && s[i+1] == 'L'){
                ans[cnt].push_back(i+1);
                swap(s[i], s[i+1]);
                i++;
                flag = false;
            }
        }
        if(flag)
            break;
        cnt++;
    }
    cnt--;
    if(!cnt){
        printf("-1\n");
        return ;
    }
    int sum = 0;
    for(int i = 1;i <= cnt;i++)
        sum += ans[i].size();
    if(sum >= k && cnt <= k){
        int now = 1, num = 0, minn = cnt;
        while(minn < k){
            printf("1 %d\n",ans[now][num]);
            num++;
            if(num == ans[now].size()){
                num = 0;
                now++;
            } else {
                minn++;
            }
        }
        printf("%d ",ans[now].size() - num);
        for(int i = num;i < ans[now].size();i++)
            printf("%d ",ans[now][i]);
        puts("");
        now++;
        for(;now <= cnt;now++){
            printf("%d ",ans[now].size());
            for(int i = 0;i < ans[now].size();i++)
               printf("%d ",ans[now][i]);
            puts("");
        }
    } else {
        printf("-1\n");
    }
}

signed main() {
    //ios::sync_with_stdio(false);
    //cin.tie(NULL),cout.tie(NULL);
    int T;
    T = 1;
    //cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

待补

E, F