AtCoder Beginner Contest 136

前言

比赛地址

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

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

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

A

题意： 有两个瓶子，1号瓶有A升水，总共可以装B升，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; }

E

F 题意地址

转载于:https://www.cnblogs.com/BaseAI/p/11301648.html