SP56 DYZIO - Dyzio 题解

题意简述

题目给出一个长为 $n$ 的类似 指令集 的字符串，遇到 $1$ 就将一个序列分为两段。遇到 $0$ 就不做任何处理。

解题思路

使用一个递归函数，每次读入指令。 当指令为 $1$ 时，继续递归。否则停止这一边的递归。

每次分为两半时都要递归左边和右边。

代码

#include<bits/stdc++.h>
using namespace std;
int tmp,ans,minlen=INT_MAX,step;
int read() {
	int x=0; char c;
	while(1) {
		c=getchar();
		if(c=='\n') return x;
		x=10*x+c-'0';
	}
}
void dfs(int len) {
	if(len>minlen) {
		minlen=len;
		ans=step;
	}
	char order=getchar();
	if(order=='0') return;
	else {
		step++;
		dfs(len+1);
		dfs(len+1);
	}
}
int main() {
	for(int i=1;i<=10;i++) {
		ans=0; minlen=-1; step=0;
		tmp=read(); dfs(0);
		getchar();
		printf("%d\n",ans);
	}
	return 0;
}
//code by TheCedar