2022 CSP-J第二轮复赛题解

一枚大果壳

发布于 2023-09-11 09:11:32

7960

发布于 2023-09-11 09:11:32

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

在网上看到一篇较详细的讲解，觉得讲解的非常好！

第一题：乘方`pow`

题目描述

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数a和b，求ab 的值是多少。ab即b个a相乘的值，例如23即为3个2相乘，结果为2x2x2=8。

“简单!”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。

小文很快意识到，她的程序里的变量都是int 类型的。在大多数机器上，int类型能表示的最大数为231-1，因此只要计算结果超过这个数，她的程序就会出现错误。由于小文刚刚学会编程，她担心使用int计算会出现问题。因此她希望你在ab的值超过109时，输出一个 -1进行警示，否则就输出正确的ab的值。

然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。

输入格式

输入共一行，两个正整数a，b。

输出格式

输出共一行，如果ab的值不超过109，则输出ab的值，否则输出 -1。

输入输出样例

输入#1

10 9

输出 #1

1000000000

输入 #2

23333 66666

输出 #2

-1

说明提示

对于 10%的数据，保证b=1。

对于30%的数据，保证b≤2。

对于60%的数据，保证b≤30，ab≤1018。

对于100%的数据，保证1≤a，b≤109。

对于很多普及组学生来说，本题的难度主要来自于对于数据范围的敏感程度。也就是需要学生“掐指一算”没有这个小动作习惯的同学，只能得到60分的暴力分了有这个习惯的同学，只要再“用心一想”，运转一下思维，可以想到满分思路。根据满分思路斟酌的时间不同整个题目耗费时间在10~30分钟之内基本可以完成。另外a可以=1是个坑点，可能有同学会因为考虑不周全失分。

60分思路

对于 60% 的数据，保证 b≤30，a <1018。乘方结果在long long int范围内。因此直接循环b次算，或者用pow函数算。但是用pow函数容易出现浮点误差，建议循环b次直接算。

#include <iostream>
using namespace std;

#define ll long long int
ll a,b,c = 1000000000;
ll f(ll a, ll b) {
 if (a == 1) return 1;
 ll ret = 1;
 for (int i= 1; i <= b; i ++) {
  ret *= a;
 }
 return ret;
}
int main() {
 cin >> a>>b;
 if ( f(a, b)>c) {
  cout<<-1;
 } else {
  cout<< f(a, b);
 }
 return 0;
}

100分思路

对于 100% 的数据，保证 1<=a,b<=109。a和b都很大，乘方肯定超过long long int，因此不能直接算a。我们可以转换思路，回到乘方的定义，看看几个a相乘会超过规定的109，然后看看b是否超过这个个数。个数的枚举是否会超时呢 ?让我们精算一下

如果a=1，那么永远到不了ab，因此需要特判a=1

如果a=2，109不超过231-1，因此最多乘30来次就会到109，不会超时。

如果a>2，那么次数就更少了，更不会超时了。因此这个枚举是没问题的。

#include <iostream>
using namespace std;
#define ll long long int
ll a, b, c = 1000000000;
ll f(ll a, ll b) {
 ll ret = 1;
 for (int i= 1; i <= b; i ++) {
  ret *= a;
 }
 return ret;
}
int main() {
 cin >> a >> b;
 if (a == 1) {
  cout << 1;
  return 0;
 }
 ll ji = 1;
 int ge = 0;
 while (1) {
  if (ji * a > c) break;
  ji*= a;
  ge ++;
 }
 if (b > ge) {
  cout << -1;
 } else {
  cout << f(a, b);
 }
 return 0;
}

第二题：解密 decode

题目描述

给定一个正整数k，有k 次询问，每次给定三个正整数ni,ei,di，求两个正整数 pi,gi，使ni=pi x gi、 ei x di=(pi - 1)(gi - 1) + 1。

输入格式

第一行一个正整数 k，表示有 k 次询问。

接下来k行，第i行三个正整数 ni,di,ei。

输出格式

输出k行，每行两个正整数 pi,qi表示答案。

为使输出统一，你应当保证 pi<= qi。如果无解，请输出 NO。

输入输出样例

输入#1 输出#1

10 2 385

770 77 5 NO

633 1 211 NO

545 1 499 NO

683 3 227 11 78

858 3 257 3 241

723 37 13 2 286

572 26 11 NO

867 17 17 NO

829 3 263 6 88

528 4 109

数据范围

以下记m=n-exd+2。

保证对于 100%的数据，1<=k<=105，对于任意的 1<=i<=k，1<=ni<=1018，1<=ei X di<=1018，1<=m<=109。

`100`分思路之代数方法

#include <iostream>
#include <cmath>
using namespace std;

#define ll long long
ll k, n, d, e, m, p, q;
int main() {
 cin >> k;
 for (ll i= 1; i <= k; i++) {
  cin >> n >> d >> e;
  m=n-e*d+2;// p+q = m,pxq=n
  ll x=m*m-4*n;
  ll y = sqrt(x);
  if(x == y*y) {
  // 有整数解
   p=(y+m) / 2;
   q=m-p;
   cout << min(p,q)<<" "<<max(p,q) << endl;
  } else {
  // 没有整数解
   cout <<"NO" << endl;
  }
 }
 return 0;
}

`100`分思路之二分算法

当一个长方形的周长一定时，长和宽怎么变化，它的面积最大 ?

反映到这个题上来，p和q分别相当于长和宽，pq=n即面积，p+q=m即周长。我们可以从1到m/2来枚举p (因为p<=q,所以枚举到m/2即可)。即从小到大枚举p，而q直接用m-p算出，这样可以让周长保持一定。当从小到大枚举p的过程中，p和q是逐渐接近的因此pq一定是逐渐变大的，这是一个单调的过程，我们在这个过程中就可以找到满足pq=n的那个点。

因为是单调的过程，因此我们可以优化“从小到大枚举p”为“二分枚举p”。二分的过程中逼近满足pq=n的那个p。具体为 :如果当前p下，pq=p(m-p)>n，说明面积过大，那么应该让p和q远离，即减小P。如果当前p下，pq=p(m-p)<n，说明面积过小，那么应该让p和q接近，即增加p。如果当前p下，pq=p(m-p)==n，那么说明找到了p。

根据刚才的分析，在1到m/2的范围内二分枚举p，算出q=m-p，再根据p*q和n的大小关系，分情况讨论向左还是向右继续枚举p

#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
ll k, n, d, e, m, p, q;
int main() {
 cin >> k;
 for (ll i = 1; i <= k; i ++) {
  cin >> n >> d >> e;
  m=n-e*d+2;
// p+q = m, p x q =n
  ll ok = 0;
  ll l = 1,r = m/2; // 在此范围内二分枚举p
  while (l <= r) {
   ll p=(l +r) / 2;
   ll q = m - p;// 算出q，固定周长m
   ll mian = p* q;// 算出面积
   if (mian > n) { // 让p和q远离
    r=p- 1;
   } else if (mian < n) { // 让p和q接近
    l= p + 1;
   } else { // 找到p*q正好==n的位置
    cout << p << " "<< q << endl;
    ok = 1;
    break;
   }
  }
  if (ok == 0) cout << "NO" << endl;
 }
 return 0;
}

第三题逻辑表达式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计入一处“短路”。

输入格式

输入共一行，一个非空字符串｀s｀表示待计算的逻辑表达式。

输出格式

输出共两行，第一行输出一个字符0或1，表示这个逻辑表达式的值;

第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和a | b的“短路"各出现了多少次。

输入输出样例

输入#1 输入#2

0 & ( 1 | 0 ) | ( 1 | 1| 1 & 0 ) ( 0 | 1 & 0 | 1 | 1 (1 | 1)) & ( 0 & 1 & (1 | 0)|0|0)&0

输出#1 输出#2

1 0

1 2 2 3

说明/提示

数范围

设|s|为字符串s的长度

对于所有数据，1<=|s|<=106。保证s 中仅含有字符0、1、&、|、(、)且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证s 中没有重复的括号嵌套(即没有形如((a))形式的子串，其中a是符合规范的逻辑表达式)。

#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;
}

第四题上升点列point

题目描述

在一个二维平面内，给定n个整数点(xi,yi)，此外你还可以自由添加k个整数点

你在自由添加k个点后，还需要从n+k个点中选出若个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为1而且横坐标、纵坐标值均单调不减，即 xi+1-xi=1，yi+1=yi 或 yi+1-yi=1，xi+1=xi 。请给出满足条件的序列的最大长度。

输入格式

第一行两个正整数n,k分别表示给定的整点个数、可自由添加的整点个数。

接下来n行，第i行两个正整数xi,yi表示给定的第i个点的横纵坐标

输出格式

输出一个整数表示满足要求的序列的最大长度。

输入输出样例

输入#1 输入#2

8 2 4 100

3 1 10 10

3 2 15 25

3 3 20 20

3 6 30 30

1 2

2 2

5 5

5 3

输出#1 输出#2

8 103

40分程序

#include <iostream>
#include <cstring>
using namespace std;

struct _pnt {
 int x,y;
} a[1005];
int n,k,ans,anstmp;
int vis[505];
//查找坐标是否存在
int exist(int x,int y) {
 for(int i=1; i<=n; i++) {
  if( a[i].x==x && a[i].y==y ) {
   return i;
  }
 }
 return -1;
}

void go(int i,int cnt) {
 if(vis[i])return;
 vis[i]=1;
 anstmp=max(anstmp,cnt);
 int newi=exist( a[i].x+1, a[i].y );
 if(newi!=-1) {
  go(newi,cnt+1);
 }
 newi=exist(a[i].x,a[i].y+1 );
 if(newi!=-1) {
  go(newi,cnt+1);
 }
}

int main() {
 cin >> n >> k;
 for (int i=1; i <= n; i ++) {
  cin >> a[i].x >> a[i].y;
 }
 for(int i=1; i<= n; i++) {
  memset(vis,0,sizeof(vis));
  anstmp = 0;// 以i号点进行搜索能走的最长路径
  go(i,1);// 以i号点为起点进行搜索
  ans = max(ans,anstmp); // 所有起点能走的最长路径
 }
 cout << ans;
 return 0;
}

60分程序

#include <iostream>
#include <cstring>
using namespace std;

struct _pnt {
 int x,y;
} a[1005];
int n,k,ans;
int you[105][105];//标记原始点的坐标存不存在
int f[105][105][105]; //dp 数组 当共补了z个点的情况下，到(x,y)点能连成的最多的点的个数

int main() {
 cin>>n>>k;
 for(int i=1; i<=n; i++) {
  cin>>a[i].x>>a[i].y;
 }

 for(int i=1; i<=n; i++ ) {
  you[a[i].x][a[i].y]=1;
 }

 for(int x=1; x<=100; x++ ) {
  for(int y=1; y<=100; y++ ) {
   for(int z=0; z<=k; z++ ) {
    if( you[x][y] ) {
     f[x][y][z]=max( f[x][y-1][z],f[x-1][y][z] )+1;
    } else {
     if(z>=1) {
      f[x][y][z]=max( f[x][y-1][z-1],f[x-1][y][z-1] )+1;
     }
    }
    ans=max(ans,f[x][y][z] );
   }
  }
 }

 cout<<ans;
 return 0;
}

70分程序

把40分和60分程序加一起。

100分程序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct _pnt {
 int x,y;
} a[1005];
int n,k,ans;
int f[105][105]; //dp 数组 f[i][z] 当共补了z个点的情况下，
//到第 i 个原始点能连成的最多的点的个数

int dis(int i,int j) { //从 j 到 i 共需要补的点的个数
 return abs( a[i].x-a[j].x   ) +abs( a[i].y-a[j].y  )  -1;
}

bool cmp(_pnt p1,_pnt p2) {
 if(p1.x==p2.x) return p1.y<p2.y;
 else return p1.x<p2.x;
}

int main() {

 cin >> n >> k;
 for (int i = 1; i <= n; i ++) {
  cin >> a[i].x >> a[i].y;
 }
 sort(a+1,a+n+1,cmp); // 排序，保证状态转移顺序的无后效性
 for (int i = 1; i <= n; i++) {
  int x = a[i].x, y = a[i].y;
  for (int z = 0; z <= k; z++) {
   f[i][z] = 1;
   for (int j= 1; j <= n; j++) {
    if (i != j && a[j].x <= x && a[j].y <= y) {//保证j在i的左下
     int len = dis(i,j); // 从j到i共需要补Len个点
     if (z >= len) {
     f[i][z] = max(f[i][z],f[j][z - len] + len + 1);
      // 多了Len+1个连续的点，+1表示第i个点自己
     }
    }
   }
   ans = max(ans,f[i][z] + k - z);// 从i把剩余的k-z个点疯狂延续出去
  }
 }
 cout << ans;
 return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-09-03，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自编程驿站微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度