AtCoderBeginnerContest112

2020 年 2 月 18 日
笔记

emm.第一次在AtCoder上的比赛. rank:754th rating:113. AC. WA.表示比赛时候的状态

A – Programming Education

AC

题目大意: 输入1的时候输出”Hello World”. 输入2的时候会输入a,b.计算a+b.

题解: emm.入门操作.beginner出这个题还是很不错的.

#include <bits/stdc++.h>  using namespace std;    int main(){  	//freopen("in.txt", "r", stdin);  	ios::sync_with_stdio(0); cin.tie(0);      int kind,a,b;      while(cin >> kind){          if(kind == 1){              cout << "Hello World" << endl;          } else {              cin >> a >> b;              cout << (a+b) << endl;          }      }  	return 0;  }

B – Time Limit Exceeded

AC

题目大意: 给两个数N,T. N组数.每组两个数$c_i$和$t_i$.求所有不超过T的$t_i$中$c_i$的最小值.

题解: emm.入门操作.beginner出这个题还是很不错的.

#include <bits/stdc++.h>  using namespace std;    #define MAX_N 105  int N,T;    int main(){  	//freopen("in.txt", "r", stdin);  	ios::sync_with_stdio(0); cin.tie(0);      int c,t;      while(cin >> N >> T){          int ans = INT_MAX;          for(int i = 1; i <= N; ++i){              cin >> c >> t;              if(t <= T) ans = min(ans, c);          }          if(ans == INT_MAX) cout << "TLE" << endl;          else cout << ans << endl;      }  	return 0;  }

C – Pyramid

WA

ps: 到最后没做出这道题.想暴力.然后看到

The center coordinates and the height of the pyramid can be uniquely identified

这句话.理解成中心点的坐标和h可能是无穷的.orz 应该是: 可以唯一地识别金字塔的中心坐标和高度. by google translate

题目大意: 有N个点.$(x_i, y_i,h_i)$. $h_i$表示这个点的高度.求一个点$(C_x, C_y, H)$满足. $h_i = max(H-|x_i – C_x| + |y_i – C_y|, 0)$.

题解: 由于$0 <= C_x, C_y <= 100.$所以暴力即可.

#include <bits/stdc++.h>  using namespace std;        #define MAX_N 110  int n;  int x[MAX_N], y[MAX_N], h[MAX_N];    int main(){  	//freopen("in.txt", "r", stdin);  	ios::sync_with_stdio(0); cin.tie(0);      while(cin >> n){          for(int i = 1; i <= n; ++i){              cin >> x[i] >> y[i] >> h[i];              if(h[i] > 0) {                  swap(h[i], h[1]);                  swap(x[i], x[1]);                  swap(y[i], y[1]);              }          }          for(int cx = 0; cx <= 100; ++cx){              for(int cy = 0; cy <= 100; ++cy){                  int ch = h[1] + abs(x[1] - cx) + abs(y[1] - cy);                  bool is = true;                  for(int i = 2; i <= n; ++i){                      if(max(ch - abs(x[i] - cx) - abs(y[i] - cy), 0) != h[i]) {                          is = false;                          break;                      }                  }                  if(is){                      cout << cx << " " << cy << " " << ch << endl;                      return 0;                  }              }          }      }  	return 0;  }

D – Partition

AC

题目大意: 两个数N,M.可以有多种方案找N个数之和是M.每种方案N个数的最大公约数是x.这多种方案中x最大 $$ sum_{i=1}^{N}a_i = M $$ $$ ans = max(gcd(a_1, a_2,…,a_N))$$

题解: 可以确定.答案不超过M/N.如果答案是x.那么.这个N个数一定是x的倍数.所以只要从M/N到1枚举.第一个满足 M每次减去x的k倍.最后如果M是0.说明当前x是答案.因为是从大到小枚举.所以第一个肯定是最大的.

#include <bits/stdc++.h>  using namespace std;    #define MAX_N 105  int N,M;    bool can(int x){      int m = M;      m -= x;      while(m > 0 && m/x){          m -= (m/x * x);      }      return m == 0;  }    int main(){  	//freopen("in.txt", "r", stdin);  	ios::sync_with_stdio(0); cin.tie(0);      while(cin >> N >> M){          for(int ans = M/N; ans >= 1; --ans){              if(can(ans)) {                  cout << ans << endl;                  break;              }          }      }  	return 0;  }