这道题不止一种做法,我用的是其中一种:贪心+RMQ
## 贪心的思路:
### 1.小L如果有正有负,分为三种情况:
#### (1)小Q只有正,这种情况对小Q不利,小L选择最大的正数(这里包括0,下同),小Q被逼的死路一条,只有选择最小的正数可以尽量实得分更小。
#### (2)小Q只有负,这种情况也对小Q不利,由于负负得正,小L选择绝对值最大的负数(相当于最小的负数),小Q没办法,只好选择绝对值最小的负数(相当于最大的负数),可以尽量实得分更小。
#### (3)小Q有正有负,这种情况对小Q有利,为何?因为小L出正,小Q出负,小L出负,小Q出正,小L不管怎么出,小Q都有办法使得它<=0,小L只能在出正或出负的情况选一个最小的,小L的第一个选择(正数),应选最小的正数,小Q就选最小的负数。小L的第二个选择(负数),应选最大的负数,小Q选最大的正数。
### 2.小L只有负,分为两种情况:
#### (1)小Q只有负,这种情况对小Q不利,由于负负得正,小L选择绝对值最大的负数(相当于最小的负数),小Q没办法,只好选择绝对值最小的负数(相当于最大的负数),可以尽量实得分更小。
#### (2)小Q只有正或有正有负,这种情况对小Q有利,小L没办法,选绝对值最小的负数(相当于最大的负数),小Q选择最大的正数。
### 3.小L只有正,分为两种情况:
#### (1)小Q只有正,这种情况对小Q不利,小L选择最大的正数,小Q选最小的正数。
#### (2)小Q只有负或有正有负,这种情况对小Q有利,小L没办法,只好选择最小的的正数,小Q选择绝对值最大的负数(相当于最小的负数)。
## 代码部分:
### 准备八个数组:fza,fza1,fzb,fzb1,ffa,ffa1,ffb,ffb1,分别代表小L正数最大值、小L正数最小值、小Q正数最大值、小Q正数最小值、小L负数最大值、小L负数最小值、小Q负数最大值、小Q负数最小值。
### 初始化:属于这个部分的(负数或正数)就直接赋值,否则是大的就-1e10,小的就1e10。
### 剩下的就按思路做。
### 代码:
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5; int a[N]; int b[N]; int fza[N][20]; int fza1[N][20]; int fzb[N][20]; int fzb1[N][20]; int ffa[N][20]; int ffa1[N][20]; int ffb[N][20]; int ffb1[N][20]; int n,q,m; signed main() { scanf("%lld %lld %lld",&n,&m,&q); for(int i = 1;i<=n;i++) { scanf("%lld",&a[i]); fza[i][0] = a[i]>=0?a[i]:(int)-1e10; fza1[i][0] = a[i]>=0?a[i]:(int)1e10; ffa[i][0] = a[i]<0?a[i]:(int)-1e10; ffa1[i][0] = a[i]<0?a[i]:(int)1e10; } for(int i = 1;i<=m;i++) { scanf("%lld",&b[i]); fzb[i][0] = b[i]>=0?b[i]:(int)-1e10; fzb1[i][0] = b[i]>=0?b[i]:(int)1e10; ffb[i][0] = b[i]<0?b[i]:(int)-1e10; ffb1[i][0] = b[i]<0?b[i]:(int)1e10; } for(int i = 1;i<=log2(n);i++) { for(int j = 1;j<=n-(1<<i)+1;j++) { fza[j][i] = max(fza[j][i-1],fza[j+(1<<(i-1))][i-1]); fza1[j][i] = min(fza1[j][i-1],fza1[j+(1<<(i-1))][i-1]); ffa[j][i] = max(ffa[j][i-1],ffa[j+(1<<(i-1))][i-1]); ffa1[j][i] = min(ffa1[j][i-1],ffa1[j+(1<<(i-1))][i-1]); } } for(int i = 1;i<=log2(m);i++) { for(int j = 1;j<=m-(1<<i)+1;j++) { fzb[j][i] = max(fzb[j][i-1],fzb[j+(1<<(i-1))][i-1]); fzb1[j][i] = min(fzb1[j][i-1],fzb1[j+(1<<(i-1))][i-1]); ffb[j][i] = max(ffb[j][i-1],ffb[j+(1<<(i-1))][i-1]); ffb1[j][i] = min(ffb1[j][i-1],ffb1[j+(1<<(i-1))][i-1]); } } for(int i = 1;i<=q;i++) { int la,ra,lb,rb; scanf("%lld %lld %lld %lld",&la,&ra,&lb,&rb); int kl = log2(ra-la+1); int num; int kr = log2(rb-lb+1); if(max(fza[la][kl],fza[ra-(1<<kl)+1][kl])!=(int)-1e10&&max(ffa[la][kl],ffa[ra-(1<<kl)+1][kl])!=(int)-1e10) { if(max(ffb[lb][kr],ffb[rb-(1<<kr)+1][kr]) == (int)-1e10) { num = max(fza[la][kl],fza[ra-(1<<kl)+1][kl])*min(fzb1[lb][kr],fzb1[rb-(1<<kr)+1][kr]); } if(max(fzb[lb][kr],fzb[rb-(1<<kr)+1][kr]) == (int)-1e10) { num = min(ffa1[la][kl],ffa1[ra-(1<<kl)+1][kl])*max(ffb[lb][kr],ffb[rb-(1<<kr)+1][kr]); } if(max(fzb[lb][kr],fzb[rb-(1<<kr)+1][kr])!=(int)-1e10&&max(ffb[lb][kr],ffb[rb-(1<<kr)+1][kr])!=(int)-1e10) { int L1 = min(fza1[la][kl],fza1[ra-(1<<kl)+1][kl])*min(ffb1[lb][kr],ffb1[rb-(1<<kr)+1][kr]),L2 = max(ffa[la][kl],ffa[ra-(1<<kl)+1][kl])*max(fzb[lb][kr],fzb[rb-(1<<kr)+1][kr]); num = max(L1,L2); } } if(max(fza[la][kl],fza[ra-(1<<kl)+1][kl]) == (int)-1e10&&max(ffa[la][kl],ffa[ra-(1<<kl)+1][kl])!=(int)-1e10) { if(max(fzb[lb][kr],fzb[rb-(1<<kr)+1][kr]) == (int)-1e10&&max(ffb[lb][kr],ffb[rb-(1<<kr)+1][kr])!=(int)-1e10) { num = min(ffa1[la][kl],ffa1[ra-(1<<kl)+1][kl])*max(ffb[lb][kr],ffb[rb-(1<<kr)+1][kr]); } else { num = max(ffa[la][kl],ffa[ra-(1<<kl)+1][kl])*max(fzb[lb][kr],fzb[rb-(1<<kr)+1][kr]); } } if(max(fza[la][kl],fza[ra-(1<<kl)+1][kl])!=(int)-1e10&&max(ffa[la][kl],ffa[ra-(1<<kl)+1][kl]) == (int)-1e10) { if(max(fzb[lb][kr],fzb[rb-(1<<kr)+1][kr])!=(int)-1e10&&max(ffb[lb][kr],ffb[rb-(1<<kr)+1][kr]) == (int)-1e10) { num = max(fza[la][kl],fza[ra-(1<<kl)+1][kl])*min(fzb1[lb][kr],fzb1[rb-(1<<kr)+1][kr]); } else { num = min(fza1[la][kl],fza1[ra-(1<<kl)+1][kl])*min(ffb1[lb][kr],ffb1[rb-(1<<kr)+1][kr]); } } printf("%lld\n",num); } return 0; }
题目3782 [CSP 2022S]策略游戏
AAAAAAAAAAAAAAAAAAAA
6
评论
2024-01-06 19:03:41
|
|
可以用RMQ
#include<bits/stdc++.h> using namespace std; const int N = 1e6; int a[N]; int f[N][20]; int n,k; int main() { scanf("%d %d",&n,&k); for(int i = 1;i<=n;i++) { scanf("%d",&a[i]); f[i][0] = a[i]; } for(int i = 1;i<=log2(n);i++) { for(int j = 1;j<=n-(1<<i)+1;j++) { f[j][i] = min(f[j][i-1],f[j+(1<<(i-1))][i-1]); } } for(int i = 1;i+k-1<=n;i++) { int x = i,y = i+k-1; int k = log2(y-x+1); printf("%d ",min(f[x][k],f[y-(1<<k)+1][k])); } printf("\n"); for(int i = 1;i<=n;i++) { f[i][0] = a[i]; } for(int i = 1;i<=log2(n);i++) { for(int j = 1;j<=n-(1<<i)+1;j++) { f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]); } } for(int i = 1;i+k-1<=n;i++) { int x = i,y = i+k-1; int k = log2(y-x+1); printf("%d ",max(f[x][k],f[y-(1<<k)+1][k])); } return 0; }
题目495 [POJ 2823]滑动窗口
AAAAAAAAA
2
评论
2024-01-06 18:47:43
|