YLOJ 11月30日考试官方solution

考试总结

---

这是一场CCF性质浓厚的比赛，起码从题目名称就可以看出来。

四道题都是原题）。

预计平均分：$30+100+30+40=200$分。

预计最高分：$70+100+100+100=370$分。

实际平均分：$0+100+0+0=100$分。

实际最高分：$0+100+100+0=200$分。

为什么没有人写暴力呀/fad。

T1 数的重心（$center$）

原题P6563 [SBCOI2020] 一直在你身旁，本题是加强版（但是本题AC代码交上去会MLE）

题意：
给定序列a，每次可以选定一个位置，获取这个位置的值，并把原区间分成两部分，任意选择一个区间进行相同的操作，使得获得的值之和最小。

T1应该是本场最难的题。（在我心中和CSP2020儒略日差不多）

分析部分分：

• 对于$10\%$的数据，$1\leqslant n\leqslant 10$，不管是爆搜还是怎么乱搞都可以过。
• 对于$30\%$的数据，$1\leqslant n\leqslant 500$：观察题面很显然可以列出转移方程：$f_{i,j}=\min_{k=i}^{j-1}\{a_k+\max\{f_{i,k},f_{k+1,j}\}\}$，直接进行$O(n^3)$的$dp$即可。

然后是一个比较麻烦的部分分：对于另外$40\%$的数据，$a_i\leqslant a_{i+1}$。

我们发现这个$\min$里面的$\max$非常讨厌，我们考虑怎么把它去掉。

可以发现一定有一个分界点$pos$，使得在这个分界点及之前，都满足$f_{k+1,j}\geqslant f_{i,k}$，在这个分界点之后，满足$f_{i,k}\geqslant f_{k+1,j}$。

这个性质很显然，因为我们消除掉一个区间一定比消除掉它的子区间更劣。

很显然我们只要固定住右端点，随着左端点的增加，$pos$一定也会增加。

倒序枚举右端点$j$，正序枚举左端点$i$，那么我们就可以同时处理出每个区间的分界点$pos$，这样我们的转移式就变为了：$f_{i,j}=\min\{\min_{k=i}^{pos}\{ f_{k+1,j}+a_k\},\min_{k=pos+1}^j\{f_{i,k}+a_k\}\}$。

我们发现前面的$f_{k+1,j}+a_k$与$i$无关，因此我们可以保存一个单调队列来记录。

对于$\min_{k=pos+1}^j\{f_{i,k}+a_k\}$，我们发现一定有$f_{i,k}+a_k\leqslant f_{i,k+1}+a_{k+1}$，因为$f_{i,k}\leqslant f_{i,k+1},a_k\leqslant a_{k+1}$。

有了这个结论，很显然$f_{i,pos+1}$最小，我们直接用$f_{i,pos+1}$代替$\min_{k=pos+1}^j\{f_{i,k}+a_k\}$就好了。

时间复杂度：$O(n^2)$。

#include<stdio.h>
#define int long long
#define inf 100000000000000000
const int maxn=3005;
int T,n;
int a[maxn],f[maxn][maxn];
inline int min(int a,int b){
    return a<b? a:b;
}
struct Monotonic_Queue{
    int l,r;
    int v[maxn],q[maxn];
    void init(){
        l=1,r=0;
    }
    void check(int k){
        while(l<=r&&q[l]>k)
            l++;
    }
    void push(int a,int b){
        while(l<=r&&a<v[r])
            r--;
        v[++r]=a,q[r]=b;
    }
    int top(){
        return l>r? inf:v[l];
    }
}MQ;
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(int r=2;r<=n;r++){
            int pos=r-1;
            MQ.init();
            for(int l=r-1;l>=1;l--){
                while(pos>=l&&f[l][pos]>=f[pos+1][r])
                    pos--;
                MQ.check(pos);
                f[l][r]=min(f[l][pos+1]+a[pos+1],MQ.top());
                if(l>1)
                    MQ.push(f[l][r]+a[l-1],l-1);
            }
        }
        printf("%lld\n",f[1][n]);
    }
    return 0;
}

考虑不满足$a_i\leqslant a_{i+1}$的数据。

瞄一眼空间范围，发现有$512MB$，因此可以知道可以多开一些数组。

首先，上面关于区间分界点的结论仍然是正确的，也就是说我们仍然可以使用这个转移方程：$f_{i,j}=\min\{\min_{k=i}^{pos}\{ f_{k+1,j}+a_k\},\min_{k=pos+1}^j\{f_{i,k}+a_k\}\}$。

我们换一种枚举方式：倒序枚举$i$，正序枚举$j$，这样我们仍然可以维护出分界点$pos$，并可以用单调队列维护$\min_{k=pos+1}^j\{f_{i,k}+a_k\}$。

然后考虑怎么求$\min_{k=i}^{pos}\{f_{k+1,j}+a_k\}$，我们发现这个东西与$i$无关，我们可以尝试使用单调队列。

具体地说，我们可以对于每个点$j$保留一个保存当前所有$f_{k+1,j}+a_k$的单调队列，在每一次处理完一个区间的数据后在单调队列$j$中插入$f_{k,j}+a_{k-1}$。

然后，我们遍历到区间$[l,r]$时，可以把$r$的单调队列去除掉位置大于等于分界点$pos$的所有值。我们发现这样的去除一定是正确的，因为我们倒序枚举左端点，所以我们每次遇到$r$，$pos$都会减小，这样我们每一次对队首的判定去除掉的所有状态以后也用不到。

这样，$\min_{k=i}^{pos}\{f_{k+1,j}+a_k\}$就让我们用$j$的队首表示出来了。

时间复杂度：$O(n^2)$。

#include<stdio.h>
#define int long long
#define inf 100000000000000000
const int maxn=3005;
int n,L;
int a[maxn],f[maxn][maxn];
inline int min(int a,int b){
    return a<b? a:b;
}
struct Monotonic_Queue{
    int l,r;
    int v[maxn],q[maxn];
    void init(){
        l=1,r=0;
    }
    void check1(int k){
        while(l<=r&&q[l]<=k)
            l++;
    }
    void check2(int k){
        while(l<=r&&q[l]>=k)
            l++;
    }
    void push(int a,int b){
        while(l<=r&&a<=v[r])
            r--;
        v[++r]=a,q[r]=b;
    }
    int front(){
        return l>r? inf:v[l];
    }
}MQ,q[maxn];
signed main(){
    scanf("%lld%lld",&n,&L);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        q[i].init();
    }
    for(int l=n-1;l>=1;l--){
        int pos=l;
        MQ.init(),MQ.push(0+a[l],l);
        q[l+1].push(0+a[l],l);
        for(int r=l+1;r<=n;r++){
            while(pos<r&&f[l][pos]<=f[pos+1][r])
                pos++;
            MQ.check1(pos-1);
            q[r].check2(pos);
            f[l][r]=min(MQ.front(),q[r].front());
            MQ.push(f[l][r]+a[r],r);
            if(l>1)
                q[r].push(f[l][r]+a[l-1],l-1);
        }
    }
    if(f[1][n]>L)
        puts("wykrank1ingenerals!");
    else printf("%lld\n",f[1][n]);
    return 0;
}

T2 赛道系统（$system$）

原题：P7100 [w3R1] 团

题意：
给定$n$个集合，每个集合有若干个元素对$p,v$，表示其中所有元素两两之间连一条边，边权为两个元素$p$相对应的权值$v$，求单源最短路径。

T2是这场比赛的签到题，应该大家都AC了吧。（在我心中和简单的CSPT2差不多）

对于每个集合，我们可以建一个虚点，其中每一个点$p$向虚点连一条它权值的边$v$。

考虑这为什么对：因为我们的虚点之间没有边，因此每个点想要到其他的点一定会经过虚点，因此这个路径的长度是等于这两个点在集合中的点权之和的。

然后我们直接跑一个$dijkstra$就可以了。

时间复杂度：$O((n+k)\log (n+k))$。

#include<stdio.h>
#include<queue>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
const int maxn=600005,maxm=800005;
int n,k,e;
int start[maxn],to[maxm],then[maxm],vis[maxn];
long long worth[maxm],dis[maxn];
priority_queue< pair<long long,int> >q;
inline void add(int x,int y,long long z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
void dijkstra(int s){
    for(int i=1;i<=n+k;i++)
        dis[i]=inf,vis[i]=0;
    dis[s]=0,q.push(make_pair(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(dis[y]>dis[x]+worth[i])
                dis[y]=dis[x]+worth[i],q.push(make_pair(-dis[y],y));
        }
    }
}
int read(){
    int x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-48;
    return x;
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=k;i++){
        int s,x,y;
        s=read();
        for(int j=1;j<=s;j++){
            x=read(),y=read();
            add(x,n+i,y),add(n+i,x,y);
        }
    }
    dijkstra(1);
    for(int i=1;i<=n;i++)
        printf("%lld%c",dis[i],i==n? '\n':' ');
    return 0;
}

T3 加法调用（$plus$）

原题CF520E Pluses everywhere，本题套上了一个期望。

题意：
给定一个正整数$n$，在$n$的所有数位中随机放置$m$个加号，求表达式值的期望。

较简单的一道题，预测会有巨佬$5min$推完式子。（在我心中和CSPT3差不多）

给定一个长度为$n$的数$a$，在$a$的数位中放入$m$个加号，求这个值的期望。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant n-1$

转化：求所有的值之和，除以${n-1\choose m}$，即$n-1$个数位，放入$m$个加号。

考虑每一位与这一位后面第一个加号：若考虑到第$i$位，它后面第一个加号位置在$i+j-1$后面。

一个一个考虑，如果第一个加号在$i$后面，那么$a_i$作为个位，贡献为$a_i$，这种情况会出现${n-2\choose m-1}$次，即还剩$n-2$个位置，放置$m-1$个加号。

同理，如果第一个加号在$i+1$后面，那么$a_i$作为十位，贡献为$10a_i$，这种情况会出现${n-3\choose m-1}$次。

一般的，如果第一个加号在$i+j-1$后面，那么$a_i$作为第$j$位（从低到高数），贡献为$10^{j-1}a_i$，出现次数为${n-j-1\choose m-1}$。

还有一种情况，就是$i$后面没有加号，那么$a_i$作为第$n-i+1$位（从低到高数），贡献为$10^{n-i}a_i$，出现次数为${i-1\choose m}$。

统计一下和：

$$\sum_{i=1}^n(\sum_{j=1}^{n-i+1}10^{j-1}\cdot a_i\cdot {n-j-1\choose m-1})+\sum_{i=m+1}^n+10^{n-i}\cdot a_i\cdot {i-1\choose m}$$

乍一看这个求和式是二维的，但是它可以转化一下：

我们考虑交换求和式，枚举位数$j$：

$$\sum_{j=1}^{n-m} 10^{j-1}\cdot (\sum_{i=1}^{n-j} a_i\cdot {n-j-1\choose m-1})+\sum_{i=m+1}^n+10^{n-i}\cdot a_i\cdot {i-1\choose m}$$

这样，因为$C_{n-j-1}^{m-1}$与$i$无关，所以可以拆出来：

$$\sum_{j=1}^{n-m} 10^{j-1}\cdot {n-j-1\choose m-1}\cdot\sum_{i=1}^{n-j}a_i+\sum_{i=m+1}^n+10^{n-i}\cdot a_i\cdot {i-1\choose m}$$

处理一下前缀和就可以做到$O(n)$了。

#include<stdio.h>
#include<iostream>
#define int long long
using namespace std;
const int maxn=2000005,mod=1777771;
int i,j,k,m,n,ans;
int fac[maxn],nfac[maxn],sum[maxn],pow10[maxn];
string s;
inline int c(int n,int m){
    return fac[n]*nfac[m]%mod*nfac[n-m]%mod;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
signed main(){
    cin>>s>>m;
    n=s.size(),s=" "+s;
    fac[0]=1;
    for(i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    nfac[n]=ksm(fac[n],mod-2);
    for(i=n;i>=1;i--)
        nfac[i-1]=nfac[i]*i%mod;
    pow10[0]=1;
    for(i=1;i<=n;i++){
        sum[i]=sum[i-1]+(s[i]-48);
        pow10[i]=pow10[i-1]*10ll%mod;
    }
    for(i=1;i<=n-m;i++)
        ans=(ans+pow10[i-1]*sum[n-i]%mod*c(n-i-1,m-1)%mod)%mod;
    for(i=m+1;i<=n;i++)
        ans=(ans+pow10[n-i]*(s[i]-48)*c(i-1,m)%mod)%mod;
    printf("%lld\n",ans*ksm(c(n-1,m)%mod,mod-2)%mod);
    return 0;
}

T4 树上的树（$tree$）

原题CF1179D Fedor Runs for President

题意：
定义简单路径为任意一个点仅经过一次的路径。给定一颗$n$个点的树，求添加一条边后最多有多少无向简单路径。

本场比赛最套路的一道题。（在我心中和CSPT4差不多）

先讲一下定义：$size_x$为$x$的子树大小，$sons_x$为$x$的儿子数量，$son(x)$指$x$所有儿子形成的集合，$path(x,y)$指$x$到$y$路径上所有点形成的集合。

因为树上每两个点有且仅有一条路径，所以原本树上的路径数量为$\frac{n(n-1)}{2}$，然后考虑添加一条边会增加多少条无向简单路径：

假如我们将要添加$(x,y)$，那么我们先提出$x$到$y$的路径，假如$k$在路径上，我们称$s_k$为以$k$为根，不向路径上扩展的子树大小。那么我们可以知道每一颗这样的子树之间都多了一条路径，根据乘法原理有这条边对答案贡献为$\frac{\sum_{k\in path(x,y)}(n-s_k)\cdot s_k}{2}$（除$2$是为了去重）。

变一下型：

$$\frac{\sum_{k\in path(x,y)}(n-s_k)\cdot s_k}{2}=\frac{\sum_{k\in path(x,y)}(n\cdot s_k-s_k^2)}{2}\\=\frac{n\cdot \sum_{k\in path(x,y)}s_k-\sum_{k\in path(x,y)}s_k^2}{2}=\frac{n^2-\sum_{k\in path(x,y)}s_k^2}{2}$$

那么我们的目的找到一条路径$path(x,y)$，让$\sum_{k\in path(x,y)}s_k^2$最小。

我们运用点分治的思想，考虑枚举每一个点$x$，计算$x$子树中，每一条经过$x$的路径的答案。

设$f_x$为从$x$到$x$子树中任意结点，且满足让上式最小的路径，那么很容易列出转移方程：

$$f_x=\min_{y\in son(x)}\{f_y+(size_x-size_y)^2\}$$

解释一下，$size_x-size_y$相当于$s_x$（因为$x$的儿子$y$在路径上）。

这个转移方程很显然，也很容易在$O(n)$的复杂度中求出。

size[x]=1;
for(int i=start[x];i;i=then[i]){
    int y=to[i];
    if(y==last)
        continue;
    dfs(y,x);
    size[x]+=size[y];
}
f[x]=size[x]*size[x];
for(int i=start[x];i;i=then[i]){
    int y=to[i];
    if(y==last)
        continue;
    f[x]=min(f[x],f[y]+(size[x]-size[y])*(size[x]-size[y]));
    p[++ps]=y;
}

然后考虑$x$子树中，每一条经过$x$的路径，设这条路径经过两个$x$的儿子$y,z$，那么我们可以把$f_y$代表的路径，$f_z$代表的路径和$x$拼起来计算答案。

我们枚举两个儿子：

$$ans=\min_{y\in son(x),z\in son(x),y\ne z}\{f_y+f_z+(n-size_y-size_z)^2\}$$

同样解释一下，$n-size_y-size_z$是除了$y$子树和$z$子树中的结点外所有的结点，因为$x,y,z$在均路径上，所以其他的点都必须分配到$x$子树中，即$s_x=n-size_y-size_z$。

枚举它的复杂度就是$O(sons_x^2)$了，加上$dfs$，复杂度肯定无法通过本题。

考虑树上斜率优化，我们枚举$x$的儿子$y$，然后在斜率优化中求出决策点$z$。

套路性地枚举两个决策点$size_q\leqslant size_p$，且$p$比$q$更优，即$f_y+f_p+(n-size_y-size_p)^2\leqslant f_y+f_q+(n-size_y-size_q)^2$。

拆开平方，消掉相同的项就可以得到$f_p+size_p^2-2(n-size_y)\cdot size_p\leqslant f_q+size_q^2-2(n-size_y)\cdot size_q$。

套路性变形：$(f_p+size_p^2)-(f_q+size_q^2)\leqslant 2(n-size_y)(size_p-size_q)$。

因为$size_p\geqslant size_q$，那么除过来不变号，化成斜率式：$\frac{(f_p+size_p^2)-(f_q+size_q^2)}{size_p-size_q}\leqslant 2(n-size_y)$。

注意如果$size_p=size_q$需要特判一下：

inline int x(int p){
    return size[p];
}
inline int y(int p){
    return f[p]+size[p]*size[p];
}
inline double slope(int a,int b){
    if(x(a)==x(b))
        return y(a)>y(b)? inf:-inf;
    return 1.0*(y(a)-y(b))/(x(a)-x(b));
}

我们在斜率优化之前给所有儿子按照$size$排一下序，就可以上斜率优化板子了。

---

我们分析一下时间复杂度：对于每个点，复杂度的瓶颈就是遍历到后面的所有儿子和给它所有儿子$\text{sort}$一遍。

先证明一个引理：

$$a\log a+b\log b\leqslant(a+b)\log(a+b)$$

不妨设$a\geqslant b$，那么$a\log a+b\log b\leqslant a\log a+b\log a=(a+b)\log a\leqslant (a+b)\log(a+b)$。

对于排序，它的复杂度是$O(n\log n)$的，因此我们可以直接看做每个点$x$都需要$O(sons_x\log sons_x)$的处理。

然后，我们处理递归：

可以按照深度归纳，我们证明对于$x$，处理它的复杂度一定是$O(size_x\log size_x)$的。

首先对于叶子结点一定成立，因为处理它的复杂度就是$O(1)$的。

对于非叶子结点$x$，假如它的儿子是$y_1\cdots y_k$，且它每个儿子都满足这个复杂度约束，那么处理它儿子的总复杂度为$size_{y_1}\log size_{y_1}+size_{y_2}\log size_{y_2}+\cdots+size_{y_k}\log size_{y_k}$，按照上面的引理一直处理下去，就可以得到上式小于等于$(size_{y_1}+\cdots+size_{y_k})\log (size_{y_1}+\cdots+size_{y_k})$，因为$size_x=size_{y_1}+\cdots+size_{y_k}+1$，所以递归所有儿子的复杂度是$O(size_x\log size_x)$的。

再加上排序的复杂度，便可以得出处理$x$的复杂度是$O(size_x\log size_x)$的。

我们从$1$开始$\text{dfs}$，那么由上面的证明可以知道处理$1$的时间复杂度为$O(size_1\log size_1)$。

即总复杂度为$O(n\log n)$。

#include<stdio.h>
#include<algorithm>
#define int long long
#define inf 1000000000000000000
using namespace std;
const int maxn=500005,maxm=1000005;
int i,j,k,m,n,e,ans=inf;
int start[maxn],to[maxm],then[maxm],f[maxn],size[maxn],p[maxn],q[maxn];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
inline bool cmp(int a,int b){
    return size[a]<size[b];
}
inline int x(int p){
    return size[p];
}
inline int y(int p){
    return f[p]+size[p]*size[p];
}
inline double slope(int a,int b){
    if(x(a)==x(b))
        return y(a)>y(b)? inf:-inf;
    return 1.0*(y(a)-y(b))/(x(a)-x(b));
}
void dfs(int x,int last){
    int ps=0,l=1,r=0;
    size[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
        size[x]+=size[y];
    }
    f[x]=size[x]*size[x];
    if(size[x]==1)
        return ;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        f[x]=min(f[x],f[y]+(size[x]-size[y])*(size[x]-size[y]));
        p[++ps]=y;
    }
    if(x==1)
        ans=min(ans,f[x]);
    sort(p+1,p+1+ps,cmp);
    q[++r]=p[1];
    for(int i=2;i<=ps;i++){
        while(l<r&&slope(q[l+1],q[l])<=2*(n-size[p[i]]))
            l++;
        ans=min(ans,f[p[i]]+f[q[l]]+(n-size[p[i]]-size[q[l]])*(n-size[p[i]]-size[q[l]]));
        while(l<r&&slope(p[i],q[r-1])<=slope(q[r],q[r-1]))
            r--;
        q[++r]=p[i];
    }
}
signed main(){
    scanf("%lld",&n);
    for(i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    printf("%lld\n",n*(n-1)/2+(n*n-ans)/2); 
    return 0;
}