ARC刷题笔记

arc064

[ARC064E] Cosmic Rays

建图 跑dijkstra即可

// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e3 + 10;

// bool st;
struct node
{
    int x, y, r;
} s[N];
int n;
vector<pair<int, double>> g[N];
double dis[N];
// bool en;

void solve()
{
    cin >> s[0].x >> s[0].y >> s[1].x >> s[1].y;
    s[0].r = s[1].r = 0;
    cin >> n;
    n++;
    rep(i, 2, n) cin >> s[i].x >> s[i].y >> s[i].r;
    rep(i, 0, n)
    {
        dis[i] = INF;
        rep(j, 0, n)
        {
            if (i == j)
                continue;
            g[i].push_back({j, max((double)0, sqrt((s[i].x - s[j].x) * (s[i].x - s[j].x) + (s[i].y - s[j].y) * (s[i].y - s[j].y)) - s[i].r - s[j].r)});
        }
    }
    dis[0] = 0;
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
    q.push({0, 0});
    while (!q.empty())
    {
        auto [ds, x] = q.top();
        q.pop();
        if (dis[x] != ds)
            continue;
        if (x == 1)
        {
            cout << fixed << setprecision(10) << ds << endl;
            return;
        }
        for (auto [v, w] : g[x])
        {
            if (dis[v] > dis[x] + w)
            {
                dis[v] = dis[x] + w;
                q.push({dis[v], v});
            }
        }
    }
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}

[ARC064F] Rotated Palindromes

因为原串是回文串，所以它的循环节必然为回文串

考虑枚举最小的循环节的大小

设长度为 \(x\) 的最小循环节的可能数 \(f(x)\)

那么

• 对于每个长度 \(x\) 为奇数的循环节，在 \(2\) 操作后会有 \(x\) 种不同情况
• 对于每个长度 \(x\) 为偶数的循环节，在 \(2\) 操作后会有 \(\frac{x}{2}\) 种不同情况

累加贡献即可

// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// bool st;
int n, m;
int res = 0;
vector<int> vec;
map<int, int> dp;
// bool en;

void solve()
{
    cin >> n >> m;
    rep(i, 1, n)
    {
        if (i * i > n)
            break;
        if (n % i == 0)
        {
            vec.push_back(i);
            if (i * i != n)
                vec.push_back(n / i);
        }
    }
    sort(ALL(vec));
    for (auto v : vec)
    {
        dp[v] = qpow(m, (v + 1) / 2);
        for (auto p : vec)
        {
            if (p >= v)
                break;
            if (v % p == 0)
                dp[v] = ((dp[v] - dp[p]) % MOD + MOD) % MOD;
        }
        // cerr << dp[v] << ' ';
    }
    for (auto v : dp)
    {
        if (v.first % 2 == 1)
            res = (res + v.second * v.first % MOD) % MOD;
        else
            res = (res + v.second * v.first / 2 % MOD) % MOD;
    }
    cout << res << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}