注：希望更好的阅读效果？点这里

一、题解

A.Takoyaki

题目大意：

高桥君 $T$ 分钟能做 $X$ 个章鱼烧，问做 $N$ 个章鱼烧至少要用多长时间。（$1\le N,X,T\le 1000$）

分析：

人口普查题1。

注意：$T$ 分钟能做 $X$ 个章鱼烧不代表1分钟能做 $\lceil \frac{X}{T}\rceil$ 个章鱼烧。

代码：

#include <cstdio>
int main(){
int n,x,t,ans=1;//ans表示需要多少个T分钟
scanf("%d%d%d",&n,&x,&t);
while(ans*x<n) ++ans;//需要满足ans*x>=n
printf("%dn",ans*t);
return 0;
}

B.Multiple of 9

题目大意：

判断整数 $N$（$0\le N\le 10^{200000}$）是否为 $9$ 的倍数，是则输出"Yes"（不带引号），否则输出"No"。

分析：

人口普查题2。

如果一个数所有数字之和为 $9$，则这个数为 $9$ 的倍数。

代码：

#include <cstdio>
char n[200003];//注意要用字符串读入
int ans;//ans为N的所有数字之和
int main(){
scanf("%s",n);
for(int i=0;n[i];i++) ans+=n[i]-'0';
puts(ans%9?"No":"Yes");
return 0;
}

C.Step

题目大意：

$N$（$1\le N\le 2\times 10^5$）个人站成一列，从前面看第 $i$ 个人的身高为 $A_i$ 。现在每个人可以站在凳子上使得在这个人前面的所有人的高度都没有这个人高（高度包括凳子），求凳子高度和的最小值。

分析：

签到题。

因为凳子高度和最小，所以每个凳子的高度也要最小。因此可以这么做：

对于第 $i$ 个人，记他前面的人高度的最大值为 $max$ 。

如果这个人的身高比 $max$ 要小，说明应该站在高度最小为 $max-a_i$ 的板凳上，否则 $max$ 的值就改为 $a_i$ 。

参照样例说明就能看懂了。

代码：

#include <cstdio>
int n,a[200003],max;
long long ans;//ans要开long long
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
max=a[1];//max初值为a[1]
for(int i=2;i<=n;i++){
if(max>a[i]) ans+=max-a[i];
else max=a[i];
}
printf("%lldn",ans);
return 0;
}

D.Wizard in Maze

题目大意：

一个 $H$ 行 $W$ 列（$1\le H,W\le 10^3$）的迷宫，’#‘表示墙，’.'表示空地。现在一个魔法师在 $(C_h,C_w)$ ,他有两种方式移动：

• A：横着或竖着走一格，到达一个空地。
• B：运用魔法瞬移到以当前格子为中心的 $5\times 5$ 区域内的一个空地。

求魔法师走到 $(D_h,D_w)$ 至少需要使用多少次魔法，如果永远走不到则输出 $-1$ 。

分析：

对于迷宫类问题显然要用BFS解决。因为要求使用魔法次数最少，所以要尽可能先用A方式移动。

因此BFS时可以采用双端队列，将不使用魔法的状态放队首、使用魔法的状态放队尾。（其实也能用优先队列）

想到这个代码就很好写了。

代码：

#include <cstdio>
#include <deque>
struct dot{
int x,y,step;
};
std::deque<dot> q;//开双端队列
int h,w,ch,cw,dh,dw;
char s[1003][1003];
bool vis[1003][1003];
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};//方向数组
int main(){
scanf("%d%d%d%d%d%d",&h,&w,&ch,&cw,&dh,&dw);
for(int i=1;i<=h;i++) scanf("%s",s[i]+1);
//采取上面的方式读入可以防止不必要的字符被读入
q.push_back((dot){ch,cw,0});//第一次前面后面入队都行
while(!q.empty()){
dot t=q.front();q.pop_front();
if(t.x==dh&&t.y==dw){
printf("%dn",t.step);
return 0;
}
vis[t.x][t.y]=1;
//使用A方式移动：
for(int i=0;i<4;i++){
int tx=t.x+dx[i],ty=t.y+dy[i];
if(tx>=1&&tx<=h&&ty>=1&&ty<=w&&!vis[tx][ty]&&s[tx][ty]=='.')
q.push_front((dot){tx,ty,t.step});//插入队列前面
}
//使用魔法移动：
for(int tx=t.x-2;tx<=t.x+2;tx++)
for(int ty=t.y-2;ty<=t.y+2;ty++)
if(tx>=1&&tx<=h&&tx!=t.x&&ty>=1&&ty<=w&&ty!=t.y&&!vis[tx][ty]&&s[tx][ty]=='.')
q.push_back((dot){tx,ty,t.step+1});//插入队列后面
}
puts("-1");
return 0;
}

然而当你把这份代码提交上去时会发现WA掉几个点，原因是在使用魔法移动这部分的代码中不考虑原地不动的状态，而原地不动的状态也是可行的！

所以删掉"tx!=t.x"和"ty!=t.y"就能AC啦~

E.Bomber

题目大意：

一个 $H\times W$ （$1\le H,W\le 3\times 10^5$）的矩阵上有 $M$ （$M$至多为 $3\times 10^5$）个目标点，高桥君现在要在矩阵中的一个点上投放炸弹，这个炸弹可以炸毁与它同一行同一列的所有格子，问最多可以炸毁多少个目标点。

分析：

根据数据规模显然是不能开二维数组暴力模拟的。因为求最多可以炸毁的目标点数，所以放炸弹的这一行和这一列目标点数都最大。

因此可以对行和列分别处理。记 $T{R}_i$ 表示第 $i$ 行有多少个目标点，$T{C}_i$ 表示第 $i$ 列有多少个目标点。每读入一个目标点，$T{R}_{h_i}$ 和 $T{C}_{w_i}$ 分别加1。再用结构体数组 $R_i$ 和 $C_i$ 分别表示第 $i$ 行、第 $i$ 列有 $T{R}_i$ 、$T{C}_i$ 个目标点，将两个数组按照目标点的个数从大到小排序，最大的目标点数量就是r[1].second+c[1].second。

**但是，**如果炸弹位于目标点上，此时最大的目标点数量就是r[1].second+c[1].second-1，那怎么快速判断某个点是不是目标点呢？

用STL中的map可以做到。

这样枚举 $i$ 使r[i].second=r[1].second，再枚举 $j$ 使c[j].second=c[1].second，如果 $i$ 行 $j$ 列的交点(r[i].first,c[j].first)不是目标点，那么炸弹放在这里最大的目标点数量是r[1].second+c[1].second，直接输出即可。如果所有的交点都是目标点，则输出r[1].second+c[1].second-1。

代码：

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
int h,w,m,tr[300003],tc[300003];
pair<int,int> r[300003],c[300003];
//上述变量含义同文字部分
map<pair<int,int>,int> mp;//mp用来判断一个点是否为目标点
bool cmp(pair<int,int> x,pair<int,int> y){//比较函数，也可以不写
return x.second>y.second;
}
int main(){
scanf("%d%d%d",&h,&w,&m);
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
mp[make_pair(x,y)]=1;//如果为目标点就置为1
++tr[x],++tc[y];//计数
}
//计算r[]和c[]：
for(int i=1;i<=h;i++) r[i]=make_pair(i,tr[i]);
for(int i=1;i<=w;i++) c[i]=make_pair(i,tc[i]);
//排序：
sort(r+1,r+1+h,cmp);
sort(c+1,c+1+w,cmp);
//枚举第i行第j列的交点：
for(int i=1;r[i].second==r[1].second;i++)
for(int j=1;c[j].second==c[1].second;j++)
if(!mp[make_pair(r[i].first,c[j].first)]){
printf("%dn",r[1].second+c[1].second);
return 0;
}
printf("%dn",r[1].second+c[1].second-1);
return 0;
}

F.Brave CHAIN

显然像我这种才学1年OI的蒟蒻是肯定不会的

二、总结

AtCoder的题目主要是思维有难度，有的题目比如说D和E代码很简单，但是如果没想到做法就肯定不会做。反正继续努力吧！

最后

以上就是纯真啤酒为你收集整理的AtCoder Beginner Contest 176 题解一、题解二、总结的全部内容，希望文章能够帮你解决AtCoder Beginner Contest 176 题解一、题解二、总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。