AtCoder Beginner Contest 367

A - Shout Everyday

思路：水题一道，模拟即可。

B - Cut .0

思路：直接 cin 和 cout 即可，c++输入输出性质。

C - Enumerate Sequences

思路：注意到数据范围很小，因此考虑到搜素所有的序列，然后判断是否合法。

D - Pedometer

思路：观察到是环上问题，先断环为链，观察题目，可以发现，对于 s,它的终点范围在 [s+1,s+n-1]。同时，设 a 为到 s 的步数，设 b 为到 t 的步数,题目的限制条件可以转化为 (b - a) mod k = 0,即 b mod k = a mod k。因此，我们可以用哈希表来维护。

代码：

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
int n, a[N], m, ans;
map<int, int> cnt;
void solve()
{
    int T = 1;
    // cin>>T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 2; i <= n + 1; i++)
        {
            cin >> a[i];
        }
        for (int i = n + 2; i <= 2 * n; i++)
        {
            a[i] = a[i - n];
        }
        for (int i = 1; i <= 2 * n; i++)
        {
            a[i] = (a[i] + a[i - 1]) % m;
        }
        for (int i = 1; i <= n; i++)
        {
            cnt[a[i]]++;
        }
        for (int i = 1; i <= n; i++)
        {
            cnt[a[i]]--;
            ans += cnt[a[i]];
            cnt[a[i + n]]++;
        }
        cout << ans;
    }
}
signed main()
{
    ios;
    solve();
    return 0;
}

E - Permute K times

思路：可以观察到，每个点其实对应一个基环树，问题转化为求每个基环树的第k个点。考虑倍增。

代码：

/*
 * @OJ:
 * @ID:
 * @Author: ZhangChao
 * @Date: 2024-08-15 17:35:14
 */
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
int n, x[N], a[N], k;
int dp[N][63];
int get(int d, int id)
{
    int s = id;
    for (int i = 62; i >= 0; i--)
    {
        if (((int)1 << i) <= d)
        {
            d -= ((int)1 << i);
            s = dp[s][i];
        }
    }
    return a[s];
}
void solve()
{
    int T = 1;
    // cin>>T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            cin >> x[i];
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = x[i];
        }
        for (int i = 1; i < 63; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
            }
        }
        for (int i = 1; i <= n; i++)
        {
            cout << get(k, i) << " ";
        }
    }
}
signed main()
{
    ios;
    solve();
    return 0;
}