AtCoder Beginner Contest 136

前言

比赛地址

这是我第一次发比赛的完整题解，留个纪念吧QwQ。

这场比赛A,B,C都比较水，D题想了想，E,F有点难（~~这是本蒟蒻的感受，有些大佬轻松AK了~~）

最后得分 100 + 200 + 300 = 600 ，rank

A

题意： 有两个瓶子，1号瓶有A升水，总共可以***升，2号瓶有C升水，尽可能多的把2号瓶的水移到1号瓶，求2号瓶最后有多少水。

签到题，小学数学题，还剩C-(B-A),如果<0,则输出0。

B

题意： 给你一个数\(n\)，让你求出所有在\(1\)~\(n\)之间的位数为奇数个的数的数量

题目分析 跟 <数字统计> 差不多，n的范围小， 暴力枚举即可。

C

题意

题目分析

可以发现我们能尽量让前面的元素小一点，才能使后面的元素尽可能变成不下降序列。如果某一位置不能满足不下降序列了，后面也就不能了。

所以果断贪心，如果该位置能-1就减，不能就不变，如果还是不满足，就输出No，反之如果最后一个都能满足，则输出Yes

D

题意给出一个长度为 \(n\) 的字符串 \(S\)，\(S\) 只由‘\(L\)’和‘\(R\)’构成。起初\(1\)~\(n\)每个位置有一个人，如果当前位置是‘L’，这个位置的所有人就向左走一步；反之，如果这个位置是‘R’，就向右走一步。所有人按照这个规则走 \(10^{100}\) 步后，求每个广场的人数。

题目分析

乍看不好做，~~但是ygt大佬还是分分钟切了，还说是水题~~。如果直接暴力求 \(10^{100}\) 次，就是天河一号来了也是呵呵呵。但是只要细心一想，\(10^{100}\)其实是告诉你走无穷多次，并且是偶数次（这个后面有用），说明是有规律可循的。

看一下数据 \(1<=N<=10^5\) 再推推数据，突然发现如果‘\(R\)’‘\(L\)’并在一起就成为了死循环 ,而题目一定会满足有‘\(R\)’，‘\(L\)’并在一起，因为中间会有一些，而且两边保证 \(1\) 一定是‘\(R\)’，\(n\) 一定是‘\(L\)’。

恍然大悟！

我们只要解决从某个位置到死循环的距离，判断距离的奇偶性，就知道这个人最后落在死循环‘\(R\)’‘\(L\)’的哪个位置。

对于一个点，如果他的位置是‘\(L\)’，它就可以一直向左走到‘\(R\)’停止。如‘\(RL\)’，‘\(RLLL\)’

反之，如果他的位置是‘\(R\)’，它就可以一直向右走到‘\(L\)’停止。如‘\(RL\)’，‘\(RRRL\)’

code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN = 1e5 + 7;
char s[MAXN];
int ans[2][MAXN],sum[MAXN];
int main()
{
    cin>>s+1;
    int n = strlen(s+1);
    for(int i=1;i<=n;++i) {
        if(s[i] == 'L')
            ans[0][i] = ans[0][i-1];
        else ans[0][i] = i;
    }
    for(int i=n;i>=1;--i) {
        if(s[i] == 'R')
            ans[1][i] = ans[1][i+1];
        else ans[1][i] = i;
    }
    int res;
    for(int i=1;i<=n;++i) {
        if(s[i] == 'L') {
            res = i - ans[0][i];
            if(res&1) {
                sum[ans[0][i]+1]++;
            } else sum[ans[0][i]]++;    //(res&1)判断奇偶
        } else {
            res = ans[1][i] - i;
            if(res&1) {
                sum[ans[1][i]-1]++;
            } else sum[ans[1][i]]++;
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d ",sum[i]);
    return 0;
}