分类讨论
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define s() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
vector<int>a(5);
for(int i=1;i<=4;i++)cin>>a[i];
string s;cin>>s;
int ans=0;
for(auto c:s)
{
if(c=='1')ans+=a[1];
else if(c=='2')ans+=a[2];
else if(c=='3')ans+=a[3];
else ans+=a[4];
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
思路:双指针.
$l=1,r=1$,从头开始,由于$r$,如果减小的话答案没有之前的优,因此$r$,只会往后移动.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define s() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int mp[N];
int cur;
void solve()
{
int n,k;
cin>>n>>k;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int r=1;
int L=0,R=-1;
for(int i=1;i<=n;i++)
{
while(cur<k&&r<=n)
{
if(!mp[a[r]])cur++;
mp[a[r]]++;
r++;
}
while(r<=n&&mp[a[r]])mp[a[r]]++,r++;
// cout<<i<<' '<<r<<endl;
if(r-i>R-L+1)R=r-1,L=i;
if(!--mp[a[i]])cur--;
}
cout<<L<<' '<<R<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
思路:
将任意,子矩阵的和,表示成$Sum_a *Sum_b$的形式.
至此,我们只需要枚举,所有$a$的不同长度的最小和前缀.和$b$,匹配就可以了.
这里可以使用双指针优化.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define s() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll sa[N],sb[N];
void solve()
{
int n,m;
cin>>n>>m;
vector<int>a(n+1);
vector<int>b(m+1);
vector<ll>c(n+1,llinf);
vector<ll>d(m+1,llinf);
for(int i=1;i<=n;i++)cin>>a[i],sa[i]=sa[i-1]+a[i];
for(int i=1;i<=m;i++)cin>>b[i],sb[i]=sb[i-1]+b[i];
for(int i=1;i<=n;i++)//枚举长度
{
for(int j=1;j+i-1<=n;j++)c[i]=min(c[i],sa[j+i-1]-sa[j-1]);
}
for(int i=1;i<=m;i++)
for(int j=1;j+i-1<=m;j++)d[i]=min(d[i],sb[j+i-1]-sb[j-1]);
ll x;cin>>x;
int l=1,r=m;//l在行上的枚举值,r在列上的枚举值
int ans=0;
while(l<=n)
{
while(d[r]*c[l]>x&&r>=1)r--;
if(r<1)
{
if(d[1]*c[l]<=x)ans=max(ans,l);
}else
{
ans=max(ans,r*l);
}
l++;
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}