CSP-J2020试题

1.优秀的拆分

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

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+255;
ll n,x=0,power[N];
int main(){
	cin>>n;
	if(n%2==1)cout<<"-1";
	else{
		while(n){
			power[++x]=n%2;
			n/=2;
		}
		for(int i=x;i>=1;i--){
			if(power[i]==1)cout<<(ll)(pow(2,i-1))<<' ';
		}
	}
	return 0;
}

解题思路：

题目中说n必须由2的正整数次幂组成，1是2的0次幂，所以n不可以是奇数，然后分解成二进制，输出就是答案

2.直播获奖

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

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 6e2+255;
int sum[N],n,w,a;
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>a;
		int fx=max(1.0,floor(i*w/100.0));
		sum[a]++;
		for(int j=600;j>=0;j--){
			fx-=sum[j];
			if(fx<=0){
				cout<<j<<' ';
				break;
			}
		}
	}
	return 0;
}

解题思路：

大模拟，计算获奖人数，用一个桶统计分数，从600到0，减去每个分数的人数，直到0或0以下为止

3.表达式

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

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+255;
struct nod{
	bool v;int l,r;char op;
}tree[4*N];
int n,q,k,flag[N],cnt;
string s;
void readp(){
	getline(cin,s);
	s+=" ";
	cin>>n;cnt=n;
	for(int i=1;i<=n;i++){
		cin>>tree[i].v;
		tree[i].l=tree[i].r=0;
		tree[i].op='#';
	}
}
void build(){
	stack<int>sta;int t=-1,num1,num2;
	for(int i=0;i<s.length();i++){
		if(s[i]=='x')t=0;
		else if(s[i]>='0'&&s[i]<='9')t=t*10+(s[i]-'0');
		else if(s[i]==' '){
			if(t!=-1){
				sta.push(t);
				t=-1;
			}
		}else if(s[i]=='!'){
			num1=sta.top();sta.pop();
			tree[++cnt].l=num1;
			tree[cnt].op='!';
			tree[cnt].r=0;
			tree[cnt].v=!tree[num1].v;
			sta.push(cnt);
		}else if(s[i]=='&'){
			num2=sta.top();sta.pop();
			num1=sta.top();sta.pop();
			tree[++cnt].l=num1;
			tree[cnt].r=num2;
			tree[cnt].op='&';
			tree[cnt].v=tree[num1].v&tree[num2].v;
			sta.push(cnt);
		}else if(s[i]=='|'){
			num2=sta.top();sta.pop();
			num1=sta.top();sta.pop();
			tree[++cnt].l=num1;
			tree[cnt].r=num2;
			tree[cnt].op='|';
			tree[cnt].v=tree[num1].v|tree[num2].v;
			sta.push(cnt);
		}
	}
}
void dfs(int root){
	flag[root]=1;
	if(tree[root].op=='#')return;
	if(tree[root].op=='!')dfs(tree[root].l);
	if(tree[root].op=='&'){
		if(tree[root].v==0){
			if(tree[tree[root].l].v==1)dfs(tree[root].r);
			else if(tree[tree[root].r].v==1)dfs(tree[root].l);
		}else{
			dfs(tree[root].l);
			dfs(tree[root].r);
		}
	}
	if(tree[root].op=='|'){
		if(tree[root].v==1){
			if(tree[tree[root].l].v==0)dfs(tree[root].r);
			else if(tree[tree[root].r].v==0)dfs(tree[root].l);
		}else{
			dfs(tree[root].l);
			dfs(tree[root].r);
		}
	}
}
int main(){
	readp();
	build();
	dfs(cnt);
	cin>>q;
	while(q--){
		cin>>k;
		if(flag[k])cout<<!tree[cnt].v<<'\n';
		else cout<<tree[cnt].v<<'\n';
	}
	return 0;
}

解题思路：

建好表达式树，进行深搜，如果是“！” ，遍历左孩子，如果是“&”或“|”，遍历左孩子和右孩子，遍历到的节点都打上标记，最终输出结果

4.方格取数

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

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+5;
ll n,m,a[N][N],dp[N][N][3];
ll dfs(ll x,ll y,ll flag){
	if(dp[x][y][flag]!=-1)return dp[x][y][flag];
	if(x==n&&y==m)return dp[x][y][flag]=a[n][m];
	ll ans=-1e10;
	if(y<m)ans=max(ans,dfs(x,y+1,2));
	if(x>1&&flag!=0)ans=max(ans,dfs(x-1,y,1));
	if(x<n&&flag!=1)ans=max(ans,dfs(x+1,y,0));
	return dp[x][y][flag]=ans+a[x][y];
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	cout<<dfs(1,1,2)<<'\n';
	return 0;
}

解题思路：运用记忆化剪枝，可以大大降低dfs的复杂度，建立一个flag，用来记录方向，遍历三个方向，取最大值就是答案