写在前面
安徽CSP取消了……
去年CSP考炸的我本来想今年一雪前耻（bushi），结果……
T1
第一题大毒瘤！
首先观察数据可以分类如下两种情况：
- \(a = 1\)
直接输出\(1\)，return 0 - \(a \le 2\)
模拟乘方，由于不能超过\(10^9\)，开long long模拟就可以过。
\(Code:\)
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
long long a, b, ans = 1;
int main()
{
freopen("pow.in","r",stdin);
freopen("pow.out","w",stdout);
cin >> a >> b;
if(a == 1) {
cout << 1;
return 0;
}
for (int i = 1; i <= b; i++) {
ans *= a;
if(ans > 1000000000) {
cout << -1;
return 0;
}
}
cout << ans;
}
T2
去年T2是大模拟题，但是我炸了……
在家写代码的时候就谨慎得多。
分析题面可知\(e \times d = pq - p - q + 2\)
\(\therefore m = n - e \times d + 2 = p + q\)
\(\therefore n = p(m - p) = mp - p^2\)
\(\therefore p^2 - mp + n = 0\)
\(\because p \leq q\)
\(\therefore p = \frac{m-\sqrt{m^2-4\times n}}{2}\)
这也就是说，这道题变成了裸的解方程！
求整数解需要有如下条件
- \(m^2 - 4 \times n\)是完全平方数
- \(m-\sqrt{m^2 - 4 \times n}\)是偶数
\(Code:\)
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int k;
long long n, e, d, m;
int main()
{
freopen("decode.in","r",stdin);
freopen("decode.out","w",stdout);
scanf("%d", &k);
while (k--) {
scanf("%lld%lld%lld",&n, &e, &d);
m = n - e * d + 2;
long long sqr = sqrt(m * m - 4 * n);
if(sqr * sqr != m * m - 4 * n) {
printf("NO\n");
continue;
}
if((m - sqr) % 2 == 1) {
printf("NO\n");
continue;
}
long long p = (m - sqr) / 2 , q = (m + sqr) / 2;
printf("%lld %lld\n", p, q);
}
}
T3
前置知识1：栈
前置知识2：表达式求值——中缀表达式
我们需要一个数值栈d以及符号栈op。
从左向右扫描表达式字符串（以本题的逻辑运算为例）
当扫到数字0或1时，直接加入数值栈。
当扫到符号时，分为一下三种情况：
- 是
(
直接入符号栈
- 不是括号
如果符号栈非空且符号栈栈顶的优先级大于当前符号优先级，则进行calc运算；
否则把当前符号入栈。
- 是
)
如果符号栈栈顶不是(，则进行calc运算，知道栈顶是(为止，并将(弹出。
calc运算步骤如下
定义ch是符号栈栈顶符号，符号栈pop。
定义y是数值栈栈顶符号，数值栈pop。
定义x是数值栈栈顶符号，数值栈pop。
将x和y执行ch操作，并将结果压进数值栈。
扫描结束后，如果符号栈非空，则进行calc操作至符号栈为空为止。
\(Code:\)
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
string expr;//表达式
stack<int>d;//数值栈
stack<char>op;//符号栈
int level(char ch) { //判断符号优先级
if(ch == '&') return 2;
else if(ch == '|') return 1;
else return 0; //括号优先级最低
}
void calc() { //calc操作
int y = d.top(); d.pop();
int x = d.top(); d.pop();
char ch = op.top(); op.pop();
if(ch == '&') d.push(x & y);
else d.push(x | y);
}
int main()
{
cin >> expr;
for (int i = 0; i < expr.size(); i++) { //从左往右扫描表达式
if (expr[i] == 0 || expr[i] == 1) {
d.push(expr[i] - '0');//压入数值栈
}
else if (expr[i] == '(') op.push('(');//直接压入
else if (expr[i] != ')'){
while(!op.empty() && level(op.top()) >= level(expr[i])) calc();//运算优先级高的表达式
op.push(expr[i]);
}
else {
while(op.top() != '(') calc();//处理括号
op.pop();
}
}
while(!op.empty()) calc();//处理剩余表达式
cout << d.top();
}
前置知识3：表达树
表达式1&0|0&(0|1)的表达树如下：
|
/ \
/ \
/ \
& |
/ \ / \
/ \ / \
1 0 0 |
/ \
/ \
0 1
我们可以看到，最早运算的运算符深度越深，且如果一个符号左边先算的式子就是该符号的左子树，右边先算的式子就是该符号的右子树，数字没有子节点。
建树过程与表达式求值类似。
\(Code:\)
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
const int N = 1E6 + 5;
string expr;
stack<int>d, op;
int num(char ch){
if(ch == '&') return 3;
else if(ch == '|') return 2;
else if(ch == '1') return 1;
else if(ch == '0') return 0;
}
void build() {
int y = d.top();d.pop();
int x = d.top();d.pop();
int ch = op.top();op.pop();
l[ch] = x, r[ch] = y;
d.push(ch);
}
int main()
{
cin >> expr;
for (int i = 0; i < expr.size(); i++) {
dat[i + 1] = num(expr[i]);
if(expr[i] == '0' || expr[i] == '1') {
d.push(i + 1);
}
else if(expr[i] == '(') op.push(-1);
else if(expr[i] != ')'){
while(!op.empty() && dat[op.top()] >= dat[i + 1]) build();
op.push(i + 1);
}
else {
while(op.top() != -1) build();
op.pop();
}
}
while(!op.empty()) build();
}
回归本题
本题最后就是在表达树上进行\(dfs\)，当左节点的表达式的值可以“垄断”右边表达式的值时，右边的就不需要进行“垄断”操作的计算。
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
const int N = 1E6 + 5;
int l[N], r[N], dat[N], root;
int And, Or;
bool vis[N];
string expr;
stack<int>d, op;
int num(char ch){
if(ch == '&') return 3;
else if(ch == '|') return 2;
else if(ch == '1') return 1;
else if(ch == '0') return 0;
return -1;
}
void build() {
int y = d.top();d.pop();
int x = d.top();d.pop();
int ch = op.top();op.pop();
l[ch] = x, r[ch] = y;
d.push(ch);
}
int dfs(int u, int &And, int &Or) {
if(dat[u] < 2) return dat[u];
int L = dfs(l[u], And, Or);
if(dat[u] == 3 && L == 0) {
And += 1;
return 0;
}
else if(dat[u] == 2 && L == 1) {
Or += 1;
return 1;
}
int R = dfs(r[u], And, Or);
if(dat[u] == 3) return L & R;
else return L | R;
}
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin >> expr;
for (int i = 0; i < expr.size(); i++) {
dat[i + 1] = num(expr[i]);
if(expr[i] == '0' || expr[i] == '1') {
d.push(i + 1);
}
else if(expr[i] == '(') op.push(-1);
else if(expr[i] != ')'){
while(!op.empty() && dat[op.top()] >= dat[i + 1]) build();
op.push(i + 1);
}
else {
while(op.top() != -1) build();
op.pop();
}
}
while(!op.empty()) build();
root = d.top();
for (int i = 1; i <= expr.size(); i++) {
vis[l[i]] = vis[r[i]] = 1;
if(!l[i] && !r[i]) vis[i] = 1;
}
cout << dfs(root, And, Or) <<'\n';
cout << And << ' ' << Or;
}
T4
很明显，是\(dp\)。
首先按\(x_i\)为第一关键字，\(y_i\)为第二关键字从小到大排序。
接下来我们定义状态\(dp_{i,j}\)，表示前\(i\)添加\(j\)个点后，最多能连接起多少个点，不包括后来添加的\(k\)个点。
则\(\max\{dp_{i,j}\}+k\)即为最大值，因为一定可以取完\(k\)个点。
状态转移方程：\(dp_{i,j} = \max\limits_{1\leq l \leq i}\{dp_{l,j-(x_i+y_i-x_l-y_l-1)}\}+1\)
\(Code:\)
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int n, k, dp[505][105], ans;
struct Pos{
int x, y;
}a[505];
bool cmp(const Pos& u, const Pos& v) {
return u.x < v.x || u.x == v.x && u.y < v.y;
}
int main()
{
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
}
stable_sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) dp[i][j] = 1;
for (int j = 1; j < i; j++) {
if(a[j].y > a[i].y) continue;
int s = a[i].x + a[i].y - a[j].x - a[j].y - 1;
for(int l = s; l <= k; l++) {
dp[i][l] = max(dp[i][l], dp[j][l - s] + 1);
}
}
ans = max(ans, dp[i][k]);
}
cout << ans + k;
}