T1：优秀的拆分

首先排除所有奇数，然后考虑如果这个数大于2的k次方，那就从 [公式] 一直减下去，如果出现了0那么就成功，否则失败

#include <bits/stdc++.h>
int s[] = {0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,1048576*2,1048576*2*2,1048576*2*2*2,1048576*2*2*2*2,1048576*2*2*2*2*2};
int vis[20], mx;
int q;
using namespace std;
int main() {

	cin >> q;
	if(q % 2) {
		cout << -1;
		return 0;
	}
	for(int i = 0; i < sizeof(s)/sizeof(int); i ++) {
		if(q < s[i]) {
			mx = i;
			break;
		}
	}
	for(int i = mx; i > 0 && q; i --) {
		if(q >= s[i]) {
			cout << s[i] << ' ';
			q -= s[i];
		}
	}
}

T2：直播领奖

这是一个动态排序问题，首先考虑到sort的时间复杂度会超限，注意到数据只有600，那么不妨桶排序，只有 O（600n），比 O（n²logn）更优秀

#include <bits/stdc++.h>
using namespace std;
int a[605]; 
int main() {
	int n, w, t, acc;
	cin >> n >> w;
	for(int p = 1;p <= n;p ++){
		cin >> t;
		a[t] ++;
		acc = max(1, p * w / 100);
		for(int i = 600;i >= 0;i --){
			acc -= a[i];
			if(acc <= 0){
				cout << i << ' ';
				break;
			}
		}
	}
}

T3：表达式

这个题确实有点难，不妨考虑先用栈把表达式转换为一棵树，再来把每个叶节点的值求出来，如果这个叶节点的值会影响整个树的值，那么把原有的结果取反。

#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
char str[N], ch[N];
int n, x[N], son[N][2], m, book[N], s;
stack<int> q;
int dfs1(int u) {
	if(u <= n)        return x[u];
	if(ch[u] == '!')  return x[u]=!dfs1(son[u][0]);
	else if(ch[u]=='&') {
		x[u] = 1;
		x[u] &= dfs1(son[u][0]);
		x[u] &= dfs1(son[u][1]);
		return x[u];
	} else if(ch[u]=='|') {
		x[u] = 0;
		x[u] |= dfs1(son[u][0]);
		x[u] |= dfs1(son[u][1]);
		return x[u];
	}
}

void dfs2(int u) {
	book[u] = 1;
	if(u > n) {
		if(ch[u]=='!') dfs2(son[u][0]); 
		else {
			if(ch[u] == '&') {
				if(x[son[u][0]]) dfs2(son[u][1]);
				if(x[son[u][1]]) dfs2(son[u][0]);
			}
			if(ch[u] == '|') {
				if(!x[son[u][0]]) dfs2(son[u][1]);
				if(!x[son[u][1]]) dfs2(son[u][0]);
			}
		}
	}
}

int main() {
	gets(str);
	scanf("%d", &n);
	for(int i=1; i<=n; i++)	scanf("%d", &x[i]);
	int len = strlen(str);
	m = n;
	for(int i = 0; i < len; i ++) {
		if(str[i] == 'x') {
			i ++;
			int t = 0;
			while(str[i] != ' ') {
				t = t * 10 + str[i] - '0';
				i++;
			}
			q.push(t);
		} else if(str[i] == '|' || str[i] == '&') {
			int t1 = q.top();
			q.pop();
			int t2 = q.top();
			q.pop();
			m ++;
			son[m][0] = t1;
			son[m][1] = t2;
			q.push(m);
			ch[m] = str[i];
		} else if(str[i] == '!') {
			int t = q.top();
			q.pop();
			m ++;
			son[m][0] = t;
			q.push(m);
			ch[m] = str[i];
		}
	}
	int root = q.top();
	int res = dfs1(root);
	dfs2(root);
	scanf("%d", &s);
	for(int i = 1; i <= s; i ++) {
		int k;
		cin >> k;
		if(!book[k]) printf("%d\n",res);
		else printf("%d\n",res^1);
	}

	return 0;
}

T4：方格取数

直接考虑蛇形走法，然后很容易的就能推出式子

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005;
LL dp[N][N];
int n, m, w[N][N];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> w[i][j];
        }
    }
    memset(dp, -0x3f3f3f3f, sizeof(dp));
    dp[1][0] = 0;
    for(int j = 1;j <= m;j ++){
        LL s = -0x3f3f3f3f;
        for(int i = 1;i <= n;i ++){
            s = max(dp[i][j-1], s) + w[i][j];
            dp[i][j] = max(s, dp[i][j]);
        }
        s = -0x3f3f3f3f;
        for(int i = n;i >= 1;i --){
            s = max(dp[i][j-1], s) + w[i][j];
            dp[i][j] = max(s, dp[i][j]);
        }
    }
    cout << dp[n][m];
    return 0;
}

CSP2020-J 复赛题解

T1：优秀的拆分

T2：直播领奖

T3：表达式

T4：方格取数