在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
https://codeforces.com/contest/1060/problem/C 题意:给你一个长度为n的数列a和长度为m的数列b,定义c(i,j)=ai*bj,得到c矩阵,给定值x,求c矩阵中的子矩阵和小于等于x的最大的元素个数 题解:和hihocoder上面一题很想~链接http://hihocoder.com/problemset/problem/1502 ,不同的是这题用n^3的做法会T哭 我们可以想到,一个子矩阵的和就是 (a[i]+a[i+1]+...+a[j])*(b[i]+b[i+1]+...+b[j])。于是我们先预处理a和b 的前缀和,然后n^2判断即可 代码如下: #include <map> #include <set> #include <cmath> #include <ctime> #include <stack> #include <queue> #include <cstdio> #include <cctype> #include <bitset> #include <string> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #include <functional> #define PI acos(-1) #define eps 1e-8 #define fuck(x) cout<<#x<<" = "<<x<<endl; #define FIN freopen("input.txt","r",stdin); #define FOUT freopen("output.txt","w+",stdout); //#pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef long long LL; typedef pair<int, int> PII; const int maxn = 1e5+5; const int INF = 0x3f3f3f3f; const int MOD = 1e9+7; LL gcd(LL a,LL b){return b?gcd(b,a%b):a;} LL lcm(LL a,LL b){return a/gcd(a,b)*b;} LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} double dpow(double a,LL b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;} LL a[2005],b[2005],c[2005][2005]; LL sum[2005][2005]; LL suma[2005]; LL sumb[2005]; int main(){ #ifndef ONLINE_JUDGE FIN #endif LL n,m,x; cin>>n>>m; a[0]=b[0]=0; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]=a[i]+a[i-1]; } for(int i=1;i<=m;i++){ cin>>b[i]; b[i]=b[i]+b[i-1]; } cin>>x; memset(suma,INF,sizeof(suma)); memset(sumb,INF,sizeof(sumb)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(j+i-1>n) break; suma[i]=min(suma[i],a[j+i-1]-a[j-1]); } } for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ if(j+i-1>m) break; sumb[i]=min(sumb[i],b[j+i-1]-b[j-1]); } } LL ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if((LL)suma[i]*sumb[j]<=x){ ans=max(ans,i*j*1LL); } } } cout<<ans<<endl; // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++){ // cout<<c[i][j]<<" "; // } // cout<<endl; // } }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论