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;
}