UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
A - Christmas Present
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
int a, b;
cin >> a >> b;
if (a > b)
{
puts("Bat");
}
else
{
puts("Glove");
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
B - Christmas Trees
解题思路:
三种情况：
- \(l \leq a \leq r\)
- \(a \leq l \leq r\)
- \(l \leq r \leq a\)
注意点:\((0,3,6,9)\):\(\frac{6 - 0}{3} = 2\),\(\frac{9 - 0}{3} = 3\),\(3 - 2 = 1\)，但答案是\(2\)。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
ll a, m, l, r;
cin >> a >> m >> l >> r;
ll ans = 0;
if (l <= a && r >= a)
{
ans += (a - l) / m + (r - a) / m + 1;
}
else if (l >= a && r >= a)
{
ans = (r - a) / m - ((l - 1) - a) / m + (l == a ? 1 : 0);
}
else if (l <= a && r <= a)
{
ans = (a - l) / m - (a - (r + 1)) / m + (r == a ? 1 : 0);
}
cout << ans << endl;
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
C - Socks 2
解题思路:
贪心地想，位置靠的近的优先配对。
如果单只的袜子的个数是偶数个，那么直接升序两两配对。
如果单只的袜子的个数是奇数个，那么必定有一个是无法配对的，我们枚举这个无法配对的单只袜子。
我们发现，如果我们选取第偶数只袜子作为剩下的袜子，一定有一种选取第奇数只袜子作为剩下袜子的选法由于它，所以直接前缀后缀和枚举即可。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(1);
for (int i = 1; i <= k; i++)
{
int x;
cin >> x;
a.push_back(x);
}
sort(a.begin() + 1, a.end());
vector<ll> pre(n + 10, 0), suf(n + 10, 0);
n = k;
for (int i = 1; i <= n; i++)
{
if (i & 1)
{
pre[i] = pre[i - 1];
}
else
{
pre[i] = pre[i - 1] + (a[i] - a[i - 1]);
}
}
if (!(n & 1))
{
cout << pre[n] << endl;
return;
}
for (int i = n; i; i--)
{
if (i & 1)
{
suf[i] = suf[i + 1];
}
else
{
suf[i] = suf[i + 1] + (a[i + 1] - a[i]);
}
}
ll ans = 1e18;
for (int i = 1; i <= n; i++)
{
if (i & 1)
{
ans = min(ans, pre[i] + suf[i]);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
D - Reindeer and Sleigh
解题思路:
预处理升序前缀和，对于每个询问直接二分查找匹配答案。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
int n, q;
cin >> n >> q;
vector<ll> r(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> r[i];
}
sort(r.begin() + 1, r.end());
vector<ll> s(n + 1);
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + r[i];
}
while (q--)
{
ll x;
cin >> x;
auto it = upper_bound(s.begin() + 1, s.end(), x);
it--;
cout << (it - s.begin()) << endl;
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
E - Christmas Color Grid 1
解题思路:
题目说明很清楚，枚举所有的红色位置，用概率乘以修改后全局的连通块数累加即可。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
#define fi first
#define se second
#define int long long
const int mod = 998244353;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
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, m;
cin >> n >> m;
vector<string> g(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
ll cnt = 0;
vector<vector<int>> id(n + 1, vector<int>(m + 1));
vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
ll uid = 0;
auto check = [&](int a, int b)
{
if (a < 1 || b < 1 || a > n || b > m)
{
return false;
}
if (st[a][b])
{
return false;
}
if (g[a][b] == '.')
{
return false;
}
return true;
};
auto dfs = [&](auto self, int x, int y, int cid) -> void
{
id[x][y] = cid;
st[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (check(nx, ny))
{
self(self, nx, ny, cid);
}
}
};
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (!st[i][j] && g[i][j] == '#')
{
uid++;
dfs(dfs, i, j, uid);
}
if (g[i][j] == '.')
{
cnt++;
}
}
}
ll ans = 0;
cnt = qmi(cnt, mod - 2) % mod;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (g[i][j] == '.')
{
map<int, bool> mp;
for (int k = 0; k < 4; k++)
{
int a = i + dx[k];
int b = j + dy[k];
// cout << a << ' ' << b << endl;
if (a >= 1 && b >= 1 && a <= n && b <= m && g[a][b] == '#')
{
// cout << id[a][b] << endl;
if (!mp.count(id[a][b]))
{
mp[id[a][b]] = true;
}
}
}
ll t = uid - mp.size() + 1;
ans = ((ans + (t * cnt) % mod + mod) % mod + mod) % mod;
}
}
}
cout << ans << endl;
}
signed main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
F - Christmas Present 2
解题思路:
\(dp[i]:考虑前i个位置的最小总距离。\)
\(dist[i]:从礼物屋子到第i个房子的直线距离\)。
\(d[i][j]:从第i个屋子到大第j个屋子的直线距离\)。
\(pre[i]:从第1个屋子到第i个屋子的顺序总距离\)。
\[\begin{align*}
dp[i] &= min\{dp[j] + dist[j + 1] + \sum_{k = j + 1}^{i - 1}d[k][k + 1] + dist[i]\} \\
&= min\{dp[j] + dist[j + 1] + (pre[i] - pre[j + 1]) + dist[i]\} \\\\
&= dist[i] + pre[i] + min\{(dp[j] + dist[j + 1] - pre[j + 1])\}
\end{align*}
\]
我们设定：
\[f[j] = dp[j] + dist[j + 1] - pre[j + 1]
\]
则
\[dp[i] =dist[i] + pre[i] + min\{f[j]\}
\]
对于上述式子有
\[j \in [max(0,i - k) ,i - 1]
\]
\[dp[i] = 在j点结束后 +从起点到(j + 1)点+从(j+1)顺序走到i点 + 从i点回到礼物屋
\]
枚举所有范围内的\(j\)得到最小值就是\(dp[i]\)的最终答案。
动态维护长度为\(k\)的区间中的最小值，我们可用滑动窗口\(O(n)\)完成。
当然，本题用其他动态查询区间最值的数据结构也可在\(O(nlogn)\)通过。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310;
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piii;
#define fi first
#define se second
const int mod = 998244353;
void solve()
{
int n, k;
cin >> n >> k;
vector<pii> p(n + 1);
for (int i = 0; i <= n; i++)
{
cin >> p[i].fi >> p[i].se;
}
vector<double> pre(n + 1), dist(n + 1);
auto getd = [&](ll x1, ll y1, ll x2, ll y2) -> double
{
return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
for (int i = 1; i <= n; i++)
{
dist[i] = getd(p[0].fi, p[0].se, p[i].fi, p[i].se);
if (i > 1)
{
pre[i] = getd(p[i].fi, p[i].se, p[i - 1].fi, p[i - 1].se);
}
}
for (int i = 2; i <= n; i++)
{
pre[i] += pre[i - 1];
}
vector<double> dp(n + 1), f(n + 1);
deque<int> q;
q.push_back(0);
f[0] = dp[0] + dist[1] - pre[1];
// cout << dp[0] << ' ' << dist[1] << endl;
for (int i = 1; i <= n; i++)
{
if (q.size() && q.front() < i - k)
{
q.pop_front();
}
dp[i] = pre[i] + dist[i] + f[q.front()];
f[i] = dp[i] + dist[i + 1] - pre[i + 1];
// cout << i << ' ' << q.front() << endl;
while (q.size() && f[q.back()] >= f[i])
{
q.pop_back();
}
q.push_back(i);
}
// cout << pre[3] << endl;
printf("%.20lf", dp[n]);
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
- Contest Programming Christmas Beginner AtCodercontest programming christmas beginner christmas beginner atcoder contest contest programming beginner atcoder christmas atcoder regular contest contest programming securities beginner contest programming beginner registry contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295