70901202-AGC028

B

$N$ 个砖块，每个重量 $A_i$ ，进行以下操作：选择一个还未被移除的砖块并移除，代价是其和与其相邻的砖块的重量之和，定义两块砖 $x,y$ 相邻当且仅当 $\mathrm{\forall }z(x\le z\le y)$ ，$z$ 没有被移除。共有 $N!$ 种移除的顺序，对于所有顺序计算移除所有 $N$ 块砖块的代价并计算和

这个可以用草率的方法，这里记录以下笛卡尔树做法

针对这种所有方案之和的有 $\text{trick}$ : 均匀随机一个删除顺序，求代价的期望，最后乘 $n!$

每次删除一个位置并两边分开做，与笛卡尔树的建树方法类似。计算每个点的删除时间，删除一个点就在使其做根，然后两边接过来，发现形成一个笛卡尔树，其中下标满足 $\text{BST}$ 性质，删除时间满足小根堆性质

一个位置的贡献就是其在笛卡尔树上的点深度，即，到根路径上点的个数， $\sum \mathrm{期}\mathrm{望}\mathrm{深}\mathrm{度}\ast \mathrm{权}\mathrm{值}=\mathrm{代}\mathrm{价}\mathrm{的}\mathrm{期}\mathrm{望}$

转化为如何求随机排列构成的笛卡尔树的期望深度：$E(dept{h}_i)=\sum _{j}p(j\in anc(i))$ ，即， $j$ 是 $i$ 祖先的概率，不妨设 $j<i$

考虑到笛卡尔树的结构，若 $j$ 是 $i$ 的祖先，则 $[j,i]$ 段中， $j$ 是最小值

也就是求：对于随机排列，区间 $[l,r]$ 中 $l$ 位置是最小值的概率：

先选择 $r-l+1$ 个位置放在区间里，剩余 $n-(r-l+1)$ 个位置随便排， $l$ 位置为最小值， $(r-l+1)-1$ 个位置再随便排，最后除以 $n!$ ，得概率 $\frac{1}{r-l+1}$

$j>i$ 同理，则有 $E(dept{h}_i)=H(i)+H(n-i+1)-1$ ，其中调和级数 $H(n)=\sum _{i=1}^n\frac{1}{i}$

const int N=1e5+100;
const int mod=1e9+7;
int fac[N],fac_inv[N],inv[N],si[N];
int n,a[N];
ll ans;

inline void init(){
    int lim=1e5;
    fac[0]=fac[1]=fac_inv[0]=fac_inv[1]=inv[1]=1;
    for(rei i=2;i<=lim;++i){
        fac[i]=(ll) fac[i-1]*i%mod;
        inv[i]=(ll) inv[ mod%i ]*(mod-mod/i)%mod;
        fac_inv[i]=(ll) fac_inv[i-1]*inv[i]%mod;
    }
    for(rei i=1;i<=lim;++i) si[i]=(ll) (si[i-1]+inv[i])%mod;
}

int main(){
    init();
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    for(rei i=1;i<=n;++i) ans=(ans+(ll) (si[i]+si[n-i+1]-1)*a[i])%mod;
    printf("%lld\n",ans*fac[n]%mod);
    getchar(),getchar();
    return 0;
}

C

给出 $n$ 边的有向完全图，每个点右两个点权 $a,b$ ，一条边的边权值为 $min(u_a,v_b)$ ，求边权和最小的哈密顿回路的边权和

一个合法的解一定是有 $n$ 条路径的一个环，环上的边权值为 $n$ 个 $a_i,b_i$ 中的 $n$ 个数

考虑所有能形成环的方式中可能是最优解的情况：

• 对所有点都选 $a_i/b_i$

• 对某些点 $u$ ，同时使用了 $a_u,b_u$

  此时，贪心选择权值小的边

  先将所有 $ab$ 混在一起排序，对前 $n$ 个求前缀和，考虑每个点 $u$ ，当 $a_u,b_u$ 都选时最小权值和( $a_u+b_u+pre[n-2]$ )是否更优

如此更新答案即可

const int N=1e5+100;
int n;
ll pre[N<<1],c[N<<1],ans,a[N],b[N],suma,sumb;

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%lld%lld",&a[i],&b[i]),c[i]=a[i],c[i+n]=b[i],suma+=a[i],sumb+=b[i];
    ans=min(suma,sumb);
    sort(c+1,c+1+n*2);
    for(rei i=1;i<=n;++i) pre[i]=pre[i-1]+c[i];
    for(rei i=1;i<=n;++i){
        ll x=a[i],y=b[i]; if(x>y) swap(x,y);
        if(lower_bound(c+1,c+1+n*2,x)-c<=n-2){
            if(lower_bound(c+1,c+1+n*2,y)-c<=n-1) ans=min(ans,pre[n]);
            else ans=min(ans,pre[n-1]+y);
        }
        else ans=min(ans,x+y+pre[n-2]);
    }
    printf("%lld\n",ans);
    getchar(),getchar();
}

D

圆周上均匀分布 $2N$ 个点，将这些点两两配对成 $N$ 个无序对，对于每个无序对 $AB$ ，做连接 $A,B$ 的弦。 对于一种配对方式，定义其连通性为 $N$ 条弦构成的等价连通块数，两条线属于一个等价连通块当且仅当它们相交或存在另一条弦与它们都连通。现在已有 $2K$ 个点完成配对，求剩下的点构成的所有配对方式的连通性之和

这里有一个很好玩的转化：把圆的半径视作 $0$ ，$2N$ 个点将慢慢靠近，问题可以转化到数轴上，即：数轴上排列着 $2N$ 个点，配对的 $A,B$ 视作 $[A,B]$ ，连通性为这些区间相交形成的连通块个数

考虑一类连通块 $[l,r]$ ，计算其贡献

枚举 $i,j$ ，设 $f_{i,j}$ 表示左右端点分别为 $i,j$ 的连通块个数

首先，连通块 $[i,j]$ 存在当且仅当 $j-i+1\equiv 0(\mathrm{mod}2)$ (即，需要两两连边)，且不存在一条边 $(u,v)$ 满足 $i\le u\le j\mathrm{且}v>j\mathrm{或}v<i$ (即，一条边不能横跨该连通块)

设 $c_{i,j}$ 表示连通块内尚未确定边的点数 ， $g_x$ 表示 $x$ 个点之间两两连边的方案数

易知 $g_x=g_{x-2}\times (x-1)$ (即，考虑第一个点与 $x-1$ 中的哪个点连边)

由于 $i,j$ 不一定连通，则无法简单的得到 $f_{i,j}=g_{c_{i,j}}$

考虑连通块问题的经典容斥，枚举 $i$ 所在的连通块:

$$f_{i,j}=g_{c_{i,j}}-\sum _{p=i}^{j-1}{f}_{i,p}\times g_{c_{p+1,j}}$$

而最终答案就是统计每个连通块，其余点任意连边:

$$\sum f_{i,j}\times g_{n-2k-c_{i,j}}$$

const int N=310;
const int mod=1e9+7;
int n,k,x[N],y[N],c[N<<1][N<<1],s[N<<1],f[N<<1][N<<1],g[N<<1],ans;

inline bool IN(int x,int i,int j){ return i<=x && x<=j;}

int main(){
    scanf("%d%d",&n,&k); n<<=1;
    for(rei i=1;i<=k;++i) scanf("%d%d",&x[i],&y[i]);
    g[0]=1;
    for(rei i=2;i<=n;++i) g[i]=(ll) g[i-2]*(i-1)%mod;
    for(rei l=2;l<=n;l+=2) for(rei i=1,j=l;j<=n;++i,++j){
        c[i][j]=j-i+1; rei p;
        for(p=1;p<=k;++p) if( (c[i][j]-=IN(x[p],i,j)+IN(y[p],i,j)) &1) break;
        if(p<=k) continue;
        f[i][j]=g[ c[i][j] ];
        for(p=i+1;p^j;p+=2) f[i][j]=(f[i][j]-(ll) f[i][p]*g[ c[p+1][j] ]%mod+mod)%mod;
        ans=(ans+(ll) f[i][j]*g[ n-2*k-c[i][j]]%mod )%mod;
    }
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

E

给定一个 $1\sim n$ 的排列 $P$ ，以长度为 $n$ 的 $01$ 串 $S$ 表示划分方案，$S_i=0$ 时分入序列 $A$ ，$S_i=1$ 时分入序列 $B$ ，使 $AB$ 的前缀最大值个数相等，求 $S$ 使字典序最小

先贪心，从前往后对于每一位尽量填 $0$ ，再检验如此放后是否能使接下来的操作合法，那么检验操作只能在 $O(\log n)$ 时间内解决

有性质：对于序列 $P$ 中的前缀最大值，划分到新序列 $A,B$ 中后仍是前缀中最大的

由此有结论：对于一个时刻的序列 $A,B$ ，设前缀最大值数量为 $c_A,c_B$ ，不改变 $c_A,c_B$ 的值的情况下，一定能重新分配序列使其中一个序列的所有前缀最大值均为原序列 $P$ 的前缀最大值

由此，考虑如何检验：

假设 $B$ 中添加的全部是 $P$ 中的前缀最大值，对于第 $i$ 位，$P_i$ 之后的前缀最大值有 $c$ 个，设在第 $i$ 位后 $A$ 中会添加 $p$ 个原序列 $P$ 的前缀最大值以及 $q$ 个新的前缀最大值，$B$ 中会有 $c-p$ 个原序列的前缀最大值

合法情况当且仅当 $c_A+p+q=c_B+c-p\iff 2p+q=c_B-c_A+c$

右边显然是一个定值，考虑 $2p+q$ 的意义：

给 $A$ 添加值时，设添加原序列的前缀最大值时权值为 $2$ ，新前缀最大值时权值为 $1$ ，那么会有一种取法使总权值为 $2p+q$

将检验转化为，对于 $i+1\sim n$ ，能否找到一个递增序列，其中原序列 $P$ 中的数权值为 $2$ ，其余权值为 $1$ ，使该序列的权值和为 $c_A-c_B+c$

假设能得到权值为 $x$ 的序列，则一定有 $x-2$ 的序列，但不一定有 $x-1$ 的序列

所以分别求出奇偶情况的最大值并与右式比大小即可

如此，转化为求每个点向后的带权 $LIS$ ，值域线段树优化一下即可

const int N=2e5+100;
const int INF=1e9;
int n,a[N],p[N];//原序列所有的前缀最大值

struct SegmentTree{
    int v[N<<2];
    inline void pushup(const int now){ v[now]=max(v[now<<1],v[now<<1|1]);}
    void build(const int l=1,const int r=n+1,const int now=1){
        v[now]=-INF;//奇数全部赋成-INF
        if(l==r) return;
        rei mid=l+r>>1; build(l,mid,now<<1),build(mid+1,r,now<<1|1);
    }
    void change(const int pos,const int val,const int l=1,const int r=n+1,const int now=1){
        if(l==r) return v[now]=val,void();
        rei mid=l+r>>1; pos<=mid ? change(pos,val,l,mid,now<<1):change(pos,val,mid+1,r,now<<1|1);
        pushup(now);
    }
    int query(const int x,const int l=1,const int r=n+1,const int now=1){//下标比x大的最大值
        if(x<l) return v[now];
        rei mid=l+r>>1;
        return max(x<mid ? query(x,l,mid,now<<1) : -INF,query(x,mid+1,r,now<<1|1));
    }
}S[2];

inline bool check(const int i,const int t1,const int t2,const int cA,const int cB,const int c){
    if(cB-cA+c>=0 && S[ (cB-cA+c)&1 ].query(t1)>=cB-cA+c) return 1;//假设B中全是原序列的前缀最大值
    if(cA-cB+c>=0 && S[ (cA-cB+c)&1 ].query(t2)>=cA-cB+c) return 1;//假设A中全是原序列的前缀最大值
    return 0;
}

int main(){
    rei t=0,c=0;
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]),t<a[i] ? (p[i]=1,t=a[i],++c) : 0;
    S[1].build();
    for(rei i=n;i;--i) S[ p[i]^1 ].change(a[i],S[0].query(a[i])+(p[i]+1)),S[ p[i] ].change(a[i],S[1].query(a[i])+(p[i]+1));//线段树优化DP
    rei t1=0,cA=0,t2=0,cB=0;
    if(!check(1,0,0,0,0,c)) return puts("-1"),0;
    for(rei i=1;i<=n;++i){
        S[0].change(a[i],-INF),S[1].change(a[i],-INF);
        putchar(48|/*从线段树上删去当前位置贡献*/( check(i+1,max(t1,a[i]),t2,cA+(t1<a[i]),cB,c-=p[i]) ? (t1<a[i] && (t1=a[i],++cA),0) : (t2<a[i]&&(t2=a[i],++cB),1)));//尽可能插入序列A
    }
    getchar(),getchar();
    return 0;
}

F

给定 $n\times n$ 的网格图，每个图有权值 $w_{i,j}$ ，定义格子 $X$ 可以到达 $Y$ 当且仅当存在路径 $X\leftarrow Y$ ，且对于路线上任意点权值 $\ne 0$ ，且 $Y$ 在 $X$ 的右下方，求对于所有合法的 $(X,Y)$ ，$\sum w_X\times w_Y$

$n=1500$ 显然是 $O(n^2\log n)$ 的复杂度，考虑分治，然后发现看不懂官方题解 考虑暴力：

以 $\mathrm{下}\to \mathrm{上}，\mathrm{右}\to \mathrm{左}$ 的顺序求出 $(i,j)$ 能到的所有点的权值和

预处理 $min/max(i,j,k)$ 表示 $(i,j)$ 在第 $k$ 行能到的点 $(k,l)$ 中 $l$ 的最小/大值

若 $min(i,j,k)\sim max(i,j,k)$ 中间不是障碍格，则由前缀和即可计算答案

那么，当遇到格子 $(i,j)$ 左上均为障碍时，将该格子改为障碍并更新当前行前缀和，并 $\text{dfs}$ 其右边及下面的格子 $(i+1,j),(i,j+1)$

每个格子至多被 $\text{dfs}$ 一次，而每次 $\text{dfs}$ 后会把整行前缀和更新，所以复杂度 $O(n^3)$

然后en卡常

const int N=1500+100;
char a[N];
ll ans;
int w[N][N],mn[2][N][N],mx[2][N][N],sum[N][N],n;

void dfs(int x,int y){
    if(w[x][y-1] || w[x-1][y] || !w[x][y]) return ;
    w[x][y]=0;
    for(rei i=y;i<=n;++i) sum[x][i]=sum[x][i-1]+w[x][i];
    dfs(x+1,y),dfs(x,y+1);
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i){
        scanf("%s",a+1);
        for(rei j=1;j<=n;++j) w[i][j]=a[j]=='#' ? 0 : a[j]-'0',sum[j][i]=sum[j-1][i]+w[i][j];
    }
    for(rei i=n+1;i>=1;--i){
        memcpy(mx[1],mx[0],sizeof mx[0]);
        memset(mx[0],0,sizeof mx[0]);
        memcpy(mn[1],mn[0],sizeof mn[0]);
        memset(mn[0],0,sizeof mn[0]);
        for(rei j=n+1;j>=0;--j){
            if(!w[i][j]){
                for(rei k=i;k<=n;++k) mn[0][j][k]=n+1,mx[0][j][k]=0;
                continue;
            }
            mn[0][j][i]=j,mx[0][j][i]=max(j,mx[0][j+1][i]),ans-=w[i][j]*w[i][j];
            for(rei k=i+1;k<=n;++k)
                mn[0][j][k]=min(mn[1][j][k],mn[0][j+1][k]),mx[0][j][k]=max(mx[1][j][k],mx[0][j+1][k]);
            for(rei k=i;k<=n;++k)
                if(mx[0][j][k]>=mn[0][j][k])ans+=(sum[k][mx[0][j][k]]-sum[k][mn[0][j][k]-1])*w[i][j];
            dfs(i,j);
        }
    }
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}

const int N=1500+100;
char a[N];
ll ans;
int w[N][N],mn[2][N][N],mx[2][N][N],sum[N][N],n,sx[N*N],sy[N*N],top,is[N];

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i){
        scanf("%s",a+1),is[i]=n+1;
        for(rei j=1;j<=n;++j) w[i][j]=a[j]=='#' ? 0 : a[j]-'0',sum[j][i]=sum[j-1][i]+w[i][j];
    }
    for(rei i=n+1,cur=0;i>=1;--i,cur^=1){
        rei u=cur,v=cur^1;
        for(rei j=n+1;j>=0;--j){
            rei *m1=mn[u][j],*m2=mn[v][j],*m3=mx[u][j],*m4=mx[v][j],*m5=mn[u][j+1],*m6=mx[u][j+1],o=w[i][j];
            if(!w[i][j]){
                for(rei k=i;k<=n;++k) m1[k]=n+1,m3[k]=0;
                continue;
            }
            m1[i]=j,m3[i]=max(j,m6[i]),ans-=o*o,ans+=(sum[m3[i]][i]-sum[m1[i]-1][i])*o;
            for(rei k=i+1;k<=n;++k){
                m1[k]=min(m2[k],m5[k]),m3[k]=max(m4[k],m6[k]);
                if(m3[k]>=m1[k]) ans+=(sum[ m3[k] ][k]-sum[m1[k]-1][k])*o;
                else{
                    while(k<=n) m3[k]=0,m1[k]=n+1,++k;
                    break;
                }
            }
            sx[top=1]=i,sy[1]=j;
            while(top){
                rei x=sx[top],y=sy[top];
                --top;
                if(w[x][y-1] || w[x-1][y] || !w[x][y]) continue;
                w[x][y]=0,is[x]=min(is[x],y),sx[++top]=x+1,sy[top]=y,sx[++top]=x,sy[top]=y+1;
            }
            for(rei j=i;j<=n;j++){
                if(is[j]==n+1)break;
                for(rei k=is[j],*v=w[j];k<=n;++k) sum[k][j]=sum[k-1][j]+v[k];
                is[j]=n+1;
            }
        }
    }
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}