链接：https://ac.nowcoder.com/acm/contest/894/B
来源：牛客网
题目描述
华华用数组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
输出描述:
输出一个数表示子矩阵的个数
一直想用二维前缀和枚举所有子矩阵结果一直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 <algorithm> #include <iostream> #include<sstream> #include<iterator> #include<cstring> #include<string> #include<cstdio> #include<cctype> #include<vector> #include<deque> #include<queue> #include<stack> #include<map> #include<set> 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<ll>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
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/295299
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
