2020牛客暑期多校第四场 | Moonglade

H.Harder-Gcd-Problem

构造。除了1和大于n/2的质数，若剩下的数的个数为偶数则都能匹配，若为奇数则只有一个不能匹配。

从大到小考虑所有小于等于n/2的素数p，将未被访问的p的倍数加入集合，若集合大小为偶数，则恰好两两匹配，若集合大小为奇数，则取出p*2这个数（因为2是最后考虑的素数，所以p*2一定没有被访问过），剩下的两两匹配。最后把所有取出来的数再两两匹配一下（都是2的倍数）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN=2e5+5,mod=1e9+7;

int T,a,b,c,d,n,cnt;
int vis[MAXN],prime[MAXN],num_p;
int pfactor[MAXN];
void getPrime()
{
    for (int i=2;i<MAXN;i++)
    {
        if (!vis[i]) prime[++num_p]=i;
        for (int j=1;j<=num_p;j++)
        {
            if (i*prime[j]>=MAXN) break;
            pfactor[i*prime[j]]=prime[j];
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}
bool visit[MAXN];

vector<pii>ans;
int main()
{
    getPrime();
    cin>>T;
    while(T--)
    {
        cin>>n;
        for (int i=1;i<=n;i++) visit[i]=0;
        int p=1;
        while(prime[p]<=n/2) p++;
        p--;
        vector<int>now;
        vector<int>tot;
        ans.clear();
        for (int i=p;i>=1;i--)
        {
            now.clear();
            for (int j=prime[i];j<=n;j+=prime[i])
            {
                if (!visit[j])
                {
                    visit[j]=1;
                    now.push_back(j);
                }
            }
            while(now.size()>3)
            {
                int x=now.back();
                now.pop_back();
                int y=now.back();
                now.pop_back();
                ans.push_back({x,y});
            }
            if (now.size()==3)
            {
                int x=now.back();
                now.pop_back();
                tot.push_back(now.back());
                now.pop_back();
                int y=now.back();
                now.pop_back();
                ans.push_back({x,y});
            }
            else
            if (now.size()==2)
            {
                int x=now.back();
                now.pop_back();
                int y=now.back();
                now.pop_back();
                ans.push_back({x,y});
            }
        }
        while(tot.size()>=2)
        {
            int x=tot.back();
            tot.pop_back();
            int y=tot.back();
            tot.pop_back();
            ans.push_back({x,y});
        }
        printf("%d\n",ans.size());
        for (auto xx:ans) printf("%d %d\n",xx.first,xx.second);
    }
    return 0;
}

A.Ancient_Distance

dfs序+线段树维护子树

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " : " << x << " "
#define debugl(x) cerr << #x << " : " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 5;

int T, n, dp[N], dep[N], mxdep, ans[N], dfn[N], esc[N], id[N], idx, pre[N][25];

ll sum;

vector<int> G[N];

vector<pii> rb;

struct segment_tree{
    #define lson ((o << 1))
    #define rson ((o << 1) | 1)
    #define mid ((l + r) >> 1)
    int t[N << 4];
    void pushup(int o) {
        t[o] = max(t[lson], t[rson]);
    }
    void build(int o, int l, int r) {
        if (l == r) {
            t[o] = dep[l];
            return;
        }
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushup(o);
    }
    int query(int o, int l, int r) {
        if (l == r) return l;
        if (t[lson] > t[rson]) return query(lson, l, mid);
        else return query(rson, mid + 1, r);
    }
    void clean(int o, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            t[o] = 0;
            return;
        }
        if (tl <= mid) clean(lson, l, mid, tl, tr);
        if (tr > mid) clean(rson, mid + 1, r, tl, tr);
        pushup(o);
    }
    void rollback(int o, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            if (l == r) t[o] = dep[l];
            else pushup(o);
            return;
        }
        if (tl <= mid) rollback(lson, l, mid, tl, tr);
        if (tr > mid) rollback(rson, mid + 1, r, tl, tr);
        pushup(o);
    }
}st;

void dfs(int x, int f) {
    dfn[x] = ++idx;
    id[idx] = x;
    dep[idx] = dp[x];
    if (f != -1) pre[idx][0] = dfn[f];
    mxdep = max(mxdep, dp[x]);
    for (int to : G[x]) {
        dp[to] = dp[x] + 1;
        dfs(to, x);
    }
    esc[x] = idx;
}

int getans(int x) {
    int res = 0;
    while(1) {
        int pos = st.query(1, 1, n);
        int temp = x;
        int k = 21;
        while(temp) {
            if (temp >= (1 << k)) {
                temp -= 1 << k;
                pos = pre[pos][k];
            }
            k--;
        }
        if (pos == 0 || pos == 1) {
            reverse(rb.begin(), rb.end());
            for (auto x : rb) st.rollback(1, 1, n, x.first, x.second);
            rb.clear();
            return res + 1;
        }
        st.clean(1, 1, n, pos, esc[id[pos]]);
        rb.push_back({pos, esc[id[pos]]});
        res++;
    }
}

void init() {
    for (int i = 1; i <= n; i++) {
        G[i].clear();
    }
    sum = mxdep = idx = 0;
    dp[1] = 1;
}

void solve() {
    init();
    for (int i = 1; i <= n - 1; i++) {
        int x; scanf("%d", &x);
        G[x].push_back(i + 1);
    }
    dfs(1, -1);
    for (int i = 1; i <= 21; i++) {
        for (int j = 1; j <= n; j++) pre[dfn[j]][i] = pre[pre[dfn[j]][i - 1]][i - 1];
    }
    st.build(1, 1, n);
    for (int i = 0; i <= mxdep - 1; i++) {
        if (i == 0) {
            ans[i] = n;
            continue;
        }
        ans[i] = getans(i);
        sum += 1ll * (ans[i - 1] - ans[i]) * i;
    }
    printf("%lld\n", sum);
}

int main() {
    while(~scanf("%d", &n)) solve();
    return 0;
}