AtCoder Beginner Contest 335 (Sponsored by Mynavi)
A - 2023
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
string s;
cin >> s;
int n = s.size() - 1;
s[n] = '4';
cout << s << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Tetrahedral Number
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= n; k++)
{
if (i + j + k <= n)
{
cout << i << ' ' << j << ' ' << k << endl;
}
}
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Loong Tracking
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n, q;
cin >> n >> q;
vector<pii> v;
for (int i = 1; i <= n; i++)
{
v.push_back({i, 0});
}
reverse(v.begin(), v.end());
int dx = 0;
int dy = 0;
while (q--)
{
int t;
cin >> t;
if (t == 1)
{
string s;
cin >> s;
auto t = v.back();
if (s[0] == 'U')
{
v.push_back({t.fi, t.se + 1});
}
else if (s[0] == 'D')
{
v.push_back({t.fi, t.se - 1});
}
else if (s[0] == 'L')
{
v.push_back({t.fi - 1, t.se});
}
else
{
v.push_back({t.fi + 1, t.se});
}
}
else
{
int x;
cin >> x;
int idx = v.size() - 1 - x + 1;
cout << v[idx].fi << ' ' << v[idx].se << endl;
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Loong and Takahashi
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const int N = 50;
int d[N][N];
bool st[N][N];
int n;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int cnt = 0;
bool check(int a, int b)
{
if (a < 1 || a > n || b < 1 || b > n)
{
return false;
}
if (d[a][b])
{
return false;
}
return true;
}
void dfs(int a, int b, int t)
{
// cout << a << ' ' << b << endl;
auto cur = (t + 1) % 4;
int x = a + dx[cur];
int y = b + dy[cur];
if (check(x, y))
{
d[x][y] = ++cnt;
dfs(x, y, t);
}
else
{
if (d[x][y] == -1)
{
return;
}
dfs(a, b, cur);
}
}
void solve()
{
cin >> n;
int idx = (n + 1) / 2;
// st[idx][idx] = true;
d[idx][idx] = -1;
d[1][1] = ++cnt;
dfs(1, 1, -1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (d[i][j] == -1)
{
cout << "T" << ' ';
}
else
{
cout << d[i][j] << ' ';
}
}
cout << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Non-Decreasing Colorful Path
解题思路:
\(bfs\)。每次先更新权值最小的点。因为大权值点不可能回搜小权值,所以每个点的距离最多被遍历一次。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1, vector<int>());
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
priority_queue<pii> q;
vector<int> d(n + 1);
q.push({-a[1], 1});
d[1] = 1;
while (q.size())
{
auto t = q.top();
int u = t.se;
// cout << t.fi << endl;
q.pop();
for (auto v : adj[u])
{
if (a[v] >= a[u])
{
if (d[v] < d[u] + (a[v] != a[u]))
{
d[v] = d[u] + (a[v] != a[u]);
q.push({-a[v], v});
}
}
}
}
cout << d[n] << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
F - Hop Sugoroku
解题思路:
\(f[i]:第i点为黑点的方案数\)。
暴力更新代码:
for(int i = 1;i<=n;i++)
{
for(int j = i + a[i];j <= n;j += a[i])
{
f[j] = (f[j] + f[i]) % mod;
}
}
很明显,时间复杂度为\(O(n^2)\)。爆了。
我们发现,对于\(a[i] > \sqrt{N}\)的遍历,时间复杂度为\(O(n\sqrt{n})\),不会爆。
所以,根号分治。
我们想办法处理\(a[i] < \sqrt{N}\)的情况,这样的\(a[i]\)数量不超过\(\sqrt{N}\)个。
对于位置\(i\),我们能够更新到的位置为\(j = i + k \times a[i],\ j > i\)。
可以发现\(i \%a[i] == j \% a[i]\)。
\(g[a[i]][i \%a[i]:表示当前(idx\%a[i] == i\% a[i])的累加量\)。
即对于\(f[1] \sim f[cur]\),若\(a[i] \leq \sqrt{N}\),\(g[a[i]][i \% a[i]] = (g[a[i]][i\% a[i]] + f[i]) \% mod\)。
对于当前\(f[i]\),将所有能从前面转移过来的情况加上。
for(int j = 1;j <= sqrt(N);j ++)
{
f[i] = (f[i] + g[j][i % j]) % mod;
}
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const int N = 2e5;
const int mod = 998244353;
ll g[500][500];
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int lim = sqrt(N) + 1;
vector<ll> f(n + 1);
f[1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= lim; j++)
{
f[i] = (f[i] + g[j][i % j]) % mod;
}
if (a[i] > lim)
{
for (int j = i + a[i]; j <= n; j += a[i])
{
f[j] = (f[j] + f[i]) % mod;
}
}
else
{
g[a[i]][i % a[i]] = (g[a[i]][i % a[i]] + f[i]) % mod;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ans = (ans + f[i]) % mod;
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
- Sponsored Beginner AtCoder Contest Mynavisponsored beginner atcoder contest sponsored panasonic 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