2020智算之道初赛第一场 - 高校组 B.开关

B.开关

题目链接-B.开关


解题思路

• 我们只需判断有几对相邻的开关状态不同即可，也就是判断该字符串由几段区间组成
• 比如1001该区间，有$cnt=2$cnt=2对相邻的开关状态不同，我们需要先翻转第一个开关0，等于翻转一次后跟后面的1合并成一个区间，翻转$2$2次后，该字符串中的所有字符一定全部相同
• 因为我们是要把开关全部关闭(即全为$0$0)，这时只需判断最后一个字符是否为$1$1即可，如果为$1$1说明需要整个区间在翻转一次(cnt++)，如果为$0$0则说明已经全部关闭，无需再翻转
• 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
string s;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int n,cnt=0;
	cin>>n>>s;
	for(int i=1;i<n;i++){
		if(s[i]!=s[i-1])
			cnt++;
	}
	if(s[n-1]=='1') cnt++;
	cout<<cnt<<endl;
	return 0;
}