UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323)
A. Weak Beats
解题思路:
按题意模拟即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
string s;
cin >> s;
int n = s.size();
for (int i = 0; i < n; i++)
{
if (i & 1)
{
if (s[i] == '1')
{
puts("No");
return;
}
}
}
puts("Yes");
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
B. Round-Robin Tournament
解题思路:
暴力统计每一行有多少个\(o\)，然后排个序即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
bool cmp(pii a, pii b)
{
if (a.fi != b.fi)
{
return a.fi > b.fi;
}
return a.se < b.se;
}
void solve()
{
int n;
cin >> n;
vector<pii> cnt(n);
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
cnt[i].se = i;
for (auto c : s)
{
if (c == 'o')
{
cnt[i].first++;
}
}
}
sort(cnt.begin(), cnt.end(), cmp);
for (auto v : cnt)
{
cout << v.se + 1 << ' ';
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
C. World Tour Finals
解题思路:
从大到小枚举每个玩家的分数，从大到小枚举每到题的分数，如果没选过就选上，一旦大于了最大值，新加的题数就是答案。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(m + 1);
vector<pii> b(m + 1);
for (int i = 1; i <= m; i++)
{
cin >> a[i];
b[i].fi = a[i];
b[i].se = i;
}
vector<pii> p(n + 1);
vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
for (int i = 1; i <= n; i++)
{
p[i].fi += i;
p[i].se = i;
string s;
cin >> s;
s = ' ' + s;
for (int j = 1; j <= m; j++)
{
if (s[j] == 'o')
{
st[i][j] = true;
p[i].fi += a[j];
}
}
}
sort(p.begin() + 1, p.end());
sort(b.begin() + 1, b.end());
vector<int> ans(n + 1);
for (int i = n; i; i--)
{
int cnt = 0;
int cur = 0;
if (i == n)
{
if (p[n - 1].fi == p[i].fi)
{
cur = p[i].fi;
}
else
{
continue;
}
}
else
{
cur = p[i].fi;
}
for (int j = m; j; j--)
{
if (!st[p[i].se][b[j].se])
{
cur += b[j].fi;
cnt++;
if (cur > p[n].fi)
{
ans[p[i].se] = cnt;
break;
}
}
}
}
for (int i = 1; i <= n; i++)
{
// cout << p[i].fi << ' ' << p[i].se << endl;
cout << ans[i] << endl;
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
D. Merge Slimes
解题思路:
从小到大看，能合并就合并。合并得到的继续能合并就合并。
每次合并剩余的不能合并的（就是只剩一个的），记得累加。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
map<ll, ll> v;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
v[a] = b;
}
for (auto &a : v)
{
ll cur = 1;
ll res = a.se >> 1;
a.se = a.se % 2;
ll t = a.fi;
while (res)
{
cur = res >> 1;
t <<= 1;
if (v.count(t))
{
v[t] += (res % 2);
}
else
{
v[t] = (res % 2);
}
res >>= 1;
}
}
ll ans = 0;
for (auto a : v)
{
// cout << a.fi << ' ' << a.se << endl;
ans += a.se;
}
cout << ans;
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
E. Playlist
解题思路:
\(f[i]\)：如\(X\)为\(i\)，答案为多少。
\(f[0]\)第一步只能选第一首歌，所以答案就是\(\frac{1}{n}\)。
对于每一个\(i\),遍历所有的歌。
对于第\(j\)首歌：
- 若\(t[j] > i\)，那么情况等同于\(f[0]\)，即我们选了这首歌，\(X +0.5\)放的就是这首。所以如果\(j == 1,f[i] = f[i] + \frac{1}{n}\)。
- 若\(t[j] \leq i\)，那么情况等同于\(f[i-t[j]]\)。\(f[i - t[j]]\)相当于时间\(0 \rightarrow (i - t[j])\)，就是要求选歌使得第\((i - t[j])+0.5\)秒后放的是第一首歌。\(f[i]\)可以相当于时间\(t[j] \rightarrow i\),同样要求选歌使得第\((i - t[j])+0.5\)秒后放的是第一首歌。二者问题等价。
时间复杂度:\(O(nx)\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
const int mod = 998244353;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = (res * a) % mod;
}
b >>= 1;
a = (a * a) % mod;
}
return res;
}
void solve()
{
int n, x;
cin >> n >> x;
vector<int> t(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> t[i];
}
// f[i]:X为i时的可能性
vector<ll> f(x + 10);
// X为0时，第一步就要选到第一首歌，所以答案是1/n
f[0] = qmi(n, mod - 2);
// X为i时，如果要X+0.5秒的时候正好在放第1首歌。
// 如果t[j] > i，意味着我们第一首歌如果点j，那么X + 0.5时播放的就是第j首，这和X等于0等价
// 所以若此时j == 1，那么答案加上1 / n。
// 如果t[j] <= i,意味着我们可以从f[i - t[j]]转移过来。
// 从i - t[j] 到 i 和 从 0 到 i 是等价的。所以此时f[i] += f[i - t[j]].
// 由于从每个(i - t[j])转移过来的情况是独立的，所以就可以变成加法了。
ll inv = qmi(n, mod - 2);
for (int i = 1; i <= x; i++)
{
for (int j = 1; j <= n; j++)
{
if (t[j] > i)
{
f[i] = (f[i] + (j == 1) * inv) % mod;
}
else
{
f[i] = (f[i] + f[i - t[j]] * inv) % mod;
}
}
}
cout << f[x];
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}