A. Leap Year
模拟
代码实现
import calendar
y = int(input())
if calendar.isleap(y):
print(366)
else:
print(365)
B. Second Best
模拟
代码实现
n = int(input())
a = list(map(int, input().split()))
print(a.index(sorted(a)[-2])+1)
C. Transportation Expenses
二分
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n; ll m;
cin >> n >> m;
vector<int> a(n);
rep(i, n) cin >> a[i];
auto f = [&](int x) {
ll s = 0;
rep(i, n) s += min(x, a[i]);
return s <= m;
};
const int INF = 1001001001;
if (f(INF)) puts("infinite");
else {
int ac = 0, wa = INF;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
if (f(wj)) ac = wj; else wa = wj;
}
cout << ac << '\n';
}
return 0;
}
D. AtCoder Janken 3
如果你考虑“从前到后遍历能赢就赢”的贪心的话，会发现过不了样例3
考虑dp
记 dp[i][j] 表示到第 \(i\) 次操作为止且最后一次出的是 \(j\) 时所能获胜的最大次数
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
const int INF = 1001001001001;
vector dp(n+1, vector<int>(3, -INF));
rep(i, 3) dp[0][i] = 0;
for (int i = 1; i <= n; ++i) {
int x = 0;
if (s[i-1] == 'R') x = 0;
if (s[i-1] == 'P') x = 1;
if (s[i-1] == 'S') x = 2;
rep(j, 3) {
int val = 0;
if (j == (x+1)%3) val = 1;
if (j == (x+2)%3) continue;
rep(pj, 3) {
if (j == pj) continue;
dp[i][j] = max(dp[i][j], dp[i-1][pj]+val);
}
}
}
int ans = ranges::max(dp[n]);
cout << ans << '\n';
return 0;
}