C++ 2019-2022 CSP_J 复赛试题横向维度分析(中)

上文讲解了2019~2022年第一题和第二题。第一题偏数学认知，算法较简单，第二题考查基本数据结构，如队列、栈……和基础算法，如排序、模拟……。

本文继续讲解第三题和第四题。

1. 第三题

1.1 2022

题目：

逻辑表达式expr

问题描述：

逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

在一个逻辑表达式中，元素的值只有两种可能:0(表示假)和1(表示真) 。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种:“与”(符号为&)和“或"(符号为 |)。其运算规则如下 :

0 & 0 = 0 & 1 = 1 & 0 = 0，1&1=1;
0|0=0，0 | 1= 1 | 0 = 1 | 1=1。

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算;两种运算并列时，& 运算优先于|运算;同种运算并列时，从左向右运算。

比如，表达式0 | 1 & 0 的运算顺序等同于0 | ( 1 & 0 );表达式0 & 1 & 0 | 1的运算顺序等同于( ( 0 & 1 ) & 0 ) | 1。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略:在形如 a&b 的逻辑表达式中，会先计算a部分的值，如果a=0，那么整个逻辑表达式的值就一定为0，故无需再计算b部分的值;同理，在形如alb的逻辑表达式中，会先计算a部分的值如果a=1，那么整个逻辑表达式的值就一定为1，无需再计算b部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式1 | ( 0 & 1 )中尽管0&1是一处“短路”，但由于外层的1 | ( 0 & 1 )本身就是一处“短路”，无需再计算0 & 1部分的值，因此不应当把这里的0 & 1计入一处“短路”。

分析问题：

此题考核前缀表达式、后缀表达式之间的关系。前缀表达式如何转换成后缀表达式，以及如何求解后缀表达式。如果对这两者很熟悉，此题拿下问题不大。问题除了需要得到最终结果，还需要求解短路的次数。所以结果是一个三元数组，当然也可以自定义结构体。

前缀表达式转后缀表达式时，需要使用栈，可以使用数组进行模拟或使用STL中的stack。

如果对此内容不是了解的，可以参考公众号里的相关文档。

编码实现：

#include <iostream>
#include <cmath>
using namespace std;
string s;
int stk1[1000005],stk2[1000005];//运算符栈和结果栈 (后缀表达式)
struct node {int v, cntand, cntor;
} stk3[1000005]; // 用来计算后缀表达式
int top1, top2, top3;
int priori(char x) { // 定义优先级if (x == '&') return 2;else if (x == '|') return 1;else if (x =='(') return 0;}
void makeSuf() { // 生成后缀表达式，即生成stk2数组for (int i = 0; i < s.size(); i ++) {if (s[i]=='(') {stk1[++top1] = s[i];} else if (s[i] ==')') {while (top1 > 0) {if (stk1[top1] =='(') break;stk2[++top2] = stk1[top1--];}top1--; // ( 自己也要出栈} else if (s[i] =='0' ||  s[i] =='1') {stk2[++top2] = s[i];} else {while (top1 > 0) {if (priori( stk1[top1]) >= priori(s[i])) {stk2[++top2] = stk1[top1--];} else break;}stk1[++top1] = s[i];}}while (top1 > 0)// 残留的运算符出栈stk2[++top2] = stk1[top1--];
}void calcSuf() {// 计算后缀表达式for (int i = 1; i <= top2; i++) {if (stk2[i] =='0' ||  stk2[i] =='1') { // 数字stk3[++top3] = (node) {stk2[i] -'0',0,0};} else if (stk2[i]=='&') { // &操作node y = stk3[top3--];node x = stk3[top3--]; // 注意x和y的顺序if (x.v == 0) { // 短路stk3[++top3] = (node) {0,x.cntand+1,x.cntor};} else {stk3[++top3] = (node) {y.v, x.cntand+y.cntand, x.cntor+y.cntor};}} else if (stk2[i] =='|') {// | 操作node y = stk3[top3--];node x = stk3[top3--];if (x.v == 1) { // 短路stk3[++top3] = (node) {1,x.cntand,x.cntor+1};} else {stk3[++top3] = (node) {y.v, x.cntand+y.cntand, x.cntor+y.cntor};}}}cout << stk3[1].v << endl;cout<< stk3[1].cntand <<" "<<stk3[1].cntor<< endl;
}int main() {cin >> s;makeSuf();// 生成后缀表达式calcSuf(); //计算后缀表达式return 0;
}

1.2 2021

题目：

网络连接

问题描述：

TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。在本问题中，计算机分为两大类：服务机(Server)和客户机(client)。服务机负责建立连接，客户机负责加入连接。需要进行网络连接的计算机共有 n台，编号为 1~n，这些机器将按编号递增的顺 序，依次发起一条建立连接或加入连接的操作。每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。 一个符合规范的地址串应当具有以下特征:

1. 必须形如 a.b.c.d:e 的格式，其中 a,b,c,d,e均为非负整数；
2. 0<a,b,cd<255,0<e65535;
3. a,b,c,d,e 均不能含有多余的前导 0。

相应地，不符合规范的地址串可能具有以下特征：

1. 不是形如 a.b.c.d:e 格式的字符串，例如含有多于 3个字符 . 或多于1个字符 : 等情况;
2. 整数 a,b,c, d,e中某一个或多个超出上述范围;
3. 整数 a,b,c,d,e 中某一个或多个含有多余的前导 0

例如，地址串 192.168.0.255:80 是符合规范的，但192.168.8.999:89 、192.168.0.1:1、192.168.0.1:088 、192:168::1.233 均是不符合规范的。

如果服务机或客户机在发起操作时提供的地址串不符合规范，这条操作将被直接忽略。在本问题中，我们假定凡是符合上述规范的地址串均可参与正常的连接，你无需考虑每个地址串的实际意义。 由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生， 后一台尝试建立连接的服务机将会无法成功建立连接,除此之外凡是提供符合规范的地址串的服务机均可成功建立连接。
如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这台服务机;如果找不到这样的服务机，则认为这台客户机无法成功加入连接。 请注意，尽管不允许两台不同的服务机使用相同的地址串，但多台客户机使用同样 的地址串，以及同一台服务机同时被多台客户机连接的情况是被允许的。 你的任务很简单:在给出每台计算机的类型以及地址串之后，判断这台计算机的连 接情况。

省略其它……

分析问题：

此题应该是史上最长文字描述了，如果对网络知识稍有一些认知的，其实题目很容易看性。服务机和客户机在建立连接时。服务机需要创建连接，监听连接。

客户机需要，发起连接，等待连接。需要此题篇幅较长，其实非常实现起来非常简单。

编码实现：

int n;int a[1005],b[1005],c[1005],d[1005],e[1005];
int good[1005]; // 服务器是否是好的
bool checkv(int i) { // 检查数值上合不合法
if (!(a[i] >= 0 && a[i] <= 255)) return false;
if (!(b[i]>= 0 && b[i] <= 255)) return false;
if (!(c[i] >= 0 && c[i] <= 255)) return false;
if (!(d[i] >= 0 && d[i] <= 255)) return false;
if (!(e[i] >= 0 && e[i] <= 65535)) return false;
return true;
}
bool deng(int i，int j) {//检查两个服务器是否完全重复
if (!(a[i] == a[j]))return false;
if (!(b[i] == b[j]))return false;
if (!(c[i]== c[j]))return false;
if (!(d[i]==d[j])) return false;
if (!(e[i] == e[j]))return false;
return true;
}
int main() {cin >> n;for (int i = 1; i <= n; i ++) {string type,,s;cin >> type >> s;int op;int err = 0;int cntdian = 0,cntmao = 0;for (int j = 0; j < s.size(); j ++) {if (s[j] =='.') cntdian ++;if (s[j]==':') cntmao ++;}if (cntdian == 3 && cntmao == 1) { S+=".";if (type == "Server") op = 1;else op = 2;string ss="";// 把.和: 之间的字符串记录下来 int cnt = 0;for(int j = 0;j<s.size();j++){if (s[j] =='.' || s[j] ==':'){if (cnt == 0 && (s[j]!='.'))  err=1;if (cnt == 1 && (s[j] !='.')) err=1;if (cnt == 2 && (s[j] !='.')) err=1;if (cnt == 3 && (s[j] !='.')) err=1;if (ss == "") err = 1// 不能是空串if (ss[0] =='0'&& ss.size() != 1) {err = 1; // 检查有没有前导0}int v = 0; // 把ss字符串表示的数字计算出来for (int k = 0; k < ss.size(); k ++) {v = v * 10 + ss[k] -0';}cnt ++; // 第几个数字if (cnt == 1) a[i] = v;else if (cnt == 2) b[i] = v;else if (cnt == 3) c[i] = v;else if (cnt == 4)d[i] = v;else if(cnt == 5) e[i] = v;Ss ="";}else{ss += s[j];}}if (!checkv(i)) err = 1; // 检验合不合法}else{err = 1; // 如果不是有3个.以及1个: 也不合法}if (err == 1) {cout <<"ERR" << endl;continue;}if (op == 1){ // 服务器int ok = 1;for (int j= 1; j <= i-1; j ++) {if (good[j] == 1 & deng(i, j)) {ok = 0;break;}}if (ok == 0) {cout << "FAIL" << endl;} else{cout << "0k" << endl;good[i] = 1;}}else if (op == 2) // 客户机int ok = 0, id;for (int j= 1; j <= i-1; j ++) {if (good[j] == 1 && deng(i, j)) {ok = 1;id = j;break;}}if (ok == 0){cout << "FAIL" << endl;} else{cout << id << endl;}}
}
return 0;
}

1.3 2020

题目：

表达式(expr)

问题描述：

小C热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为0或1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：
与运算：a&b。当且仅当a和b的值都为1时，该表达式的值为1。其余情况该表达式的值为0。
或运算：a | b。当且仅当a和b的值都为0时，该表达式的值为0。其余情况该表达式的值为1。
取反运算：!a。当且仅当a的值为0时，该表达式的值为1。其余情况该表达式的值为0。
小C想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。为了化简对表达式的处理，我们有如下约定：

表达式将采用后缓表达式的方式输入。

后缀表达式的定义如下：

如果E是一个操作数，则E的后缀表达式是它本身。

如果E是E1 op E2形式的表达式，其中op是任何二元操作符，且优先级不高于 E1、E2中括号外的操作符，则E的后缀式为E1'E2'op，其中E1'E2'分别为E1、E2的后缀式。
如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。同时为了方便，输入中：
与运算符(&)、或运算符(|)、取反运算符(!)的左右均有一个空格，但表达式末尾没有空格。操作数由小写字母x与一个正整数拼接而成，正整数表示这个变量的下标。例如x10表示下标为10的变量x10。数据保证每个变量在表达式中出现恰好一次。

分析问题：

本质就是求解后缀表达式的结果，后缀表达式也是一棵二叉树，即可以按后缀表达式的特点求解，也可以构建一模二叉树后再求解。

编码实现：

#include <bits/stdc++.h>  // c 头文件 
#include <cstdio>
#include <algorithm>
using namespace std;int n,a[100],q;
int z[100],top;
int cnt;
struct tnode {int left,right,val;
};
tnode tree[100];
bool f[100];
bool change[100];bool dfs( int i ) {if( tree[i].val>=0 ) {f[i]=a[tree[i].val ];return f[i];}bool lval=dfs( tree[i].left );bool rval=dfs( tree[i].right );if( tree[i].val==-1 )f[i]=!lval;else if( tree[i].val==-2 )f[i]=lval & rval;else f[i]=lval | rval;return f[i];
}void result(int i) {if( tree[i].val>=0 ) {change[ tree[i].val ]=1;return;}if( tree[i].val==-1 )result( tree[i].left );else if( tree[ i ].val==-2 ) {if( f[tree[i].left]==1 &&  f[tree[i ].right]==1 ) {result( tree[i].left );result( tree[i].right );} else if( f[tree[i ].left]==0 &&  f[tree[i ].right]==1 ) {result( tree[i].left );} else if( f[tree[i ].left]==1 &&  f[tree[i ].right]==0 ) {result( tree[i].right );}} else {if( f[tree[i ].left]==0 &&  f[tree[i ].right]==0 ) {result( tree[i].left );result( tree[i].right );} else if( f[tree[i ].left]==0 &&  f[tree[i ].right]==1 ) {result( tree[i].right );} else if( f[tree[i ].left]==1 &&  f[tree[i ].right]==0 ) {result( tree[i].left );}}
}int main() {string s;getline(cin,s);int t=0;for(int i=0; s[i]; i++ ) {char ch=s[i];int val;if( ch=='x' ) {//数字++cnt;++t;tree[cnt].val=t;z[++top]=cnt;}//空格else if(ch==' ')continue;else {//运算符if( ch=='!' ) {++cnt;//一元运算符tree[cnt].left=z[top--];tree[cnt].val=-1;z[++top]=cnt;} else if(ch=='&') {++cnt;tree[cnt].left=z[top--];tree[cnt].right=z[top--];tree[cnt].val=-2;z[++top]=cnt;} else if(ch=='|') {++cnt;tree[cnt].left=z[top--];tree[cnt].right=z[top--];tree[cnt].val=-3;z[++top]=cnt;}}}cin>>n;for(int i=1; i<=n; i++) {cin>>a[i];}dfs(cnt );result(cnt);cin>>q;for(int i=1; i<=q; i++) {int x;cin>>x;if(change[x]) {cout<<!f[cnt]<<endl;} else {cout<<f[cnt]<<endl;}}return 0;
}

1.4 2019

题目：

纪念品

问题描述：

小伟突然获得一种超能力，他知道未米 T 天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品。
2. 卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
T 天之后，小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。
小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币。

分析问题：

这是一道完全背包的题，把今天手里的钱当做背包的容量，把商品今天的价格当成它的消耗，把商品明天的价格当做它的价值，

每一天结束后把总钱数加上今天赚的钱。

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

编码实现：

#include <iostream>
#include <memory.h>
using namespace std;
const int N = 101;
const int M = 10001;
int n, m, t, price[N][N], f[M];
int main() {cin >> t >> n >> m;//读入每种商品每天的价格for(int i = 1; i <= t; i++)for(int j = 1; j <= n; j++)cin >> price[j][i];//遍历天数for(int k = 1; k < t; k++) {memset(f, 0, sizeof f);//遍历物品for(int i = 1; i <= n; i++)//price[i][k] 第 i 件物品在第 k 天的价值for(int j = price[i][k]; j <= m; j++)//f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k] );m += f[m];}cout << m;return 0;
}

1.5 小结

2021和2022的第三题是同性质的题，所以，认识前缀、后缀表达式，以及如何求解其表达式应该是重点也是难点知识。需要学生一定掌握。

3. 总结

从第三题开始，难度在逐步增加，需要有良好的算法和数据结构基础。