题解：P11068 「QMSOI R1」 转转楼梯

· · 题解

思路

分类讨论的数学题。

我们选择当前位置是一的情况进行讨论。

我们发现一个性质，下一轮前 n 个转转楼梯的状态是上一轮第二个到第 n+1 的状态，且若干次后，转转楼梯一定会全部变成零。

所以，分如下情况讨论。

当前位置的左边是一且右边是零的时候，此时只需要转动一次。总共转动 i 次。

当前位置左右两边都是零的时候，此时需要转动两次。总共需要转动 2\times i-1 次。

当前位置左边为零右边为一的时候，此时需要转动 i-1 次。

然而我们只执行了 k 轮。

所以所有的的答案记录都要让 k 和 i 取最小值进行操作。

最后，别忘赋初值。

代码

#include<bits/stdc++.h>
#define int long long//一定开long long！！！！！ 
using namespace std;
int a[2000005];
signed main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }//输入 
    int ans=0;//答案记录变量 
    a[0]=1;//赋初值 
    for(int i=1;i<=n;i++){
        if(a[i]){
            if(a[i-1]&&!a[i+1]){//第一种情况 
                ans+=min(m,i);//和轮数取最小值 
            }
            if(!a[i-1]&&!a[i+1]){//第二种情况 
                int s=min(m,i);
                if(s==i){
                    ans+=2*(s-1)+1;
                }
                else{
                    ans+=2*s;
                }
            }
            if(!a[i-1]&&a[i+1]){//第三种情况 
                int s=min(m,i);
                if(s==i){
                    ans+=s-1;
                }
                else{
                    ans+=s;
                }
            }
        }
    }
    cout<<ans+m*n;//输出结果 
    return 0;
}