Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337）
A - Scoreboard
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int n;
cin >> n;
int x = 0;
int y = 0;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
x += a;
y += b;
}
int ans = x - y;
if (ans > 0)
{
puts("Takahashi");
}
else if (ans < 0)
{
puts("Aoki");
}
else
{
puts("Draw");
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Extended ABC
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
string s;
cin >> s;
int n = s.size();
for (int i = 1; i < n; i++)
{
if (s[i] < s[i - 1])
{
puts("No");
return;
}
}
puts("Yes");
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Lining Up 2
解题思路:
\(dfs\)一次即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
int r = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x == -1)
{
r = i;
}
else
{
adj[x].push_back(i);
}
}
auto dfs = [&](auto self, int u) -> void
{
cout << u << ' ';
for (auto v : adj[u])
{
self(self, v);
}
};
dfs(dfs, r);
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Cheating Gomoku Narabe
解题思路:
记录时，\(o\)为1，其余为0.
\(a[i][j]:记录以第i行第j列为末尾，总长度为k的序列的区间和。\)
遍历时，\(x为-1\)，其余为\(1\)。遍历过程中，长度为\(k\)的区间和刚好为\(k\)时，\(k - a[i][j]\)就是一种填补数量。
横着跑一次，竖着跑一次。
时间复杂度\(O(n)\).
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int h, w, k;
cin >> h >> w >> k;
vector<string> g(h + 1);
for (int i = 1; i <= h; i++)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
vector<vector<int>> a(h + 1, vector<int>(w + 1));
int cur = 0;
for (int i = 1; i <= h; i++)
{
cur = 0;
queue<int> q;
for (int j = 1; j <= w; j++)
{
if (q.size() == k)
{
cur -= q.front();
q.pop();
}
int x = 0;
if (g[i][j] == 'o')
{
x = 1;
}
q.push(x);
cur += x;
if (q.size() == k)
{
// cout << i << ' ' << j << ' ' << cur << endl;
a[i][j] = cur;
}
}
}
int ans = 1e9;
for (int i = 1; i <= h; i++)
{
cur = 0;
queue<int> q;
for (int j = 1; j <= w; j++)
{
if (q.size() == k)
{
cur -= q.front();
q.pop();
}
int x = 1;
if (g[i][j] == 'x')
{
x = -1;
}
q.push(x);
cur += x;
if (q.size() == k)
{
if (cur == k)
{
ans = min(k - a[i][j], ans);
}
}
}
}
for (int i = 1; i <= w; i++)
{
cur = 0;
queue<int> q;
for (int j = 1; j <= h; j++)
{
if (q.size() == k)
{
cur -= q.front();
q.pop();
}
int x = 0;
if (g[j][i] == 'o')
{
x = 1;
}
q.push(x);
cur += x;
if (q.size() == k)
{
// cout << i << ' ' << j << ' ' << cur << endl;
a[j][i] = cur;
}
}
}
for (int i = 1; i <= w; i++)
{
cur = 0;
queue<int> q;
for (int j = 1; j <= h; j++)
{
if (q.size() == k)
{
cur -= q.front();
q.pop();
}
int x = 1;
if (g[j][i] == 'x')
{
x = -1;
}
q.push(x);
cur += x;
if (q.size() == k)
{
if (cur == k)
{
ans = min(k - a[j][i], ans);
}
}
}
}
if (ans > k)
{
ans = -1;
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Bad Juice
解题思路:
每个人第二天出问题或者没出问题对应二进制变化\(1或者0\)。
所以有\(n\)杯果汁，我们就需要\(n\)中不同的二进制编码。每种唯一即可对应情况选择出坏的果汁。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int n;
cin >> n;
n--;
int m = 0;
for (int i = 30; i >= 0; i--)
{
if (n >> i & 1)
{
cout << i + 1 << endl;
m = i + 1;
break;
}
}
vector<vector<int>> a(m + 10, vector<int>(0));
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 30; j++)
{
if (i >> j & 1)
{
a[j + 1].push_back(i + 1);
}
}
}
for (int i = 1; i <= m; i++)
{
cout << a[i].size() << ' ';
for (auto x : a[i])
{
cout << x << ' ';
}
if (a[i].size() == 0)
{
continue;
}
cout << endl;
}
cout.flush();
string s;
cin >> s;
int ans = 1;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '1')
{
ans += 1 << i;
}
}
cout << ans << endl;
cout.flush();
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}