2022CSP-J 题解[完整版]-Toy模板网

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

前言

“西西弗”的脑子是被宇宙射线影响了吗，造的题目我都写到睡着了……

T 1 T1 T1 [CSP-J 2022] 乘方

题目描述

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 $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$ 。

分析

这道题很简单啊。因为它的数据范围比较大，所以我们只需要用一个快速幂来计算，在每次res=res*a时判断一下是否大于 $10^9$ 即可。
特判： $10^9$ 这个数有点特别，因为它的平方已经超 $l o n g l o n g$ 了，所以我们要在快速幂之前判断一下 $10^9$ 这个数，如果 $b$ 大于1，直接输出 $- 1$ 。

CODE

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int inf=1e9;
int n,m;

int qmi(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a;
			if(ans>inf||ans<0) return -1;
		}
		a=a*a,b>>=1;
	}
	if(ans<0||ans>inf) return -1;
	return ans;
}

signed main() 
{
	cin>>n>>m;
	
	if(n>inf||(m>64&&n!=1)) return cout<<-1,0;
	cout<<qmi(n,m);
	
	return 0;
}

总结

就是以个模板题，当然也可以直接 $O (n)$ 循环，做法差不多。

T 2 T2 T2 [CSP-J 2022] 解密

题目描述

给定一个正整数 $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

提示

【数据范围】

以下记 $\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$	无

分析

根据题目下面的： $m = n - e \times d + 2$ ，我们可以推断出： $p + q = m$ 。然后用二分来查找 $p, q$ ，只要有一次的 $mi d = n$ ，就输出。否则输出 $- 1$ 。

CODE

#include<bits/stdc++.h>
#define int long long

using namespace std;

int aa(int n,int m)
{
	int L=0,R=(m>>1);
	
	while(L<=R)
	{
		int mid=L+((R-L)>>1);
		int sum=mid*(m-mid);//mid与m-mid表示每次查找的pq
		
		if(sum==n)//pq相乘是否等于n
		{
			return mid;
		}
		else 
		{
			if(sum>n)
			{
				R=mid-1;
			}
			else
			{
				L=mid+1;
			}
		}
	}
	
	return -1;//无解
}

int t;

signed main()
{
	cin>>t;
	
	while(t--)
	{
		int n,e,d;
		cin>>n>>e>>d;
		
		int m=n-e*d+2;
		
		int ans=aa(n,m);//二分查找
		
		if(ans!=-1)
		{
			cout<<ans<<" "<<m-ans<<endl;
		}
		else
		{
			cout<<"NO\n";
		}
	}
	
	return 0;
}

总结

这道题思路还是比较简单，就是二分这个不容易想起来（导致我TLE了）。

T 3 T3 T3 [CSP-J 2022] 逻辑表达式

题目描述

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

在一个逻辑表达式中，元素的值只有两种可能： $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

【数据范围】

设 $\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 均是符合规范的；
所有符合规范的逻辑表达式均可由以上方法生成。

分析

一道经典大模拟啊，根据题意做就行了。唯一的难点应该就是有先级，这个必须按照括号，按位与，按位或的顺序计算。

CODE

#include<bits/stdc++.h>

using namespace std;

const int S=1000010;
char s[S];

int li[S],ce[S],ls[S],la[S],sk[S];

int work(int l,int r,int &tand,int &tor)//大模拟函数
{
	while(li[r]==l)
	{
		r--;
		l++;
	}
	if(l==r&&isdigit(s[l]))
	{
		return s[l]-'0';
	}
	int opt=2,w=0;
	
	if(ls[r]>=l)
	{
		opt=0;
		w=ls[r];
	}
	else
	{
		opt=1;
		w=la[r];
	}
	
	int lsum=work(l,w-1,tand,tor);
	
	if((!lsum)&&opt)
	{
		tand++;
		return 0;
	}
	else 
	{
		if(lsum&&(!opt))
		{
			tor++;
			return 1;
		}
	}
	
	int rsum=work(w+1,r,tand,tor);
	
	if(opt==1)
	{
		return lsum&rsum;
	}
	else
	{
		return lsum|rsum;
	}
}

int main()
{
	scanf("%s",s+1);

	int tot=0;
	
	for(int i=1;i<=strlen(s+1);i++)
	{
		if(s[i]=='(')
		{
			sk[++tot]=i;
		}
		if(s[i]==')')
		{
			int lst=sk[tot--];
			li[i]=lst;
		}
		
		ce[i]=tot;
	}
	for(int i=0;i<=strlen(s+1);i++)
	{
		sk[i]=0;
	}
	for(int i=1;i<=strlen(s+1);i++)
	{
		if(s[i]=='|')
		{
			sk[ce[i]]=i;
		}
		
		ls[i]=sk[ce[i]];
	}
	for(int i=0;i<=strlen(s+1);i++)
	{
		sk[i]=0;
	}
	
	for(int i=1;i<=strlen(s+1);i++)
	{
		if(s[i]=='&')
		{
			sk[ce[i]]=i;
		}
		
		la[i]=sk[ce[i]];
	}
	
	int tand=0,tor=0;
	
	printf("%d\n",work(1,strlen(s+1),tand,tor));
	
	printf("%d %d",tand,tor);
	
	return 0;
}

总结

题目本身不是很难，就是CSP这次的题面有点难懂，很啰嗦，导致很多人选择放弃。

T 4 T4 T4 [CSP-J 2022] 上升点列

题目描述

在一个二维平面内，给定 $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

提示

【数据范围】

保证对于所有数据满足： $\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$

分析

用动态规划啊。
题目中的 “ 两点间的欧几里得距离恰好为 $1$ ” 就相当于点 $x_{1},y_{1}),(x_{2},y_{2})$ 中 $\left | x_{1}-x_{2} \right |+\left | y_{1}-y_{2} \right |=1$
那么我们就令 $f [i] [j]$ 表示当前的第 $i$ 个点添加了 $j$ 个点后，最大的个数。再令 $s=\left | x_{1}-x_{2} \right |+\left | y_{1}-y_{2} \right |+1$ 。则可得到状态转移方程： $f[i]{[x+s]}=max(f[i]{[x+s}],f[j][x]+s+1)$ 。且 $f [i] [0]$ 是等于 $1$ 的。

CODE

#include<bits/stdc++.h>

using namespace std;

struct aa{
	
	int x,y;
	
}a[10000000];
bool cmp(aa x,aa y)//排序使用
{
	if(x.x==y.x)
	{
		return x.y<y.y;
	}
	else
	{
		return x.x<y.x;
	}
}

int f[2000][2000];//状态转移数组

int n,k;

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);//从小到大排序
	
	int ans=0;
	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;
			}
			else
			{
				int s=a[i].x-a[j].x+a[i].y-a[j].y-1;
				
				for(int x=0;x<=k;x++)
				{
					if(x+s>k)//不满足要求
					{
						break;
					}
					
					f[i][x+s]=max(f[i][x+s],f[j][x]+s+1);//DP
					ans=max(ans,f[i][x + s]+k-x-s);//取最大
				}
			}
		}
	}
	
	cout<<ans;//输出答案
	
	return 0;
}

总结

就是一个普通的动态规划，只要我们能够考虑到 $s$ ，并且知道欧几里得距离是什么，就很简单了。

后序

关于这次的 $CSP$ ，我已经爆 $0$ 了。我真的无言以对，我在考场上，究竟做了些什么？[大无语] [大无语] [大无语]文章来源地址https://www.toymoban.com/news/detail-496755.html

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

2022CSP-J 题解[完整版]

前言

T 1 T1 T1 [CSP-J 2022] 乘方

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

分析

CODE

总结

T 2 T2 T2 [CSP-J 2022] 解密

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

分析

CODE

总结

T 3 T3 T3 [CSP-J 2022] 逻辑表达式

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

分析

CODE

总结

T 4 T4 T4 [CSP-J 2022] 上升点列

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

分析

CODE

总结

后序

相关文章

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

支付宝扫一扫打赏

微信扫一扫打赏

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

二维码1

二维码2