AtCoder Beginner Contest 136 A

目录

• A-Transfer
• B - Uneven Numbers
• C - Build Stairs
• D - Gathering Children

点击标题可传送

A-Transfer

输出c -= (a - b)，如果(cle0)输出(0)

B - Uneven Numbers

给你一个(n)，输出(1dots n)中位数为奇数的数字有几个

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n;
int main() {
    char t[200000];
    scanf("%d", &n);
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        sprintf(t, "%d", i);
        if(strlen(t) & 1) cnt ++;
    }
    
    cout << cnt << '
';
    
    return 0;
}

C - Build Stairs

给你(N)个方块，它们各自的高度为(H_i)。对于这些方块，你必须对它们做一次以下操作：

• 让方块的高度减(1)
• 什么也不做

将排序后的方块存到一个数组中，然后对排序后的和原先的作差，若差值大于(1)则输出No，否则输出Yes

D - Gathering Children

一道模拟+思维的题目，经过推导可得到一些规律：

• 小孩最终会在RL这一组位置
• 当(r(L,overbrace {Rdots ,R}^r,L)+l(R,overbrace{L,dots ,L}^l,R))为偶数时，(r = l = frac{l+r}{2}).
• 当(r>l)时，如果(r)为偶数，则(r=lfloor frac{l+r}{2} floor ,l=lceil frac{l+r}{2} ceil)；如果(r)为奇数，则(r=lceil frac{l+r}{2} ceil,l=lfloor frac{l+r}{2} floor).
• 当(l>r)时，如果(l)为奇数，则(l=lfloor frac{l+r}{2} floor,r=lceil frac{l+r}{2} ceil)；如果(l)为偶数，则(l=lceil frac{l+r}{2} ceil,r=lfloor frac{l+r}{2} floor).

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 3;
char s[N];
int a[N], l, r;

int main() {
    scanf("%s", s);
    int n = strlen(s);
    
    for(int i = 0; i < n; i++) {
        if(s[i] == 'R') r++;
        else a[i] = r, r = 0;
    }
    
    for(int i = n - 1; i >= 0; i--) {
        if(s[i] == 'L') l++;
        else a[i] = l, l = 0;
    }
    // 经过上述两个for循环后，字符串中‘R’对应的是l的值，'L'对应的是r的值，顺序别搞错了
    
    for(int i = 1; i < n; i++) {
        if(s[i - 1] == 'R' && s[i] == 'L') {
            int sum = a[i - 1] + a[i];
            if(sum & 1) {
                //当r > l时
                if(a[i - 1] < a[i]) { 
                    if(a[i] & 1) {
                        a[i - 1] = sum - sum / 2;
                        a[i] = sum / 2;
                    } else {
                        a[i - 1] = sum / 2;
                        a[i] = sum - sum / 2;
                    }
                  //当l > r时
                } else if(a[i - 1] > a[i]){
                    if(a[i - 1] & 1) {
                        a[i - 1] = sum / 2;
                        a[i] = sum - sum / 2;
                    } else {
                        a[i - 1] = sum - sum / 2;
                        a[i] = sum / 2;
                    }
                }
            } else {
                a[i - 1] = a[i] = sum >> 1;
            }
        }
    }
    
    for(int i = 0; i < n; i++) printf("%d ", a[i]); puts("");
     
    return 0;
}