欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

AtCoder Beginner Contest 176

程序员文章站 2022-03-30 18:37:54
目录A TakoyakiB Multiple of 9C StepD Wizard in MazeE BomberFABCDEF√√√√√(√:做出;●:尝试未做出;○:已补题)题目地址:https://atcoder.jp/contests/abc176A Takoyaki题意:签到题思路:代码:#define DIN freopen("input.txt","r",stdin);#define DOUT freopen("out...


A B C D E F

( √:做出; ●:尝试未做出; ○:已补题 )


题目地址:https://atcoder.jp/contests/abc176



A Takoyaki

题意:签到题

思路

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

int main()
{
    int n=read(),x=read(),t=read();
    if(n%x==0) cout<<n/x*t;
    else cout<<(n/x+1)*t;

    return 0;
}



B Multiple of 9

题意:签到题

思路

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

char s[1000005];

int main()
{
    scanf("%s",s);
    int a=0;
    for(int i=0;s[i];i++) a+=s[i]-'0';
    puts(a%9==0?"Yes":"No");

    return 0;
}



C Step

题意:签到题

思路

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=2e5+5;
int a[maxn];

int main()
{
    int n=read();
    REP(i,1,n) a[i]=read();
    LL ans=0;
    REP(i,2,n) if(a[i]<a[i-1]) ans+=a[i-1]-a[i],a[i]=a[i-1];
    cout<<ans;

    return 0;
}



D Wizard in Maze

题意:一张 n*m 的地图(1n,m1031\le n,m\le 10^3),上面有空地和墙。你一开始在一个点,目标是另一个点,你可以往上下左右相邻的结点走,但是只能走空地,你也可以用魔法跳到以当前点为中心,5*5的范围内的任意空地。要求出走到目标点使用魔法的最少次数。

思路:典型的01BFS。用双端队列维护候选结点,对于当前结点,首先走上下左右,如果可以走并且没有标记过,就加入队首;然后使用魔法,如果可以跳到某个空地并且没有标记,那么把这个点加入队尾。这样保证每次从队首取出来的点到达它使用的魔法数一定是最少的。

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=1e3+5;
char s[maxn][maxn];
int ans[maxn][maxn],vis[maxn][maxn],n,m,fx,fy,tx,ty;
int dir[4][2]={1,0,-1,0,0,1,0,-1};

struct node
{
    int x,y,step=0;
};
deque<node> Q;

int main()
{
    n=read(),m=read();
    fx=read(),fy=read();
    tx=read(),ty=read();
    REP(i,1,n) scanf("%s",s[i]+1);
    REP(i,1,n) REP(j,1,m) ans[i][j]=-1;
    Q.push_back((node){fx,fy,0});
    while(!Q.empty())
    {
        node nd=Q.front(); Q.pop_front();
        int x=nd.x,y=nd.y,step=nd.step;
        if(vis[x][y]) continue;
        //cout<<x<<' '<<y<<endl;
        vis[x][y]=1;
        ans[x][y]=step;
        for(int i=0;i<4;i++)
        {
            int xx=x+dir[i][0],yy=y+dir[i][1];
            if(xx>0 && xx<=n && yy>0 && yy<=m && !vis[xx][yy] && s[xx][yy]=='.')
                Q.push_front((node){xx,yy,step});
        }
        for(int xx=x-2;xx<=x+2;xx++)
            for(int yy=y-2;yy<=y+2;yy++)
            {
                if(xx>0 && xx<=n && yy>0 && yy<=m && !vis[xx][yy] && s[xx][yy]=='.')
                    Q.push_back((node){xx,yy,step+1});
            }
    }
    if(ans[tx][ty]<0) puts("-1");
    else printf("%d\n",ans[tx][ty]);

    return 0;
}



E Bomber

题意:有一个 n*m(1n,m3×1051\le n,m \le 3\times 10^5)大小的矩阵,上面有 M 个目标点,你要选择一个点安置炸药,这个炸药可以炸毁同一行同一列的所有格子,要求出最多能炸毁多少目标点。

思路:安放位置一定是目标最多的列和目标最多的行的交点,如果所有这样的交点中,存在一个交点不是目标点,那么答案就是这一行和这一列的目标数之和;如果这些交点中全部都是目标点,那么答案就是目标数之和减一。因为目标点总数不会超过 M,所以直接枚举这些交点,找到不是目标点的跳出就行了。

代码

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=3e5+5;
int nx[maxn],ny[maxn],n,m,N;
P xx[maxn],yy[maxn];
set<P> s;

int main()
{
    n=read(),m=read(); N=read();
    REP(i,1,N)
    {
        int x=read(),y=read();
        nx[x]++; ny[y]++;
        s.insert(P(x,y));
    }
    REP(i,1,n) xx[i]=P(nx[i],i);
    REP(i,1,m) yy[i]=P(ny[i],i);
    sort(xx+1,xx+n+1,greater<P>());
    sort(yy+1,yy+m+1,greater<P>());

    int maxx=xx[1].first,maxy=yy[1].first,flag=0;
    for(int i=1;xx[i].first==maxx;i++)
    {
        if(flag) break;
        for(int j=1;yy[j].first==maxy;j++)
        {
            if(!s.count(P(xx[i].second,yy[j].second)))
            {
                flag=1;
                break;
            }
        }
    }
    int ans=xx[1].first+yy[1].first;
    if(flag) cout<<ans;
    else cout<<ans-1;

    return 0;
}



F

题意

思路:不会做。

代码


本文地址:https://blog.csdn.net/dragonylee/article/details/108175384

相关标签: atcoder