CSP-J2022题解

T1 乘方

思路

非常简单，直接for循环上就行了。为什么不会炸呢？因为就算a=1e9，乘两次也炸不了long long。

代码

#include<cstdio>
long long a,n,ans=1;
int main(){
	scanf("%lld%lld",&a,&n);
	for(int i=1;i<=n;i++){
		ans*=a;
		if(ans>1000000000){
			puts("-1");
			return 0;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

T2 解密

思路

比较困难（我不会解一元二次方程），需要推一下式子。

设\(m\)为\(n-ed+2\)：

解方程即可：

带式子算就可以了。

代码

#include<cstdio>
#include<cmath>
void solve(){
	long long n,e,d,m,p,q;
	scanf("%lld%lld%lld",&n,&e,&d);
	m=n-e*d+2,p=sqrt(m*m-4*n);
	if(p*p==m*m-4*n){
		p=(p+m)/2,q=m-p;
		if(p>q)p^=q^=p^=q;
		printf("%lld %lld\n",p,q);
	}else puts("NO");
}
int main(){
	int q;
	scanf("%d",&q);
	while(q--)solve();
	return 0;
}

T3 逻辑表达式

思路

思路较简单，代码较难写。

先通过题目给出的表达式构建出表达式树，然后通过dfs的方式找出短路现象。

遍历到的节点，先遍历左子树，然后再根据题意判断是否为短路，如果否再遍历右子树，如果是就返回。

代码

#include<bits/stdc++.h>
using namespace std;
char s[1000005],h[1000005];
char stk[1000005];
int stk2[1000005];
int top,len,cnt,root,ans1,ans2;
struct node{int data,ls,rs,fa,val;};
node t[1000005];
void dfs(int x){
	if(x==0)return;
	if(t[x].ls==0&&t[x].rs==0){
		t[x].val=t[x].data;
		return;
	}
	dfs(t[x].ls);
	if(t[x].data==2&&t[t[x].ls].val==0){
		ans1++;
		t[x].val=0;
		return;
	}
 	if(t[x].data==3&&t[t[x].ls].val==1){
		ans2++;
		t[x].val=1;
		return;
	}
	dfs(t[x].rs);
	if(t[x].data==2)t[x].val=t[t[x].ls].val&t[t[x].rs].val;
	if(t[x].data==3)t[x].val=t[t[x].ls].val|t[t[x].rs].val;
}
int main(){
	scanf("%s",s+1);
	len=strlen(s+1);
	for(int i=1;i<=len;i++){
		if(s[i]=='(')stk[++top]='(';
		else if(s[i]=='|'){
			while(stk[top]=='&'||stk[top]=='|')h[++cnt]=stk[top--];
			stk[++top]='|';
		}
		else if(s[i]=='&'){
			while(stk[top]=='&')h[++cnt]=stk[top--];
			stk[++top]='&';
		}
		else if(s[i]==')'){
			while(stk[top]!='(')h[++cnt]=stk[top--];
			top--;
		}else h[++cnt]=s[i];
	}
	while(top)h[++cnt]=stk[top--];
	for(int i=1;i<=cnt;i++){
		if(h[i]=='&')t[i].data=2;
		else if(h[i]=='|')t[i].data=3;
		else t[i].data=h[i]-'0';
	}
	for(int i=1;i<=cnt;i++){
		if(h[i]=='&'||h[i]=='|'){
			t[i].rs=stk2[top];
			t[i].ls=stk2[top-1];
			t[stk2[top]].fa=i;
			t[stk2[top-1]].fa=i;
			top-=2;
		}
		stk2[++top]=i;
	}
	root=stk2[top--];
	dfs(root);
	printf("%d\n%d %d\n",t[root].val,ans1,ans2);
	return 0;
}

T4 上升点列

还没写

原文地址：http://www.cnblogs.com/maniubi/p/16885848.html