AtCoder Beginner Contest 176
程序员文章站
2022-06-22 14:47:11
目录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 的地图(),上面有空地和墙。你一开始在一个点,目标是另一个点,你可以往上下左右相邻的结点走,但是只能走空地,你也可以用魔法跳到以当前点为中心,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()大小的矩阵,上面有 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
上一篇: PHP4实际应用经验篇(7)
推荐阅读
-
AtCoder Grand Contest 043--A - Range Flip Find Route
-
AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )
-
AtCoder Beginner Contest 163 D - Sum of Large Numbers(递推&找规律)
-
AtCoder Beginner Contest 182----C. To 3
-
AtCoder Beginner Contest 182----E. Akari
-
AtCoder Beginner Contest 182 题解
-
AtCoder Beginner Contest 182----D. Wandering
-
【Atcoder】Atcoder Beginner Contest 143
-
AtCoder Beginner Contest 176 D-Wizard in Maze(双端队列)
-
Atcoder - abc176 -- D - Wizard in Maze【BFS + 双端队列】