A.Phone Numbers

题意

给定一组数字，计算在每一组数字串均以8开头的前提下，能构成的长度为11的字符串的最大数量。

代码

#include <cstdio>

using namespace std;

int main()
{
    int n;
    char s[105];
    scanf("%d",&n);
    scanf("%s",s);
    int cnt=0;
    for(int i=0;i<n;i++)
        if(s[i]=='8') cnt++;
    int ans=0;
    for(int i=1;i<=cnt;i++)
    {
        int tmp=n-i;
        if(tmp>=i*10) ans=i;
    }
    printf("%d\n",ans);
    return 0;
}

B.Maximum Sum of Digits

题意

$S(x)$表示数字$x$各位相加的值。给定一个数$x$，令$a+b=x$，求$S(a)+S(b)$的最大值。

解法

贪心。使a中包含尽可能多的9，即为所求解。

代码

#include <cstdio>

using namespace std;

int main()
{
    long long n;
    scanf("%lld",&n);
    if(n<10) return 0*printf("%lld\n",n);
    long long tmp=1,i=-1;
    while(tmp<=n) tmp*=10,i++;
    tmp/=10;
    tmp--;
    long long ans=0;
    ans=i*9;
    tmp=n-tmp;
    while(tmp)
    {
        ans+=tmp%10;
        tmp/=10;
    }
    printf("%lld\n",ans);
    return 0;
}

C.Maximum Subrectangle

题意

给定数组$a,b$,建立矩阵$c$，令矩阵$c[i][j]=a[i]·b[j]$，求不超过$x$的最大子矩阵和。

解法

可以得知子矩阵和为$(a[i]+a[i+1]+…+a[j])*(b[i]+b[i+1]+…+b[j])$.

对数组$a,b$求前缀和，分别计算出$a,b$区间长度为$[1,n]$时所能达到的最大值，遍历求解即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n,m;
    long long x,a[2005],b[2005],ma[2005],mb[2005];
    scanf("%d%d",&n,&m);
    a[0]=b[0]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&b[i]);
        b[i]+=b[i-1];
    }
    scanf("%lld",&x);
    memset(ma,0x3f,sizeof ma);
    memset(mb,0x3f,sizeof mb);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ma[j-i+1]=min(ma[j-i+1],a[j]-a[i-1]);
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            mb[j-i+1]=min(mb[j-i+1],b[j]-b[i-1]);
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ma[i]*mb[j]<=x) ans=max(ans,i*j);
    printf("%d\n",ans);
    return 0;
}

题意

使用若干个圆桌，给$n$个人排座位。每个人左边需要有$L[i]$个空凳子，右边需要有$R[i]$个空凳子，求最少需要的凳子数。

解法

贪心。

每次加入一个人，这个人可能与他人相邻或与自己成环。与他人相连时，所需的值为$max(L_{i},R_{j})+1$；与自己成环时，所需的值为$max(L_i,R_i)+1$.要使总贡献最小，只需要使当前所取得的$max(L,R)$最小。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=1e5+10;
int l[maxn],r[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&l[i],&r[i]);
    sort(l,l+n);
    sort(r,r+n);
    long long ans=0;
    for(int i=0;i<n;i++)
        ans+=max(l[i],r[i])+1;
    printf("%lld\n",ans);
    return 0;
}

A.Phone Numbers

题意

代码

B.Maximum Sum of Digits

题意

解法

代码

C.Maximum Subrectangle

题意

解法

代码

D.Social Circles

题意

解法

代码