【题解】abc176(A-E)

A

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x,t;
    cin>>n>>x>>t;
    cout<<((n-1)/x+1)*t;
    return 0;
}

B

字符串操作

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    long long ans=0;
    for(int i=0;i<s.length();i++){
        ans+=s[i]-'0';
    }
    if(ans%9==0){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}

C

很明显最优情况是如果a[i]<a[i-1],则将a[i]提升到a[i-1]即可。

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]<a[i-1]){
            ans+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    printf("%lld",ans);
    return 0;
}

D

本题为了保证魔法使用次数最少用priority_queue为BFS以使用魔法次数排序。然后BFS一次即可。

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int h,w;
int x,y,xx,yy;
char mp[1005][1005];
struct kkk{
    int step,nx,ny;
};
int wx[4]={1,0,0,-1};
int wy[4]={0,1,-1,0};
bool vis[1005][1005];
struct cmp{
    bool operator () (kkk aa, kkk bb){
        return aa.step>bb.step;
    }
};
int main(){
    cin>>h>>w;
    cin>>x>>y;
    cin>>xx>>yy;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>mp[i][j];
        }
    }
    priority_queue<kkk,vector<kkk>,cmp> q;
    kkk now,nxt;
    now.nx=x,now.ny=y,now.step=0;
    q.push(now);
    while(!q.empty()){
        now=q.top();
        if(now.nx==xx&&now.ny==yy){
            cout<<now.step;
            return 0;
        }
        q.pop();
        if(vis[now.nx][now.ny])continue;
        vis[now.nx][now.ny]=1;
        for(int i=0;i<4;i++){
            if(mp[now.nx+wx[i]][now.ny+wy[i]]=='.'&&!vis[now.nx+wx[i]][now.ny+wy[i]]){
                nxt.nx=now.nx+wx[i],nxt.ny=now.ny+wy[i],nxt.step=now.step;
                q.push(nxt);
            }
        }
        for(int i=max(1,now.nx-2);i<=min(h,now.nx+2);i++){
            for(int j=max(1,now.ny-2);j<=min(w,now.ny+2);j++){
                if(mp[i][j]=='.'&&!vis[i][j]){
                    nxt.nx=i,nxt.ny=j,nxt.step=now.step+1;
                    q.push(nxt);
                }
            }
        }
    }
    cout<<"-1";
    return 0;
}

E

我们先对每一行,每一列从大到小排序,找到可能最大值xx[1],yy[1],记录他们的和为maxn。我们对每一个h[i],w[i]枚举如果当前点在可能是最大值的行列交点上则cnt++;
记录最大值的可能对的个数为ch(最大行的数量),cl(最大列的数量),ch*cl就是最大值的可能个数
如果ch*cl>cnt则说明有至少一个点可以取到maxn,于是输出maxn。否则输出maxn-1。

#include<bits/stdc++.h>
using namespace std;
int h,w,m;
struct kkk{
    int num,sum;
};
kkk lie[300005],hang[300005];
kkk ly[300005],hy[300005];
bool cmp(kkk a,kkk b){
    return a.sum>b.sum;
}
int xx[300005],yy[300005];
int main(){
    scanf("%d%d%d",&h,&w,&m);
    for(int i=1;i<=h;i++){
        hang[i].num=i;
    }
    for(int i=1;i<=w;i++){
        lie[i].num=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&xx[i],&yy[i]);
        lie[yy[i]].sum++;
        hang[xx[i]].sum++;
    }
    for(int i=1;i<=h;i++){
        hy[i].sum=hang[i].sum;
    }
    for(int i=1;i<=w;i++){
        ly[i].sum=lie[i].sum;
    }
    sort(hang+1,hang+h+1,cmp);
    sort(lie+1,lie+w+1,cmp);
    int maxn=hang[1].sum+lie[1].sum;
    long long cnt=0;
    for(int i=1;i<=m;i++){
        if(hy[xx[i]].sum+ly[yy[i]].sum==maxn){
            cnt++;
        } 
    }
    long long ch=0,cl=0;
    for(int i=1;i<=h;i++){
        if(hang[i].sum==hang[1].sum)ch++;
    }
    for(int i=1;i<=w;i++){
        if(lie[i].sum==lie[1].sum)cl++; 
    }
    if(ch*cl-cnt>0){
        printf("%d",hang[1].sum+lie[1].sum);
    }else{
        printf("%d",hang[1].sum+lie[1].sum-1);
    }
    return 0;
} 

F

我tcl,不会做。。。

PS:E考完七分钟过。。气哭

本文链接:http://kaispace.com.cn/index.php/archives/699/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者