Star 的档案库

Appearance

我还是太菜了，只签了一道签到，实现了一个正解，打了点暴力和对拍。

B. Bitwise Maximization ​

  • 异或线性基

异或线性基，模板记住了。

cpp
#include <iostream>

using namespace std;

const int N = 500010;
int a[N], p[30];

void insert(int x) {
    for (int i = 29; i >= 0; --i) {
        if (!(x >> i & 1)) continue;
        if (!p[i]) {
            p[i] = x;
            break;
        }
        else x ^= p[i];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        fill(p, p + 30, 0);
        int n, s = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            s ^= a[i];
        }
        for (int i = 1; i <= n; ++i) {
            insert(a[i] & (~s));
        }
        int res = 0;
        for (int i = 30; i >= 0; --i) {
            res = max(res, res ^ p[i]);
        }
        cout << (res << 1) + s << endl;
    }
    return 0;
}

F. Fabulous Tree ​

  • 树形 DP

是一个比较抽象的树形 DP

G. GCD Graph ​

  • 数论
  • 动态规划
  • 埃氏筛
  • 前缀和

打了一堆表之后发现，1e7 以内素数间隔最大只有 150，间隔以内的暴力 DP 求，以外的统计 互质 ? 1 : 2 步，求和两部分。

cpp
#include <bits/stdc++.h>
#define vi vector<int>

using namespace std;

const int N = 10000010;
typedef long long LL;
int dis[N], ne[N];
int v[N], prime[N], len;

void init() {
    int n = 10000000;
    for (int i = 2; i <= n; ++i) {
        if (v[i] == 0) {
            v[i] = i;
            prime[++len] = i;
        }
        for (int j = 1; j <= len; ++j) {
            if (prime[j] > v[i] || prime[j] > n / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
}

int getp(int n) {
    int l = 1, r = len;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (prime[mid] <= n) l = mid;
        else r = mid - 1;;
    }
    return prime[l];
}

vi get(int a) {
    vi ret;
    for (int i = 1; i * i <= a; i++) {
        if (a % i == 0) {
            ret.push_back(i);
            if (i != a / i)
                ret.push_back(a / i);
        }
    }
    return ret;
}

int get1(int l, int r,int n) {
    vi a = get(n);
    sort(a.begin(), a.end());
    vi cnt(a.size());
    for (int i = 0; i < a.size(); i++) {
        cnt[i] = r / a[i] - (l - 1) / a[i];
    }
    for (int i = a.size() - 1; i >= 0; i--) {
        for (int j = i + 1; j < a.size(); j++) {
            if (a[j] % a[i] == 0)
                cnt[i] -= cnt[j];
        }
    }
    return cnt[0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int T;
    cin >> T;
    while (T--) {
        int l, r, n;
        cin >> l >> r >> n;
        int p = getp(n);
        if (r <= p) {
            int t = get1(l, r, n);
            cout << (r - l + 1) * 2 - t << '\n';
        }
        else if (p <= l) {
            LL res = 0;
            memset(dis + l, 0x3f, sizeof(int) * (n - l + 1));
            dis[n] = 0;
            for (int i = n - 1; i >= l; --i) {
                for (int j = i + 1; j <= n; ++j) {
                    dis[i] = min(dis[i], __gcd(i, j) + dis[j]);
                }
            }
            for (int i = l; i <= r; ++i) {
                res += dis[i];
            }
            cout << res << '\n';
        }
        else {
            LL res = 0;
            memset(dis + p, 0x3f, sizeof(int) * (n - p + 1));
            dis[n] = 0;
            for (int i = n - 1; i > p; --i) {
                for (int j = i + 1; j <= n; ++j) {
                    dis[i] = min(dis[i], __gcd(i, j) + dis[j]);
                }
            }
            for (int i = p + 1; i <= r; ++i) {
                res += dis[i];
            }
            cout << res + (p - l + 1) * 2 - get1(l, p, n) << '\n';
        }
    }
    return 0;
}

H. Hyperspace Pairing ​

K. Kindergarten ​

L. Lazy Shuffling ​

M. Maybe Connected ​

  • 构造

签到，尽可能连一个最大的菊花。

cpp
#include <iostream>

using namespace std;
typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LL n, m;
        cin >> n >> m;
        if (m >= n - 1) cout << (n - 1) * (n - 2) / 2 - m + (n - 1) << '\n';
        else cout << (m - 1) * m / 2 << '\n';
    }
    return 0;
}

N. Narrow to Median ​

cpp