比赛地址

A. 代价

注意到除了有 1 的情况，相邻两个数乘起来都是要比三个数乘起来要好的。那么对于一个没有 1 的序列，可以从两端开始删数，最后会剩下来一个多加一次，我们当然是贪心地让这个多加的数最小了。有 1 的情况可以把它拆成几个没有 1 的极大区间，这些区间都是不相互影响的。每个区间分别计算答案即可，复杂度 O(n)。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAXN=1100000;
const int INF=1E4+233;
int a[MAXN];
int read()
{
    int x=0; char ch=0;
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return x;
}
int main()
{
//  freopen("A.in", "r", stdin);
//  freopen("A.out", "w", stdout);
    int n;
    scanf("%d", &n); a[0]=a[n+1]=1;
    for (int i=1; i<=n; i++) a[i]=read();
    long long ans=0;
    for (int i=1, mn=INF; i<=n+1; i++)
    {
        if (a[i]==1) ans+=(mn==INF?0:mn)+1, mn=INF;
        else
        {
            mn=min(mn, a[i]);
            if (a[i-1]!=1) ans+=a[i]*a[i-1];
        }
    }
    printf("%lld\n", ans-1);
    return 0;
}

B. 礼物

数据范围怎么看怎么是道毒瘤多项式。。比赛时先跑去做 C 了。

回来打表找规律，发现第 p 个位置满足性质的充要条件是 p\mid ans+1。而 p 又是质数，所以直接将所有需要满足性质的质数乘起来减一就是答案了。

背景里大写着时限扩大，这应该是比较明显地放线性筛过了。由于评测机有波动可能需要多交几次。。

所以正解是什么科技啊（）

#include <cstdio>
const int MAXN=3E8+5;
const int MAXP=2E7;
bool mark[MAXN];
int pri[MAXP];
int inv(int n, int p)
{
    int r=1, k=p-2;
    while (k)
    {
        if (k&1) r=1ll*r*n%p;
        n=1ll*n*n%p; k>>=1;
    }
    return r;
}
int main()
{
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    int n, m, c, p=0;
    scanf("%d%d%d", &n, &m, &c);
    for (int i=2; i<=n; i++)
    {
        if (!mark[i]) pri[++p]=i;
        for (int j=1; j<=p&&i*pri[j]<=n; j++)
        {
            mark[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        }
    }
    int ans=1;
    for (int i=2; i<=p; i++) ans=1ll*ans*pri[i]%c;
    while (m--)
    {
        int x; scanf("%d", &x);
        if (x==1) { puts("-1"); return 0; }
        if (pri[x]!=1) ans=1ll*ans*inv(pri[x], c)%c, pri[x]=1;
    }
    printf("%d\n", ans-1);
    return 0;
}

C. 单调栈

有一点点反套路，虽然是找字典序最小但不是逐位确定。

考虑先复选 S 序列。我们假设前 i-1 个位置的 p 排列和 S 序列已经确定了，现在加入第 i 个位置。那么我们应该是希望尽量少弹出一些栈里的元素为好，因为多弹一个元素就表明当前位置比它小，它就得“让位”加一。那么不弹元素显然是最好的，也不会不满足题意，所以若 S_i=-1 就直接把它改成 S_{i-1}+1。

但一个 S 序列可能不止对应一个排列。要还原最小字典序的排列，还是需要用到上面的贪心思想，使“让位”的元素尽量少。画几个样例就可以发现直接把 p_i 设成最后一个弹掉的元素就可以了，然后把弹出所有该弹的元素后的栈顶之后的元素都“让位”加一。我们需要及时知道 p_i 的值，所以需要维护区间 +1 、单点修改和单点查询，这用树状数组维护一下就好了，复杂度 O(n\log n)。不知道有没有线性做法= =

#include <cstdio>
const int MAXN=1100000;
int n, s[MAXN], q[MAXN];
struct BIT
{
    int c[MAXN];
    static int lb(int x) { return x&-x; }
    void add(int x, int k)
    {
        while (x<=n) c[x]+=k, x+=lb(x);
    }
    int sum(int x)
    {
        int ret=0;
        while (x>0) ret+=c[x], x-=lb(x);
        return ret;
    }
} bit;
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
    {
        scanf("%d", &s[i]);
        if (s[i]==-1) s[i]=s[i-1]+1;
        if (s[i]==s[i-1]+1)
            bit.add(i, i), bit.add(i+1, -i);
        else
        {
            int t=bit.sum(q[s[i]]);
            bit.add(q[s[i]-1]+1, 1);
            bit.add(i, t-1), bit.add(i+1, -t);
        }
        q[s[i]]=i;
    }
    for (int i=1; i<=n; i++)
        printf("%d ", bit.sum(i));
    putchar('\n');
    return 0;
}

D. 河童重工

题意

给出两棵边带权的树 T_1,T_2 和一张完全图，完全图的边权为两棵树中对应节点距离之和。求该完全图的最小生成树。

这个题的子问题是 AT3611 Tree MST。我的题解在这里。

考虑对 T_2 点分治。对于过每个分治中心的所有路径，它可以被拆成两条路径。设分治范围内一点 v 到分治中心的距离为 w_v，那么当前的问题可以转化为求 x,y 边长为 w_x+w_y+dis_{x,y} 的完全图的 MST（这里的 dis 是 T_1 上的距离），也就是子问题。然后用里面的三种做法分别可以做到 O(n\log^3 n),O(n\log^2 n),O(n\log n)。

我选用了第二种做法，也就是 O(n\log^2 n) 的实现。实测常数并不大。

长代码预警

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=110000;
const int MAXB=20;
const int INF=1E9;
struct Edge1
{
    int to, val;
    Edge1(int v, int w): to(v), val(w) {}
};
struct Edge2
{
    int u, v, w;
    Edge2() {}
    Edge2(int a, int b, int c):
        u(a), v(b), w(c) {}
    bool operator < (const Edge2& rhs) const
    {
        return w<rhs.w||w==rhs.w&&v<rhs.v;
    }
};
struct DSU
{
    int f[MAXN];
    void init(int n)
    {
        for (int i=1; i<=n; i++) f[i]=i;
    }
    int getf(int x)
    {
        if (x==f[x]) return x;
        return f[x]=getf(f[x]);
    }
    bool merge(int u, int v)
    {
        int x=getf(u), y=getf(v);
        if (x==y) return 0;
        f[x]=y; return 1;
    }
};
typedef pair<int, int> pii;
int n, m, c;
int pos[MAXN], dis[MAXN];
vector<Edge2> edg;
namespace SubProb
{
    int root, a[MAXN];
    vector<Edge1> g[MAXN];
    DSU dsu;
    pii dp1[MAXN], dp2[MAXN];
    Edge2 p[MAXN];
    void clear()
    {
        for (int i=1; i<=m; i++) g[i].clear();
    }
    void dfs1(int u)
    {
        for (Edge1 e:g[u])
        {
            int v=e.to; dfs1(v);
            dp1[u]=min(dp1[u], make_pair(dp1[v].first+e.val, dp1[v].second));
        }
        for (Edge1 e:g[u])
        {
            int v=e.to;
            dp2[u]=min(dp2[u], dsu.f[dp1[v].second]!=dsu.f[dp1[u].second]?
            make_pair(dp1[v].first+e.val, dp1[v].second):
            make_pair(dp2[v].first+e.val, dp2[v].second));
        }
    }
    void dfs2(int u)
    {
        for (Edge1 e:g[u])
        {
            int v=e.to;
            dp1[v]=min(dp1[v], make_pair(dp1[u].first+e.val, dp1[u].second));
            dp2[v]=min(dp2[v], dsu.f[dp1[u].second]!=dsu.f[dp1[v].second]?
            make_pair(dp1[u].first+e.val, dp1[u].second):
            make_pair(dp2[u].first+e.val, dp2[u].second));
            dfs2(v);
        }
    }
    void MST()
    {
        dsu.init(m);
        int cnt=0;
        while (cnt<c-1)
        {
            for (int i=1; i<=m; i++)
            {
                dp1[i]=make_pair(a[i], i);
                dp2[i]=make_pair(INF, 0);
            }
            dfs1(root); dfs2(root);
            for (int i=1; i<=m; i++)
            {
                pii t=dsu.f[dp1[i].second]!=dsu.f[i]?dp1[i]:dp2[i];
                p[i]=Edge2(i, t.second, t.first+a[i]);
            }
            for (int i=1; i<=m; i++) p[dsu.f[i]]=min(p[dsu.f[i]], p[i]);
            for (int i=1; i<=m; i++)
            {
                Edge2 t=p[dsu.getf(i)];
                if (t.w<INF&&dsu.merge(t.u, t.v))
                    edg.push_back(Edge2(pos[t.u], pos[t.v], t.w)), cnt++;
            }
            for (int i=1; i<=m; i++) dsu.getf(i);
        }
    }
}
namespace Tree1
{
    vector<Edge1> g[MAXN];
    int fa[MAXN][MAXB];
    int dfn[MAXN], dfc;
    int dep[MAXN], sum[MAXN];
    int sta[MAXN], top;
    inline bool cmp(int a, int b)
    {
        return dfn[a]<dfn[b];
    }
    void read()
    {
        for (int i=1; i<n; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back(Edge1(v, w));
            g[v].push_back(Edge1(u, w));
        }
    }
    void dfs(int u, int f, int d)
    {
        dfn[u]=++dfc, fa[u][0]=f, dep[u]=d;
        for (int b=1; b<=16; b++)
            fa[u][b]=fa[fa[u][b-1]][b-1];
        for (Edge1 e:g[u])
        {
            int v=e.to;
            if (v!=f) sum[v]=sum[u]+e.val, dfs(v, u, d+1);
        }
    }
    int lca(int u, int v)
    {
        if (dep[u]<dep[v]) swap(u, v);
        for (int b=16; b>=0; b--)
            if (dep[fa[u][b]]>=dep[v]) u=fa[u][b];
        if (u==v) return u;
        for (int b=16; b>=0; b--)
            if (fa[u][b]!=fa[v][b]) u=fa[u][b], v=fa[v][b];
        return fa[u][0];
    }
    void insert(int x)
    {
        if (top==0) { sta[++top]=x; return; }
        int v=lca(pos[x], pos[sta[top]]);
        if (v==pos[sta[top]]) { sta[++top]=x; return; }
        while (top>1&&dfn[pos[sta[top-1]]]>=dfn[v])
        {
            SubProb::g[sta[top-1]].push_back(
            Edge1(sta[top], sum[pos[sta[top]]]-sum[pos[sta[top-1]]]));
            top--;
        }
        if (v!=pos[sta[top]])
        {
            int y=++m; pos[y]=v;
            SubProb::g[y].push_back(Edge1(sta[top], sum[pos[sta[top]]]-sum[v]));
            sta[top]=y;
        }
        sta[++top]=x;
    }
    void getVT()
    {
        sort(pos+1, pos+m+1, cmp);
        c=m; top=0;
        for (int i=1; i<=c; i++) insert(i);
        while (top>1)
        {
            SubProb::g[sta[top-1]].push_back(
            Edge1(sta[top], sum[pos[sta[top]]]-sum[pos[sta[top-1]]]));
            top--;
        }
        int rt=1;
        for (int i=2; i<=m; i++)
            if (dep[pos[i]]<dep[pos[rt]]) rt=i;
        SubProb::root=rt;
        for (int i=1; i<=c; i++) SubProb::a[i]=dis[pos[i]];
        for (int i=c+1; i<=m; i++) SubProb::a[i]=INF;
    }
}
namespace Tree2
{
    vector<Edge1> g[MAXN];
    bool vis[MAXN];
    int sz[MAXN], mx[MAXN];
    int sum, root;
    void read()
    {
        for (int i=1; i<n; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back(Edge1(v, w));
            g[v].push_back(Edge1(u, w));
        }
    }
    void getRoot(int u, int f)
    {
        sz[u]=1, mx[u]=0;
        for (Edge1 e:g[u])
        {
            int v=e.to;
            if (!vis[v]&&v!=f)
            {
                getRoot(v, u); sz[u]+=sz[v];
                mx[u]=max(mx[u], sz[v]);
            }
        }
        mx[u]=max(mx[u], sum-sz[u]);
        if (mx[u]<mx[root]) root=u;
    }
    void getDis(int u, int f)
    {
        pos[++m]=u;
        for (Edge1 e:g[u])
        {
            int v=e.to;
            if (!vis[v]&&v!=f)
            {
                dis[v]=dis[u]+e.val;
                getDis(v, u);
            }
        }
    }
    void solve(int u)
    {
        m=0, dis[u]=0;
        getDis(u, 0);
        Tree1::getVT();
        SubProb::MST();
        SubProb::clear();
        vis[u]=1;
        for (Edge1 e:g[u])
        {
            int v=e.to;
            if (!vis[v])
            {
                sum=sz[v], root=0;
                getRoot(v, u); solve(root);
            }
        }
    }
    void work()
    {
        mx[0]=sum=n, root=0;
        getRoot(1, 0); solve(root);
    }
}
DSU dsu;
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    scanf("%d", &n);
    Tree1::read(); Tree2::read();
    Tree1::dfs(1, 0, 1); Tree2::work();
    sort(edg.begin(), edg.end());
    dsu.init(n);
    int cnt=0; long long ans=0;
    for (Edge2 e:edg)
    {
        if (dsu.merge(e.u, e.v)) cnt++, ans+=e.w;
        if (cnt==n-1) break;
    }
    printf("%lld\n", ans);
    return 0;
}