AtCoder Beginner Contest 088

总结：rank203，+90分。C题考虑复杂了，直接暴力就好，总体很简单，D题最短路模板题。

题目链接：https://abc088.contest.atcoder.jp/

A题题意：你有A个1元硬币和无限个500元硬币，问是否可以凑出N元。

A题题解：直接NP0，看余数和A的大小即可。

AC代码：

#include <iostream> int main() { int n,m; cin>>n>>m; int k = nP0; if(m>=k)cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }

B题题意：给定N个数，两个人取数，求两人和的差值，A想让差值最大，B想让差值最小。

B题题解：两个人都是取当前数组中最大的数，排序后求和，判断奇偶即可。

AC代码：

#include<iostream> #include<algorithm> using namespace std; const int maxn = 107; int n,a[maxn]; int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n); int sum1 = 0; int sum2 = 0; for(int i=1;i<=n;i+=2) { sum1+=a[i]; } for(int i=2;i<=n;i+=2) { sum2+=a[i]; } if(n&1)cout<<sum1-sum2<<endl; else cout<<sum2-sum1<<endl; return 0; }

C题题意：给定一个3*3的数组A，其中A[i][j]=B[i]+C[j]，问是否存在整数数组B和C。

C题题解：因为最大为100，枚举a[1]，然后根据a[1]的值推算剩下的值，有冲突即不存在，否则存在。

AC代码：

#include<iostream> #include<algorithm> using namespace std; int a[4][4]; int x[4],y[4]; int main() { for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { cin>>a[i][j]; } } int ax = min(min(a[1][1],a[1][2]),a[1][3]); int now = 0; for(int i=0;i<=ax;i++) { int ok = 0; x[1] = i; y[1] = a[1][1]-x[1]; y[2] = a[1][2]-x[2]; y[3] = a[1][3]-x[3]; x[2] = a[2][1]-y[1]; x[3] = a[3][1]-y[1]; for(int j=1;j<=3;j++) { for(int k=1;k<=3;k++) { if(x[j]+y[k]!=a[j][k]) { ok = 1; break; } } } if(ok==0)now = 1; } if(now)cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }

D题题意：给定一个迷宫，一个人从（1，1）出发，（n,m）为终点，可以将任意的点变为障碍，求可以走出迷宫的前提下最多可变的点数。

D题题解：转换后就是求最短路长度，然后最大可变的点数就是可行点-最短路长度。

AC代码：

#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int INF = 100000000; typedef pair<int ,int> P; char maze[55][55]; int n,m; int sx,sy; int gx,gy; int d[55][55]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int bfs() { queue<P> que; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { d[i][j] = INF; } } que.push(P(sx,sy)); d[sx][sy] = 0; while(que.size()) { P p = que.front(); que.pop(); if(p.first == gx && p.second == gy) break; for(int i = 0;i<4;i++) { int nx = p.first + dx[i]; int ny = p.second + dy[i]; if(nx>=0 && nx<=n && ny>=0 && ny<=m && maze[nx][ny] != '#' &&d [nx][ny] == INF) { que.push(P(nx,ny)); d[nx][ny] = d[p.first][p.second] + 1; } } } return d[gx][gy]; } int main() { cin>>n>>m; int sum1 = 0; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { cin>>maze[i][j]; if(maze[i][j]=='.')sum1++; } } sx=0; sy=0; gx=n-1; gy=m-1; int resourt = bfs(); if(resourt==INF)cout<<"-1"<<endl; else cout<<sum1-resourt-1<<endl; return 0; }