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

一枚大果壳

发布于 2023-09-26 14:44:53

2910

发布于 2023-09-26 14:44:53

文章被收录于专栏：编程驿站

上文讲解了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，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。一个符合规范的地址串应当具有以下特征:

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

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

不是形如 a.b.c.d:e 格式的字符串，例如含有多于 3个字符 . 或多于1个字符 : 等情况;
整数 a,b,c, d,e中某一个或多个超出上述范围;
整数 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 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

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

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

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。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;
}