CSP-J2022试题题解

1.乘方

原题：https://www.luogu.com.cn/problem/P8813

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int XN = 1e9;
ll a,b,ans=1;
int main(){
	cin>>a>>b;
	for(int i=1;i<=b;i++){
		ans*=a;
		if(ans>XN){
			cout<<"-1";
			return 0;
		}
	}
	cout<<ans;
	return 0;
}

解题思路：

因为pow的速度太慢，所以要使用累乘的方法去判断

2.解密

原题：https://www.luogu.com.cn/problem/P8814

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll k,n,d,e;
vector<ll>vec;
pair<ll,ll>ans;
bool Solve(ll n,ll d,ll e){
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			vec.push_back(i);
			if(n/i!=i){
				vec.push_back(n/i);
			}
		}
	}
	for(ll i=0;i<vec.size();i+=2){
		if((vec[i]-1)*(vec[i+1]-1)+1==e*d){
			ans.first=vec[i];
			ans.second=vec[i+1];
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>k;
	while(k--){
		vec=vector<ll>();
		cin>>n>>d>>e;
		if(Solve(n,d,e))cout<<ans.first<<' '<<ans.second<<'\n';
		else cout<<"NO\n";
	}
	return 0;
}

题解代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll k,n,e,d,m;
int main(){
	cin>>k;
	while(k--){
		cin>>n>>e>>d;
		m=n-e*d+2;
		ll l=1,r=m/2;
		while(l<r){
			ll mid=(l+r)>>1;
			if(mid*(m-mid)>=n)r=mid;
			else l=mid+1;
		}
		if(m-r>=1&&r*(m-r)==n)cout<<r<<' '<<m-r<<'\n';
		else cout<<"NO\n";
	}
	return 0;
}

解题思路：

计算m，使用二分确定第一个数，通过第一个数可以得出第二个数

错误原因：

想到过二分，却没有坚持自己的思路去走下去，而是选择了因数分解的方式去解题

3.逻辑表达式

原题：https://www.luogu.com.cn/problem/P8815

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6+520;
stack<int>num;
stack<char>op;
int cnt1,cnt2,cnt=0;string s;
struct node{
	char op;
	int l,r;
}tree[N];
void creart(){
	int a=num.top();num.pop();
	int b=num.top();num.pop();
	char c=op.top();op.pop();
	if(c=='&')num.push(a&b);
	else if(c=='|')num.push(a|b);
}
void build(){
	for(int i=0;i<s.length();i++){
		if(s[i]=='(')op.push(s[i]);
		else if(s[i]==')'){
			while(op.top()!='(')creart();
			cnt--;
		}else if(s[i]=='&'){
			tree[++cnt].op='&';
			tree[cnt].l=tree[cnt].r=0;
			op.push(s[i]);
		}else if(s[i]=='|'){
			tree[++cnt].op='|';
			tree[cnt].l=tree[cnt].r=0;
			op.push(s[i]);
		}else{
			tree[++cnt].op=s[i];
			tree[cnt].l=tree[cnt].r=0;
			num.push(s[i]-'0');
		}
	}
}
int dfs(int x){
	if(tree[x].op=='0')return 0;
	if(tree[x].op=='1')return 1;
	if(tree[x].op=='&'){
		if(dfs(tree[x].l)==0){
			cnt1++;
			return 0;
		}else return dfs(tree[x].r);
	}
	if(tree[x].op=='|'){
		if(dfs(tree[x].l)==1){
			cnt2++;
			return 1;
		}else return dfs(tree[x].r);
	}
}
int main(){
	cin>>s;
	build();
	int ans=dfs(cnt);
	cout<<ans<<'\n'<<cnt1<<' '<<cnt2;
	return 0;
}

题解代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6+520;
map<char,int>yx;
stack<int>num;
stack<char>op;
int cnt1,cnt2,cnt=0;string s;
struct node{
	char op;
	int l,r;
	node(){};
	node(char opv,int ls,int rs){
		op=opv;
		l=ls;
		r=rs;
	}
	node(char opv){
		op=opv;
	}
}tree[N];
void create(){
	int a=num.top();num.pop();
	int b=num.top();num.pop();
	char c=op.top();op.pop();
	tree[++cnt]=node(c,b,a);
	num.push(cnt);
}
void build(){
	for(int i=0;i<s.length();i++){
		if(s[i]=='(')op.push(s[i]);
		else if(s[i]==')'){
			while(op.top()!='(')create();
			op.pop();
		}else if(s[i]=='&'||s[i]=='|'){
			while(op.size()&&yx[op.top()]>=yx[s[i]])create();
			op.push(s[i]);
		}else{
			tree[++cnt]=node(s[i]);
			num.push(cnt);
		}
	}
	while(op.size())create();
}
int dfs(int x){
	if(tree[x].op=='0')return 0;
	if(tree[x].op=='1')return 1;
	if(tree[x].op=='&'){
		if(dfs(tree[x].l)==0){
			cnt1++;
			return 0;
		}else return dfs(tree[x].r);
	}
	if(dfs(tree[x].l)==1){
		cnt2++;
		return 1;
	}
	return dfs(tree[x].r);
}
int main(){
	yx['(']=0;
	yx['&']=2;
	yx['|']=1;
	cin>>s;
	build();
	
//	for(int i=1;i<=cnt;i++){
//		cout<<tree[i].op<<' '<<tree[i].l<<' '<<tree[i].r<<'\n';
//	}
	
	int ans=dfs(cnt);
	cout<<ans<<'\n'<<cnt1<<' '<<cnt2;
	return 0;
}

解题思路：

先读入表达式，建立表达式树，通过深搜计算每个“短路”的个数

错误原因：

建树错误，编号传递错误，导致答案错误，且没有运算符的优先级

4.上升点列

原题：https://www.luogu.com.cn/problem/P8816

代码：

#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 5e2+255;
pair<int,int>a[N];
int n,K,xdp[N],dp[N],ans,xn=0;
int main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		int j=i+1;
		if(a[i].y>a[j].y)continue;
		xdp[j]=abs(a[j].x-a[i].x)+abs(a[j].y-a[i].y)-1;
	}
	for(int i=2;i<=n;i++)if(xdp[i])dp[++xn]=xdp[i];
	n=xn;
	for(int i=1;i<=n;i++)dp[i]+=dp[i-1];
	for(int t=1;t<=n;t++){
		for(int i=1;i<=n;i++){
			int j=i+t-1;
			if(j>n)break;
			ans=max(ans,t+(dp[j]-dp[i-1])+(K-(dp[j]-dp[i-1])));
		}
	}
	cout<<ans;
	return 0;
}

题解代码：

#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 5e2+255;
pair<int,int>a[N];
int n,K,dp[N][N],ans;
int main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=K;j++){
			dp[i][j]=1;
			for(int k=1;k<i;k++){
				if(a[i].y<a[k].y)continue;
				int dis=(a[i].x-a[k].x)+(a[i].y-a[k].y)-1;
				if(j>=dis)dp[i][j]=max(dp[i][j],dp[k][j-dis]+dis+1);
			}
			ans=max(ans,dp[i][j]+K-j);
		}
	}
	cout<<ans;
	return 0;
}

解题思路：

输入每个点的坐标，进行排序，枚举每种组合，组成dp的数据，计算欧几里得距离，取dp的最大值即为答案

错误原因：

思路错误，原代码是前缀和，题解代码是dp算法，导致“听取WA声一片”