AtCoderBeginnerContest112
- 2020 年 2 月 18 日
- 筆記
AtCoder Beginner Contest 112比賽鏈接
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; }