欢迎大家订阅我的专栏算法题解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_jCijAi×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优化#【代码详解】#includebits/stdc.husingnamespacestd;// 定义int为long long类型#defineintlonglong// 定义常量constintN100005;// 变量定义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, qcinnmq;// 读入序列a并初始化ST表for(inti1;in;i){cinazmax[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(inti1;im;i){cinbmax[i][0];// 读入序列b的第i个元素bmin[i][0]bmax[i][0];// 同时赋值给最小值}// 计算log2值intlenalog2(n);// 序列a的ST表最大层数intlenblog2(m);// 序列b的ST表最大层数// 构建序列a的非负数最大值ST表for(intj1;jlena;j){for(inti1;i(1j)-1n;i){azmax[i][j]max(azmax[i][j-1],azmax[i(1(j-1))][j-1]);}}// 构建序列a的非负数最小值ST表for(intj1;jlena;j){for(inti1;i(1j)-1n;i){azmin[i][j]min(azmin[i][j-1],azmin[i(1(j-1))][j-1]);}}// 构建序列a的负数最大值ST表for(intj1;jlena;j){for(inti1;i(1j)-1n;i){afmax[i][j]max(afmax[i][j-1],afmax[i(1(j-1))][j-1]);}}// 构建序列a的负数最小值ST表for(intj1;jlena;j){for(inti1;i(1j)-1n;i){afmin[i][j]min(afmin[i][j-1],afmin[i(1(j-1))][j-1]);}}// 构建序列b的最大值ST表for(intj1;jlenb;j){for(inti1;i(1j)-1m;i){bmax[i][j]max(bmax[i][j-1],bmax[i(1(j-1))][j-1]);}}// 构建序列b的最小值ST表for(intj1;jlenb;j){for(inti1;i(1j)-1m;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;// 初始化答案为负无穷// 读入查询区间cinx1y1x2y2;// 查询序列b在[x2,y2]区间的最大值和最小值intk2log2(y2-x21);maxymax(bmax[x2][k2],bmax[y2-(1k2)1][k2]);minymin(bmin[x2][k2],bmin[y2-(1k2)1][k2]);// 查询序列a在[x1,y1]区间的四种极值intk1log2(y1-x11);maxzxmax(azmax[x1][k1],azmax[y1-(1k1)1][k1]);// 非负数最大值minzxmin(azmin[x1][k1],azmin[y1-(1k1)1][k1]);// 非负数最小值maxfxmax(afmax[x1][k1],afmax[y1-(1k1)1][k1]);// 负数最大值minfxmin(afmin[x1][k1],afmin[y1-(1k1)1][k1]);// 负数最小值// 根据序列a和b的极值计算最大乘积if(minzx!INT_MAX)// 如果存在非负数{ansmax(ans,maxzx*miny);// 最大非负数 × 最小bansmax(ans,minzx*miny);// 最小非负数 × 最小b}if(maxfx!-INT_MAX)// 如果存在负数{ansmax(ans,maxfx*maxy);// 最大负数 × 最大bansmax(ans,minfx*maxy);// 最小负数 × 最大b}// 输出结果coutansendl;}return0;}【运行结果】3 2 2 0 1 -2 -3 4 1 3 1 2 0 2 3 2 2 4