[CF1060X]Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)

这次总算有时间和同机房的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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注