前言
比赛地址
这是我第一次发比赛的完整题解，留个纪念吧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;
}
京公网安备 11010502036488号