2022 CSP-J 复赛题解

解题流程

1. 开a，b变量+输入

*特殊情况：如果a等于1直接输出1

2. 开变量n，每次循环里会增加一次a

3. for循环0～b-1次循环求幂

        n求幂，每次乘a

        判断最新的数字是否大于10^9

                是：输出-1，结束运行

                否：继续for循环

4. 输出最终答案n

注意事项

1. 两个变量记得开ll或者ull 都行 反正int过不了

2. 场上freopen的文件名别写错 

3. 想我这种手敲了10^9的数清楚几个0

4. n变量初始值为1

代码

#include
using namespace std;
int main(){
    long long a,b,n=1;
    cin>>a>>b;
    if(a==1){ 
        cout<<"1";
        return 0;
    }
    else{
        for(long long i=0;i
            n*=a;
            if(n>1000000000){
                cout<<"-1";
                return 0;
            }
        }
    }
    cout<
    return 0;
}

第二题 解密

#include
#define ll long long
using namespace std;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
 
inline ll read()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
	return x*f;
}
 
int main(){ 
	int k=read();
	while(k--)
	{
		ll n=read(),d=read(),e=read();
		ll x=e*d-n-2;
		x=-x; 
		double s=sqrt(x*x-4*n);
		if(x<0||x*x-4*n<0||s!=int(s))
		{
			printf("NO\n");
			continue;			
		}
		int ss=s;
		if((-x-ss)&1||(-x+ss)&1)
		{
			printf("NO\n");
			return 0;
		}
		int yy=(-x-ss)/(-2),xx=(-x+ss)/(-2);
		if(xx<=0||yy<=0)
		{
			printf("NO\n");
			return 0;				
		}
		printf("%d %d\n",xx,yy);
	}
	return 0;
}

#include 
using namespace std; 
 
int n,ch[1000010][2],root,num[1000010],op[1000010],pri[1<<10],topn,topo;
char s[1000010]; 
void calc(){
	int u=op[topo];
	ch[u][0]=num[topn-1],ch[u][1]=num[topn];
	topo--,topn-=2,num[++topn]=u;
}
int build(){
	topn=0,topo=0;
	s[0]='(',s[n+1]=')'; 
	for(int i=0;i<=n+1;i++){
		if(s[i]=='0'||s[i]=='1') num[++topn]=i;
		else if(s[i]=='(') op[++topo]=i;
		else if(s[i]=='&'||s[i]=='|'){
			while(topo&&pri[s[op[topo]]]calc();
			op[++topo]=i;
		}else if(s[i]==')'){
			while(topo&&pri[s[op[topo]]]calc();
 
			topo--;
		}
	}
 
	return num[topn];
}
int cnt1,cnt0; 
bool dfs(int u){
	if(s[u]=='0') return 0;
	if(s[u]=='1') return 1;
	if(s[u]=='&'){
		if(!dfs(ch[u][1])) return cnt0++,0;
		return dfs(ch[u][0]);
	}
	if(s[u]=='|'){
		if(dfs(ch[u][1])) return cnt1++,1;
		return dfs(ch[u][0]);
	}
	return -1;
}
int main(){ 
	scanf("%s",s+1),n=strlen(s+1);
	pri['(']=1e9,pri['|']=1,pri['&']=0,pri[')']=1e9-1;
	reverse(s+1,s+n+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='(') s[i]=')';
		else if(s[i]==')') s[i]='(';
	}
	printf("%d\n",dfs(build()));
	printf("%d %d\n",cnt0,cnt1);
	return 0;
} 

第四题 上升点列