历年CSP-S复赛真题解析 | 2022年CSP-S复赛-深圳市維司達科技有限公司

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总贴：历年CSP-S复赛真题解析 | 汇总

P8818 策略游戏

【题目来源】

洛谷：[P8818 CSP-S 2022] 策略游戏 - 洛谷

【题目描述】

小 L 和小 Q 在玩一个策略游戏。

有一个长度为n nn的数组A AA和一个长度为m mm的数组B BB，在此基础上定义一个大小为n × m n \times mn×m的矩阵C CC，满足C i j = A i × B j C_{i j} = A_i \times B_jCij=Ai×Bj。所有下标均从1 11开始。

游戏一共会进行q qq轮，在每一轮游戏中，会事先给出4 44个参数l 1 , r 1 , l 2 , r 2 l_1, r_1, l_2, r_2l1,r1,l2,r2，满足1 ≤ l 1 ≤ r 1 ≤ n 1 \le l_1 \le r_1 \le n1≤l1≤r1≤n、1 ≤ l 2 ≤ r 2 ≤ m 1 \le l_2 \le r_2 \le m1≤l2≤r2≤m。

游戏中，小 L 先选择一个l 1 ∼ r 1 l_1 \sim r_1l1∼r1之间的下标x xx，然后小 Q 选择一个l 2 ∼ r 2 l_2 \sim r_2l2∼r2之间的下标y yy。定义这一轮游戏中二人的得分是C x y C_{x y}Cxy。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

【输入】

第一行输入三个正整数n , m , q n, m, qn,m,q，分别表示数组A AA，数组B BB的长度和游戏轮数。

第二行：n nn个整数，表示A i A_iAi，分别表示数组A AA的元素。

第三行：m mm个整数，表示B i B_iBi，分别表示数组B BB的元素。

接下来q qq行，每行四个正整数，表示这一次游戏的l 1 , r 1 , l 2 , r 2 l_1, r_1, l_2, r_2l1,r1,l2,r2。

【输出】

输出共q qq行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。

【输入样例】

3 2 2 0 1 -2 -3 4 1 3 1 2 2 3 2 2

【输出样例】

0 4

【算法标签】

《洛谷 P8818 策略游戏》 #贪心# #线段树# #ST表# #CSP-S提高级# #2022# #O2优化#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义int为long long类型#defineintlonglong// 定义常量constintN=100005;// 变量定义intn,m,q;// n: 第一个序列长度, m: 第二个序列长度, q: 查询次数// ST表数组intazmax[N][32];// 存储序列a中非负数的最大值intazmin[N][32];// 存储序列a中非负数的最小值intafmax[N][32];// 存储序列a中负数的最大值intafmin[N][32];// 存储序列a中负数的最小值intbmax[N][32];// 存储序列b的最大值intbmin[N][32];// 存储序列b的最小值signedmain(){// 读入n, m, qcin>>n>>m>>q;// 读入序列a并初始化ST表for(inti=1;i<=n;i++){cin>>azmax[i][0];// 读入序列a的第i个元素if(azmax[i][0]<0)// 如果是负数{// 负数存储在afmax和afmin中afmax[i][0]=afmin[i][0]=azmax[i][0];// 非负数表设为无效值azmax[i][0]=-1;// 非负最大值设为-1azmin[i][0]=INT_MAX;// 非负最小值设为极大值}else// 如果是非负数{// 非负数存储在azmax和azmin中azmin[i][0]=azmax[i][0];// 负数表设为无效值afmax[i][0]=-INT_MAX;// 负最大值设为负无穷afmin[i][0]=0;// 负最小值设为0}}// 读入序列b并初始化ST表for(inti=1;i<=m;i++){cin>>bmax[i][0];// 读入序列b的第i个元素bmin[i][0]=bmax[i][0];// 同时赋值给最小值}// 计算log2值intlena=log2(n);// 序列a的ST表最大层数intlenb=log2(m);// 序列b的ST表最大层数// 构建序列a的非负数最大值ST表for(intj=1;j<=lena;j++){for(inti=1;i+(1<<j)-1<=n;i++){azmax[i][j]=max(azmax[i][j-1],azmax[i+(1<<(j-1))][j-1]);}}// 构建序列a的非负数最小值ST表for(intj=1;j<=lena;j++){for(inti=1;i+(1<<j)-1<=n;i++){azmin[i][j]=min(azmin[i][j-1],azmin[i+(1<<(j-1))][j-1]);}}// 构建序列a的负数最大值ST表for(intj=1;j<=lena;j++){for(inti=1;i+(1<<j)-1<=n;i++){afmax[i][j]=max(afmax[i][j-1],afmax[i+(1<<(j-1))][j-1]);}}// 构建序列a的负数最小值ST表for(intj=1;j<=lena;j++){for(inti=1;i+(1<<j)-1<=n;i++){afmin[i][j]=min(afmin[i][j-1],afmin[i+(1<<(j-1))][j-1]);}}// 构建序列b的最大值ST表for(intj=1;j<=lenb;j++){for(inti=1;i+(1<<j)-1<=m;i++){bmax[i][j]=max(bmax[i][j-1],bmax[i+(1<<(j-1))][j-1]);}}// 构建序列b的最小值ST表for(intj=1;j<=lenb;j++){for(inti=1;i+(1<<j)-1<=m;i++){bmin[i][j]=min(bmin[i][j-1],bmin[i+(1<<(j-1))][j-1]);}}// 查询变量intx1,y1,x2,y2;// 查询区间：a的[x1,y1]，b的[x2,y2]intmaxy,miny;// 序列b在查询区间的最大值和最小值intmaxzx,maxfx,minzx,minfx;// 序列a在查询区间的四种极值// 处理每个查询while(q--){intans=-1e18;// 初始化答案为负无穷// 读入查询区间cin>>x1>>y1>>x2>>y2;// 查询序列b在[x2,y2]区间的最大值和最小值intk2=log2(y2-x2+1);maxy=max(bmax[x2][k2],bmax[y2-(1<<k2)+1][k2]);miny=min(bmin[x2][k2],bmin[y2-(1<<k2)+1][k2]);// 查询序列a在[x1,y1]区间的四种极值intk1=log2(y1-x1+1);maxzx=max(azmax[x1][k1],azmax[y1-(1<<k1)+1][k1]);// 非负数最大值minzx=min(azmin[x1][k1],azmin[y1-(1<<k1)+1][k1]);// 非负数最小值maxfx=max(afmax[x1][k1],afmax[y1-(1<<k1)+1][k1]);// 负数最大值minfx=min(afmin[x1][k1],afmin[y1-(1<<k1)+1][k1]);// 负数最小值// 根据序列a和b的极值计算最大乘积if(minzx!=INT_MAX)// 如果存在非负数{ans=max(ans,maxzx*miny);// 最大非负数 × 最小bans=max(ans,minzx*miny);// 最小非负数 × 最小b}if(maxfx!=-INT_MAX)// 如果存在负数{ans=max(ans,maxfx*maxy);// 最大负数 × 最大bans=max(ans,minfx*maxy);// 最小负数 × 最大b}// 输出结果cout<<ans<<endl;}return0;}