2019 ICPC徐州网络赛部分题解

Sep 7, 2019 由 小羊

E. XKC’s basketball team

就在区间 $[i+1,R]$ 找最右边大于 $a_i+m$ 的数的位置。然后考虑到线段树去查询，先查右子树，再查左子树，然后写着写着就成了二叉树了……

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+5;
int mmax[MAXN*4], a[MAXN];
#define lson i<<1
#define rson i<<1|1
int n, m;

int query(int x, int y, int L, int R, int i)
{
    if (mmax[i] < x || R <= y) return -1; else if (L == R) return L;
    int mid = (L+R)>>1; int q = query(x, y, mid+1, R, rson);
    if (~q) return q; else return query(x, y, L, mid, lson);
}

void build(int L, int R, int i)
{
    if (L == R) { scanf("%d", &mmax[i]); a[L] = mmax[i]; return; }
    int mid = (L+R)>>1; build(L,mid,lson), build(mid+1,R,rson);
    mmax[i] = max(mmax[lson], mmax[rson]);
}

int main()
{
    scanf("%d %d", &n, &m);
    build(1, n, 1);
    for (int i = 1; i <= n; i++)
    {
        int loc = query(a[i]+m, i, 1, n, 1);
        if (loc > 0) loc = loc - i - 1;
        printf("%d%c", loc, " \n"[i==n]);
    }
    return 0;
}

H. function

想不到，也只能抄抄题解过日子了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 2e5+5;
const int MOD = 998244353;
const int INV2 = (MOD+1)/2;
int pri[MAXN], pcn, sp[MAXN];
int m, Sqrt, id1[MAXN], id2[MAXN];
bool isnp[MAXN]; lld g[MAXN], h[MAXN], w[MAXN], n;

int main()
{
    scanf("%lld", &n);

    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            pcn++; pri[pcn] = i;
            sp[pcn] = (sp[pcn-1] + i) % MOD;
        }

        for (int j = 1; j <= pcn; j++)
        {
            if (i * pri[j] >= MAXN) break;
            isnp[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }

    m = 0, Sqrt = sqrt(n);

    for (lld L = 1, R; L <= n; L = R+1)
    {
        R = n / (n / L), w[++m] = n / L;
        (w[m] <= Sqrt ? id1[w[m]] : id2[R]) = m;
        g[m] = (w[m] - 1) % MOD;
        h[m] = (w[m] % MOD + 2) * (w[m] % MOD - 1) % MOD * INV2 % MOD;
    }

    for (int j = 1; j <= pcn; j++)
    {
        for (int i = 1, d; i <= m && pri[j] <= w[i]/pri[j]; i++)
        {
            d = (w[i]/pri[j]<=Sqrt) ? id1[w[i]/pri[j]] : id2[n/(w[i]/pri[j])];
            g[i] -= g[d] - j + 1;
            h[i] -= pri[j] * (h[d] - sp[j-1]) % MOD;
        }
    }

    lld ans = 0;

    for (int i = 1; i <= pcn; i++)
    {
        if (n / pri[i] >= pri[i])
        {
            for (lld p = pri[i]; p <= n; p *= pri[i])
            {
                lld fk = n/p%MOD;
                ans += (n+1)%MOD*fk%MOD;
                ans -= fk*(fk+1)%MOD*INV2%MOD*p%MOD;
            }
        }
    }

    for (int i = 1; i < Sqrt; i++)
    {
        lld sp2 = h[i] - h[i+1], sp1 = g[i] - g[i+1];
        ans += (n+1)%MOD*i%MOD*sp1%MOD;
        ans -= i*(i+1ll)/2%MOD*sp2%MOD;
    }

    ans %= MOD; if (ans < 0) ans += MOD;
    printf("%lld\n", ans);
    return 0;
}

J. Random Access Iterator

假设深度为树高的叶节点集合为 $R$，则相当于从起点按某种移动方式转移到 $R$ 中的概率。考虑 $dp[u]$ 为从 $u$ 转移不到 $R$ 中的概率，那么有

$dp[u] = \frac{1}{d(u)} \sum_{(u,v)\in T} dp[v]$

同时注意深度为树高的叶节的概率为 $0$，其他叶节点概率为 $1$，即DP初值。然后两遍DFS解决。

#include <vector>
#include <cstdio>
using namespace std;
typedef long long lld;
const int MAXN = 1e6+5;
const int MOD = 1e9+7;
vector<int> G[MAXN];
int maxdep;

lld fpow(lld a, lld k)
{
    lld b = 1;
    for (; k; k>>=1, a=a*a%MOD)
        if (k&1) b=b*a%MOD;
    return b;
}

void dfs1(int u, int p, int d)
{
    maxdep = max(maxdep, d);
    for (auto v : G[u]) if (v != p) dfs1(v, u, d+1);
}

lld dfs2(int u, int p, int d)
{
    int k = 0; lld dp = 0;
    for (auto v : G[u]) if (v != p) dp += dfs2(v, u, d+1), k++;
    if (k) return fpow(dp * fpow(k, MOD-2) % MOD, k);
    else return d != maxdep ? 1 : 0;
}

int main()
{
    int n; scanf("%d", &n);

    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(1,0,1);
    printf("%lld\n", (1+MOD-dfs2(1,0,1))%MOD);
    return 0;
}

K. Center

#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long lld;
typedef pair<int,int> pii;

const lld INF = 1e8;
const lld STD = 1e7;
#define X first
#define Y second

lld trans(int x, int y) { return x * INF + y; }
lld trans(pii n) { return n.X * INF + n.Y; }
pii inv(lld t) { return pii(t/INF, t%INF); }
pii operator*(pii a, int n) { return pii(a.X * n, a.Y * n); }
pii operator+(pii a, pii b) { return pii(a.X + b.X, a.Y + b.Y); }
pii operator-(pii a, pii b) { return pii(a.X - b.X, a.Y - b.Y); }

pii p[1010];
unordered_set<lld> existed;
unordered_map<lld, int> newCenter;

int main()
{
    int n, x, y, tot;
    scanf("%d", &n), tot = n;

    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        x += STD, y += STD;
        p[i] = make_pair(x, y);
        existed.insert(trans(x, y));
    }

    for (int i = 0; i < n; i++)
    {
        int ans = 0;
        for (int j = 0; j < n; j++)
            if (!existed.count(trans(p[i] * 2 - p[j])))
                ans++;
        tot = min(tot, ans);
    }

    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            newCenter[trans(p[i] + p[j])]++;

    int ptp = 0; pii nc;
    for (auto cnt : newCenter)
        if (cnt.second > ptp)
            nc = inv(cnt.first), ptp = cnt.second;
    int maybe = 0;
    for (int j = 0; j < n; j++)
        if (!existed.count(trans(nc - p[j])))
            maybe++;
    tot = min(tot, maybe);

    printf("%d\n", tot);
    return 0;
}