目录
显示
这次总算有时间和同机房的dalao们一起打比赛了。
题目链接
https://codeforces.com/contest/1060
A. Phone Numbers
大意
一个合法的电话号码的形式为“8xxxxxxxxxx”，现在你有 \(n\) 张卡片，求出一共可以做出多少组电话号码（每张卡片最多只能使用一次）。
题解
做出电话号码的数量只和卡片的数量和8的数量有关系。
#include <cstdio>
#include <algorithm>
using namespace std;
char s[105];
int main()
{
int n,ans=0;
scanf("%d",&n);
scanf("%s",s);
for(int i=0;i<n;i++)
if(s[i]=='8')ans++;
printf("%d",min(ans,n/11));
return 0;
}
B. Maximum Sum of Digits
大意
将整数 \(n\) 拆分成两个整数之和，求这两个数各位数字的和最大是多少。
题解
显然，拆分出尽可能多的’9’肯定是最优解。
#include <iostream>
#include <algorithm>
using namespace std;
long long my_pow(int x)
{
long long ans=1;
for(int i=1;i<=x;i++)
ans*=10;
return ans;
}
int main()
{
long long n,ans=0,cnt=0,n1;
cin>>n;
n1=n;
while(n1>0)//根据位数来拆分尽可能多的‘9’
{
n1/=10;
ans++;
}
ans--;
for(int i=0;i<ans;i++)
n-=9*my_pow(i);//求另外一个数字
if(n==0)ans++;
ans*=9;
while(n>0)//把另外一个数字的各位数字加到结果上
{
ans+=n%10;
n/=10;
}
cout<<ans;
return 0;
}
C. Maximum Subrectangle
大意
给出一个长度为 \(n\) 的序列 \(A\) 和长度为 \(m\) 的序列 \(B\)，构造一个矩阵 \(C\)，其中 \(C_{i,j}=a_i \times b_j\)，在这个矩阵中找到一个面积最大的子矩阵，使得这个子矩阵各元素的和不超过给定的整数 \(x\)。
题解
先分别处理行和列的前缀和，然后二分答案即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2005],b[2005],suma[2005],sumb[2005],c[2005];
int n,m,x;
int search(int num)
{
int l=1,r=n;
int mid=(l+r)>>1;
while(l<=r)
{
mid=(l+r)>>1;
if((long long)c[mid]*num==x)return mid;
if((long long)c[mid]*num<x)l=mid+1;
else r=mid-1;
}
return r;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
suma[i]=suma[i-1]+a[i];
}
for(int i=1;i<=m;i++)
{
scanf("%d",&b[i]);
sumb[i]=sumb[i-1]+b[i];
}
scanf("%d",&x);
memset(c,0x3f,sizeof(c));
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
c[j-i+1]=min(c[j-i+1],suma[j]-suma[i-1]);
int ans=0;
for(int i=1;i<=m;i++)
for(int j=i;j<=m;j++)
{
int res=search(sumb[j]-sumb[i-1]);
ans=max(ans,res*(j-i+1));
}
printf("%d",ans);
return 0;
}