2022CSP-J如期举行，<del>本人在封控区参加不了</del>，CCF收钱之后题目确实是变简单了，所以半场外人士写了一片题解，希望对各位大佬有帮助。
# T1-乘方
第一题往往没有**实现难度**。如果稍微有点难度的第一题，可能暴力60~80分，需要简单数学实现优化。但本题并没有思维难度。
注意点：
1.不开**long long**见祖宗。
2.**a=1**时要特判，否则会痛失10分。
3.不能使用pow，因为会爆范围。
**完整代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
long long i,a,b,s=1; // 不开long long见祖宗
int main()
{
//freopen("pow.in","r",stdin);
//freopen("pow.out","w",stdout);
cin>>a>>b;
if(a==1) // a=1要特判，否则会超时
{
cout<<1;
return 0;
}
for(i=1;i<=b;i++) // 求幂过程
{
s*=a; // 累乘
if(s>1e9) // 超出1e9
{
cout<<-1;
return 0;
}
}
cout<<s; //不超出则输出结果
return 0;
}
```
# T2-解密
本题极度不符合CCF往年出题风格，两三行的题目让人怀疑自己是不是走错考场了。不过从简短的题干也能很容易清晰看出，本题是数学题。
## F0-暴力求解（60分）
相信大家应该都会吧，这里不啰嗦了。
## F1-一元二次方程求根公式
仔细观察一下题目给的两个式子：
$n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。
将第二个式子进行转换：
$e_i \times d_i = p_i \times q_i - p_i - q_i + 1 + 1$
$p_i + q_i = p_i \times q_i - e_i \times d_i + 2$
将第一个式子代入转换后的第二个式子：
$p_i + q_i = n - e_i \times d_i + 2$
等式太繁琐了，怎么办？
观察一下题目**数据范围**框的第一行：
以下记 $m = n - e \times d + 2$。
……
其实这是提示。
如果将 $m = n - e \times d + 2$再次代入第二个式子：
$p_i + q_i = m$
综上可得：
$$
\begin{cases} p_i + q_i = m \\
p_i \times q_i = n_i
\end{cases}
$$
再次代入：
$ p_i \times ( m - p_i ) = n_i $
$ p_i \times m - p_i ^ 2 = n_i $
$ p_i \times m - p_i ^ 2 - n_i= 0 $
$ p_i ^ 2 - p_i \times m + n_i= 0 $
而形如 $ax^2 + bx +c$ 一元二次方程的求根公式为：
$$
x_{1,2} = \frac{-b \pm \sqrt {b^2 - 4ac}}{2a}
$$
这里$ a = 1 $，$ b = -m $，$ c = n $
如果$ b ^ 2 - 4ac < 0 $，即$ m ^ 2 -4n < 0 $（一元二次方程判别式），则方程无解，输出```NO```即可。
**此外，还要判断一种无解情况：**
1.如果$ m ^ 2 - 4 * n $不是完全平方数，则解为无理数，不符合题意，输出```NO```。
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,k,e,d,m,p,q; // 还是不开long long见祖宗
void solve()
{
m=n-e*d+2;
if(m*m-4*n<0) // 一元二次方程判别式
{
cout<<"NO\n";
return;
}
else
{
long long d=round(sqrt(m*m-4*n));
if(d*d!=m*m-4*n) // 如果开根号不是整数，则无解
{
cout<<"NO\n";
return;
}
p=(m-d)/2,q=m-p; // 一元二次方程求根公式求解
cout<<p<<' '<<q<<'\n';
}
}
int main()
{
//freopen("decode.in", "r", stdin);
//freopen("decode.out", "w", stdout);
cin>>k;
while(k--)
{
cin>>n>>d>>e;
solve();
}
return 0;
}
```
## F2-完全平方公式
F1是初二数学，那么没有学过一元二次方程的Oier怎么办呢？还有一种理解方式，那就是完全平方公式，虽说是初一数学，但大部分小学生应该也知道。
前面推导过程与F1相同，此处不赘述。
来到这一步：
$p_i + q_i = m$
再来看看两个完全平方公式：
平方和：$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$
平方差：$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$
不难推导出：
$ a - b $
= $ \sqrt{a ^ 2 + b ^ 2 - 2ab} $
= $ \sqrt{a ^ 2 + b ^ 2 + 2ab -4ab} $
= $ \sqrt{(a + b) ^ 2 - 4ab} $
此处$a$为$p_i$，$b$为$q_i$，$a + b = m$，$ab = n$。
所以$ \vert{p_i - q_i}\vert = \sqrt{m ^ 2 - 4n}$。
因为题目中$ p_i \leqslant q_i $，所以$ q_i - p_i= \sqrt{m ^ 2 - 4n}$。
这时，求$p_i$和$q_i$就变成了三年级小学生也会的和差问题。
$ p_i = ( m - \sqrt{m ^ 2 - 4n} ) $ ，$ q_i = ( m + \sqrt{m ^ 2 - 4n} ) $
**注意几点：**
2.$ m ^ 2 - 4 * n $是个负数或不是完全平方数，则解为无理数，不符合题意，输出```NO```。
3.和差异奇偶，则为分数，不符合题意，输出```NO```。
4.若$ p_i $和$ q_i $中有负数，则不符合题意，输出```NO```。
**完整代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
long long i,k,n,e,d,p,q;
void solve()
{
long long a=n+2-e*d,b=a*a-4*n;
if(a<0)cout<<"NO\n"; // 需要开平方的是个负数，舍
else if(sqrt(b*1.0)!=(long long)sqrt(b*1.0))cout<<"NO\n"; // 根式结果不是有理数，舍
else if(a%2!=b%2)cout<<"NO\n"; // 和差异奇偶，则为分数，舍
else
{
b=sqrt(b);
p=(a-b)/2,q=(a+b)/2; // 和差求解
if(p<0||q<0)cout<<"NO\n"; // 不能为负
else cout<<p<<' '<<q<<endl;
}
}
int main()
{
//freopen("decode.in","r",stdin);
//freopen("decode.out","w",stdout);
cin>>k;
while(k--)
{
cin>>n>>e>>d;
solve();
}
return 0;
}
```
## F3-二分查找
如果说什么公式都不知道，该怎么办呢？
那么，二分查找也是一种选择。
还是一样，前几步与F1、F2相同。直到推出：
$$
\begin{cases} p_i + q_i = m \\
p_i \times q_i = n_i \\
p_i \leqslant q_i
\end{cases}
$$
$ p_i \leqslant m / 2 $
由"和一定,差小积大"，易得:$ p \times q $ 在 $ p\in [1,m/2]$上，单调递增，因此可以对$ p $进行二分查找。
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,k,e,d,m,p,q;
void solve()
{
long long m = n - e*d +2;
long long l = 1, r = m/2, p, q; // p <= q 所以 p <= m/2
while(l<=r)
{
p=(l+r)/2;
q=m-p;
if(n==p*q)break; // 在 p 的值域范围内，p*q 是单调递增的
else if(n<p*q)r=p-1;
else l=p+1;
}
if(n==p*q)cout<<p<<' '<<q<<'\n';
else cout<<"NO\n";
}
int main()
{
//freopen("decode.in","r",stdin);
//freopen("decode.out","w",stdout);
cin>>k;
while(k--)
{
cin>>n>>d>>e;
solve();
}
return 0;
}
```
# T3-逻辑表达式
还是一样，CCF保留了出题传统——最难题放T3。
## Step1-中缀转后缀
首先看题目中给出的是中缀表达式。中缀表达式人看着舒服，但计算机读取很是难受。所以，想要解决问题，必须先要将中缀表达式转为后缀表达式。
显而易见，这里需要借助栈来实现中缀表达式到后缀表达式的转换。
相信大家备战J1时也知道了，中缀转后缀有如下规则：
1.如果是数字，直接入后缀表达式。
2.如果是'('，入运算符栈。
3.如果是')'，运算符栈不断出栈到后缀表达式，直到碰到'('，'('要出栈。
4.如果是运算符，运算符栈不断出栈到后缀表达式，直到碰到一个优先级更低的运算符或者栈为空。然后当前运算符入栈。
5.结束时，运算符栈可能不空，要不断出栈到后缀表达式。
```cpp
void change()
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='0'||s[i]=='1')sf.push_back(s[i]); // 数字直接写下
else if(s[i]=='(')ops.push(s[i]); // 是 (，直接入运算符栈
else if(s[i]==')') // 是 )
{
while(!ops.empty()&&ops.top()!='(')
{
sf.push_back(ops.top()); // 一直输出，直到碰到左括号
ops.pop();
}
ops.pop(); // 弹出额外的 '('
}
else if(s[i] == '&') // 是 &
{
while(!ops.empty()&&ops.top()=='&')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('&');
}
else // 是 |
{
while(!ops.empty()&&ops.top() != '(')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('|');
}
}
while(!ops.empty())
{
sf.push_back(ops.top());
ops.pop();
}
}
```
## Step2-建表达式树
逐次读取后缀表达式的每一个符号。
如果符号是操作数，那么我们就建立一个单节点树并将一个指向它的指针推入栈中；
如果符号不是操作数，则从栈中弹出两棵树 T1 和 T2（先弹出 T1），并形成一颗以操作符为根的树，其中 T1 为右儿子，T2 为左儿子；
然后将新的树压入栈中，继续上述过程。
```cpp
void build()
{
for(int i=0;i<sf.size();i++)
{
if(sf[i]=='0'||sf[i] == '1')
{
tr[++num]={sf[i]-'0',-1,-1};
sta.push(num);
}
else
{
int r=sta.top();sta.pop();
int l=sta.top();sta.pop();
int v=(sf[i]=='&'?2:3);
tr[++num]={v,l,r};
sta.push(num);
}
}
}
```
## Step3-遍历表达式树求结果
DFS 遍历即可。
表达式树中，叶子一定是数值 0 或 1，非叶子一定是 & 或者 |。
DFS 过程：
遍历到叶子直接返回叶子的值；
遍历到非叶子时，先递归遍历左子树返回对应的子树的值。
然后基于左子树的返回值和当前结点的运算符判断是否会短路：
```1|``` 会发生“或短路”，并且返回 1；
```0&``` 会发生“与短路”，并且返回 0。
非上面两种情况，计算右子树的值并返回其结果即可：
```1&``` ，不管是0还是1，结果都是那个数；
```0&``` ，不管是0还是1，结果都是那个数。
```cpp
int dfs(int u)
{
if(tr[u].v==0||tr[u].v==1)return tr[u].v; // 是叶子（数字）结点
int l=dfs(tr[u].l);
if(l==0&&tr[u].v == 2) // 0&
{
ans1++;
return 0;
}
if(l==1&&tr[u].v == 3) // 1|
{
ans2++;
return 1;
}
int r=dfs(tr[u].r);
return r; // 只要不短路，结果肯定就取决于右值 1& 0|
}
```
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s;
struct Node
{
int v,l,r;
} tr[N];
int num, ans1, ans2;
stack<char> ops;
stack<int> sta;
vector<char> sf; // suffix 后缀表达式
void change()
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='0'||s[i]=='1')sf.push_back(s[i]); // 数字直接写下
else if(s[i]=='(')ops.push(s[i]); // 是 (，直接入运算符栈
else if(s[i]==')') // 是 )
{
while(!ops.empty()&&ops.top()!='(')
{
sf.push_back(ops.top()); // 一直输出，直到碰到左括号
ops.pop();
}
ops.pop(); // 弹出额外的 '('
}
else if(s[i] == '&') // 是 &
{
while(!ops.empty()&&ops.top()=='&')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('&');
}
else // 是 |
{
while(!ops.empty()&&ops.top() != '(')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('|');
}
}
while(!ops.empty())
{
sf.push_back(ops.top());
ops.pop();
}
}
void build()
{
for(int i=0;i<sf.size();i++)
{
if(sf[i]=='0'||sf[i] == '1')
{
tr[++num]={sf[i]-'0',-1,-1};
sta.push(num);
}
else
{
int r=sta.top();sta.pop();
int l=sta.top();sta.pop();
int v=(sf[i]=='&'?2:3);
tr[++num]={v,l,r};
sta.push(num);
}
}
}
int dfs(int u)
{
if(tr[u].v==0||tr[u].v==1)return tr[u].v; // 是叶子（数字）结点
int l=dfs(tr[u].l);
if(l==0&&tr[u].v == 2) // 0&
{
ans1++;
return 0;
}
if(l==1&&tr[u].v == 3) // 1|
{
ans2++;
return 1;
}
int r=dfs(tr[u].r);
return r; // 只要不短路，结果肯定就取决于右值 1& 0|
}
int main()
{
//freopen("expr.in", "r", stdin);
//freopen("expr.out", "w", stdout);
cin>>s;
change(); // 在构建表达式树前，需要把中缀表达式转后缀
build(); // 利用后缀表达式构建表达式树
cout<<dfs(num)<<'\n'; // 后缀表达式下，根在末尾，从根 dfs
cout<<ans1<<' '<<ans2;
return 0;
}
```
# T4-上升点列
仍然是一道不符合CSP风格的题目。所以说很容易看出，这是一道很模板的DP。
题目大意：从$ n $个坐标中选择若干个，使得横坐标不减，且纵坐标不减，同时可以插入$ k $个任意位置的点，使得选择的点和差入的点相邻两个点之间距离为 1，求最大点的数量。
考虑一个更简单的问题：令$ k = 0 $，则问题变成了从$ n $个坐标中选择若干个，使得横坐标不减，且纵坐标不减，相邻点之间距离为 1，求最大点数。
感觉有一种熟悉的味道？没错，就是最长上升子序列！此时容易想到对 n 个点排序，先按横坐标排序，再按纵坐标排序。如此，再对这 n 个点求最长上升子序列即可。
记$ f[i] $为以$ i $结尾的最长上升点序列最大长度，则有：
若$ {j\in[1,i-1]} $ ，则$ f[i] = \max ( f[i], f[j] + 1 ) $
此时，我们再考虑$ k > 0$，只需对上述状态增加一维，记$ f[i][p] $为以$ i $结尾，且已经插入了$ p $个额外点的最长上升点序列最大长度，则有：
$$
若 { j\in[1,i-1], p\in[d,k] } ，则 f[i][p] = \max ( f[i][p] , f[j][p-d] + d + 1 )\\d = a[i].x - a[j].x + a[i].y - a[j].y - 1
$$
**所以推得动态转移方程为：**
```cpp
int d=a[i].x-a[j].x+a[i].y-a[j].y-1;
......
f[i][p]=max(f[i][p],f[j][p-d]+d+1);
```
当然，别忘了初始化：
给定一个点i，可以在前面插入j个点，怎么插入上升点列最长？
当然是直接插入j个点！
```cpp
for(i=1;i<=n;i++)
{
for(j=0;j<=k;j++)f[i][j]=j+1;
}
```
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
int i,j,p,n,k,f[505][105]; // f[i][j]: 前 i 个点，插入了 j 个点后最大长度
pair<int,int>a[505];
int main()
{
cin>>n>>k;
for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
for(j=0;j<=k;j++)f[i][j]=1+j; // 直接在 i 点前插入 j 个点
}
// 类似最长上升子序列
for(i=2;i<=n;i++)
{
for(j=i-1;j>=1;j--) // j -> i
{
if(a[j].y>a[i].y)continue;
// 从 j 到 i 要插入 d 个点才能满足
int d=a[i].x-a[j].x+a[i].y-a[j].y-1;
for(p=d;p<=k;p++)f[i][p]=max(f[i][p],f[j][p-d]+d+1);
}
}
int ans=0;
for(i=1;i<=n;i++)ans=max(ans,f[i][k]);
cout<<ans;
return 0;
}
```2022CSP-J如期举行，<del>本人在封控区参加不了</del>，CCF收钱之后题目确实是变简单了，所以半场外人士写了一片题解，希望对各位大佬有帮助。
# T1-乘方
第一题往往没有**实现难度**。如果稍微有点难度的第一题，可能暴力60~80分，需要简单数学实现优化。但本题并没有思维难度。
注意点：
1.不开**long long**见祖宗。
2.**a=1**时要特判，否则会痛失10分。
3.不能使用pow，因为会爆范围。
**完整代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
long long i,a,b,s=1; // 不开long long见祖宗
int main()
{
//freopen("pow.in","r",stdin);
//freopen("pow.out","w",stdout);
cin>>a>>b;
if(a==1) // a=1要特判，否则会超时
{
cout<<1;
return 0;
}
for(i=1;i<=b;i++) // 求幂过程
{
s*=a; // 累乘
if(s>1e9) // 超出1e9
{
cout<<-1;
return 0;
}
}
cout<<s; //不超出则输出结果
return 0;
}
```
# T2-解密
本题极度不符合CCF往年出题风格，两三行的题目让人怀疑自己是不是走错考场了。不过从简短的题干也能很容易清晰看出，本题是数学题。
## F0-暴力求解（60分）
相信大家应该都会吧，这里不啰嗦了。
## F1-一元二次方程求根公式
仔细观察一下题目给的两个式子：
$n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。
将第二个式子进行转换：
$e_i \times d_i = p_i \times q_i - p_i - q_i + 1 + 1$
$p_i + q_i = p_i \times q_i - e_i \times d_i + 2$
将第一个式子代入转换后的第二个式子：
$p_i + q_i = n - e_i \times d_i + 2$
等式太繁琐了，怎么办？
观察一下题目**数据范围**框的第一行：
以下记 $m = n - e \times d + 2$。
……
其实这是提示。
如果将 $m = n - e \times d + 2$再次代入第二个式子：
$p_i + q_i = m$
综上可得：
$$
\begin{cases} p_i + q_i = m \\
p_i \times q_i = n_i
\end{cases}
$$
再次代入：
$ p_i \times ( m - p_i ) = n_i $
$ p_i \times m - p_i ^ 2 = n_i $
$ p_i \times m - p_i ^ 2 - n_i= 0 $
$ p_i ^ 2 - p_i \times m + n_i= 0 $
而形如 $ax^2 + bx +c$ 一元二次方程的求根公式为：
$$
x_{1,2} = \frac{-b \pm \sqrt {b^2 - 4ac}}{2a}
$$
这里$ a = 1 $，$ b = -m $，$ c = n $
如果$ b ^ 2 - 4ac < 0 $，即$ m ^ 2 -4n < 0 $（一元二次方程判别式），则方程无解，输出```NO```即可。
**此外，还要判断一种无解情况：**
1.如果$ m ^ 2 - 4 * n $不是完全平方数，则解为无理数，不符合题意，输出```NO```。
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,k,e,d,m,p,q; // 还是不开long long见祖宗
void solve()
{
m=n-e*d+2;
if(m*m-4*n<0) // 一元二次方程判别式
{
cout<<"NO\n";
return;
}
else
{
long long d=round(sqrt(m*m-4*n));
if(d*d!=m*m-4*n) // 如果开根号不是整数，则无解
{
cout<<"NO\n";
return;
}
p=(m-d)/2,q=m-p; // 一元二次方程求根公式求解
cout<<p<<' '<<q<<'\n';
}
}
int main()
{
//freopen("decode.in", "r", stdin);
//freopen("decode.out", "w", stdout);
cin>>k;
while(k--)
{
cin>>n>>d>>e;
solve();
}
return 0;
}
```
## F2-完全平方公式
F1是初二数学，那么没有学过一元二次方程的Oier怎么办呢？还有一种理解方式，那就是完全平方公式，虽说是初一数学，但大部分小学生应该也知道。
前面推导过程与F1相同，此处不赘述。
来到这一步：
$p_i + q_i = m$
再来看看两个完全平方公式：
平方和：$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$
平方差：$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$
不难推导出：
$ a - b $
= $ \sqrt{a ^ 2 + b ^ 2 - 2ab} $
= $ \sqrt{a ^ 2 + b ^ 2 + 2ab -4ab} $
= $ \sqrt{(a + b) ^ 2 - 4ab} $
此处$a$为$p_i$，$b$为$q_i$，$a + b = m$，$ab = n$。
所以$ \vert{p_i - q_i}\vert = \sqrt{m ^ 2 - 4n}$。
因为题目中$ p_i \leqslant q_i $，所以$ q_i - p_i= \sqrt{m ^ 2 - 4n}$。
这时，求$p_i$和$q_i$就变成了三年级小学生也会的和差问题。
$ p_i = ( m - \sqrt{m ^ 2 - 4n} ) $ ，$ q_i = ( m + \sqrt{m ^ 2 - 4n} ) $
**注意几点：**
2.$ m ^ 2 - 4 * n $是个负数或不是完全平方数，则解为无理数，不符合题意，输出```NO```。
3.和差异奇偶，则为分数，不符合题意，输出```NO```。
4.若$ p_i $和$ q_i $中有负数，则不符合题意，输出```NO```。
**完整代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
long long i,k,n,e,d,p,q;
void solve()
{
long long a=n+2-e*d,b=a*a-4*n;
if(a<0)cout<<"NO\n"; // 需要开平方的是个负数，舍
else if(sqrt(b*1.0)!=(long long)sqrt(b*1.0))cout<<"NO\n"; // 根式结果不是有理数，舍
else if(a%2!=b%2)cout<<"NO\n"; // 和差异奇偶，则为分数，舍
else
{
b=sqrt(b);
p=(a-b)/2,q=(a+b)/2; // 和差求解
if(p<0||q<0)cout<<"NO\n"; // 不能为负
else cout<<p<<' '<<q<<endl;
}
}
int main()
{
//freopen("decode.in","r",stdin);
//freopen("decode.out","w",stdout);
cin>>k;
while(k--)
{
cin>>n>>e>>d;
solve();
}
return 0;
}
```
## F3-二分查找
如果说什么公式都不知道，该怎么办呢？
那么，二分查找也是一种选择。
还是一样，前几步与F1、F2相同。直到推出：
$$
\begin{cases} p_i + q_i = m \\
p_i \times q_i = n_i \\
p_i \leqslant q_i
\end{cases}
$$
$ p_i \leqslant m / 2 $
由"和一定,差小积大"，易得:$ p \times q $ 在 $ p\in [1,m/2]$上，单调递增，因此可以对$ p $进行二分查找。
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,k,e,d,m,p,q;
void solve()
{
long long m = n - e*d +2;
long long l = 1, r = m/2, p, q; // p <= q 所以 p <= m/2
while(l<=r)
{
p=(l+r)/2;
q=m-p;
if(n==p*q)break; // 在 p 的值域范围内，p*q 是单调递增的
else if(n<p*q)r=p-1;
else l=p+1;
}
if(n==p*q)cout<<p<<' '<<q<<'\n';
else cout<<"NO\n";
}
int main()
{
//freopen("decode.in","r",stdin);
//freopen("decode.out","w",stdout);
cin>>k;
while(k--)
{
cin>>n>>d>>e;
solve();
}
return 0;
}
```
# T3-逻辑表达式
还是一样，CCF保留了出题传统——最难题放T3。
## Step1-中缀转后缀
首先看题目中给出的是中缀表达式。中缀表达式人看着舒服，但计算机读取很是难受。所以，想要解决问题，必须先要将中缀表达式转为后缀表达式。
显而易见，这里需要借助栈来实现中缀表达式到后缀表达式的转换。
相信大家备战J1时也知道了，中缀转后缀有如下规则：
1.如果是数字，直接入后缀表达式。
2.如果是'('，入运算符栈。
3.如果是')'，运算符栈不断出栈到后缀表达式，直到碰到'('，'('要出栈。
4.如果是运算符，运算符栈不断出栈到后缀表达式，直到碰到一个优先级更低的运算符或者栈为空。然后当前运算符入栈。
5.结束时，运算符栈可能不空，要不断出栈到后缀表达式。
```cpp
void change()
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='0'||s[i]=='1')sf.push_back(s[i]); // 数字直接写下
else if(s[i]=='(')ops.push(s[i]); // 是 (，直接入运算符栈
else if(s[i]==')') // 是 )
{
while(!ops.empty()&&ops.top()!='(')
{
sf.push_back(ops.top()); // 一直输出，直到碰到左括号
ops.pop();
}
ops.pop(); // 弹出额外的 '('
}
else if(s[i] == '&') // 是 &
{
while(!ops.empty()&&ops.top()=='&')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('&');
}
else // 是 |
{
while(!ops.empty()&&ops.top() != '(')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('|');
}
}
while(!ops.empty())
{
sf.push_back(ops.top());
ops.pop();
}
}
```
## Step2-建表达式树
逐次读取后缀表达式的每一个符号。
如果符号是操作数，那么我们就建立一个单节点树并将一个指向它的指针推入栈中；
如果符号不是操作数，则从栈中弹出两棵树 T1 和 T2（先弹出 T1），并形成一颗以操作符为根的树，其中 T1 为右儿子，T2 为左儿子；
然后将新的树压入栈中，继续上述过程。
```cpp
void build()
{
for(int i=0;i<sf.size();i++)
{
if(sf[i]=='0'||sf[i] == '1')
{
tr[++num]={sf[i]-'0',-1,-1};
sta.push(num);
}
else
{
int r=sta.top();sta.pop();
int l=sta.top();sta.pop();
int v=(sf[i]=='&'?2:3);
tr[++num]={v,l,r};
sta.push(num);
}
}
}
```
## Step3-遍历表达式树求结果
DFS 遍历即可。
表达式树中，叶子一定是数值 0 或 1，非叶子一定是 & 或者 |。
DFS 过程：
遍历到叶子直接返回叶子的值；
遍历到非叶子时，先递归遍历左子树返回对应的子树的值。
然后基于左子树的返回值和当前结点的运算符判断是否会短路：
```1|``` 会发生“或短路”，并且返回 1；
```0&``` 会发生“与短路”，并且返回 0。
非上面两种情况，计算右子树的值并返回其结果即可：
```1&``` ，不管是0还是1，结果都是那个数；
```0&``` ，不管是0还是1，结果都是那个数。
```cpp
int dfs(int u)
{
if(tr[u].v==0||tr[u].v==1)return tr[u].v; // 是叶子（数字）结点
int l=dfs(tr[u].l);
if(l==0&&tr[u].v == 2) // 0&
{
ans1++;
return 0;
}
if(l==1&&tr[u].v == 3) // 1|
{
ans2++;
return 1;
}
int r=dfs(tr[u].r);
return r; // 只要不短路，结果肯定就取决于右值 1& 0|
}
```
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s;
struct Node
{
int v,l,r;
} tr[N];
int num, ans1, ans2;
stack<char> ops;
stack<int> sta;
vector<char> sf; // suffix 后缀表达式
void change()
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='0'||s[i]=='1')sf.push_back(s[i]); // 数字直接写下
else if(s[i]=='(')ops.push(s[i]); // 是 (，直接入运算符栈
else if(s[i]==')') // 是 )
{
while(!ops.empty()&&ops.top()!='(')
{
sf.push_back(ops.top()); // 一直输出，直到碰到左括号
ops.pop();
}
ops.pop(); // 弹出额外的 '('
}
else if(s[i] == '&') // 是 &
{
while(!ops.empty()&&ops.top()=='&')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('&');
}
else // 是 |
{
while(!ops.empty()&&ops.top() != '(')
{
sf.push_back(ops.top());
ops.pop();
}
ops.push('|');
}
}
while(!ops.empty())
{
sf.push_back(ops.top());
ops.pop();
}
}
void build()
{
for(int i=0;i<sf.size();i++)
{
if(sf[i]=='0'||sf[i] == '1')
{
tr[++num]={sf[i]-'0',-1,-1};
sta.push(num);
}
else
{
int r=sta.top();sta.pop();
int l=sta.top();sta.pop();
int v=(sf[i]=='&'?2:3);
tr[++num]={v,l,r};
sta.push(num);
}
}
}
int dfs(int u)
{
if(tr[u].v==0||tr[u].v==1)return tr[u].v; // 是叶子（数字）结点
int l=dfs(tr[u].l);
if(l==0&&tr[u].v == 2) // 0&
{
ans1++;
return 0;
}
if(l==1&&tr[u].v == 3) // 1|
{
ans2++;
return 1;
}
int r=dfs(tr[u].r);
return r; // 只要不短路，结果肯定就取决于右值 1& 0|
}
int main()
{
//freopen("expr.in", "r", stdin);
//freopen("expr.out", "w", stdout);
cin>>s;
change(); // 在构建表达式树前，需要把中缀表达式转后缀
build(); // 利用后缀表达式构建表达式树
cout<<dfs(num)<<'\n'; // 后缀表达式下，根在末尾，从根 dfs
cout<<ans1<<' '<<ans2;
return 0;
}
```
# T4-上升点列
仍然是一道不符合CSP风格的题目。所以说很容易看出，这是一道很模板的DP。
题目大意：从$ n $个坐标中选择若干个，使得横坐标不减，且纵坐标不减，同时可以插入$ k $个任意位置的点，使得选择的点和差入的点相邻两个点之间距离为 1，求最大点的数量。
考虑一个更简单的问题：令$ k = 0 $，则问题变成了从$ n $个坐标中选择若干个，使得横坐标不减，且纵坐标不减，相邻点之间距离为 1，求最大点数。
感觉有一种熟悉的味道？没错，就是最长上升子序列！此时容易想到对 n 个点排序，先按横坐标排序，再按纵坐标排序。如此，再对这 n 个点求最长上升子序列即可。
记$ f[i] $为以$ i $结尾的最长上升点序列最大长度，则有：
若$ {j\in[1,i-1]} $ ，则$ f[i] = \max ( f[i], f[j] + 1 ) $
此时，我们再考虑$ k > 0$，只需对上述状态增加一维，记$ f[i][p] $为以$ i $结尾，且已经插入了$ p $个额外点的最长上升点序列最大长度，则有：
$$
若 { j\in[1,i-1], p\in[d,k] } ，则 f[i][p] = \max ( f[i][p] , f[j][p-d] + d + 1 )\\d = a[i].x - a[j].x + a[i].y - a[j].y - 1
$$
**所以推得动态转移方程为：**
```cpp
int d=a[i].x-a[j].x+a[i].y-a[j].y-1;
......
f[i][p]=max(f[i][p],f[j][p-d]+d+1);
```
当然，别忘了初始化：
给定一个点i，可以在前面插入j个点，怎么插入上升点列最长？
当然是直接插入j个点！
```cpp
for(i=1;i<=n;i++)
{
for(j=0;j<=k;j++)f[i][j]=j+1;
}
```
**完整代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
int i,j,p,n,k,f[505][105]; // f[i][j]: 前 i 个点，插入了 j 个点后最大长度
pair<int,int>a[505];
int main()
{
cin>>n>>k;
for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
for(j=0;j<=k;j++)f[i][j]=1+j; // 直接在 i 点前插入 j 个点
}
// 类似最长上升子序列
for(i=2;i<=n;i++)
{
for(j=i-1;j>=1;j--) // j -> i
{
if(a[j].y>a[i].y)continue;
// 从 j 到 i 要插入 d 个点才能满足
int d=a[i].x-a[j].x+a[i].y-a[j].y-1;
for(p=d;p<=k;p++)f[i][p]=max(f[i][p],f[j][p-d]+d+1);
}
}
int ans=0;
for(i=1;i<=n;i++)ans=max(ans,f[i][k]);
cout<<ans;
return 0;
}
```
2022CSP-J如期举行，<del>本人在封控区参加不了</del>，CCF收钱之后题目确实是变简单了，所以半场外人士写了一片题解，希望对各位大佬有帮助。# T1-乘方
第一题往往没有**实现难度**。如果稍微有点难度的第一题，可能暴力60~80分，需要简单数学实现优化。但本题并没有思维难度。
注意点：1.不开**long long**见祖宗。2.**a=1**时要特判，否则会痛失10分。3.不能使用pow，因为会爆范围。
**完整代码**
```cpp#include<bits/stdc++.h>
using namespace std;
long long i,a,b,s=1; // 不开long long见祖宗int main(){//freopen("pow.in","r",stdin);//freopen("pow.out","w",stdout);cin>>a>>b;if(a==1) // a=1要特判，否则会超时{cout<<1;return 0;}for(i=1;i<=b;i++) // 求幂过程{s*=a; // 累乘if(s>1e9) // 超出1e9{cout<<-1;return 0;}}cout<<s; //不超出则输出结果return 0;}```
# T2-解密
本题极度不符合CCF往年出题风格，两三行的题目让人怀疑自己是不是走错考场了。不过从简短的题干也能很容易清晰看出，本题是数学题。
## F0-暴力求解（60分）
相信大家应该都会吧，这里不啰嗦了。
## F1-一元二次方程求根公式
仔细观察一下题目给的两个式子：$n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。将第二个式子进行转换：$e_i \times d_i = p_i \times q_i - p_i - q_i + 1 + 1$$p_i + q_i = p_i \times q_i - e_i \times d_i + 2$将第一个式子代入转换后的第二个式子：$p_i + q_i = n - e_i \times d_i + 2$
等式太繁琐了，怎么办？观察一下题目**数据范围**框的第一行：以下记 $m = n - e \times d + 2$。……其实这是提示。如果将 $m = n - e \times d + 2$再次代入第二个式子：$p_i + q_i = m$
综上可得：$$\begin{cases} p_i + q_i = m \\p_i \times q_i = n_i\end{cases}$$
再次代入：$ p_i \times ( m - p_i ) = n_i $$ p_i \times m - p_i ^ 2 = n_i $$ p_i \times m - p_i ^ 2 - n_i= 0 $$ p_i ^ 2 - p_i \times m + n_i= 0 $
而形如 $ax^2 + bx +c$ 一元二次方程的求根公式为：$$x_{1,2} = \frac{-b \pm \sqrt {b^2 - 4ac}}{2a}$$
这里$ a = 1 $，$ b = -m $，$ c = n $如果$ b ^ 2 - 4ac < 0 $，即$ m ^ 2 -4n < 0 $（一元二次方程判别式），则方程无解，输出```NO```即可。
**此外，还要判断一种无解情况：**1.如果$ m ^ 2 - 4 * n $不是完全平方数，则解为无理数，不符合题意，输出```NO```。
**完整代码**
```cpp#include <bits/stdc++.h>
using namespace std;
long long n,k,e,d,m,p,q; // 还是不开long long见祖宗void solve(){m=n-e*d+2;if(m*m-4*n<0) // 一元二次方程判别式{cout<<"NO\n";return;}else{long long d=round(sqrt(m*m-4*n));if(d*d!=m*m-4*n) // 如果开根号不是整数，则无解{cout<<"NO\n";return;}p=(m-d)/2,q=m-p; // 一元二次方程求根公式求解cout<<p<<' '<<q<<'\n';}}int main(){//freopen("decode.in", "r", stdin);//freopen("decode.out", "w", stdout);cin>>k;while(k--){cin>>n>>d>>e;solve();}return 0;}```
## F2-完全平方公式
F1是初二数学，那么没有学过一元二次方程的Oier怎么办呢？还有一种理解方式，那就是完全平方公式，虽说是初一数学，但大部分小学生应该也知道。
前面推导过程与F1相同，此处不赘述。来到这一步：$p_i + q_i = m$
再来看看两个完全平方公式：平方和：$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$平方差：$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$不难推导出：$ a - b $= $ \sqrt{a ^ 2 + b ^ 2 - 2ab} $= $ \sqrt{a ^ 2 + b ^ 2 + 2ab -4ab} $= $ \sqrt{(a + b) ^ 2 - 4ab} $
此处$a$为$p_i$，$b$为$q_i$，$a + b = m$，$ab = n$。所以$ \vert{p_i - q_i}\vert = \sqrt{m ^ 2 - 4n}$。因为题目中$ p_i \leqslant q_i $，所以$ q_i - p_i= \sqrt{m ^ 2 - 4n}$。
这时，求$p_i$和$q_i$就变成了三年级小学生也会的和差问题。$ p_i = ( m - \sqrt{m ^ 2 - 4n} ) $ ，$ q_i = ( m + \sqrt{m ^ 2 - 4n} ) $
**注意几点：**2.$ m ^ 2 - 4 * n $是个负数或不是完全平方数，则解为无理数，不符合题意，输出```NO```。3.和差异奇偶，则为分数，不符合题意，输出```NO```。4.若$ p_i $和$ q_i $中有负数，则不符合题意，输出```NO```。
**完整代码**
```cpp#include<bits/stdc++.h>
using namespace std;
long long i,k,n,e,d,p,q;void solve(){long long a=n+2-e*d,b=a*a-4*n;if(a<0)cout<<"NO\n"; // 需要开平方的是个负数，舍else if(sqrt(b*1.0)!=(long long)sqrt(b*1.0))cout<<"NO\n"; // 根式结果不是有理数，舍else if(a%2!=b%2)cout<<"NO\n"; // 和差异奇偶，则为分数，舍else{b=sqrt(b);p=(a-b)/2,q=(a+b)/2; // 和差求解if(p<0||q<0)cout<<"NO\n"; // 不能为负else cout<<p<<' '<<q<<endl;}}int main(){//freopen("decode.in","r",stdin);//freopen("decode.out","w",stdout);cin>>k;while(k--){cin>>n>>e>>d;solve();}return 0;}
```
## F3-二分查找如果说什么公式都不知道，该怎么办呢？那么，二分查找也是一种选择。
还是一样，前几步与F1、F2相同。直到推出：$$\begin{cases} p_i + q_i = m \\p_i \times q_i = n_i \\p_i \leqslant q_i\end{cases}$$$ p_i \leqslant m / 2 $
由"和一定,差小积大"，易得:$ p \times q $ 在 $ p\in [1,m/2]$上，单调递增，因此可以对$ p $进行二分查找。
**完整代码**
```cpp#include <bits/stdc++.h>
using namespace std;
long long n,k,e,d,m,p,q;void solve(){long long m = n - e*d +2;long long l = 1, r = m/2, p, q; // p <= q 所以 p <= m/2while(l<=r){p=(l+r)/2;q=m-p;if(n==p*q)break; // 在 p 的值域范围内，p*q 是单调递增的else if(n<p*q)r=p-1;else l=p+1;}if(n==p*q)cout<<p<<' '<<q<<'\n';else cout<<"NO\n";}int main(){//freopen("decode.in","r",stdin);//freopen("decode.out","w",stdout);cin>>k;while(k--){cin>>n>>d>>e;solve();}return 0;}
```
# T3-逻辑表达式还是一样，CCF保留了出题传统——最难题放T3。
## Step1-中缀转后缀首先看题目中给出的是中缀表达式。中缀表达式人看着舒服，但计算机读取很是难受。所以，想要解决问题，必须先要将中缀表达式转为后缀表达式。
显而易见，这里需要借助栈来实现中缀表达式到后缀表达式的转换。
相信大家备战J1时也知道了，中缀转后缀有如下规则：1.如果是数字，直接入后缀表达式。2.如果是'('，入运算符栈。3.如果是')'，运算符栈不断出栈到后缀表达式，直到碰到'('，'('要出栈。4.如果是运算符，运算符栈不断出栈到后缀表达式，直到碰到一个优先级更低的运算符或者栈为空。然后当前运算符入栈。5.结束时，运算符栈可能不空，要不断出栈到后缀表达式。
```cppvoid change(){for(int i=0;i<s.size();i++){if(s[i]=='0'||s[i]=='1')sf.push_back(s[i]); // 数字直接写下else if(s[i]=='(')ops.push(s[i]); // 是 (，直接入运算符栈else if(s[i]==')') // 是 ){while(!ops.empty()&&ops.top()!='('){sf.push_back(ops.top()); // 一直输出，直到碰到左括号ops.pop();}ops.pop(); // 弹出额外的 '('}else if(s[i] == '&') // 是 &{while(!ops.empty()&&ops.top()=='&'){sf.push_back(ops.top());ops.pop();}ops.push('&');}else // 是 |{while(!ops.empty()&&ops.top() != '('){sf.push_back(ops.top());ops.pop();}ops.push('|');}}while(!ops.empty()){sf.push_back(ops.top());ops.pop();}}```
## Step2-建表达式树
逐次读取后缀表达式的每一个符号。如果符号是操作数，那么我们就建立一个单节点树并将一个指向它的指针推入栈中；如果符号不是操作数，则从栈中弹出两棵树 T1 和 T2（先弹出 T1），并形成一颗以操作符为根的树，其中 T1 为右儿子，T2 为左儿子；然后将新的树压入栈中，继续上述过程。
```cppvoid build(){for(int i=0;i<sf.size();i++){if(sf[i]=='0'||sf[i] == '1') {tr[++num]={sf[i]-'0',-1,-1};sta.push(num);}else{int r=sta.top();sta.pop();int l=sta.top();sta.pop();int v=(sf[i]=='&'?2:3);tr[++num]={v,l,r};sta.push(num);}}}```## Step3-遍历表达式树求结果
DFS 遍历即可。表达式树中，叶子一定是数值 0 或 1，非叶子一定是 & 或者 |。
DFS 过程：遍历到叶子直接返回叶子的值；遍历到非叶子时，先递归遍历左子树返回对应的子树的值。然后基于左子树的返回值和当前结点的运算符判断是否会短路：```1|``` 会发生“或短路”，并且返回 1；```0&``` 会发生“与短路”，并且返回 0。非上面两种情况，计算右子树的值并返回其结果即可：```1&``` ，不管是0还是1，结果都是那个数；```0&``` ，不管是0还是1，结果都是那个数。
```cppint dfs(int u){if(tr[u].v==0||tr[u].v==1)return tr[u].v; // 是叶子（数字）结点int l=dfs(tr[u].l);if(l==0&&tr[u].v == 2) // 0&{ans1++;return 0;}if(l==1&&tr[u].v == 3) // 1|{ans2++;return 1;}int r=dfs(tr[u].r); return r; // 只要不短路，结果肯定就取决于右值 1& 0|}```
**完整代码**
```cpp#include <bits/stdc++.h>using namespace std;const int N = 1e6+5;string s;struct Node{ int v,l,r;} tr[N];int num, ans1, ans2;stack<char> ops;stack<int> sta;vector<char> sf; // suffix 后缀表达式void change(){for(int i=0;i<s.size();i++){if(s[i]=='0'||s[i]=='1')sf.push_back(s[i]); // 数字直接写下else if(s[i]=='(')ops.push(s[i]); // 是 (，直接入运算符栈else if(s[i]==')') // 是 ){while(!ops.empty()&&ops.top()!='('){sf.push_back(ops.top()); // 一直输出，直到碰到左括号ops.pop();}ops.pop(); // 弹出额外的 '('}else if(s[i] == '&') // 是 &{while(!ops.empty()&&ops.top()=='&'){sf.push_back(ops.top());ops.pop();}ops.push('&');}else // 是 |{while(!ops.empty()&&ops.top() != '('){sf.push_back(ops.top());ops.pop();}ops.push('|');}}while(!ops.empty()){sf.push_back(ops.top());ops.pop();}}void build(){for(int i=0;i<sf.size();i++){if(sf[i]=='0'||sf[i] == '1') {tr[++num]={sf[i]-'0',-1,-1};sta.push(num);}else{int r=sta.top();sta.pop();int l=sta.top();sta.pop();int v=(sf[i]=='&'?2:3);tr[++num]={v,l,r};sta.push(num);}}}int dfs(int u){if(tr[u].v==0||tr[u].v==1)return tr[u].v; // 是叶子（数字）结点int l=dfs(tr[u].l);if(l==0&&tr[u].v == 2) // 0&{ans1++;return 0;}if(l==1&&tr[u].v == 3) // 1|{ans2++;return 1;}int r=dfs(tr[u].r); return r; // 只要不短路，结果肯定就取决于右值 1& 0|}int main(){//freopen("expr.in", "r", stdin);//freopen("expr.out", "w", stdout);cin>>s;change(); // 在构建表达式树前，需要把中缀表达式转后缀build(); // 利用后缀表达式构建表达式树cout<<dfs(num)<<'\n'; // 后缀表达式下，根在末尾，从根 dfscout<<ans1<<' '<<ans2;return 0;}```
# T4-上升点列
仍然是一道不符合CSP风格的题目。所以说很容易看出，这是一道很模板的DP。
题目大意：从$ n $个坐标中选择若干个，使得横坐标不减，且纵坐标不减，同时可以插入$ k $个任意位置的点，使得选择的点和差入的点相邻两个点之间距离为 1，求最大点的数量。
考虑一个更简单的问题：令$ k = 0 $，则问题变成了从$ n $个坐标中选择若干个，使得横坐标不减，且纵坐标不减，相邻点之间距离为 1，求最大点数。
感觉有一种熟悉的味道？没错，就是最长上升子序列！此时容易想到对 n 个点排序，先按横坐标排序，再按纵坐标排序。如此，再对这 n 个点求最长上升子序列即可。
记$ f[i] $为以$ i $结尾的最长上升点序列最大长度，则有：若$ {j\in[1,i-1]} $ ，则$ f[i] = \max ( f[i], f[j] + 1 ) $
此时，我们再考虑$ k > 0$，只需对上述状态增加一维，记$ f[i][p] $为以$ i $结尾，且已经插入了$ p $个额外点的最长上升点序列最大长度，则有：$$若 { j\in[1,i-1], p\in[d,k] } ，则 f[i][p] = \max ( f[i][p] , f[j][p-d] + d + 1 )\\d = a[i].x - a[j].x + a[i].y - a[j].y - 1 $$
**所以推得动态转移方程为：**
```cppint d=a[i].x-a[j].x+a[i].y-a[j].y-1;......f[i][p]=max(f[i][p],f[j][p-d]+d+1);```
当然，别忘了初始化：给定一个点i，可以在前面插入j个点，怎么插入上升点列最长？当然是直接插入j个点！
```cppfor(i=1;i<=n;i++){for(j=0;j<=k;j++)f[i][j]=j+1;}```
**完整代码**
```cpp#include <bits/stdc++.h>
using namespace std;#define x first#define y secondint i,j,p,n,k,f[505][105]; // f[i][j]: 前 i 个点，插入了 j 个点后最大长度pair<int,int>a[505];int main(){cin>>n>>k;for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;sort(a+1,a+n+1);for(i=1;i<=n;i++){for(j=0;j<=k;j++)f[i][j]=1+j; // 直接在 i 点前插入 j 个点}// 类似最长上升子序列for(i=2;i<=n;i++){for(j=i-1;j>=1;j--) // j -> i{if(a[j].y>a[i].y)continue;// 从 j 到 i 要插入 d 个点才能满足int d=a[i].x-a[j].x+a[i].y-a[j].y-1;for(p=d;p<=k;p++)f[i][p]=max(f[i][p],f[j][p-d]+d+1);}}int ans=0;for(i=1;i<=n;i++)ans=max(ans,f[i][k]);cout<<ans;return 0;}
``` 标签：ops,int,题解,tr,long,times,2022CSP,表达式 From： https://www.cnblogs.com/WiFi-dreamer/p/16874719.html