zhouwc 的博客

题解 P5639 【【CSGRound2】守序者的尊严】

官方题解

I 50pt

每一秒变化一次,就直接一次一次地改动监控的开关情况再走路

这样的时间复杂度 $O(n^2)$

你可以顺利的拿到50分

II 100pt

其实这个监控的变化只是为了你能够顺利到达终点而已。

就是一个模拟题,直接判断一下初始的监控开关状况即可。

连在一起的0和连在一起的1都可以1秒经过(因为1可以变成0,0可以还是0)。只要把连续的0或连续的1的段数加起来就完事了。

时间复杂度 $O(n)$

std

#include<bits/stdc++.h>
using namespace std;
int a[1000005],n;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int ans=1;
    for (int i=2;i<=n;i++)
        if (a[i]!=a[i-1]) ans++;
    printf("%d\n",ans);
}

2019-11-10 15:01:20 in 题解