题解 | 正式赛题解

IloveACM!

https://ac.nowcoder.com/acm/contest/44558/A

A-IloveACM!

#include <bits/stdc++.h>
using namespace std;

int main(){
    cout<<"I love ACM!"<<endl;
}

B-静默区划分

使用二维前缀和处理

注意是左下角和右上角

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=1005;
using namespace std;

ll n,m;
ll a[maxn][maxn];
ll b[maxn][maxn];
ll q;

int main(){
    cin>>n>>m;
    ll x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x,&y);
        a[x][y]=1;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        b[x][y]=1;
    }
    
    for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++)
    {
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
    }
    
    cin>>q;
    while(q--)
    {
        ll x0,y0,x1,y1;
        scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
        ll ans1=a[x1][y1]-a[x0-1][y1]-a[x1][y0-1]+a[x0-1][y0-1];
        ll ans2=b[x1][y1]-b[x0-1][y1]-b[x1][y0-1]+b[x0-1][y0-1];
        printf("%lld %lld\n",ans1,ans2);
    }
    
    
}

C-但鱼很好吃，所以值得

从原字符串后开始暴力每种情况，如果满足拼接条件，则输出并结束。

#include <bits/stdc++.h>
using namespace std;

int a[10];

int March(int x,int p)
{
    if(x==0&&a[p]==0)   return p-1;
    while(x!=0&&p!=0)
    {
        int idx=x%10;
        x/=10;
        if(a[p]!=idx)
        {
            return -1;
        }
        p--;
    }
    return p;
}

int GetNum(int l,int r)
{
    int res=0;
    for(int i=l;i<=r;i++)
    {
        res*=10;
        res+=a[i];
    }
    return res;
}

int main(){
string s;

cin>>s;

for(int i=1;i<=4;i++)
    a[i]=s[i-1]-'0';

for(int i=4;i>=1;i--)
{
    int last=GetNum(i,4);
    int ans=last;
    last--;
    int p=March(last,i-1);
    if(p==-1)   continue;
    while(p!=0)
    {
        if(p==-1)   break;
        last--;
        p=March(last,p);
    }
    if(p==0)
    {
        cout<<(ans+1)<<endl;
        break;
    }
}

}

D- acm

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

string s;
ll a,c,m;

int main(){
    
    cin>>s;
    
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='a')
            a++;
        else if(s[i]=='c')
            c++;
        else if(s[i]=='m')
            m++;
    }
    cout<<a<<" "<<c<<" "<<m<<endl; 
    
}

E-心甘晴愿

使用数组保存数

1.如果当前数为0，不计分

1.如果当前数个位%2==0，甘雨加一分

3.如果当前数各个位上数字之和%3==0，刻晴加一分

#include <bits/stdc++.h>
using namespace std;

int main(){
int num[35];
string s;

int a=0;int b=0;
int time=10;

while(time--)
{
    int cnt=0;
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        num[i]=s[i]-'0';
        cnt+=num[i];
    }

    if(s=="0")  continue;
    if(num[s.length()-1]%2==0)  a++;
    if(cnt%3==0)    b++;
}

printf("%d %d\n",a,b);

}

F-炉石传说

对原数组进行排序，如果存在攻击力第一个大于等于地方嘲讽随从的我方随从，判断我方总攻击力-该随从攻击力>=敌方英雄血量。如果大于，则输出YES，否则输出N0。如果不存在，则输出N0

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=15;
using namespace std;

ll a[maxn];
ll x,y;

int main(){
    ll sum=0;
    for(int i=1;i<=7;i++)
    {
        cin>>a[i];    
        sum+=a[i];
    }

    sort(a+1,a+7+1);
    

    cin>>x>>y;
    
    for(int i=1;i<=7;i++)
    {
        if(a[i]>=x)
        {
            sum-=x;
            
            if(sum>=y)
                cout<<"YES"<<endl;
            else
                cout<<"N0"<<endl;
            
            return 0;
        }
    }
    
    cout<<"N0"<<endl;
    
}

G-序列1

使用数组保存每个长度的连续序列最大值，每次更新即可。

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=5e3+5;
using namespace std;

ll n;
ll a[maxn];
ll ans[maxn];

int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        ans[1]=max(ans[1],a[i]);
    }
        
    for(int i=1;i<=n;i++)
    {
        ll now=a[i];
        for(int j=i+1;j<=n;j++)
        {
            now=__gcd(now,a[j]);
            ans[j-i+1]=max(ans[j-i+1],now);
        }
    }
    
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
        
}

H-绫人的奶茶

此题数据范围非常小，排序可以用任一方法。

每杯奶茶需要保存的是输入的风味评分和奶茶质量，还有自己额外保存的顺序编号（在输入时保存for循环里的i）

保存奶茶信息可以用结构体。如果不会用三个一维数组也可实现，只需要交换时把三个一维数组相应位置分别交换即可。

#include <bits/stdc++.h>
using namespace std;

struct Node{
    string s;
    int a;
    int b;
    int id;
}nd[55];
int n;

bool cmp(const Node& l,const Node& r)
{
    if(l.a!=r.a)    return l.a>r.a;
    if(l.b!=r.b)    return l.b>r.b;
    return l.id<r.id;
}

int main(){
int i,j;
cin>>n;

for(int i=1;i<=n;i++)
{
    cin>>nd[i].s;
    cin>>nd[i].a>>nd[i].b;
    nd[i].id=i;
}

sort(nd+1,nd+n+1,cmp);

for(int i=1;i<=n;i++)
    cout<<nd[i].s<<endl;

}

I-神里绫华的狗

该题原题题解链接：https://www.acwing.com/solution/content/68473/

把题意转化为小猫需要饲养员出发的时间，排序后可以得到贪心策略，即饲养员一定会选择某只猫需要的出发时间。然后前面未带走的猫则根据公式可以算出最小时间

公式：

$a_{i}$ 是该猫需要饲养员出发的时间， $b_{i}$ 是对 $a_{i}$ 排序后的前缀和

遍历饲养员的数量，对于当前饲养员的数量 $k$ ， $f_{i} = f_{j} + (i - j) * a_{i} - (b_{i} - b_{j})$ 。其中 $f_{i}$ 是 $d p [k] [i]$ ， $f_{j}$ 是 $d p [k - 1] [j]$

公式等价于 $(f_{j} + b_{j}) = (f_{i} + b_{i}) - (i - j) * a_{i}$ 。所以把公式等价于 $y$ 为 $f_{i} + b_{i}$ ， $k$ 为 $a_{i}$ ， $x$ 为 $j$ ， $- i * a_{i}$ 为 $b$ 的斜率方程

处理斜率方程即可求解

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=1e5+5;
using namespace std;

ll hill[maxn];
ll f[105][maxn];
ll a[maxn];ll b[maxn];
ll m,n,amo;
ll que[maxn];ll hh,tt;

int main(){
ll i,j;

cin>>m>>n>>amo;

for(i=2;i<=m;i++)
{
    scanf("%lld",&hill[i]);
    hill[i]+=hill[i-1];
}

for(i=1;i<=n;i++)
{
    scanf("%lld%lld",&a[i],&b[i]);
    a[i]=hill[a[i]];
    a[i]=b[i]-a[i];
}

sort(a+1,a+n+1);

for(i=1;i<=n;i++)
    b[i]=b[i-1]+a[i];

memset(f,0x3f3f3f3f3f3f3f3f,sizeof f);
for(i=0;i<=amo;i++)
    f[i][0]=0;

for(ll k=1;k<=amo;k++)
{
    hh=0,tt=-1;que[++tt]=0;
    for(i=1;i<=n;i++)
    {
        while(hh<tt&&(f[k-1][que[hh+1]]-f[k-1][que[hh]])<=a[i]*(que[hh+1]-que[hh]) )  hh++;
        j=que[hh];
        f[k][i]=f[k-1][j]-j*a[i]+i*a[i];
        while(hh<tt&&(f[k-1][que[tt]]-f[k-1][que[tt-1]])*(i-que[tt-1])>=(f[k-1][i]-f[k-1][que[tt-1]])*(que[tt]-que[tt-1]) ) tt--;
        que[++tt]=i;
    }
}

ll ans=0x3f3f3f3f3f3f3f3f;
for(i=1;i<=amo;i++)
    ans=min(ans,f[i][n]);

printf("%lld\n",ans-b[n]);
}

公开处刑： alt

J-01字符串

分别维护一个前连续1和一个后连续0，更新即可

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=1e5+5;
using namespace std;

char ch[maxn];
ll fro[maxn];
ll bac[maxn];
ll ans;
ll n;

int main(){
ll i,j;

scanf("%s",ch+1);
n=strlen(ch+1);

for(i=1;i<=n;i++)
if(ch[i]=='0')
{
    fro[i]=fro[i-1]+1;
    ans=max(ans,fro[i]);
}

for(i=n;i>=1;i--)
if(ch[i]=='1')
{
    bac[i]=bac[i+1]+1;
    ans=max(ans,bac[i]);
}
for(i=1;i<=n;i++)
    ans=max(ans,fro[i]+bac[i+1]);

printf("%lld\n",ans);
}