有没有做catalog的网站,wordpress分类目录分页显示,新媒体营销的概念,网站建设与维护 国赛[CSP-S 2022] 策略游戏
题目描述
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 n n n 的数组 A A A 和一个长度为 m m m 的数组 B B B#xff0c;在此基础上定义一个大小为 n m n \times m nm 的矩阵 C C C#xff0c;满足 C i j A i B j C_{i j} A_i \times …[CSP-S 2022] 策略游戏
题目描述
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 n n n 的数组 A A A 和一个长度为 m m m 的数组 B B B在此基础上定义一个大小为 n × m n \times m n×m 的矩阵 C C C满足 C i j A i × B j C_{i j} A_i \times B_j CijAi×Bj。所有下标均从 1 1 1 开始。
游戏一共会进行 q q q 轮在每一轮游戏中会事先给出 4 4 4 个参数 l 1 , r 1 , l 2 , r 2 l_1, r_1, l_2, r_2 l1,r1,l2,r2满足 1 ≤ l 1 ≤ r 1 ≤ n 1 \le l_1 \le r_1 \le n 1≤l1≤r1≤n、 1 ≤ l 2 ≤ r 2 ≤ m 1 \le l_2 \le r_2 \le m 1≤l2≤r2≤m。
游戏中小 L 先选择一个 l 1 ∼ r 1 l_1 \sim r_1 l1∼r1 之间的下标 x x x然后小 Q 选择一个 l 2 ∼ r 2 l_2 \sim r_2 l2∼r2 之间的下标 y y y。定义这一轮游戏中二人的得分是 C x y C_{x y} Cxy。
小 L 的目标是使得这个得分尽可能大小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家每次都会采用最优的策略。
请问按照二人的最优策略每轮游戏的得分分别是多少
输入格式
第一行输入三个正整数 n , m , q n, m, q n,m,q分别表示数组 A A A数组 B B B 的长度和游戏轮数。
第二行 n n n 个整数表示 A i A_i Ai分别表示数组 A A A 的元素。
第三行 m m m 个整数表示 B i B_i Bi分别表示数组 B B B 的元素。
接下来 q q q 行每行四个正整数表示这一次游戏的 l 1 , r 1 , l 2 , r 2 l_1, r_1, l_2, r_2 l1,r1,l2,r2。
输出格式
输出共 q q q 行每行一个整数分别表示每一轮游戏中小 L 和小 Q 在最优策略下的得分。
样例 #1
样例输入 #1
3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2样例输出 #1
0
4样例 #2
样例输入 #2
6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3样例输出 #2
0
-2
3
2
-1提示
【样例解释 #1】
这组数据中矩阵 C C C 如下 [ 0 0 − 3 4 6 − 8 ] \begin{bmatrix} 0 0 \\ -3 4 \\ 6 -8 \end{bmatrix} 0−3604−8
在第一轮游戏中无论小 L 选取的是 x 2 x 2 x2 还是 x 3 x 3 x3小 Q 都有办法选择某个 y y y 使得最终的得分为负数。因此小 L 选择 x 1 x 1 x1 是最优的因为这样得分一定为 0 0 0。
而在第二轮游戏中由于小 L 可以选 x 2 x 2 x2小 Q 只能选 y 2 y 2 y2如此得分为 4 4 4。
【样例 #3】
见附件中的 game/game3.in 与 game/game3.ans。
【样例 #4】
见附件中的 game/game4.in 与 game/game4.ans。
【数据范围】
对于所有数据 1 ≤ n , m , q ≤ 10 5 1 \le n, m, q \le {10}^5 1≤n,m,q≤105 − 10 9 ≤ A i , B i ≤ 10 9 -{10}^9 \le A_i, B_i \le {10}^9 −109≤Ai,Bi≤109。对于每轮游戏而言 1 ≤ l 1 ≤ r 1 ≤ n 1 \le l_1 \le r_1 \le n 1≤l1≤r1≤n 1 ≤ l 2 ≤ r 2 ≤ m 1 \le l_2 \le r_2 \le m 1≤l2≤r2≤m。
测试点编号 n , m , q ≤ n, m, q \le n,m,q≤特殊条件 1 1 1 200 200 2001, 2 2 2 2 200 200 2001 3 3 3 200 200 2002 4 ∼ 5 4 \sim 5 4∼5 200 200 200无 6 6 6 1000 1000 10001, 2 7 ∼ 8 7 \sim 8 7∼8 1000 1000 10001 9 ∼ 10 9 \sim 10 9∼10 1000 1000 10002 11 ∼ 12 11 \sim 12 11∼12 1000 1000 1000无 13 13 13 10 5 {10}^5 1051, 2 14 ∼ 15 14 \sim 15 14∼15 10 5 {10}^5 1051 16 ∼ 17 16 \sim 17 16∼17 10 5 {10}^5 1052 18 ∼ 20 18 \sim 20 18∼20 10 5 {10}^5 105无
其中特殊性质 1 为保证 A i , B i 0 A_i, B_i 0 Ai,Bi0。 特殊性质 2 为保证对于每轮游戏而言要么 l 1 r 1 l_1 r_1 l1r1要么 l 2 r 2 l_2 r_2 l2r2。
前置题目ST表
ST表模板
#includebits/stdc.h
#define int long long int
using namespace std;
const int N2e5123;
int n,m;
int a[N],rmax[N][27];
void rmq(){for(int i1;(1i)n;i){for(int j1;jn;j){rmax[j][i]max(rmax[j][i-1],rmax[j(1(i-1))][i-1]);}}
}
int query(int l,int r){int klog2(r-l1);return max(rmax[l][k],rmax[r-(1k)1][k]);
}
signed main(){scanf(%lld%lld,n,m);for(int i1;in;i){scanf(%lld,a[i]);rmax[i][0]a[i];}rmq();for(int i1,l,r;im;i){scanf(%lld%lld,l,r);int kquery(l,r);printf(%lld\n,k);}return 0;
} 大致思路
小 L L L 和小 Q Q Q 都会跟据对方的数字来选择自己的数字且都很聪明那么就可以有许多种情况 设小 L L L 取出的为 A A A 小 Q Q Q 取出的是 B B B
当 A 0 A0 A0或 B 0 B0 B0
无论谁取到了 0 0 0 无需讨论 a n s 0 ans0 ans0
当 A 0 A0 A0
若 B 0 B0 B0,则 A A A取 m a x max max B B B取 m i n min min 若 B 0 B0 B0,则 A A A取 m i n min min B B B取 m a x max max 且 B B B能取到负值是一定会取负值
当 A 0 A0 A0
若 B 0 B0 B0,则 A A A取 m a x max max B B B取 m a x max max 若 B 0 B0 B0,则 A A A取 m i n min min B B B取 m i n min min 且 B B B能取到正数 m a x max max的值就一定会取正数 m a x max max的值
由此可见我们只需要求出以下四个区间最值
非负最大值非负最小值非正数最大值非正数最小值
一般来说我们需要按照上面讨论的进行 i f if if 语句判断 但有一种逃课的思路 a n s ans ans一定在四个最值的两两乘积之间 那么只需要枚举取 m a x max max即可总计 4 ∗ 4 16 4*416 4∗416次不会超时
AC CODE
#includebits/stdc.h
#define int long long
#includecstdio
using namespace std;
int n,m,q,a[100010],b[100010];
struct re{int a,b,c,d;
};
struct nod{int ST1[100010][20],ST2[100010][20],ST3[100010][20],ST4[100010][20];void bulid(int *p,int len){for(int i1;ilen;i){ST1[i][0]p[i];if(p[i]0){ST2[i][0]p[i];}else{ST2[i][0]2e9;}ST3[i][0]p[i];if(p[i]0){ST4[i][0]-2e9;}else{ST4[i][0]p[i];}}for(int j1;jlog2(len);j){for(int i1;ilen-(1j)1;i){ST1[i][j]min(ST1[i][j-1],ST1[i(1(j-1))][j-1]);ST2[i][j]min(ST2[i][j-1],ST2[i(1(j-1))][j-1]);ST3[i][j]max(ST3[i][j-1],ST3[i(1(j-1))][j-1]);ST4[i][j]max(ST4[i][j-1],ST4[i(1(j-1))][j-1]);}}}re query(int l,int r){int lenr-l1;int plog2(len);int amin(ST1[l][p],ST1[r-(1p)1][p]);int bmin(ST2[l][p],ST2[r-(1p)1][p]);int cmax(ST3[l][p],ST3[r-(1p)1][p]);int dmax(ST4[l][p],ST4[r-(1p)1][p]);return re{a,b,c,d};}
}ST1,ST2;
signed main(){scanf(%lld%lld%lld,n,m,q);for(int i1;in;i){scanf(%lld,a[i]);}for(int i1;im;i){scanf(%lld,b[i]);}ST1.bulid(a,n);ST2.bulid(b,m);while(q--){int l1,r1,l2,r2;scanf(%lld%lld%lld%lld,l1,r1,l2,r2);re tmp1ST1.query(l1,r1);re tmp2ST2.query(l2,r2);int ansmax(min(tmp1.c*tmp2.a,tmp1.c*tmp2.c),min(tmp1.a*tmp2.c,tmp1.a*tmp2.a));if(tmp1.b1e9){ansmax(ans,(int)tmp1.b*(int)tmp2.a);}if(tmp1.d-1e9){ansmax(ans,(int)tmp1.d*(int)tmp2.c);}printf(%lld\n,ans);}return 0;
}封面
