A - Weak Beats
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
string s;
cin >> s;
for( int i = 1 ; i < 16 ; i += 2 )
if( s[i] == '1' ){
cout << "No\n";
return 0;
}
cout << "Yes\n";
return 0;
}
B - Round-Robin Tournament
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
string s;
int n;
cin >> n;
vector<pii> a;
for (int i = 1, cnt; i <= n; i++) {
cin >> s, cnt = 0;
for (auto j: s)
cnt += (j == 'o');
a.emplace_back(cnt, i);
}
sort( a.begin(), a.end() , []( pii x , pii y ){
if( x.first != y.first ) return x.first > y.first;
return x.second < y.second;
});
for( auto [ cnt , id ] : a )
cout << id << " ";
return 0;
}
C - World Tour Finals
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vi a(m), cnt(n);
for (auto &i: a) cin >> i;
for (int i = 0; i < n; i++)
cnt[i] = i + 1;
vector<string> s(n);
for (auto &i: s)
cin >> i;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cnt[i] += (s[i][j] == 'o') * a[j];
int top = *max_element(cnt.begin(), cnt.end());
for (int i = 0, res; i < n; i++) {
priority_queue<int> q;
for (int j = 0; j < m; j++)
if (s[i][j] == 'x') q.push(a[j]);
res = 0;
while (!q.empty() and cnt[i] < top)
cnt[i] += q.top(), q.pop(), res++;
cout << res << "\n";
}
return 0;
}
D - Merge Slimes
#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
using vi = vector<int>;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
map<int, int> a;
for (int x, y; n; n--)
cin >> x >> y, a[x] += y;
for (auto &[c, s]: a) {
a[c * 2] += s / 2, s %= 2;
}
int res = 0;
for( auto [c,s] : a )
res += s;
cout << res << "\n";
return 0;
}
E - Playlist
令\(f[i]\)表示第\(i\)秒开始播放音乐的概率,所以\(\frac 1 n \sum_{i=x-t_0+1}^{x}f[i]\)就是答案。
我们求\(f[i]\)可以枚举上一首放的歌,然后从\(f[i-t_j]\)转移过来即可。记得要乘上播放这首歌的概率$\frac 1 n $
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9, INF = 1e18;
const int mod = 998244353;
int power(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
x = x * x % mod, y /= 2;
}
return ans;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vi t(n);
for (auto &i: t) cin >> i;
vi f(m + 1);
f[0] = 1;
int inv = power(n, mod - 2);
for (int i = 1; i <= m; i++) {
for (auto j: t) {
if (i - j < 0) continue;
f[i] = (f[i] + f[i - j]) % mod;
}
f[i] = f[i] * inv % mod;
}
int ans = 0;
for (int i = max(0ll, m - t[0] + 1); i <= m ; i++)
ans = (ans + f[i]) % mod;
ans = ans * inv % mod;
cout << ans << "\n";
return 0;
}
F - Push and Carry
首先我们一定是是移动到某一个点上,然后把货物一直推到终点。
如果货物到终点是一条斜线,则过程中需要变换一次方向,移动次数加 2
如果人货物终点三点共线,且人位于中间,则需要绕道另一侧,移动次数加 2
然后就是特判出移动到货物周围的哪一个点。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9, INF = 1e18;
const int mod = 998244353;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int xa, xb, xc, ya, yb, yc;
cin >> xa >> ya >> xb >> yb >> xc >> yc;
xa -= xb, ya -= yb, xc -= xb, yc -= yb, xb = yb = 0;
int res = abs(xc) + abs(yc);
if (xc < 0 and yc < 0) xc = -xc, yc = -yc, xa = -xa, ya = -ya;
if (xc > 0 and yc > 0) {
cout << res + min(abs(xa + 1) + abs(ya), abs(xa) + abs(ya + 1)) + 2;
return 0;
}
if (xc > 0 and yc < 0) xc = -xc, yc = -yc, xa = -xa, ya = -ya;
if (xc < 0 and yc > 0) {
cout << res + min(abs(xa - 1) + abs(ya), abs(xa) + abs(ya + 1)) + 2;
return 0;
}
if (xc == 0) {
if (yc < 0) xc = -xc, yc = -yc, xa = -xa, ya = -ya;
if (ya > 0 and xa == 0) res += 2;
cout << res + abs(xa) + abs(ya + 1);
} else {
if (xc < 0) xc = -xc, yc = -yc, xa = -xa, ya = -ya;
if (xa > 0 and ya == 0) res += 2;
cout << res + abs(xa + 1) + abs(ya);
}
return 0;
}
- Beginner AtCoder Contest 323beginner atcoder contest 323 题解323 beginner atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332