10 solutions

  • 1
    @ 2025-1-18 15:53:42 
    //freopen("xx.in","r",stdin);
//freopen("xx.out","w",stdout);
#include<bits/stdc++.h>
#include<iostream> 
#include<iomanip>
#include<cmath>
#include<algorithm> 
#include<string> 
#include<cstdio>
#include<cstring> 
//#include<vector>
//#include<map>
//#include<stack>  
//#include<queue> 
//#include<set>
using namespace std; 
struct node{
	char v;
	int l,r;
};
node g[10010];
int ans=0; 
string k;
void dfs(int x,int y){
	if(x==y){//当只有一个时 
		if(k[x]=='0'){
			cout<<'B';
		}else{
			cout<<'I';
		}
		return ;
	}
	int mid=x+(y-x)/2;//对原长度进行等分 
	dfs(x,mid);//右子树递归 
	dfs(mid+1,y);//左子树递归 
	bool fxs=true,fws=true;
	for(int i=x;i<=y;i++){
		if(k[i]!='0')fxs=false;
		if(k[i]!='1')fws=false;
	}
	if(fxs==true){
		cout<<'B';
	}else if(fws==true){
		cout<<'I';
	}else{
		cout<<'F';
	}
}
int main(){
	int n;
	cin>>n;
	cin>>k;
	dfs(0,k.size()-1);
	return 0;
	
}
    • 1
      @ 2025-1-18 15:05:09

      解题思路

      1.建树。 按照题意是在递归过程中建立树，建树的方法实际上就是树的先序遍历。当本节点长度大于1时递归建立子树。

      2.输出。 而输出过程是对树的后序遍历，这里有个技巧就是可以和建树过程集成在一起。只需将代码放在递归调用之后就可以了。

      3.判断。 最后是判断当前节点的FBI树类型，可以用B保存全是‘0’的情况，如果遇到‘1’就将B置为0，用I保存全是‘1’的情况，如果遇到‘0’就将I置为0。最后判断B和I中的值，如果两个都为0则输出F。

      完整代码

      #include <bits/stdc++.h>
using namespace std;
string s;
int n;
void slove(int x, int y)
{
    if (y > x)
	{
        slove(x, (x + y) / 2);
        slove((x + y + 1) / 2, y);
    }    
    int B = 1, I = 1;
    for (int i = 0; i <= y - x; i++)
	{
        if (s[x + i] == '1') B = 0; 
		else if (s[x + i] == '0') I = 0;
    }
    if (B) cout << 'B';
	else if (I) cout << 'I';
	else cout << 'F';
}
int main()
{
    cin >> n >> s;
    slove(0, (1 << n) - 1);
    return 0;
}
      • 1
        @ 2023-12-29 18:45:44 
        #include <iostream>
#include <cmath>
using namespace std;
string a;
int dfs(int left,int right)
{
	if (left == right){
		if (a[left]=='0'){
			cout << "B";
			return 0;
		}
		if (a[left]=='1'){
			cout << "I";
			return 1;
		}
	}
	int flag1;
	int flag2;
	flag1=dfs(left,(right+left)/2);
	flag2=dfs((right+left)/2+1,right);
	
	if (flag1==1 && flag2==1){
		cout << "I";
		return 1;
	}
	if (flag1==0 && flag2==0){
		cout << "B";
		return 0;
	}
	if ((flag1!=flag2) || (flag1==-1 || flag2==-1)){
		cout << "F";
		return -1;
	}
}

int main(){
	int n;
	cin >> n;
	cin >> a;
	dfs(0,pow(2,n)-1);
}
        • 0
          @ 2025-1-22 7:25:36 
          #include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	string h;
    cin>>h;
	int jsq[n+1]={};
	int sum=0,num=0;
	char pwf[n+1][h.size()];
	char a[h.size()*2-1];
	for(int i=h.size();i>=1;i/=2){
		for(int j=0;j<i;j++){
			if(h.size()/i==1){
				if(h[j*h.size()/i]=='0')a[sum]='B';
				else a[sum]='I';
			}
			else{
			    if(a[sum-i*2+j]==a[sum-i*2+1+j]&&a[sum-i*2+j]=='B')a[sum]='B';
			    else if(a[sum-i*2+j]==a[sum-i*2+1+j]&&a[sum-i*2+j]=='I')a[sum]='I';
			    else a[sum]='F';
			}
			sum++; 
		}
		for(int s=0;s<i;s++)pwf[num][s]=a[sum-i+s];//把一维数组转化成二维数组
		num++;
	}
	for(int j=0;j<h.size();j++){
		cout<<pwf[0][j];
		jsq[0]++;
		for(int i=0;jsq[i]%2==0;i++)cout<<pwf[i+1][jsq[i+1]++];
	}//后序遍历输出
	return 0;
}
//循环写法第一人
          • 0
            @ 2024-7-14 22:01:32 
            #include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s="";
string C(string x){
	bool is1,is0;
	is1=is0=0;
	for(int i=0;i<x.size();i++){
		if(x[i]=='1') is1=1;
		if(x[i]=='0') is0=1;
	}
	if(is1&&is0) return "F";
	if(is0&&!is1) return "B";
	if(is1&&!is0) return "I";
	return "";
}//判断字符类型 
void dfs(string aa,int len,string type){
	if(len==1){
		cout<<C(aa);
		//特殊情况 
		return;
	}
	string xx="";//作为临时变量存字符串 
	
	//左边 
	for(int i=0;i<len/2;i++) xx+=aa[i];
	if(len)dfs(xx,len/2,C(xx));
	
	
	xx="";//重置xx 
	
	//右边 
	for(int i=len/2;i<aa.size();i++) xx+=aa[i];
	if(len)dfs(xx,len/2,C(xx));
	
	
	cout<<type;
	//因为是后序所以输出放最后 
}
signed main(){
	cin>>n;
	cin>>s;
	dfs(s,pow(2,n),"");
	//递归 
	if(s.size()>1) cout<<"F";
	//特判输出F 
	return 0;
}

            这道题的难点在于两个特判

            容易漏的是第二个因为基本上不会有一个字符的测试数据

            • 0
              @ 2024-4-25 13:44:15

              题意:

              输入一个01串,为s

              将s分两半 , 一个为l , 一个为r

              如果l==r,0返回"B",1返回"I"

              如果l与r全为0就说明s的节点为"B"

              如果l与r全为1就说明s的节点为"I"

              如果l与r有1有0就说明s的节点为"F"

              判断完后,再递归l和r(重复以上操作,直到l和r重合,在判断是"B"还是"I")

              最后输出这个树的后序遍历

              模拟:

              输入 : 10001011

              输出 : IBFBBBFIBFIIIFF

              模拟过程:
    10001011
   /        \
 1000      1011 --- F
 /  \      /  \
 10 00     10 11 --- F F
/ \ / \   / \ / \
1 0 0 0   1 0 1 1 --- F B F I
| | | |   | | | |
1 0 0 0   1 0 1 1 --- I B B B I B I I
所构成的树:
       F
      / \
     F   F
    / \ / \
   F  B F  I
 //  /| |\  \\
I B B B I B I I
后序遍历:
IBFBBBFIBFIIIFF

              代码:

              #include<iostream>
using namespace std;
string s;//01串
void f(int l,int r)
{
	if(l==r)//为一个数字时
	{
		if(s[l]=='0')//判断是0还是1
		{
			cout<<'B';
		}
		else
		{
			cout<<'I';
		}
		return;//返回
	}
	int m=l+(r-l)/2;//l , r 的中间
	f(l,m);//左边
	f(m+1,r);//右边
	bool f1=false,f2=false;//标记是否出现过0,1
	for(int i=l;i<=r;i++)
	{
		if(s[i]=='0')//出现过0
		{
			f1=true;
		}
		if(s[i]=='1')//出现过1
		{
			f2=true;
		}
	}
	if(f1 && f2)//有0也有1时
	{
		cout<<'F';
	}
	else if(f1 && (!f2))//全0时
	{
		cout<<'B';
	}
	else
	{
		cout<<'I';//全1时
	}
}
int main()
{
	int n;//其实n根本没有用
	cin>>n;//输入
	cin>>s;//输入
	f(0,s.size()-1);//FBI树
	return 0;//完结散花
}
            • 0
              @ 2023-12-29 13:05:57

              题意

              输入一个长度为 2n2^n 的 01 串，全 1 串叫 I 串，全 0 串叫 B 串，又有 0 又有 1 的串叫 F 串

              11 为 I 串

              00 为 B 串

              10 为 F 串

              子串里有 F 串的也是 F 串

              思路

              其实就是二叉树，如果子树全是 1 就是 I 串，全是 0 就是 B 串，两个子树不同就是 F 串

              然后后序输出这个树

              代码

              #include <bits/stdc++.h>
using namespace std;
char a[1030];
int f(int l,int r){
	if (r > l){	// 如果串还可以二分
		int a = f(l,(l + r + 1) / 2 - 1);	// 左半部分
		int b = f((l + r + 1) / 2,r);	// 右半部分
		if (a == 1 && b == 1){	// 如果子树都是 1（I 串）
			printf("I");
			return 1;
		}else if (a == 0 && b == 0){	// 如果子树都是 0（B 串）
			printf("B");
			return 0;
		}else{	// 如果子树又有 1 又有 0（F 串）
			printf("F");
			return 2;
		}
	}
	int B = 1,I = 1;
	for (int i = 0;i <= r - l;i++){
		if (a[l + i] == '1')	B = 0;
		else	I = 0;
	}
	if (B){
		printf("B");
		return 0;
	}else if (I){
		printf("I");
		return 1;
	}else{
		printf("F");
		return 2;
	}
}
int main(int argc, char **argv){
	int n;
	cin >> n >> a;
	f(0,(1 << n) - 1);
	return 0;
}
              • -2
                @ 2024-1-22 13:24:48 
                #include<iostraem>
using namespeca std;
stirng fbi;
int main(){
	{int n;cin>>n;}//没有JB用
	cin>>fbi;
	void f(int,int);
	f(0,fbi.size()-1);
}
void f(int x,int y){
	bool I=0,B=0;//I为有没有1，B为有没有0
	for(int i=x;i<=y;i++){
		if(fbi[i]=='1')//有1
		I=1;
		if(fbi[i]=='0')//有0
		B=1;
	}
	if(x==y){//叶节点
		if(I)
		cout<<'I';
		else
		cout<<'B';
		return;
	}
	f(x,(x+y)/2);
	f((x+y)/2+1,y);//递归
	if(I&&B){//有1又有0
		cout<<'F';
		retrun;
	}
	if(I)
	cout<<'I';
	else
	cout<<'B';
} 
//我在代码里留了些小小的拼写错误，谨防抄袭
                • -2
                  @ 2023-12-31 14:51:30

                  题意:

                  输入一个01串,为s

                  将s分两半 , 一个为l , 一个为r

                  如果l==r,0返回"B",1返回"I"

                  如果l与r全为0就说明s的节点为"B"

                  如果l与r全为1就说明s的节点为"I"

                  如果l与r有1有0就说明s的节点为"F"

                  判断完后,再递归l和r(重复以上操作,直到l和r重合,在判断是"B"还是"I")

                  最后输出这个树的后序遍历

                  模拟:

                  输入 : 10001011

                  输出 : IBFBBBFIBFIIIFF

                  模拟过程:
    10001011
   /        \
 1000      1011 --- F
 /  \      /  \
 10 00     10 11 --- F F
/ \ / \   / \ / \
1 0 0 0   1 0 1 1 --- F B F I
| | | |   | | | |
1 0 0 0   1 0 1 1 --- I B B B I B I I
所构成的树:
       F
      / \
     F   F
    / \ / \
   F  B F  I
 //  /| |\  \\
I B B B I B I I
后序遍历:
IBFBBBFIBFIIIFF

                  代码:

                  #include<iostream>
using namespace std;
string s;//01串
void f(int l,int r)
{
	if(l==r)//为一个数字时
	{
		if(s[l]=='0')//判断是0还是1
		{
			cout<<'B';
		}
		else
		{
			cout<<'I';
		}
		return;//返回
	}
	int m=l+(r-l)/2;//l , r 的中间
	f(l,m);//左边
	f(m+1,r);//右边
	bool f1=false,f2=false;//标记是否出现过0,1
	for(int i=l;i<=r;i++)
	{
		if(s[i]=='0')//出现过0
		{
			f1=true;
		}
		if(s[i]=='1')//出现过1
		{
			f2=true;
		}
	}
	if(f1 && f2)//有0也有1时
	{
		cout<<'F';
	}
	else if(f1 && (!f2))//全0时
	{
		cout<<'B';
	}
	else
	{
		cout<<'I';//全1时
	}
}
int main()
{
	int n;//其实n根本没有用
	cin>>n;//输入
	cin>>s;//输入
	f(0,s.size()-1);//FBI树
	return 0;//完结散花
}
                • -3
                  @ 2025-1-20 23:10:21

                  如果你看到这个东西，说明这道题茶叶写了讲解，在他的blog

                  校内茶叶blog

                  校外茶叶blog

                  • 1

                  FBI树(fbi)

                  Information

                  ID
                  850
                  Time
                  1000ms
                  Memory
                  256MiB
                  Difficulty
                  6
                  Tags
                  # Submissions
                  96
                  Accepted
                  28
                  Uploaded By
                  1. About
                  2. Contact Us
                  3. Privacy
                  4. Terms of Service
                  5. Copyright Complaint
                  6. Language
                  7. Legacy mode
                  8. Theme
                  2. 粤ICP备2022044963号-1
                  3. Worker 0, 30ms
                  4. Powered by Hydro v4.13.3 Community