2022 CSP-J第二轮复赛题解

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

第一题：乘方

题目描述

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

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

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

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

输入格式

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

输出格式

输出共一行，如果b的值不超过9，则输出ab的值，否则输出 。

输入输出样例

输入

输出

输入

2333366666

输出

-1

说明提示

对于 的数据，保证。

对于的数据，保证。

对于的数据，保证，ab≤1018。

对于的数据，保证。

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

分思路

对于 的数据，保证 ，18。乘方结果在范围内。因此直接循环次算，或者用函数算。但是用函数容易出现浮点误差，建议循环次直接算。

分思路

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

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

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

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

第二题 ：解密 decode

题目描述

给定一个正整数，有 次询问，每次给定三个正整数，求两个正整数 ，使。

输入格式

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

接下来行，第行三个正整数 。

输出格式

输出行，每行两个正整数 表示答案。

为使输出统一，你应当保证 。如果无解，请输出 。

输入输出样例

输入#1输出#1

数据范围

以下记。

保证对于 的数据，，对于任意的 i18，18，19。

分思路之代数方法

3

分思路之二分算法

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

4

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

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

根据刚才的分析，在到的范围内二分枚举，算出，再根据和的大小关系，分情况讨论向左还是向右继续枚举

第三题逻辑表达式expr

题目描述

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

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

;。

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

比如，表达式 的运算顺序等同于;表达式的运算顺序等同于。

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

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

输入格式

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

输出格式

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

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

输入输出样例

输入输入

输出#1输出#2

10

1223

说明/提示

数范围

设为字符串的长度

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

第四题上升点列point

题目描述

在一个二维平面内，给定个整数点，此外你还可以自由添加个整数点

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

输入格式

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

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

输出格式

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

输入输出样例

824 100

311010

321525

332020

36            3030

12

22

55

53

输出#1输出#2

8103

40分程序

60分程序

70分程序

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

100分程序