Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

CF405B 题解

posted on 2022-02-20 14:07:34 | under 题解 |

题意

给你一些多米诺骨牌,现在将他们向左或向右推,并且保证,在每两个多米诺骨牌推向相同方向之间的某个地方,至少有一个多米诺骨牌被推向相反的方向

可以看此图理解样例一:

橙色的是站着的(共 $4$ 个)。

思路

有三种情况可能会让骨牌站着:

  1. 最左边有骨牌且没别的骨牌推它;

  2. 最右边有骨牌且没别的骨牌推它;

  3. 向右的力和向左的力间有奇数个骨牌。

注意一下,LR 也是骨牌,一样会倒。

按照上面的思路,可以写出如下代码:

#include<iostream>
using namespace std;
int cnt,n,ans,flag;
string s;
int main(){
    cin>>n>>s;
    for(int i=0;i<n;i++){
        if(flag){
            if(s[i]=='.') cnt++;
            else{
                ans+=(cnt%2);
                cnt=0,flag--;
            }
        }
        else{
            if(s[i]=='.') cnt++;
            else{
                if(s[i]!='L') ans+=cnt,flag++;
                cnt=0;
            }
        } 
    }
    cout<<ans;
}

然后就会发现样例 $2$ 都没过。

这时候就提醒了我们要特判,$flag$ 依旧为 $0$ 就说明向左或向右的力没有另一股力阻挡它。

加上如下代码:if(!flag) ans+=cnt;

即可 AC!

AC 记录(洛谷)

AC 记录(CF)