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个点即可
\[f_{i,k} = \max_{x_i\leq x_j, y_j\leq y_i} f_{j,k - d + 1} + d; \]其中 \(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;
}