A 乘方

签到题

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, k;

// 签到

int main() {
	int a = read(), b = read(); long long res = 1;
	for (int i = 1; i <= b; i++) {
		res *= a; if (res > 1e9) {printf("-1\n"); return 0;}
	}
	printf("%lld", res);
	return 0;
}

B 解密

化式子发现就是问一个二元二次方程组是否有整数解，直接求解即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define int long long
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, k;

// 中学数学题

signed main() {
	int T = read();
	while (T--) {
		n = read(); int e = read(), d = read(); m = n + 2 - e * d; n = m * m - (n << 2);
		if ((int)sqrt(n) * (int)sqrt(n) != n || (int)sqrt(n) + m & 1) printf("NO\n");
		else printf("%lld %lld\n", m - (int)sqrt(n) >> 1, m + (int)sqrt(n) >> 1);
	}
	return 0;
}

C 逻辑表达式

用栈对表达式建树，碰到右括号就一直出栈直到左括号，每个符号入栈前把栈内运算优先级大于等于自己的建好

对于表达式树，若左子树直接求解，就不进入右子树，并对这个运算符的答案计算一次贡献

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 1e6 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, k, to[N], s[N], top, rk[N], cnt, cnt_or, cnt_and, son[N][2];

stack<int>num;

stack<char>opt;

char ch[N], dat[N];

void add() {
	int x, y = num.top(); num.pop(); x = num.top(); num.pop();
	dat[++cnt] = opt.top(); opt.pop(); son[cnt][0] = x; son[cnt][1] = y; num.push(cnt);
}

int dfs(int u) {
	// if (!u) {printf("%d\n", u); return 0;}
	// printf("%d ", u); putchar(dat[u]); printf(" %d %d\n", son[u][0], son[u][1]);
	if (dat[u] == '0' || dat[u] == '1') return dat[u] == '1';
	if (dat[u] == '&') if (dfs(son[u][0]) == 0) {cnt_and++; return 0;} else return dfs(son[u][1]);
	if (dat[u] == '|') if (dfs(son[u][0]) == 1) {cnt_or++; return 1;} else return dfs(son[u][1]);
}

// 构造表达式树

int main() {
	scanf("%s", ch + 1); n = strlen(ch + 1); rk['&'] = 2; rk['|'] = 1;
	for (int i = 1; i <= n; i++) {
		if (isdigit(ch[i])) dat[++cnt] = ch[i], num.push(cnt);
		if (ch[i] == '(') opt.push(ch[i]);
		if (ch[i] == ')') {while (opt.top() != '(') add(); opt.pop();}
		if (ch[i] == '&' || ch[i] == '|') {while (opt.size() && rk[opt.top()] >= rk[ch[i]]) add(); opt.push(ch[i]);}
	}
	while (opt.size()) add(); int ans = dfs(cnt);
	printf("%d\n%d %d", ans, cnt_and, cnt_or);
	return 0;
}

D 上升点列

把背包和二维偏序放一块了，那么对二维偏序问题，加一层状态表示已经加了j个点即可

其中 \(d\) 表示 \(i\) 点到 \(j\) 点的距离

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

struct DAT {int x, y;} dat[N];

int n, m, dp[1010][1010];

bool cmp(DAT a, DAT b) {return a.x == b.x ? a.y < b.y : a.x < b.x;}

int dist(DAT a, DAT b) {return a.x - b.x + a.y - b.y;}

// 最优dp

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) dat[i] = (DAT){read(), read()};
	sort(dat + 1, dat + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) dp[i][j] = j + 1;
		for (int j = 1; j < i; j++) {
			if (dat[j].y > dat[i].y) continue; int d = dist(dat[i], dat[j]);
			for (int k = d - 1; k <= m; k++) {
				dp[i][k] = max(dp[i][k], dp[j][k - d + 1] + d);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) ans = max(ans, dp[i][j]);
	printf("%d", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/zrzring/p/2022-CSP-J.html