第 30 题

#include <iostream>
using namespace std;

const int inf =0x3f3f3f3,N=4e5+5;
struct edge {
	int  to,nt ;
}E[N<<1];
int cnt, n,m,rt,MX;
int H[N],sz[N],mxs[N];
void add_edge(int u, int v) {
	E[++cnt]=(edge) {v,H[u]};
	H[u]=cnt;
}
void dfs(int u, int fa) {
	sz[u]=1;
	for (int e=H[u]; e; e=E[e].nt) {
		int v=E[e].to;
		if (v==fa) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		mxs[u]=max(mxs[u],sz[v]);
	}
	mxs[u] =max(mxs[u],n-sz[u]);
	if (mxs[u]<mxs[rt])rt=u;
	if (mxs[u]==mxs[rt] &&u<rt)rt=u;
}
int main() {
	cin>>n,
	    rt =cnt= 0;
	for (int i=1; i<=n; i++) {
		int u,v;
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	mxs[0] = inf ;
	dfs(1,0);
	cout<<rt<<' '<<mxs[rt]<<'\n';
	return 0;
}

第 30 题 第33,34行只需保留任意一行也不会影响程序的正确性。()

第 31 题 第37行函数调用dfs(x,y)，只需保证1≤x≤n,y≤0即可。()

第 32 题 第32行输入若有重复(重边)，不影响输出结果的正确性。()

第 33 题 程序运行结束时可能存在正整数i(i≤n)使sz[i]等于mxs[i]。()

第 34 题 n=6,二元组(u,v)各个值分别是{(1，3),(6.3),(2,6),(5,6),(3,4)},则输出是()。

第 35 题 若n=1000，则程序运行后mxs[]数组中除初始值 inf 外，最大值是( )。

三、编程题（每题 25 分，共 50 分）

第 37 题 (翻硬币) 一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们整体一起翻面后放回原处(如101111前5个翻面结果是000101)，再取3枚，取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，m为1时，翻两次即可；m 为4时﹐翻11次；m为9时，翻80 次。 【输入】 仅有的一个数字是这摞硬币的枚数m(0 #include <iostream> using namespace std; int solve(int m); int main() { freopen("demo.out","w", stdout); int m; do { scanf("%d",&m); if(m>0 && m<1000) printf("%d\n",___(1)___); } while (m>0 && m< 1000); return 0; } int solve(int m) { int i,t,s;//翻转的次数 int flag; if(m==1) s=___(2)___; else { d=2*m+1; //确定硬币是经过偶数次翻转还是奇数次翻转 t= 2; //表示一个COIN必须翻转偶数次，才能从正面继续翻到正面 i=1;//翻转的轮数，每轮为从1翻转到m flag=0;//退出循环标志，翻转完成标志 do { if(t==1) { s=___(3)___; flag = 1; } else if(___(4)___) { s=i*m-1; flag=1; } else { t=___(5)___; } i=i+1; } while(!flag); } return s; }

第 37 题 ①处应填( )

第 38 题 ②处应填( )

第 39 题 ③处应填( )

第 40 题 ④处应填( )

第 41 题 ⑤处应填( )

第 43 题 (FBZ串问题) 已知一个由0,1字符组成的长度为2^n的字符串。请按以下规则分解为FBZ串: ·若其中字符全为1，则称其为B串: ·若其中字符全为0，则称其为Z串; ·若不全为0，也不全为1,则称F串。 若此串为F串,则应将此串分解为2个长为2^(i-1)的子串。对分解后的子串，仍按以上规则继续分解直到全部为B串或为Z串为止。例如n=3时,给出0-1串为“10111001” 最后输出:FFFBZBFFBZFZB。给定一个0-1串，分解成FBZ串。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int n= 8;
char str1[2*n][n];
char str2[40]=" ";
int main() {
	int s1,s2,x,s,t;
	s1=s2=x= 0;
	gets(str1[0]);
	while(___(1)___) {
		s=t=0;
		for (int i = 0; i< n; i++) {
			if (str1[s2][i]=='1')
				s++;
			if (str1[s2][i]=='0')
				t++;
		}
		if(___(2)___)
			str2[x++]='B';
		else if(___(3)___)
			str2[x++]='Z';
		else {
			str2[x++]='F';
			int j=(s+t)>>1;
			for (int k=n*2-2; k>=___(4)___; k--)
				for (int i=0; i<n; i++)
					str1[k+2][i]=str1[k][i];
			s1 += 2;
			for (int i=0; i<j; i++) {
				str1[s2+1][i]=str1[s2][i];
				str1[s2+2][i]=___(5)___;
			}
			for (int i=___(6)___; ___(7)___; i++) {
				str1[s2+1][i]=' ';
				str1[s2+2][i]=' ';
			}
		}
		s2++;
	}
	puts(str2);
	return 0;
}

第 43 题 ⑴处应填( )

第 44 题 ⑵处应填( )

第 45 题 ⑶处应填( )

第 46 题 ⑷处应填( )

第 47 题 ⑸处应填( )

第 48 题 ⑹处应填( )

第 49 题 ⑺处应填( )