题意
如题目的图所示,每行都可以左右移动,但是数字不允许断开,且不许越界(宽度为w)。
单独求每一列的最大的和为多少。
思路
对于每一列来说,在每一行上都有一个可以取到的区间,
所以,对于一列来说,答案就是每行的区间最大值的和。区间最大值可以用RMQ或者单调队列求。
一开始题目看错了,以为是w*n<=1e6,其实是w<=1e6,n<=1e6,Σleni<=1e6(leni为第i行的长度),直接上w*n*log,果断T了。
显然,当leni 比w小很多时,中间会有很多列都可以取到整行的所有数字,所以对于这些列,它们求的区间最大值,其实就是整行的最大值。
对于头尾的一些列,取不到所有数字,那我们就暴力算出它们可以取到的区间,然后查询。
由于w*n<=1e12,而中间那些列查出来的最大值其实是一样的,所以可以用差分。
(一些细节)
有时候查询出来的区间最大值是负数,但是有时候其实可以取到0(移到空格),而有时候只能取负数(移不到空格)。
len <= i <= w - len + 1 符合条件的第i列可以取到整行
当整行都为负数时,
有时候第len列和第(w-len+1)列只能取负数,
但是,第len+1列和第(w-len+1 - 1)列一定可以取到空格,也就是0
所以,我们把第len列和第(w-len+1)列,归为暴力算的部分,因为暴力算的时候,都有特判是否可以取0。
这样,中间的那些就可以直接max(0,rmq(1,len))了
代码(RMQ)
(我的姿势比较差,代码又长,跑的还慢,跑了700+ms)
#include <stdio.h> #include <queue> #include <string> #include <string.h> #include <algorithm> #include <math.h> #include <set> using namespace std; typedef long long int ll; const int maxn = 1e6 + 10; const int inf = 70000000; const ll mod = 998244353; const ll seed = 131; int st[maxn][20],mm[maxn],b[maxn]; void initRMQ(int n) { mm[0] = -1; for(int i = 1;i <= n;i++){ mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1:mm[i - 1]; st[i][0] = b[i]; } for(int j = 1;j <= mm[n];j++){ for(int i = 1;i + (1 << j) - 1 <= n;i++){ st[i][j] = max(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]); } } } int rmq(int x,int y) { int k = mm[y - x + 1]; return max(st[x][k],st[y - (1 << k) + 1][k]); } ll ans[maxn]; int main() { int n,w,len,l,r; ll temp; while(scanf("%d%d",&n,&w) != EOF){ memset(ans,0,sizeof(ans)); while(n--){ scanf("%d",&len); for(int i = 1;i <= len;i++){ scanf("%d",&b[i]); } initRMQ(len); //i <= w - len + 1 //i >= len //len <= i <= w - len + 1 符合条件的第i列可以取到整行 int cnt = w,flag = 0; //中间 if(len + 1 <= w - len + 1 - 1){ temp = max((ll)rmq(1,len),(ll)0); ans[len + 1] += temp; ans[w - len + 1] -= temp; cnt = len; flag = 1; } //头 for(int i = 1;i <= cnt;i++){ if(len >= i) r = i; else r = len; if(w - len < i)//w-len+l=i l = i - (w - len); else l = 1; temp = rmq(l,r); if(temp < 0){ if(len < i || (w - len) >= i) temp = 0; } ans[i] += temp; ans[i + 1] -= temp; } //尾 if(!flag) cnt = len; else cnt = 0; for(int i = w - len + 1 + cnt;i <= w;i++){ if(len >= i) r = i; else r = len; if(w - len < i)//w-len+l=i l = i - (w - len); else l = 1; temp = rmq(l,r); if(temp < 0){ if(len < i || (w - len) >= i) temp = 0; } ans[i] += temp; ans[i + 1] -= temp; } } for(int i = 1;i <= w;i++){ ans[i] += ans[i - 1]; printf("%lld ",ans[i]); } puts(""); } return 0; }View Code
还有单调队列版的,等我过了再来更新