前缀和+折半二分搜索——又是自闭的一天呢-白红宇

前缀和+折半二分搜索——又是自闭的一天呢

阅读量：7073 次

发布时间：2019-06-28

本文共 2232 字，大约阅读时间需要 7 分钟。

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 524288K，其他语言1048576K

64bit IO Format: %lld

题目描述

华华用数组a和数组b合成了矩阵c。其中a数组长度为n，b数组长度为m，c是n行m列的矩阵，且c[i][j]=a[i]*b[j]。定义矩阵的权值为矩阵中所有元素的和。然后他想把矩阵送给奕奕。然而他怕奕奕不喜欢。若矩阵的权值小于L,奕奕会讨厌它，因为奕奕不喜欢太小的数字。若矩阵的权值大于R，奕奕会生气因为奕奕不认识比R大的数字。所以奕奕只喜欢权值大于等于L并且小于等于R的矩阵。还好华华学过acm，他马上想到可以送奕奕一个子矩阵，并且他立马写程序从c矩阵中找出了所有奕奕喜欢的子矩阵。你只需要帮他算算这样的子矩阵有多少个即可。

输入描述:

第一行输入n,m,L,R。 第二行n个数表示a数组 第三行m个数表示b数组 1<=n,m<=1000,1<=L<=R<=1e18 1<=a[i],b[i]<=1e6

输出描述:

输出一个数表示子矩阵的个数

示例1

输入

3 3 3 83 2 32 3 1

输出

一直想用二维前缀和枚举所有子矩阵结果一直TLE，后面才发现大佬就是大佬

首先我们记录下 a序列的前缀和 A_sum[] 和b序列的前缀和 B_sum[]，然后我们再枚举出所有b序列的长度情况并且排序（折半）

然后我们可以推出 c[i][j]=a[i]*b[j]，那么一个左上角坐标为（x1,y1）右下角坐标为（x2,y2）的子矩阵

其实就是 S=(a[x1]+a[x1+1]+a[x1+2]………+a[x2]）*（b[y1]+b[y1+1]+b[y1+2]………+b[y2]）==(A_sum[x2]-A_sum[x1-1])*(B_sum[y2]-B_sum[y2-1])

最后我们只要枚举下所有 a序列的长度情况，然后二分b序列的长度情况便可以了

下面再结合下代码会更加清晰

//#pragma comment(linker, "/STACK:1024000000,1024000000")//#pragma GCC optimize(2)#include 
     
      #include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;typedef double dou;typedef long long ll;#define pai acos(-1)#define M 1005#define inf 1e18#define mod 1e18 #define left k<<1#define right k<<1|1#define W(a) while(a) #define ms(a,b) memset(a,b,sizeof(a))ll LL, RR;ll n, m, L, R;ll a[M], b[M], A_sum[M], B_sum[M];vector
                   
                    B_all;ll solve(ll limit) { ll ans = 0; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { ans += upper_bound(B_all.begin(), B_all.end(), limit / (A_sum[j] - A_sum[i - 1])) - B_all.begin();//当矩阵的行范围为i~j时,有多少种b序列的情况满足 } } return ans;}int main() { ios::sync_with_stdio(false); cin >> n >> m >> L >> R; for (int i = 1; i <= n; i++)cin >> a[i], A_sum[i] = A_sum[i - 1] + a[i];//读入a序列，并且建立a序列前缀和 for (int i = 1; i <= m; i++)cin >> b[i], B_sum[i] = B_sum[i - 1] + b[i];//读入b序列，并且建立b序列前缀和 for (int i = 1; i <= m; i++) { for (int j = i; j <= m; j++) { B_all.push_back(B_sum[j] - B_sum[i - 1]);//枚举b序列所有情况 } } sort(B_all.begin(), B_all.end());//排序b序列的所有情况 cout << solve(R) - solve(L - 1) << endl;//相减得到满足L~R范围大小的子矩阵数 return 0;}

转载于:https://www.cnblogs.com/caibingxu/p/10884226.html

你可能感兴趣的文章