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

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷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【解题思路】【算法标签】#普及# #ST表#【代码详解】#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