2022CSP-J2题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了2022CSP-J2题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

今天(2022,10,29)， $C S P - J S$ 第二轮成功举办，~~虽然大部分省市疫情取消~~

本蒟蒻今天有幸参加CSP，特发入门组题解

T1 乘方

题目描述

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 $a$ 和 $b$ ，求 $a^b$ 的值是多少。

$a^b$ 即 $b$ 个 $a$ 相乘的值，例如 $2^3$ 即为 $3$ 个 $2$ 相乘，结果为 $\times 2 \times 2 = 8$ 。

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

小文很快意识到，她的程序里的变量都是 int 类型的。在大多数机器上，int 类型能表示的最大数为 $2^{31} - 1$ ，因此只要计算结果超过这个数，她的程序就会出现错误。

由于小文刚刚学会编程，她担心使用 int 计算会出现问题。因此她希望你在 $a^b$ 的值超过 ${10}^9$ 时，输出一个 -1 进行警示，否则就输出正确的 $a^b$ 的值。

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

输入格式

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

输出格式

输出共一行，如果 $a^b$ 的值不超过 ${10}^9$ ，则输出 $a^b$ 的值，否则输出 -1。

样例 #1

样例输入 #1

10 9

样例输出 #1

1000000000

样例 #2

样例输入 #2

23333 66666

样例输出 #2

-1

提示

对于 $\%$ 的数据，保证 $b = 1$ 。
对于 $\%$ 的数据，保证 $\le 2$ 。
对于 $\%$ 的数据，保证 $\le 30$ ， $a^b \le {10}^{18}$ 。
对于 $\%$ 的数据，保证 $\le a, b \le {10}^9$ 。

分析

送分题，循环求值，超过 $1 e 9$ 及时退出循环输 $- 1$ 即可

记得特判 $a = 1$ ~~(然而我忘了)~~

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

long long read(){
	long long f=1,r=0;
	char ch;
	do ch=getchar(); while(!isdigit(ch) && ch!='-');
	if(ch=='-') f=-1,ch=getchar();
	do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));
	return r*f;
}//快读 

ll a,b;
ll ans = 1;

int main(){
	a = read(); b = read();
	if(a == 1){
		cout << 1;
		return 0;
	}
	for(int i=1;i<=b;i++){
		ans *= a;
		if(ans > 1000000000){
			cout << "-1";
			return 0;
		}
	}
	cout << ans;
	return 0;
}

当然，本题也可以用快速幂，就不用判1了

#include<bits/stdc++.h>
#define ll long long
using namespace std;

long long read(){
	long long f=1,r=0;
	char ch;
	do ch=getchar(); while(!isdigit(ch) && ch!='-');
	if(ch=='-') f=-1,ch=getchar();
	do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));
	return r*f;
}//快读 

ll a,b;
ll ans = 1;

int main(){
	a = read(); b = read();
	for(;b;b>>=1,a=a*a){
		if(b&1)
			ans *= a;
		if(ans > 1000000000 || a > 1000000000){
            //不判a可能爆long long
			cout << "-1";
			return 0;
		}
	}
	cout << ans;
	return 0;
}

T2 解密

题目描述

给定一个正整数 $k$ ，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$ ，求两个正整数 $p_i, q_i$ ，使 $n_i = p_i \times q_i$ 、 $e_i \times d_i = (p_i - 1)(q_i - 1) + 1$ 。

输入格式

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

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i, d_i, e_i$ 。

输出格式

输出 $k$ 行，每行两个正整数 $p_i, q_i$ 表示答案。

为使输出统一，你应当保证 $p_i \leq q_i$ 。

如果无解，请输出 NO。

样例 #1

样例输入 #1

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

以下记 $\times d + 2$ 。

保证对于 $100\%$ 的数据， $\leq k \leq {10}^5$ ，对于任意的 $\leq i \leq k$ ， $\leq n_i \leq {10}^{18}$ ， $\leq e_i \times d_i \leq {10}^{18}$
， $\leq m \leq {10}^9$ 。

测试点编号	$\leq$	$\leq$	$\leq$	特殊性质
$1$	$10^3$	$10^3$	$10^3$	保证有解
$2$	$10^3$	$10^3$	$10^3$	无
$3$	$10^3$	$10^9$	$6\times 10^4$	保证有解
$4$	$10^3$	$10^9$	$6\times 10^4$	无
$5$	$10^3$	$10^9$	$10^9$	保证有解
$6$	$10^3$	$10^9$	$10^9$	无
$7$	$10^5$	$10^{18}$	$10^9$	保证若有解则 $p = q$
$8$	$10^5$	$10^{18}$	$10^9$	保证有解
$9$	$10^5$	$10^{18}$	$10^9$	无
$10$	$10^5$	$10^{18}$	$10^9$	无

分析

对没学过一元二次方程的部分小学生与初一初二学生极其不友好！！！！！

~~(不排除有超强小学生自学)~~

看到 $k, n, e, d$ 的范围就知道要推公式

记 $\times d + 2$ ~~话说数据范围提示的已经够明显的了~~

$m$ 是怎么来的呢？很简单
$\because n = p \times q，e \times d = (p - 1)(q - 1) + 1$

$\therefore e \times d=pq-p-q+2$

$\therefore e\times d = n - p-q+2$

$\therefore p+q = n-e\times d+2$

$\therefore m = n-e\times d+2 = p+ q$

那么既然 $n$ 已知， $n-e\times d+2$ 也是已知量，显然这是一个关于 $p, q$ 的一元二次方程组，那我们先消元
$\because q = m-p$

$\therefore n = p(m-p)$

$\therefore n = pm-p^2$

$\therefore p^2-pm+n =0$

那么根据根的判别式，对于一般的一元二次方程
$ax^2+bx+c=0(a\not=0)$
其有实数根仅当
$\Delta = b^2-4ac>=0$
其解为
$x=\frac{-b±\sqrt{b^2-4ac}}{2a}$
那么对于本题的方程，有
$\Delta=m^2-4n >= 0$
即其小于零或不是完全平方数时无解，那么
$\frac{m±\sqrt{\Delta}}{2}$

$\because p<=q$

$\therefore p =\frac{m-\sqrt{\Delta}}{2}， q = \frac{m+\sqrt{\Delta}}{2}$

因为 $p, q$ 是整数，所以当 $m+\sqrt{\Delta}$ 不能被2整除时，也算无解

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

long long read(){
	long long f=1,r=0;
	char ch;
	do ch=getchar(); while(!isdigit(ch) && ch!='-');
	if(ch=='-') f=-1,ch=getchar();
	do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));
	return r*f;
}//快读 

int k;

int main(){
	int k = read();
	while(k--){
		ll n = read(), d = read() , e = read();
		ll m = n-e*d+2;
		ll delta = m*m-4*n;
		if(delta < 0){//delta < 0,无解 
			puts("NO");
			continue;
		}
		ll a = sqrt(delta);
		if(a*a != delta){//delta不是完全平方数 
			puts("NO");
			continue;
		}
		if((m-a) & 1){//即不能被2整除 
			puts("NO");
			continue;
		}
		ll p = (m-a)/2 , q = m-p;
		printf("%lld %lld\n",p,q);
	}
	return 0;
}

T3 逻辑表达式

题目描述

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

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

$\mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0$ ， $\mathbin{\&} 1 = 1$ ；
$\mathbin{|} 0 = 0$ ， $\mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1$ 。

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

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

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 a&b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 0$ ，那么整个逻辑表达式的值就一定为 $0$ ，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 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

样例输入 #1

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

样例输出 #1

1
1 2

样例 #2

样例输入 #2

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

样例输出 #2

0
2 3

提示

【样例解释 #1】

该逻辑表达式的计算过程如下，每一行的注释表示上一行计算的过程：

0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1

【样例 #3】

见附件中的 expr/expr3.in 与 expr/expr3.ans。

【样例 #4】

见附件中的 expr/expr4.in 与 expr/expr4.ans。

【数据范围】

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

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

测试点编号	$\lvert s \rvert \le$	特殊条件
$\sim 2$	$3$	无
$\sim 4$	$5$	无
$5$	$2000$	1
$6$	$2000$	2
$7$	$2000$	3
$\sim 10$	$2000$	无
$\sim 12$	${10}^6$	1
$\sim 14$	${10}^6$	2
$\sim 17$	${10}^6$	3
$\sim 20$	${10}^6$	无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

字符串 0 和 1 是符合规范的；
如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
所有符合规范的逻辑表达式均可由以上方法生成。

分析

本题蒟蒻考场上没做出来，只骗了特殊情况的分

应该是可以递归求解

代码过后补充

T4 上升点列

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

【样例 #3】

见附件中的 point/point3.in 与 point/point3.ans。

第三个样例满足 $k = 0$ 。

【样例 #4】

见附件中的 point/point4.in 与 point/point4.ans。

【数据范围】

保证对于所有数据满足： $\leq n \leq 500$ ， $\leq k \leq 100$ 。对于所有给定的整点，其横纵坐标 $\leq x_i, y_i \leq {10}^9$ ，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号	$\leq$	$\leq$	$x_i,y_i \leq$
$\sim 2$	$10$	$0$	$10$
$\sim 4$	$10$	$100$	$100$
$\sim 7$	$500$	$0$	$100$
$\sim 10$	$500$	$0$	${10}^9$
$\sim 15$	$500$	$100$	$100$
$\sim 20$	$500$	$100$	${10}^9$

分析

先看 $n, k$ 的范围，显然可在 $O(n^2k)$ 复杂度解决

那么很容易看出这是一道 $d p$

既然是 $d p$ 就少不了状态

状态怎么找呢？看答案的转移需要哪些条件

显然，其转移与序列最后一个点的坐标和添加点的个数有关

那么容易得出

状态

设 $f_{i,j}$ 表示序列以 $i$ 为结尾，添加了 $j$ 个点序列的最大长度

初始值

当没添加点时，每个点可视为长度为一的序列

那么 $f_{i,0} = 1$

转移方程

分为添加点与不添加点两种情况

如果新的点满足与原来最后一个点的欧几里得距离为1且横纵坐标单调不减

~~说了那么多废话其实就是新点在原点正上或正右方~~

那么这个点可以加入序列，长度加一

反之，如果不满足就要自己添加点

读者可以画图，容易发现，对于两个点 $x_1,y_1),(x_2,y_2)$ 其中 $x_1<=x_2 ,y_1<=y_2$

需要添加的点数 $d=x_2-x_1+y_2-y_1-1$

可以发现当新点在原点正上或正右方时， $d = 0$ ，那么两种情况可以合并

即
$设d=x_2-x_1+y_2-y_1-1$

$f_{i,j} = \max_{k<i}{f_{k,j-d}}+d+1$
代码中则是

f[i][l+d] = max(f[i][l+d],f[j][l]+d+1);

这里的 $i, j$ 指的是新点原点的下标， $l$ 就是状态里的 $j$

答案

过程中找最大值

当然， $d p$ 过程中不一定会把添加的点全部用完，所以计算答案时应将其全部加上

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int n,k;
struct node{
	int x,y;
}a[N];
bool cmp(node x,node y){
	if(x.x == y.x) return x.y < y.y;
	return x.x < y.x;
}
int ans;
int f[N][N];

int main() {
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> a[i].x >> a[i].y;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		f[i][0] = 1;
		for(int j=1;j<i;j++){
			if(a[i].y < a[j].y) continue;
			int d = a[i].x-a[j].x+a[i].y-a[j].y-1;
			for(int l=0;l<=k;l++){
				if(l+d > k) continue;
				f[i][l+d] = max(f[i][l+d],f[j][l]+d+1);
				ans = max(ans,f[i][l+d]+k-l-d);
			}
		}
	}
	cout << ans;
    return 0;
}

最后

本人估分90+100+30+100 = 320

第一次参加就没满分…

while(true) rp--;

祝大家 $r p + +$ ，因疫情失去参赛机会的同学来年再战文章来源地址https://www.toymoban.com/news/detail-403676.html

到了这里，关于2022CSP-J2题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

2022CSP-J2题解

T1 乘方

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

分析

代码

T2 解密

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

分析

代码

T3 逻辑表达式

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

分析

T4 上升点列

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

分析

状态

初始值

转移方程

答案

代码

最后

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2