PAT (Advanced Level) Practice 题解代码 - II （1101-1167）

1001-1167（持续更新）

#include
using namespace std;
const int maxn = 1e5+5;
int minx[maxn] = {0};
int maxx[maxn] = {0};
int a[maxn];
const int maxnum = INT_MAX;
int b[maxn];
int main(){
	int N;
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> a[i];
	}
	minx[N+1] = maxnum;
	maxx[N+1] = maxnum;
	for(int i=1;i<=N;i++){
		maxx[i] = max(maxx[i-1],a[i]);
	}
	for(int i=N;i>=1;i--){
		minx[i] = min(minx[i+1],a[i]);
	}
	int cnt = 0;
	for(int i=1;i<=N;i++){
		if(a[i]>maxx[i-1] && a[i] 
1102 Invert a Binary Tree (25 分) 
#include
using namespace std;
struct node{
	int data;
	int lchild;
	int rchild;
};
node n[105];

int index_num = 0;
int newnode(int v){
	n[index_num].data = v;
	n[index_num].lchild = -1;
	n[index_num].rchild = -1;
	return index_num++;
}

bool hashT[105];
int cnt1 = 0;
int cnt2 = 0;
void Level(int root){
	queue q;
	q.push(root);
	while(!q.empty()){
		int f = q.front();
		if(cnt1==0){
			printf("%d",f);
		}else{
			printf(" %d",f);
		}
		cnt1++;
		q.pop();
		if(n[f].lchild!=-1){
			q.push(n[f].lchild);
		}
		if(n[f].rchild!=-1){
			q.push(n[f].rchild);
		}
	}
	printf("n");
}
void InOrder(int root){
	if(root==-1){
		return;
	}
	InOrder(n[root].lchild);
	if(cnt2==0){
		printf("%d",root);
	}else{
		printf(" %d",root);
	}
	cnt2++;
	InOrder(n[root].rchild);
}
int main(){
	int N;
	cin >> N;
	for(int i=0;i> s1 >> s2;
		int now = newnode(i);
		if(s1[0]!='-'){
			n[now].rchild = s1[0]-'0';
			hashT[s1[0]-'0'] = true;
		}
		if(s2[0]!='-'){
			n[now].lchild = s2[0] -'0';
			hashT[s2[0]-'0'] = true;
		}
	}
	int root;
	for(int i=0;i 
1103 Integer Factorization (30 分) 
#include
using namespace std;
int a[1005];
int muti[1005];
int N,K,P;
int ans = -1;
int ans_a[1005];

void dfs(int depth,int index,int sum,int factor_sum){
	if(depth==K && sum==N){
		if(factor_sum>ans){
			ans = factor_sum;
			for(int i=0;iN || depth>K){
		return;
	}
	
	if(index>=1){
		a[depth] = index;
		dfs(depth+1,index,sum+muti[index],factor_sum+index);
		a[depth] = 0;
		dfs(depth+0,index-1,sum+0,factor_sum+0);
	}
		
}

int main(){
	cin >> N >> K >> P;
	
	int index_start;
	for(int i=0;;i++){
		int tmp = 1;
		for(int j=1;j<=P;j++){
			tmp = tmp * i;
		}
		if(tmp>N){
			index_start = i-1;
			break;
		}else{
			muti[i] = tmp;
		}
	}
	
	dfs(0,index_start,0,0);
	
	if(ans==-1){
		printf("Impossiblen");
	}else{
		printf("%d = ",N);
		for(int i=0;i 
1104 Sum of Number Segments (20 分) 
#include
using namespace std;

int main(){
	double a;
	int N;
	scanf("%d",&N);
	long long result = 0;
	for(int i=1;i<=N;i++){
		scanf("%lf",&a);
		result = result + ((long long)(1000.0*a))*(i) * (N-i+1);
	}
	double r = result*1.0/1000.0;
	printf("%.2lf",r);
	
	return 0;
}
 
1105 Spiral Matrix (25 分) 
#include
using namespace std;
int N;
int m,n;
int b[10005];
int main(){
	cin >> N;
	for(int i=(ceil)(sqrt(N));i<=N;i++){
		if(N%i==0){
			m = i;
			n = N/i;
			break;
		}
	} 
	for(int i=0;i> b[i];
	}
	sort(b,b+N);
	int a[m+1][n+1];
	memset(a,0,sizeof(a));
	int i = 0;
	int j = 0;
	while(N){
		while(j=0 && !a[i][j]){
			a[i][j--] = b[--N];
		}
		j++;
		i--;
		while(i>=0 && !a[i][j]){
			a[i--][j] = b[--N];
		}
		i++;
		j++;
	}
	for(int i=0;i 
1106 Lowest Price in Supply Chain (25 分) 
#include
using namespace std;
const int maxn = 1e5+5;
vector child[maxn];
int N;
double P;
double r;
bool hashT[maxn];
int mindepth = INT_MAX;
int minnum = 0;
void dfs(int depth,int root){
	if(child[root].size()==0){
		if(depth> N >> P >> r;
	for(int i=0;i 
1107 Social Clusters (30 分) 
#include
using namespace std;
int father[1005];
int vis[1005];
int course[1005];

int findfather(int x){
	if(x == father[x]){
		return x;
	}else{
		int F = findfather(father[x]);
		father[x] = F;
		return F;
	}
}

void Union(int a,int b){
	int fa = findfather(a);
	int fb = findfather(b);
	if(fa!=fb){
		father[fa] = fb;
	}
}

vector v;

int main(){
	int N;
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		father[i] = i;
	}
	for(int i=1;i<=N;i++){
		int k;
		scanf("%d:",&k);
		for(int j=0;j 
1108 Finding Average (20 分) 
#include
using namespace std;
int main(){
	int N;
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	int count = 0;
	double res = 0.0;
	for(int i=0;i1000){
			cout << "ERROR: "<< str1 << " is not a legal number" << endl;
		}else{
			count ++;
			res += num;
		}
	}
	
	if(count==1){
		printf("The average of 1 number is %.2lfn",res);
	}else if(count==0){
		cout << "The average of 0 numbers is Undefined" << endl;
	}else{
		res = res / count;
		printf("The average of %d numbers is %.2lfn",count,res);
	}
	return 0;
} 

 
1109 Group Photo (25 分) 
#include
using namespace std;
typedef struct photo{
	string name;
	int height;
}photo;
const int maxn = 1e4+5;
photo p[maxn];
int a[maxn];

int N,K;
bool cmp(photo p1,photo p2){
	if(p1.height>p2.height){
		return true;
	}else if(p1.height==p2.height){
		if(p1.name> N >> K;
	int num = (int)(N/K);
	for(int i=0;i> p[i].name >> p[i].height;
	}
	sort(p,p+N,cmp);
	
	int start = (N - num*K) + num;
	for(int i=0;i 
1110 Complete Binary Tree (25 分) 
#include
using namespace std;
int N;
struct node{
	int lchild = -1;
	int rchild = -1; 
};
node tree[105];
bool hashT[105];
int cnt = 0;

int LevelOrder(int root){
	queue q;
	q.push(root);
	int last;
	while(!q.empty()){
		int f = q.front();
		q.pop();
		last = f;
		cnt++;
		if(cnt*2+1<=N){
			if(tree[f].lchild==-1 || tree[f].rchild==-1){
				return -1;
			}
		}else if(cnt*2<=N){
			if(tree[f].lchild==-1 || tree[f].rchild!=-1){
				return -1;
			}
		}else{
			if(tree[f].lchild!=-1 || tree[f].rchild!=-1){
				return -1;
			}
		}
		if(tree[f].lchild!=-1){
			q.push(tree[f].lchild);
		}
		if(tree[f].rchild!=-1){
			q.push(tree[f].rchild);
		}
	}
	if(cnt==N){
		return last;
	}else{
		return -1;
	}
}

int main(){
	cin >> N;
	for(int i=0;i> s;
		if(s[0]>='0' && s[0]<='9'){
			int t = 0;
			for(int i=0;i> s;
		if(s[0]>='0' && s[0]<='9'){
			int t = 0;
			for(int i=0;i 
1160 Forever (20 分) 
#include
using namespace std;

const int maxn = 1e5+5;
struct node{
	int n;
	int A;
};
node store[maxn];

bool cmp(node n1,node n2){
	if(n1.n!=n2.n){
		return n1.n < n2.n;
	}else{
		return n1.A < n2.A;
	}
}

int K,m;
int gcd(int a,int b){
    if(b>a){
        swap(a,b);
    }
	if(b==0){
		return a;
	}else{
		return gcd(b,a%b);
	}
}

bool p[105]={1,1,0};

void init(){
	for(int i=2;i<100;i++){
		if(!p[i]){
			for(int j=2*i;j<100;j+=i){
				p[j] = 1;
			}
		}
	}
	p[2] = 1;
}

int main(){
	init();
	int N;
	scanf("%d",&N);
	for(int i=0;i3 && !p[g]){
					cnt++;
					store[count].n = sum2;
					store[count].A = num1;
					count++;
					//printf("%d %dn",sum2,num1);
				}
			}
		}
		if(!cnt){
			printf("No Solutionn");
		}else{
			for(int i=0;i 
1161 Merging linked Lists (25 分) 
#include
using namespace std;
const int maxn = 1e5+5;
map next1;
map value1;
int a_value[maxn];
int a_add[maxn];
int b_value[maxn];
int b_add[maxn];
int change[maxn];
int cnt1 = 0;
int cnt2 = 0;

int main(){
	int start_s1,start_s2;
	int N;
	scanf("%d%d%d",&start_s1,&start_s2,&N);
	for(int i=0;icnt2){
		reverse(b_add,b_add+cnt2);
		reverse(b_value,b_value+cnt2);
	}else{
		reverse(a_add,a_add+cnt1);
		reverse(a_value,a_value+cnt1);
		for(int i=0;i 
1167 Cartesian Tree (30 分) 
#include
using namespace std;
int a[35];

struct node{
	int data;
	node* lchild;
	node* rchild;
};
node* root = NULL;
node* newnode(int v){
	node* Node = new node;
	Node->data = v;
	Node->lchild = NULL;
	Node->rchild = NULL;
	return Node;
}
node* Create(int inL,int inR){
	if(inL>inR){
		return NULL;
	}
	int k = inL;
	for(int i=inL;i<=inR;i++){
		if(a[i]lchild = Create(inL,k-1);
	root->rchild = Create(k+1,inR);
	return root;
}

void levelorder(node* root){
	queue q;
	q.push(root);
	int cnt = 0;
	while(!q.empty()){
		node* f= q.front();
		q.pop();
		cnt++;
		if(cnt==1){
			printf("%d",f->data);
		}else{
			printf(" %d",f->data);
		}
		if(f->lchild){
			q.push(f->lchild);
		}
		if(f->rchild){
			q.push(f->rchild);
		}
	} 
	printf("n");
}
int main(){
	int N;
	cin >> N;
	for(int i=0;i> a[i];
	}
	node* root = NULL;
	root = Create(0,N-1);
	levelorder(root);
	return 0;
}