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\)：
\[n=pq \]\[m=p+q \]解方程即可：
\[(p+q)^2=p^2+q^2+2n \]\[(p-q)^2=p^2+q^2-2n \]\[(p+q)^2-(p-q)^2=4n \]\[m^2-(p-q)^2=4n \]\[(p-q)^2=m^2-4n \]\[p-q=\sqrt {m^2-4n} \]\[p-q+m=p-q+p+q=2p=\sqrt {m^2-4n}+m \]\[p=\frac {\sqrt {m^2-4n}+m}{2} \]\[q=m-\frac {\sqrt {m^2-4n}+m}{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;
}