UOJ Logo WrongAnswer的博客

博客

各省省选题完成计划(一)

2017-04-26 10:15:14 By WrongAnswer

最后一次FJOI滚粗,APIO也没考好,让我明白自己技不如人,需要多刷题。

打算先把各省省选题刷完。


SHOI2017(六省联考)

做完之后的感觉是难度偏小,出题人很良心,暴力送了很多分……省队线一定很高……

比较资磁的是数学题比较多。

D1T1:期末考试

数据范围 $t_i,b_i\le 10^5$ 直接告诉我们算法——枚举。

枚举最后结束的时间 $T\le\max\{b_i\}$,那么等待的不愉快度为 $\sum_{t_i\le T}(T-t_i)$。

考虑把所有 $b_i$ 调到不大于 $T$ 的最小不愉快度。假设先进行操作1再进行操作2,那么对 $b_i\le T$ 的操作没意义,所以操作2只对 $b_i>T$ 的 $b_i$ 减到 $T$ 有意义。假设先进行操作2再进行操作1,设 $b_i'$ 为操作后的 $b_i$,由于操作1不改变总和,故需要满足 $$\sum_ib_i'\le mT$$

即 $$\sum_{b_i'>T}(b_i'-T)\le \sum_{b_i'\le T}(T-b_i')$$

同时,满足上述条件一定能通过每次选一对小于 $T$ 和大于 $T$ 的 $b_i'$ 总共进行 $\sum_{b_i'>T}(b_i'-T)$ 次操作1完成。所以:

(1)如果 $A>B$,那么只用操作2最优,否则可以把所有操作1换成对减小的 $b_i$ 进行操作2,不愉快度为 $$B\sum_{b_i>T}(b_i-T)$$

(2)否则,如果 $\sum_{b_i>T}(b_i-T)\le \sum_{b_i\le T}(T-b_i)$,那么只需要做操作1,不愉快度为 $$A\sum_{b_i>T}(b_i-T)$$

(3)否则,需要先对 $b_i>T$ 的 $b_i$ 做 $\sum_{b_i>T}(b_i-T)-\sum_{b_i\le T}(T-b_i)$ 次操作2,再做 $\sum_{b_i\le T}(T-b_i)$ 次操作1,不愉快度为 $$B[\sum_{b_i>T}(b_i-T)-\sum_{b_i\le T}(T-b_i)]+A\sum_{b_i\le T}(T-b_i)$$

预处理前缀和可以 $O(1)$ 计算不愉快度和。复杂度 $O(n+m+\max\{b_i\})$。

#include<cstdio>
#define ull unsigned long long
int n,m;
ull A,B,C,t_cnt[100010],b_cnt[100010],
    t_sum[100010],b_sum[100010];
ull min(ull a,ull b){return a<b?a:b;}
int main(){
    scanf("%llu%llu%llu%d%d",&A,&B,&C,&n,&m);
    int T=0;
    for(int i=0,t;i<n;i++){
        scanf("%d",&t);
        t_cnt[t]++;t_sum[t]+=t;
    }
    for(int i=0,b;i<m;i++){
        scanf("%d",&b);b>T?T=b:1;
        b_cnt[b]++;b_sum[b]+=b;
    }
    for(int i=1;i<=T;i++){
        t_cnt[i]+=t_cnt[i-1];t_sum[i]+=t_sum[i-1];
        b_cnt[i]+=b_cnt[i-1];b_sum[i]+=b_sum[i-1];
    }
    ull ans=1ull<<63;
    for(int i=0;i<=T;i++){
        ull c=i*t_cnt[i]-t_sum[i],
            b=b_sum[T]-b_sum[i]-i*(b_cnt[T]-b_cnt[i]),
            a=min(b,i*b_cnt[i]-b_sum[i]);
        if(!(C>>54)||!c)ans=min(ans,C*c+B*b-(A<B?(B-A)*a:0));
    }
    printf("%llu\n",ans);
}

D1T2:相逢是问候

这题不会做,乱搞拿了90分。

首先,当 $a\ge p$ 时,$c^a\bmod p=c^{a\bmod\varphi(p)+\varphi(p)}\bmod p$,那么就可以递归下去,在 $O(\log t\log p)$ 的时间内算出 $a$ 经过 $t$ 次变换后的结果。

注意到 $p$ 变成 $\varphi(p),\varphi(\varphi(p)),\cdots$ 只要 $O(\log p)$ 次就会变成1,那么递归到1就可以不用继续递归,计算单个结果复杂度为 $O(\log^2p)$。

预处理 $a_{i,j}$ 为 $a_i$ 做 $j$ 次变换的结果,复杂度 $O(n\log^3p)$。

不妨设最大递归次数为 $D$,维护序列 $d_i$ 表示 $a_i$ 这个数变换了几次,那么每次操作 $[l,r]$ 时只需修改 $l\le i\le r$ 且 $d_i < D$ 的 $a_i$ 并更新 $d_i$ 为 $d_i+1$,用并查集维护每个位置的下一个满足 $d_i < D$ 的位置,就可以暴力修改,复杂度均摊 $O(nD\alpha(n))$。

这个算法前面的 $O(n\log^3p)$ 会超时?然后我生成了一些数据,对每个 $i$ 打出 $a_{i,0},\cdots,a_{i,D}$,发现5-6项后面的 $a_{i,j}$ 就相同了。于是……骗分大法好……卡时枚举 $D$ 计算 $a_{i,D}$!于是骗了90分。

后来听说这题的坑点是 $\varphi$ 要多迭代一层,这样才能保证倒数第二层的指数为1。于是改完以后水过100分了。

这个做法可以优化到 $O(n\log^2p)$:注意到所有快速幂都是 $c^a\bmod p_i$ 的形式,$p_i$ 是 $p$ 迭代 $i$ 次 $\phi$ 的形式,所以可以对每个 $i$ 和 $x\le 2^{14}$ 预处理 $c^x\bmod p_i$ 和 $c^{14x}\bmod p_i$,就可以做到 $O(1)$ 计算 $c^a\bmod p_i$ 了。(感谢 @zhouyi 和 @Sengxian 提供该算法)

#include<cstdio>
#include<ctime>
int n,m,p,c,a[50010],list[50010][30];
int phi(int x){
    int y=1;
    for(int i=2;i*i<=x;i++)if(x%i==0)
        for(y*=i-1,x/=i;x%i==0;x/=i)y*=i;
    if(x>1)y*=x-1;
    return y;
}
int ph[30],cnt,pw[30][16385],pw1[30][16385],pw2[16385],pw3[16385];
int Ph(int i){return i<cnt?ph[i]:1;}
int f(int x,int t){
    int y=x,z=x;
    for(int i=t;i--;){
        if(z<p)y=1ll*pw1[i][z>>14]*pw[i][z&16383]%ph[i];
        else y=1ll*pw1[i][y+Ph(i+1)>>14]*pw[i][y+Ph(i+1)&16383]%ph[i];
        z=1ll*pw3[z>>14]*pw2[z&16383]>p?p:pw3[z>>14]*pw2[z&16383];
    }
    return y;
}
int fa[50010],d[50010],BIT[50010];
int find(int i){return fa[i]==i?i:fa[i]=find(fa[i]);}
void add(int i,int x){for(a[i]=(a[i]+x)%p;i<=n;i+=i&-i)BIT[i]=(BIT[i]+x)%p;}
int query(int i){int x=0;for(;i;i-=i&-i)x=(x+BIT[i])%p;return x;}
int main(){
    scanf("%d%d%d%d",&n,&m,&p,&c);
    for(ph[cnt]=p;ph[cnt]!=1;cnt++)ph[cnt+1]=phi(ph[cnt]);
    ph[++cnt]=1;
    for(int i=0;i<cnt;i++){
        for(int j=*pw[i]=1;j<=16384;j++)pw[i][j]=1ll*pw[i][j-1]*c%ph[i];
        for(int j=*pw1[i]=1;j<16384;j++)pw1[i][j]=1ll*pw1[i][j-1]*pw[i][16384]%ph[i];
    }
    for(int j=*pw2=1;j<=16384;j++)pw2[j]=1ll*pw2[j-1]*c>p?p:pw2[j-1]*c;
    for(int j=*pw3=1;j<16384;j++)pw3[j]=1ll*pw3[j-1]*pw2[16384]>p?p:pw3[j-1]*pw2[16384];
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        list[i][0]=a[i];
        BIT[i]=(BIT[i-1]+a[i])%p;
    }
    int c=0;
    while(c<cnt){
        c++;
        for(int i=1;i<=n;i++)list[i][c]=f(list[i][0],c);
    }
    for(int i=1;i<=n+1;i++)fa[i]=i;
    for(int i=n;i;i--)BIT[i]=(BIT[i]+p-BIT[i&(i-1)])%p;
    while(m--){
        int op,l,r;scanf("%d%d%d",&op,&l,&r);
        if(op)printf("%d\n",(query(r)-query(l-1)+p)%p);
        else for(int i=find(l);i<=r;i=find(i+1)){
            add(i,p-a[i]+list[i][++d[i]]);
            if(d[i]==c)fa[i]=find(i+1);
        }
    }
}

D1T3:组合数问题

前段时间自己出过的一道题,不知为何碰巧撞题。

记 $f(i,j)$ 为从 $i$ 个物品中选模 $k$ 余 $r$ 个的方案数,则 $$f(i,j)=f(i-1,j)+f(i-1,(j-1)\bmod k)$$

这个递推显然可以矩阵快速幂优化。由于矩阵是循环矩阵,即转移是 $f_i'=\sum_{j=0}^{k-1}a_{(j-i)\bmod k}f_j$ 形式的,所以可以只算矩阵的第一行 $a_0,a_1,\cdots,a_{k-1}$。

复杂度 $O(k^2\log n)$。

#include<cstdio>
#define ll long long
int n,p,k,r,f[60],g[60],t[60];
void mul(int*a,int*b){
    for(int i=k;i--;)for(int j=k;j--;)t[(i+j)%k]=(t[(i+j)%k]+a[i]*(ll)b[j])%p;
    for(int i=k;i--;)a[i]=t[i],t[i]=0;
}
int main(){
    scanf("%d%d%d%d",&n,&p,&k,&r);
    f[0]++;g[0]++;(g[1%k]+=1)%=p;
    for(ll N=n*(ll)k;N;N/=2){
        if(N%2)mul(f,g);
        mul(g,g);
    }
    printf("%d\n",f[r]);
}

D2T1:摧毁“树状图”

树形DP细节题。

两条链 $P,H$ 不能有公共边,但可以有公共点,于是公共点最多一个。分两类情况:

(1)$P$ 和 $H$ 有一个公共点 $r$,那么 $P\cup H$ 为 $r$ 出发的 $c\le 4$ 条链构成的子图。

由于 $P\cup H$ 是树(为 $T$ 的连通导出子图),$|E(P\cup H)|=|V(P\cup H)|-1$。考虑树 $T$ 删去 $P\cup H$ 的连通块个数,为

\begin{align*} & |V(T-P-H)|-|E(T-P-H)| \\ = & n-|V(P\cup H)|-\sum_{(u,v)\in E(T)}[[u\in V(P\cup H)]+[v\in V(P\cup H)]=0] \\ = & n-|V(P\cup H)|-|E(T)|+\sum_{(u,v)\in E(T)}([u\in V(P\cup H)]+[v\in V(P\cup H)])-\sum_{(u,v)\in E(T)}[[u\in V(P\cup H)]+[v\in V(P\cup H)]=2] \\ = & n-|V(P\cup H)|-(n-1)+\sum_{u\in V(P\cup H)}\sum_{v\in V(T),(u,v)\in E}[u < v]+\sum_{v\in V(P\cup H)}\sum_{u\in V(T),(u,v)\in E}[u < v]-|E(P\cup H)| \\ = & 1-|V(P\cup H)|+\sum_{v\in V(P\cup H)}\deg_T(v)-|V(P\cup H)|+1 \\ = & 2-2|V(P\cup H)|+\sum_{v\in V(P\cup H)}\deg_T(v) \\ = & 2+\sum_{v\in V(P\cup H)}(\deg_T(v)-2) \end{align*}

DP时,记 $f(i)$ 为从结点 $i$ 出发往下的链 $P$ 中,$\sum_{v\in P}(\deg_T(v)-2)$ 的最大值,用 $Ch(i)$ 表示 $i$ 的子结点集合,则 $$f(i)=\deg_T(i)-2+\max\{\max_{j\in Ch(i)}\{f(j)\},0\}$$

那么,枚举点 $r$,取以 $r$ 为根时 $f(v)$ 最大的 $4$ 个 $v\in N_T(r)$。

由于一遍树形DP只能求出以某个特定的点为根时的 $f(i)$ 值,故需要一些技巧:以 $1$ 号点为根DP,DP时需要记 $f(i)$ 为最大的,$f_2(i)$ 为次大的,然后记 $f'(i)$ 为以 $i$ 为根时 $f(fa_i)$ 的值($fa_i$ 为$i$ 的父结点),由于记录了次大值,可以很容易得到 $fa_i$ 去掉 $i$ 这个子结点后的DP值。

(2)$P$ 和 $H$ 没有公共点,但存在 $(u,v)\in E(T)$ 使 $u\in P,v\in H$,显然这样的边只有一条。

由于 $T[V(P\cup H)]=E(P\cup H)\cup\{(u,v)\}$,同样有 $|E(P\cup H)|=|V(P\cup H)|-1$,因此树 $T$ 删去 $P\cup H$ 的连通块个数同样为 $$2+\sum_{v\in V(P\cup H)}(\deg_T(v)-2)$$

枚举这条边 $(u,v)$,求出以 $u,v$ 为根时它的 $f(i)$ 最大的两个出边(不含 $u$)。DP时可能需要记 $f_3(i)$ 为第三大的。

(3)$P$ 和 $H$ 没有公共点,也不存在 $(u,v)\in E(T)$ 使 $u\in P,v\in H$。那么 $P$ 上的任一点到 $H$ 上的任一点,不属于 $P\cup H$ 的边数至少为 $2$,从而必然存在 $r\in T$,满足从 $T$ 中删去 $r$ 后,$P$ 和 $H$ 在不同子树内。树 $T$ 删去 $P\cup H$ 的连通块个数同样为 $$3+\sum_{v\in V(P\cup H)}(\deg_T(v)-2)$$

记 $g(i)$ 为 $i$ 子树内的所有链 $P$ 中,$\sum_{v\in P}(\deg_T(v)-2)$ 的最大值,则 $$g(i)=\max\{\max_{j\in Ch(i)}\{g(j)\},f(i)+f_2(i)-\deg_T(i)+2\}$$

为了对所有根计算结果,可能需要记 $g_2(i)$ 为次大值。

这样就可以枚举根 $r$,取最大的 $2$ 个 $g(v)$。

时间复杂度 $O(n)$,常数较大(?)。(由于写的时候不放心就维护了前4大,常数飞起)

#include<cstdio>
const int inf=1<<25;
int n,deg[100010];
struct edge{int to;edge*next;}E[200010],*ne,*first[100010];
void link(int u,int v){*ne=(edge){v,first[u]};first[u]=ne++;deg[u]++;}
struct info{
    int v1,v2,v3,v4;
    info(int a=0){v1=v2=v3=v4=a;}
    void operator|=(int x){
        if(x>v1)v4=v3,v3=v2,v2=v1,v1=x;
        else if(x>v2)v4=v3,v3=v2,v2=x;
        else if(x>v3)v4=v3,v3=x;
        else if(x>v4)v4=x;
    }
    void operator-=(int x){
        if(x==v1)v1=v2,v2=v3,v3=v4;
        else if(x==v2)v2=v3,v3=v4;
        else if(x==v3)v3=v4;
    }
}f[100010],g[100010];
void dfs1(int i,int fa){
    f[i]=deg[i]-2;
    g[i]=-inf;
    for(edge*e=first[i];e;e=e->next)if(e->to!=fa){
        dfs1(e->to,i);
        f[i]|=f[e->to].v1+deg[i]-2;
        g[i]|=g[e->to].v1;
    }
    g[i]|=f[i].v1+f[i].v2-deg[i]+4;
}
int ans;
void cmax(int&a,int b){b>a?a=b:1;}
void dfs2(int i,int fa,int fv,int gv){
    info t=-inf;
    t|=gv;
    for(edge*e=first[i];e;e=e->next)if(e->to!=fa){
        info v=f[i],w=g[i];
        v-=f[e->to].v1+deg[i]-2;
        v|=fv+deg[i]-2;
        w-=g[e->to].v1;
        w-=f[i].v1+f[i].v2-deg[i]+4;
        w|=gv;
        w|=v.v1+v.v2-deg[i]+4;
        t|=g[e->to].v1;
        cmax(ans,f[e->to].v1+f[e->to].v2-deg[e->to]+v.v1+v.v2-deg[i]+6);
        dfs2(e->to,i,v.v1,w.v1);
    }
    cmax(ans,t.v1+t.v2-1);
    t=f[i];
    t|=fv+deg[i]-2;
    cmax(ans,t.v1+2);
    cmax(ans,t.v1+t.v2-deg[i]+4);
    cmax(ans,t.v1+t.v2+t.v3-deg[i]*2+6);
    cmax(ans,t.v1+t.v2+t.v3+t.v4-deg[i]*3+8);
}
int main(){
    int T,x;scanf("%d%d",&T,&x);
    while(T--){
        scanf("%d",&n);ne=E;
        for(int i=n;i;i--)first[i]=0,deg[i]=0;
        for(int i=x;i--;)scanf("%*d%*d");
        for(int i=1,u,v;i<n;i++){
            scanf("%d%d",&u,&v);
            link(u,v);link(v,u);
        }
        ans=-inf;
        dfs1(1,0);
        dfs2(1,0,0,-inf);
        printf("%d\n",ans);
    }
}

D2T2:分手是祝愿

挺送分的题,直接按50分做有80分,100分也不难。

考虑最优策略。设开关 $i$ 按的次数奇偶性为 $x_i$,灯 $i$ 被切换次数的奇偶性为 $y_i$,则 $$y_i=\oplus_{j=1}^{\lfloor\frac{n}{i}\rfloor}x_{ij}$$

于是 $$x_i=\oplus_{j=2}^{\lfloor\frac{n}{i}\rfloor}x_{ij}\oplus y_i$$

由于按开关操作顺序无关且按一个开关两次没有意义,可以认为最优策略唯一。根据上式可以 $O(n\log n)$ 求出最优策略。

我们可以把过程看成这样:由上式计算出序列 $\{x_i\}$,然后当 $\sum_{i=1}^nx_i\le k$ 时选一个 $x_i=1$ 的 $i$ 令 $x_i\leftarrow 0$,否则随机选择一个 $i$ 令 $x_i\leftarrow 1-x_i$,问 $x$ 全变为 $0$ 的期望次数。

设 $f(x)$ 为当前 $\sum_{i=1}^nx_i=x$ 的情况下,$\sum_{i=1}^nx_i$ 第一次变为 $x-1$ 的期望次数。如果 $1\le x\le k$,显然 $f(x)=1$。

如果 $x > k$,由于 $\sum_{i=1}^nx_i$ 有 $\frac{x}{n}$ 概率减 $1$,$1-\frac{x}{n}$ 概率加 $1$,可得 $$f(x)=1+\frac{x}{n}+(1-\frac{x}{n})[f(x+1)+f(x)]$$

即 $$f(x)=\frac{n+x+(n-x)f(x+1)}{x}$$

记 $x$ 为当前 $\sum_{i=1}^nx_i$ 的值,答案为 $n!\sum_{i=1}^xf(i)$。

#include<cstdio>
#include<vector>
const int mod=100003;
int n,k,a[100010],fac[100010],cnt[100010],cur[100010],mem[2000010],*iter=mem,*f[100010];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=*fac=1;i<=n;i++){
        scanf("%d",a+i);
        for(int j=i;j<=n;j+=i)cnt[j]++;
        fac[i]=1ll*i*fac[i-1]%mod;
    }
    for(int i=1;i<=n;i++)f[i]=iter,iter+=cnt[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)f[j][cur[j]++]=i;
    int x=0,y=n,z=n,s;
    for(int i=n;i;i--)if(a[i]){
        for(int j=cnt[i];j--;)a[f[i][j]]^=1;
        x++;
    }
    if(x<=k)s=1ll*x*fac[n]%mod;
    else{
        s=1ll*k*fac[n]%mod;
        for(int i=n;i-->k;){
            if(i<x)s=(s+1ll*fac[i]*y)%mod;
            y=(1ll*y*(n-i)+1ll*n*z)%mod;
            z=1ll*z*i%mod;
        }
    }
    printf("%d\n",s);
}

D2T3:寿司餐厅

一开始想DP,发现某个限制要状压,于是复杂度爆炸。又想了一会儿才意识到可以网络流。

对于 $i < j$,$(i,j)$ 向 $(i,j-1),(i-1,j)$ 连边,那么一种方案对应于该图的闭合子图。

令 $(i,j)$ 的点权为 $$\begin{cases}d_{i,j},&i < j,\\d_{i,j}-a_i,&i=j\end{cases}$$

同时,对于每个 $a$,新建一个结点 $v_a$,点权为 $-ma^2$,将满足 $a_j=a$ 的 $(j,j)$ 连向 $v_a$。

则该图的最大权闭合子图即为最优解,用网络流解决。

网络流用Dinic时间复杂度 $O(n^6)$?也许是 $O(n^3)$ 或者 $O(n^4)$?(我不会分析)反正敢写就能过。

#include<cstdio>
#include<cstring>
const int inf=1<<30;
struct edge{int to,cap;edge*rev,*next;}E[55000],*ne=E,*first[5500],*cur[5500];
void link(int a,int b,int c){
    *ne=(edge){b,c,ne+1,first[a]};first[a]=ne++;
    *ne=(edge){a,0,ne-1,first[b]};first[b]=ne++;
}
int Q[5500],D[5500];
int dfs(int i,int c){
    if(i==1||!c)return c;
    int flow=0,f;
    for(edge*&e=cur[i];e;e=e->next)if(e->cap&&D[e->to]==D[i]-1&&(f=dfs(e->to,c<e->cap?c:e->cap))){
        flow+=f;e->cap-=f;e->rev->cap+=f;
        if(!(c-=f))return flow;
    }
    return flow;
}
int maxflow(){
    for(int f=0;;f+=dfs(0,inf)){
        memset(D,0,sizeof(D));
        memcpy(cur,first,sizeof(cur));
        for(int*h=Q,*t=Q+(*Q=D[1]=1);h<t;h++)
            for(edge*e=first[*h];e;e=e->next)
                if(e->rev->cap&&!D[e->to])D[*(t++)=e->to]=D[*h]+1;
        if(!*D)return f;
    }
}
int a[110],d[110][110],v[110][110];
bool vis[110];
int main(){
    int n,m,tot=2,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",a+i);
    for(int i=0;i<n;i++)for(int j=i;j<n;j++)scanf("%d",d[i]+j),v[i][j]=tot++;
    for(int i=0;i<n;i++)if(!vis[i]){
        for(int j=i;j<n;j++)if(!vis[j]&&a[i]==a[j])link(v[j][j],tot,inf),vis[j]=1;
        link(tot++,1,m*a[i]*a[i]);
    }
    for(int i=0;i<n;i++)for(int j=i;j<n;j++){
        int x=d[i][j];
        if(i==j)x-=a[i];
        else{
            link(v[i][j],v[i][j-1],inf);
            link(v[i][j],v[i+1][j],inf);
        }
        if(x>0)ans+=x,link(0,v[i][j],x);
        if(x<0)link(v[i][j],1,-x);
    }
    printf("%d\n",ans-maxflow());
}

SDOI2017

先做了D2T3。

D2T3:相关分析

这种题入手,先推个式子:

$$a=\frac{\sum_{i=L}^R(x_i-\overline{x})(y_i-\overline{y})}{\sum_{i=L}^R(x_i-\overline{x})^2} =\frac{\sum_{i=L}^R(x_iy_i-x_i\overline{y}-y_i\overline{x}+\overline{x}\overline{y})}{\sum_{i=L}^R(x_i^2-2x_i\overline{x}+\overline{x}^2)} =\frac{\sum_{i=L}^Rx_iy_i-n^{-1}\sum_{i=L}^Rx_i\sum_{i=L}^Ry_i}{\sum_{i=L}^Rx_i^2-n^{-1}(\sum_{i=L}^Rx_i)^2}$$

于是问题转化为询问 $\sum_{i=L}^Rx_i$,$\sum_{i=L}^Ry_i$,$\sum_{i=L}^Rx_i^2$,$\sum_{i=L}^Rx_iy_i$,就比较裸了。

用线段树维护这4个和,以及维护两种标记:区间的 $x,y$ 增加量,区间是否被修改为等差数列。显然标记可以合并,注意后一个标记会覆盖前一个标记。接着考虑标记如何应用到结点信息。

设 $x_L,x_{L+1},\cdots,x_R$ 应用 $x_i\leftarrow x_i+s$,$y_i\leftarrow y_i+t$ 标记后为 $x_L',x_{L+1}',\cdots,x_R'$,则 $$\sum_{i=L}^Rx_i'=\sum_{i=L}^R(x_i+s)=\sum_{i=L}^Rx_i+(R-L+1)s$$ $$\sum_{i=L}^Ry_i'=\sum_{i=L}^R(y_i+t)=\sum_{i=L}^Ry_i+(R-L+1)t$$ $$\sum_{i=L}^Rx_i'^2=\sum_{i=L}^R(x_i+s)^2=\sum_{i=L}^Rx_i^2+2s\sum_{i=L}^Rx_i+(R-L+1)s^2$$ $$\sum_{i=L}^Rx_i'y_i'=\sum_{i=L}^R(x_i+s)(y_i+t)=\sum_{i=L}^Rx_iy_i+t\sum_{i=L}^Rx_i+s\sum_{i=L}^Ry_i+(R-L+1)st$$

设 $x_L,x_{L+1},\cdots,x_R$ 应用 $x_i\leftarrow i$,$y_i\leftarrow i$ 标记后为 $x_L',x_{L+1}',\cdots,x_R'$,则 $$\sum_{i=L}^Rx_i'=\sum_{i=L}^Ry_i'=\sum_{i=L}^Ri=\frac{(L+R)(R-L+1)}{2}$$ $$\sum_{i=L}^Rx_i'^2=\sum_{i=L}^Rx_i'y_i'=\sum_{i=L}^Ri^2=\frac{R(R+1)(2R+1)-L(L-1)(2L-1)}{6}$$

于是线段树信息维护完成。复杂度 $O(n+m\log n)$。

由于我没有chentong那么强,写得比较复杂,差不多2KB……

#include<cstdio>
int n,m;
double X[100010],Y[100010];
struct info{
    double x,y,x2,xy,s,t;
    bool fa,fm;
    info operator+(const info&a)const{
        return(info){x+a.x,y+a.y,x2+a.x2,xy+a.xy,0,0,0,0};
    }
}T[1<<18];
#define Def int node,int L,int R
#define Mid (L+R>>1)
#define Cur node,L,R
#define Ls node<<1,L,Mid
#define Rs node<<1|1,Mid+1,R
void add_v(Def,double s,double t){
    T[node]=(info){
        T[node].x+s*(R-L+1),T[node].y+t*(R-L+1),
        T[node].x2+2*s*T[node].x+(R-L+1)*s*s,
        T[node].xy+t*T[node].x+s*T[node].y+s*t*(R-L+1),
        T[node].s+s,T[node].t+t,1,T[node].fm
    };
}
void modify_v(Def){
    T[node]=(info){
        (L+R)*(R-L+1.0)/2,(L+R)*(R-L+1.0)/2,
        (R*(R+1.0)*(2*R+1)-L*(L-1.0)*(2*L-1))/6,
        (R*(R+1.0)*(2*R+1)-L*(L-1.0)*(2*L-1))/6,
        0,0,0,1
    };
}
void pushdown(Def){
    if(T[node].fm){
        modify_v(Ls);
        modify_v(Rs);
        T[node].fm=0;
    }
    if(T[node].fa){
        add_v(Ls,T[node].s,T[node].t);
        add_v(Rs,T[node].s,T[node].t);
        T[node].s=T[node].t=0;T[node].fa=0;
    }
}
void build(Def){
    if(L==R)add_v(Cur,X[L],Y[L]);
    else build(Ls),build(Rs),T[node]=T[node<<1]+T[node<<1|1];
}
void add(Def,int l,int r,bool ty,double s,double t){
    if(l==L&&r==R){
        if(ty)modify_v(Cur);
        add_v(Cur,s,t);
    }
    else{
        pushdown(Cur);
        if(r<=Mid)add(Ls,l,r,ty,s,t);
        else if(l>Mid)add(Rs,l,r,ty,s,t);
        else add(Ls,l,Mid,ty,s,t),add(Rs,Mid+1,r,ty,s,t);
        T[node]=T[node<<1]+T[node<<1|1];
    }
}
info query(Def,int l,int r){
    if(l==L&&r==R)return T[node];
    pushdown(Cur);
    if(r<=Mid)return query(Ls,l,r);
    if(l>Mid)return query(Rs,l,r);
    return query(Ls,l,Mid)+query(Rs,Mid+1,r); 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lf",X+i);
    for(int i=1;i<=n;i++)scanf("%lf",Y+i);
    build(1,1,n);
    int op,L,R;
    double S,T;
    while(m--){
        scanf("%d%d%d",&op,&L,&R);
        if(op==1){
            info a=query(1,1,n,L,R);
            printf("%.10lf\n",((R-L+1)*a.xy-a.x*a.y)/((R-L+1)*a.x2-a.x*a.x));
        }
        else{
            scanf("%lf%lf",&S,&T);
            add(1,1,n,L,R,op>2,S,T);
        }
    }
}

ZJOI2017

这套题好难……暂时只想出一题。

D2T2:线段树

记得上次被srwudi的题卡内存的经历……启发我们不能满足于表面性质,要发掘更深入的性质!!!

注意到区间定位就是 $l-1$ 到LCA的右子结点加上 $r-1$ 到LCA的左子结点($l$ 和 $r$ 有一个和LCA端点重合的特判掉),于是对每个点维护它到根的路径的左/右子结点集合即可。

然而集合很大,而我们只需要知道距离和,所以只要维护集合中的结点个数以及结点深度和即可。

查询的时候用前缀相减的思想即可。

#include<cstdio>
int n,tot,L[400010],mid[400010],R[400010],leaf[400010],
    fa[400010],ls[400010],rs[400010],dep[400010],val[400010][2],
    siz[400010],son[400010],top[400010];
long long vals[400010][2];
int read(int l,int r){
    int x=++tot;
    L[x]=l;R[x]=r;
    if(l<r){
        scanf("%d",mid+x);
        fa[ls[x]=read(l,mid[x])]=x;
        fa[rs[x]=read(mid[x]+1,r)]=x;
    }
    else leaf[l]=x;
    return x;
}
int lca(int i,int j){
    while(top[i]!=top[j])dep[top[i]]>dep[top[j]]?i=fa[top[i]]:j=fa[top[j]];
    return dep[i]<dep[j]?i:j;
}
int dis(int i,int j){
    return dep[i]+dep[j]-2*dep[lca(i,j)];
}
long long getsum(int u,int x,bool ty){
    int a=lca(u,x);
    long long res=0;
    res+=vals[x][ty]-vals[a][ty]+1ll*(dep[u]-2*dep[a])*(val[x][ty]-val[a][ty]);
    res+=1ll*(dep[u]+2)*val[a][ty]-vals[a][ty];
    if(u==a||x==a)return res;
    while(fa[u]!=a){
        if(top[u]==top[a])u=son[a];
        else u=top[u];
        if(fa[u]!=a)u=fa[u];
    }
    if((u==rs[a])==ty)res-=2;
    return res;
}
long long query(int u,int l,int r){
    int a=lca(leaf[l],leaf[r]);
    if(l==L[a]&&r==R[a])return dis(u,a);
    if(l==L[a])return dis(u,ls[a])+getsum(u,leaf[r+1],0)-getsum(u,rs[a],0);
    if(r==R[a])return dis(u,rs[a])+getsum(u,leaf[l-1],1)-getsum(u,ls[a],1);
    return getsum(u,leaf[r+1],0)-getsum(u,rs[a],0)+getsum(u,leaf[l-1],1)-getsum(u,ls[a],1);
}
int main(){
    scanf("%d",&n);
    read(1,n);
    for(int i=1;i<=tot;i++)dep[i]=dep[fa[i]]+1;
    for(int i=2;i<=tot;i++){
        val[i][0]=val[fa[i]][0]+(i==rs[fa[i]]);
        val[i][1]=val[fa[i]][1]+(i==ls[fa[i]]);
        vals[i][0]=vals[fa[i]][0]+(i==rs[fa[i]]?dep[i]:0);
        vals[i][1]=vals[fa[i]][1]+(i==ls[fa[i]]?dep[i]:0);
    }
    for(int i=tot;i;i--)siz[fa[i]]+=++siz[i],siz[i]>siz[son[fa[i]]]?son[fa[i]]=i:1;
    top[1]=1;
    for(int i=2;i<=tot;i++)top[i]=i==son[fa[i]]?top[fa[i]]:i;
    int m,u,l,r;scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&u,&l,&r);
        printf("%lld\n",query(u,l,r));
    }
}

做出这题以后顺便把srwudi的互测题也A掉了。


HNOI2017

除了迷之D2T2以外难度十分正常,不会太难,D1具有可AK性。代码量也很正常,都在1KB到2KB之间。虽然D1考点有点偏?不过反正比HNOI2016好

D1T1:单旋

这题本来很简单的,然而我卡了很久= =因为我读错题了!以为要旋任意结点,然后思博了一个多小时,越想越复杂……等我写了个暴力,考虑暴力怎么卡的时候,才发现只要求旋最小/最大就行了。。。

那么就是个线段树/树状数组练习题。。。

考虑几个操作对树的形态和深度的变化:

插入 $x$,则 $x$ 的深度为其父结点加 $1$。

把最小/最大值结点 $x$ 旋到根,相当于 $x$ 的父结点到根这一段看成一个结点,旋转 $x$ 一次。那么 $x$ 的深度变成 $1$,$x$ 子树内结点深度不变,其余结点深度加 $1$。

删除根 $x$,则所有结点的深度减 $1$。

将所有的键值 $key$ 排序,根据二叉排序树的性质,不论怎么旋转,树的中序遍历都是 $key$ 的递增序。并且在中序遍历中,一个子树对应一段连续区间,因此对所有结点的 $key$ 递增序建线段树或树状数组,即可维护结点深度。

另外考虑一个问题,如何确定插入结点 $x$ 的父结点 $y$。假如 $x$ 是 $y$ 的左子结点,那么 $y$ 是最小的比 $x$ 大的结点;反之,$y$ 是最大的比 $x$ 小的结点。用线段树维护当前树上结点,支持查询前驱后继即可。我比较懒直接拉了个STL的 set……

复杂度 $O(m\log m)$。注意特判根的情况(如果用比较好的写法可能不用判)。代码有点长,快2KB了:

#include<cstdio>
#include<set>
#include<algorithm>
int m,op[100010],sz;
struct node{
    int id,key;
    node*fa,*ch[2];
    bool operator<(const node&x)const{return key<x.key;}
}nodes[100010],*cur[100010],*root;
std::set<node>S;
int dep[100010];
void add(int i,int x){for(;i<=sz;i+=i&-i)dep[i]+=x;}
int query(int i){int s=0;for(;i;i-=i&-i)s+=dep[i];return s;}
int rot_min(){
    int i=S.begin()->id,d=query(i);
    node*x=nodes+i;
    if(x==root)return d;
    add(i,1-d);add(i+1,d-1);add(x->fa->id,1);
    if(x->fa->ch[0]=x->ch[1])x->ch[1]->fa=x->fa;
    x->ch[1]=root;x->fa=0;root->fa=x;root=x;
    return d;
}
int rot_max(){
    int i=S.rbegin()->id,d=query(i);
    node*x=nodes+i;
    if(x==root)return d;
    add(i,1-d);add(i+1,d-1);add(1,1);add(x->fa->id+1,-1);
    if(x->fa->ch[1]=x->ch[0])x->ch[0]->fa=x->fa;
    x->ch[0]=root;x->fa=0;root->fa=x;root=x;
    return d;
}
int main(){
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d",op+i);
        if(op[i]==1)scanf("%d",&nodes[++sz].key),nodes[sz].id=i;
    }
    std::sort(nodes+1,nodes+sz+1);
    for(int i=1;i<=sz;i++)cur[nodes[i].id]=nodes+i,nodes[i].id=i;
    for(int i=0;i<m;i++){
        if(op[i]==1){
            std::set<node>::iterator it=S.insert(*cur[i]).first;
            int f=0;
            if(it!=S.begin())it--,nodes[it->id].ch[1]?0:nodes[f=it->id].ch[1]=cur[i],it++;
            it++;it==S.end()||nodes[it->id].ch[0]?0:nodes[f=it->id].ch[0]=cur[i];it--;
            int fd=1,td=query(cur[i]->id);
            if(f)cur[i]->fa=nodes+f,fd+=query(f);
            else root=cur[i];
            add(cur[i]->id,fd-td);
            add(cur[i]->id+1,td-fd);
            printf("%d\n",fd);
        }
        else if(op[i]%2){
            printf("%d\n",rot_max());
            if(op[i]>3)S.erase(*root),add(1,-1),add(root->id,1),(root=root->ch[0])?root->fa=0:0;
        }
        else{
            printf("%d\n",rot_min());
            if(op[i]>3)S.erase(*root),add(root->id+1,-1),(root=root->ch[1])?root->fa=0:0;
        }
    }
}

D1T2:影魔

CTSC那段时间immaotalCO给我看了这题,我想了很久的单调栈都没想清楚,还想到分块去了……现在想想当时真是SB。

记 $v(l,r)=\max\{k_i|l\le i\le r\}$,$\mathrm{last}_i=\min\{j\in\mathbf{N}|v(j+1,i-1) < k_i\}$,$\mathrm{next}_i=\max\{j\in\mathbf{N}|v(i+1,j-1)< k_i\}$。last和next数组可以用单调栈 $O(n)$ 求出。

我们可以把区间 $[l,r]$ 的答案 $S[l,r]$ 的式子写成这种形式:

$$S[l,r]=p_1\left(\sum_{\begin{array}{c}l\le i< j\le r\\k_i< k_j\end{array}} [v_{i+1,j-1}< k_i]+\sum_{\begin{array}{c}l\le i< j\le r\\k_i>k_j\end{array}} [v_{i+1,j-1}< k_j]\right)+p_2\left[\sum_{\begin{array}{c}l\le i< j\le r\\k_i< k_j\end{array}} ([v_{i+1,j-1}< k_j]-[v_{i+1,j-1}< k_i])+\sum_{\begin{array}{c}l\le i< j\le r\\k_i>k_j\end{array}} ([v_{i+1,j-1}< k_i]-[v_{i+1,j-1}< k_j])\right]$$

当然,可以化成这样:

$$S[l,r]=(p_1-p_2)\left(\sum_{l\le i< j\le r,k_i< k_j} [v_{i+1,j-1}< k_i]+\sum_{l\le i< j\le r,k_i>k_j} [v_{i+1,j-1}< k_j]\right)+p_2\left[\sum_{l\le i< j\le r,k_i< k_j} [v_{i+1,j-1}< k_j]+\sum_{l\le i< j\le r,k_i>k_j} [v_{i+1,j-1}< k_i]\right]$$

容易发现求 $\sum_{l\le i< j\le r,k_i< k_j} [v_{i+1,j-1}< k_i]$ 这个式子是so easy的,因为 $v_{i+1,j-1}< k_i$ 等价于 $j\le\mathrm{next}_i$,而如果 $j<\mathrm{next}_i$,则 $k_j< k_i$,仅当 $j=\mathrm{next}_i$ 时 $k_j>k_i$,因此

$$\sum_{l\le i< j\le r,k_i< k_j} [v_{i+1,j-1}< k_i]=\sum_{i=l}^r[\mathrm{next}_i\le r]$$

同理

$$\sum_{l\le i< j\le r,k_i>k_j} [v_{i+1,j-1}< k_j]=\sum_{j=l}^r[\mathrm{last}_j\ge l]$$

类似的我们还可以继续推:

$$\sum_{l\le i< j\le r,k_i< k_j}[v_{i+1,j-1}< k_j]=\sum_{\begin{array}{c}l\le i< j\le r\\i>\mathrm{last}_j\end{array}}1=\sum_{\begin{array}{c}l\le j\le r\\ \mathrm{last}_j< l\end{array}}\sum_{i=l}^{j-1}1+\sum_{\begin{array}{c}l\le j\le r\\ \mathrm{last}_j\ge l\end{array}}\sum_{i=\mathrm{last}_j+1}^{j-1}1=\sum_{\begin{array}{c}l\le j\le r\\ \mathrm{last}_j< l\end{array}}(j-l)+\sum_{\begin{array}{c}l\le j\le r\\ \mathrm{last}_j\ge l\end{array}}(j-\mathrm{last}_j-1)$$

同理

$$\sum_{l\le i< j\le r,k_i>k_j}[v_{i+1,j-1}< k_i]=\sum_{\begin{array}{c}l\le i\le r\\ \mathrm{next}_i>r\end{array}}(r-i)+\sum_{\begin{array}{c}l\le i\le r\\ \mathrm{next}_i\le r\end{array}}(\mathrm{next}_i-i-1)$$

询问这些式子的值很简单。以 $\sum_{l\le i\le r,\mathrm{next}_i\le r}(\mathrm{next}_i-i-1)$ 为例,可以将其拆成 $\sum_{i\le r,\mathrm{next}_i\le r}(\mathrm{next}_i-i-1)-\sum_{i\le l-1,\mathrm{next}_i\le r}(\mathrm{next}_i-i-1)$。考虑 $\sum_{i\le r,\mathrm{next}_i\le r}(\mathrm{next}_i-i-1)$ 怎么求,这相当于一个二维偏序,可以离线树状数组解决,即:维护一个初始值为 $0$ 的序列 $A$,按照 $i=1,2,\cdots,n$ 的顺序,将 $A_{\mathrm{next}_i}$ 的值加上 $\mathrm{next}_i-i-1$,然后就可以更新 $r=i$ 的询问的答案为 $A_1+A_2+\cdots+A_r$,树状数组维护。

复杂度 $O(n+m\log n)$。代码比上一题简单。我想吐槽的是为什么HNOI2017D1出两道树状数组题。。。

#include<cstdio>
#include<vector>
#define ll long long
const int maxn=200010,maxm=200010;
int n,m,p1,p2,k[maxn],stk[maxn],lst[maxn],nxt[maxn],a[maxn],b[maxn];
ll B[6][200010],S[6],ans[200010];
void add(int t,int i,int x){for(S[t]+=x,i++;i<=n+2;i+=i&-i)B[t][i]+=x;}
ll pre(int t,int i){ll s=0;for(i++;i;i-=i&-i)s+=B[t][i];return s;}
ll pos(int t,int i){return S[t]-pre(t,i-1);}
std::vector<int>Q[200010];
int main(){
    scanf("%d%d%d%d",&n,&m,&p1,&p2);
    int top=0;*k=k[n+1]=n+1;
    for(int i=1;i<=n;i++){
        for(scanf("%d",k+i);k[stk[top]]<k[i];top--);
        lst[i]=stk[top];stk[++top]=i;
    }
    top=0;*stk=n+1;
    for(int i=n;i;i--){
        while(k[stk[top]]<k[i])--top;
        nxt[i]=stk[top];stk[++top]=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",a+i,b+i);
        Q[a[i]-1].push_back(-i);Q[b[i]].push_back(i);
    }
    for(int i=0,l,r;i<=n;i++){
        if(i)add(0,l=lst[i],1),add(1,r=nxt[i],1),add(2,l,i),add(3,r,i),add(4,l,i-l-1),add(5,r,r-i-1);
        for(int q=Q[i].size(),t,j;q--;){
            t=(j=Q[i][q])<0?j=-j,-1:1;l=a[j];r=b[j];
            ans[j]+=t*((pos(0,l)+pre(1,r))*(p1-p2)+(pre(2,l-1)-pre(0,l-1)*l+pos(4,l)-pos(3,r+1)+pos(1,r+1)*r+pre(5,r))*p2);
        }
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
}

然后看别人题解说这题和HNOI2016D2T1做法差不多,诶我的做法好像不一样啊,有空的时候交叉写一波?

D1T3:礼物

可能是D1最裸的题?

设 $y$ 顺时针转动了 $d$ 个位置,$c$ 表示对 $x$ 的增加量(如果对 $y$ 增加则用相反数),则差异值为(以下从 $0$ 开始标号)

$$\begin{align*} \sum_{i=0}^{n-1}(x_i-y_{(i+d)\bmod n}+c)^2&=&\sum_{i=0}^{n-1}(x_i^2+y_{(i+d)\bmod n}^2-2x_iy_{(i+d)\bmod n}+c^2+2x_ic-2y_{(i+d)\bmod n}c) \\&=&\sum_{i=0}^{n-1}x_i^2+\sum_{i=0}^{n-1}y_i^2-2\sum_{i=0}^{n-1}x_iy_{(i+d)\bmod n}+nc^2+2(\sum_{i=0}^{n-1}x_i-\sum_{i=0}^{n-1}y_i)c \end{align*}$$

这样就会发现 $d,c$ 是独立的,可分开考虑。

先考虑最小化项 $-2\sum_{i=0}^{n-1}x_iy_{(i+d)\bmod n}$,即最大化 $\sum_{i=0}^{n-1}x_iy_{(i+d)\bmod n}$。设 $y'_i=y_{n-i-1}$,则 $$\sum_{i=0}^{n-1}x_iy_{(i+d)\bmod n}=\sum_{i=0}^{n-1}x_iy'_{(n-1-i-d)\bmod n}$$

不难看出这是一个卷积的形式,即设 $f(d)=\sum_{i+j=d\lor i+j=d+n}x_iy'_j$,则上式的值为 $f(n-1-d)$。卷积可以用FFT计算,复杂度 $O(n\log n)$。

再考虑最小化 $nc^2+2(\sum_{i=0}^{n-1}x_i-\sum_{i=0}^{n-1}y_i)c$,这是一个关于 $c$ 的二次函数,令 $c_0=-\frac{\sum_{i=0}^{n-1}x_i-\sum_{i=0}^{n-1}y_i}{n}$,则函数在 $(-\infty,c_0)$ 上递减,在 $(c_0,+\infty)$ 上递增,由于 $c$ 是整数(不一定非负,因为可以对另一个环增加),只要将不大于 $c_0$ 的最大整数和大于 $c_0$ 的最小整数 $c$ 代入函数,取较小值即可,复杂度为计算 $\sum_{i=0}^{n-1}x_i-\sum_{i=0}^{n-1}y_i$ 的复杂度,即 $O(n)$。

总复杂度为 $O(n\log n)$。为什么 $n\le 50000$?为什么 $m\le 100$?想想就会发现这样答案不会爆 int,出题人真良心。

#include<cstdio>
typedef long long ll;
const int maxn=1<<17,mod=998244353;
ll W[maxn];
ll pw(ll a,ll b){ll c=1;for(;b;b>>=1)b%2?c=c*a%mod:1,a=a*a%mod;return c;}
void dft(int*a,int n,bool r=0){
    ll*w=W+n/2;w[*w=1]=pw(3,(mod-1)/n);
    if(r)w[1]=pw(w[1],mod-2);
    for(int i=2;i<n/2;i++)w[i]=w[i-1]*w[1]%mod;
    for(int i=n/2;i--;)W[i]=W[i*2];
    for(int i=0,j=0,t;i<n;i++){
        if(i<j)t=a[i],a[i]=a[j],a[j]=t;
        for(t=n/2;(j^=t)<t;t/=2);
    }
    w=W+1;
    for(int i=1;i<n;w+=i,i*=2)
        for(int j=0;j<n;j+=i<<1)
            for(int k=0,t;k<i;k++)
                t=a[i+j+k]*w[k]%mod,a[i+j+k]=(a[j+k]+mod-t)%mod,(a[j+k]+=t)%=mod;
    if(!r)return;
    ll I=pw(n,mod-2);
    for(int i=0;i<n;i++)a[i]=a[i]*I%mod;
}
int n,x[maxn],y[maxn],d,s,N,M;
int f(int c){return(n*c-2*d)*c;}
int min(int a,int b){return a<b?a:b;}
int main(){
    scanf("%d%*d",&n);
    for(int i=0;i<n;i++)scanf("%d",x+i),d-=x[i],s+=x[i]*x[i];
    for(int i=n;i--;)scanf("%d",y+i),d+=y[i],s+=y[i]*y[i];
    s+=min(f(d/n),min(f(d/n-1),f(d/n+1)));
    for(N=1;N<n*2;N*=2);
    dft(x,N);dft(y,N);
    for(int i=0;i<N;i++)x[i]=x[i]*(ll)y[i]%mod;
    dft(x,N,1);
    for(int i=0;i<n;i++)x[i]+x[i+n]>M?M=x[i]+x[i+n]:1;
    printf("%d\n",s-2*M);
}

D2T1:大佬

好题,并不像之前听说的那样玄学。我们来分析一下。

首先在第 $i$ 天,如果我方自信值 $C'\ge 0$,设对方自信值为 $C$,令变量 $t$ 的初始值为 $0$,我们有五种可能的操作:

1、$C\leftarrow C-1$;

2、$C'\leftarrow\min\{C'+w_i,mc\}$;

3、$L\leftarrow L+1$;

4、$F\leftarrow FL$;

5、$C\leftarrow C-F,L\leftarrow 0,F\leftarrow 1,t\leftarrow t+1$,如果 $t < 2$。

除了操作2以外的四种操作均和 $i$ 及 $C'$ 无关,因此最后能否战胜取决于能分配多少天给这四个操作。

设计DP:$f(i,c)$ 表示前 $i$ 天的行动使第 $i$ 天结束后 $C'=c$ 的所有方案中,最多能使用多少次非操作2。如果没有这样的方案,$f(i,c)=-\infty$。显然 $C'$ 只和什么时候使用操作2有关。考虑转移,枚举最后一天的操作,如果使用非操作2,那么上一天的自信值 $c'$ 满足 $c=c'-a_i$;否则 $c=\min\{c'-a_i+w_i\}$ 且 $c'-a_i\ge 0$。可以得到如下的状态转移方程:

$$f(i,c)=\max\left\{\max_{c'}\{f(i-1,c')+1|c=c'-a_i\},\max_{c'}\{f(i-1,c')|c=\min\{c'-a_i+w_i\},c'-a_i\ge 0\}\right\}$$

其中 $0\le i\le n$,$0\le c\le mc$。实现时用顺推法即可,这一步的复杂度为 $O(n\cdot mc)$。

令 $T=\max_{i,c}\{f(i,c)\}$,则当对方自信值为 $C$ 时,能够战胜的条件是用不超过 $T$ 天时间进行操作1、3、4、5能够恰好把 $C$ 减到 $0$。

考虑这个问题如何解决。

注意问题的突破口,操作5只能做不超过2次。先探究做恰好2次的情况。设2次操作5使用值的 $F$ 值分别为 $F_1,F_2$,2次操作5前使用的操作3、4总次数分别为 $T_1-1,T_2-1$($T_2$ 不包含 $T_1$),那么操作1可使用的天数不超过 $T-T_1-T_2$,需要使用的次数为 $C-F_1-F_2$,条件等价于

$$F_1+F_2\le C$$

$$C-F_1-F_2\le T-T_1-T_2$$

可以枚举 $F_1,F_2$,然后找出两个用时最小的由3、4构成的操作序列 $seq_1,seq_2$,满足从 $L=0,F=1$ 开始,如果做 $seq_1$ 则最后 $F=F_1$,如果做 $seq_2$ 则最后 $F=F_2$。

这里,我们预处理 $T(F)$ 为从 $L=0,F=1$ 开始,使用若干次操作3、4,最后用一次操作5,恰好使对方 $C$ 减少 $F$ 的操作方案中,操作3、4、5的使用次数之和的最小值,那么枚举 $F_1,F_2$(满足 $F_1+F_2\le C$)之后,只需判断是否有

$$C-F_1-F_2\le T-T(F_1)-T(F_2)$$

即可。

问题来了——$C$ 的范围是 $10^8$,这意味着 $F_1,F_2$ 也可能达到 $10^8$,暴力DP预处理 $T(F)$ 函数的复杂度太高,如何解决?

注意另一突破口:$T\le n\le 100$,因此整个操作过程中 $L\le T\le 100$,而 $F$ 是由操作过程中的若干个 $L$ 相乘得到,这说明 $F$ 一定可以由若干个不超过 $100$ 的正整数相乘得到,经过验证,这样的 $F$ 不到 $10^6$ 个。

我用的是BFS来预处理这些数 $F$,同时预处理出它们的 $T(F)$ 值。首先,如果构成 $F$ 用了 $k$ 次操作4,每次使用前的 $L$ 值为 $L_1\le L_2\le\cdots\le L_k$,那么 $F=\prod_{i=1}^kL_i$,$T(F)=L_k+k+1$。因此如果要判断 $F$ 能否得到或者求 $T(F)$ 的值,可以

  • 枚举最大的 $L_k$
  • 然后找一条最短从大到小加入 $L_i$ 的途径,使得 $F=\prod_{i=1}^kL_i$

注意 $F=1$ 时不需要用操作4,所以要特判。

定义结点 $(i,x)$ 表示当前 $F=x$,目前用于构成 $x$ 的最小 $L$ 值为 $i$。之后

  • 初始化结点 $(i,i)$($i\le T$)的距离为 $i+1$;
  • 对每个结点 $(i,x)$ 和正整数 $j\le\min\{i,\frac{C_\max}{x}\}$,从 $(i,x)$ 到 $(j,jx)$ 连长度为 $1$ 的边。

其中 $C_\max=10^8$。初始化距离还可以做得更简单一些,只初始化 $(2,2)$ 的距离为 $3$,然后对每个结点 $(i,i)$($i < T$),从 $(i,i)$ 到 $(i+1,i+1)$ 连长度为 $1$ 的边。

然后,以 $(2,2)$ 为源点做一遍BFS,那么所有到达的点 $(1,x)$ 对应的 $x$ 均可取作 $F$,$(1,F)$ 的距离就是 $T(F)$。

实测表明BFS的总状态数不超过 $8\times 10^6$,总转移数约为 $3.5\times 10^7$,完全可以接受。然而BFS时如何记录这些状态哪些已被访问过?由于可到达的状态 $(i,x)$ 都满足 $i|x$,预处理 $A_i=\sum_{j=1}^{i-1}\lfloor\frac{C_\max}{i}\rfloor$(其中 $C_\max=10^8$),则状态 $(i,x)$ 可以映射为正整数 $A_i+\frac{x}{i}$,用这个整数作为状态的hash值是不会冲突的。并且这个数不超过 $5.2\times 10^8$,用一个 bitset 就能存下了。(我手写了 bitset

于是我们成功找出了所有合法的 $F$ 及其 $T(F)$ 值,将其按照 $F$ 从小到大排序。最后只差一步了——枚举 $F_1,F_2$ 并判断是否有

$$F_1+F_2\le C$$

$$C-F_1-F_2\le T-T(F_1)-T(F_2)$$

的复杂度是 $O(c_F^2)$ 的($c_F$ 为满足要求的 $F$ 个数),需要优化。这两个约束可以改写成

$$F_2\le C-F_1$$

$$C-F_1+T(F_1)-T\le F_2-T(F_2)$$

所以只需预处理 $F-T(F)$ 的前缀最大值,即 $M(F)=\max_{F'\le F}\{F'-T(F')\}$,就可以只枚举 $F_1$,用Two-pointers方法找出最大的 $F_2$ 满足 $F_2\le C-F_1$,然后 $O(1)$ 判断是否有 $C-F_1+T(F_1)-T\le M(F_2)$ 就做完了。

预处理复杂度难以估计(但对于极限数据的测试不到 $1\texttt{s}$),查询总复杂度为 $O(m\cdot c_F)$,其中 $c_F < 10^6$。

#include<cstdio>
#include<algorithm>
#define ull unsigned long long
const int inf=1<<30;
int n,m,mc,a[110],w[110],C[1010],maxc,f[110][110],add[110],cnt;
int min(int a,int b){return a<b?a:b;}
void cmax(int&a,int b){b>a?a=b:1;}
struct item{
    int i,x,d;
    bool operator<(const item&it)const{return x<it.x;}
}Q[7840010],*H=Q,*T=Q,S[930000];
ull vis[8110000];
void ext(int i,int x,int d){
    int c=add[i]+x;
    if(!(vis[c>>6]>>(c&63)&1))vis[c>>6]|=1ull<<(c&63),*(T++)=(item){i,i*x,d};
}
int pmax[930000];
void init(int lim,int tot){
    for(int i=1;i<tot;i++)add[i+1]=add[i]+lim/i;
    ext(2,1,3);
    for(;H<T;H++){
        int jmax=lim/H->x;
        if(jmax>H->i)jmax=H->i;
        if(H->i<tot&&H->i==H->x)ext(H->i+1,1,H->d+1);
        if(H->i>1)for(int j=1;j<=jmax;j++)ext(j,H->x,H->d+1);
        else S[cnt++]=*H;
    }
    S[cnt++]=(item){1,1,1};
    std::sort(S,S+cnt);
    *pmax=-inf;
    for(int i=0;i<cnt;i++)cmax(pmax[i+1]=S[i].x-S[i].d,pmax[i]);
}
int check(int t,int c){
    if(c<=t)return 1;
    for(int i=cnt,j=0;i--;)if(S[i].x<=c){
        while(j<cnt&&S[i].x+S[j].x<=c)j++;
        if(c-S[i].x<=t-S[i].d||c-S[i].x+S[i].d<=t+pmax[j])return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&m,&mc);
    for(int i=0;i<n;i++)scanf("%d",a+i);
    for(int i=0;i<n;i++)scanf("%d",w+i);
    for(int i=0;i<m;i++)scanf("%d",C+i),cmax(maxc,C[i]);
    for(int i=0;i<=n;i++)for(int j=0;j<=mc;j++)f[i][j]=-inf;
    int t=f[0][mc]=0;
    for(int i=0;i<n;i++)for(int j=0;j<=mc;j++)if(f[i][j]>=0&&j-a[i]>=0){
        cmax(f[i+1][j-a[i]],f[i][j]+1);
        cmax(f[i+1][min(j-a[i]+w[i],mc)],f[i][j]);
    }
    for(int i=1;i<=n;i++)for(int j=0;j<=mc;j++)cmax(t,f[i][j]);
    init(maxc,t);
    for(int i=0;i<m;i++)printf("%d\n",check(t,C[i]));
}

D2T3:抛硬币

这题也很妙,我搞了很久。

看完题发现题目要求的其实是这么一个东西:

$$\sum_{x=0}^a\sum_{y=0}^b[x>y]{a\choose x}{b\choose y}\bmod 10^k$$

然后没想到怎么求。。。就把 $f(a,b)=\sum_{x=0}^a\sum_{y=0}^b[x>y]{a\choose x}{b\choose y}$ 打了个表看看:

     0 
     1      1 
     3      4      5 
     7     11     16     22 
    15     26     42     64     93 
    31     57     99    163    256    386 
    63    120    219    382    638   1024   1586 
   127    247    466    848   1486   2510   4096   6476 
   255    502    968   1816   3302   5812   9908  16384  26333 
   511   1013   1981   3797   7099  12911  22819  39203  65536 106762 
  1023   2036   4017   7814  14913  27824  50643  89846 155382 262144 431910

发现了很多性质,比如

  • $f(b+1,b)=4^b$
  • $f(a,0)=2^a-1$
  • $f(a,b)=f(a-1,b)+f(a-1,b+1)$
  • ……

然而倒数第二条对角线的规律这么明显,第一条对角线的规律我居然没看出来?这不科学!我想知道 $f(a,a)$ 是个啥玩意。

$$f(a,a)=\sum_{0\le y < x\le a}{a\choose x}{a\choose y}=\sum_{0\le x < y\le a}{a\choose x}{a\choose y}$$

$$2f(a,a)=\sum_{0\le x,y\le a,x\ne y}{a\choose x}{a\choose y}=\sum_{x=0}^a\sum_{y=0}^a{a\choose x}{a\choose y}-\sum_{x=0}^a{a\choose x}^2=\left(\sum_{x=0}^a{a\choose x}\right)^2-\sum_{x=0}^a{a\choose x}^2=4^a-\sum_{x=0}^a{a\choose x}^2$$

然后我发现我不会求 $\sum_{x=0}^a{a\choose x}^2$,怎么办?继续打 $g(a)=\sum_{x=0}^a{a\choose x}^2$ 的表:

1 2 6 20 70 252 924 3432 12870 48620 184756

组合数既视感……再把组合数表打出来看,看出来是对称轴上的数,也就是 $g(a)={2a\choose a}$。为什么呢?

想了一下就想明白了:

$$g(a)=\sum_{x=0}^a{a\choose x}{a\choose x}=\sum_{x=0}^a{a\choose x}{a\choose a-x}$$

设两个集合 $A,B$,满足 $|A|=|B|=a$,$A\cap B=\varnothing$,则

$$g(a)=\sum_{S\subseteq A}\sum_{T\subseteq B}[|T|=a-|S|]=\sum_{S\subseteq A}\sum_{T\subseteq B}[|S|+|T|=a]=\sum_{X\subseteq A\cup B}[|X|=a]={2a\choose a}$$

这样就可以做了?然而 $a,b$ 范围很大,并不知道如何优化。唯一有用的条件是 $a-b$ 很小,也就是说要求的值离对角线很近,能不能用对角线上的值暴力递推?

接着发现暴力递推的复杂度是 $O((a-b)^2)$,多组数据下并不能过……

感觉有点掉坑?

准备重新想下整个题。再把式子列出来:

$$f(a,b)=\sum_{x=0}^a\sum_{y=0}^b[x>y]{a\choose x}{b\choose y}$$

嗯,这似乎可以用之前化简 $\sum_{x=0}^a{a\choose x}{a\choose x}$ 的思路来做!

$$f(a,b)=\sum_{x=0}^a\sum_{y=0}^b[a-x>y]{a\choose a-x}{b\choose y}=\sum_{x=0}^a\sum_{y=0}^b[x+y < a]{a\choose a-x}{b\choose y}=\sum_{x=0}^{a-1}{a+b\choose x}$$

妙!这下就简单多了。

设 $S=\sum_{x=0}^{\lfloor\frac{a+b}{2}\rfloor}{a+b\choose x}$,则

$$2S=\sum_{x=0}^{\lfloor\frac{a+b}{2}\rfloor}{a+b\choose x}+\sum_{x=a+b-\lfloor\frac{a+b}{2}\rfloor}^{a+b}{a+b\choose x}=\sum_{x=0}^{a+b}{a+b\choose x}+[2|a+b]{a+b\choose\frac{a+b}{2}}=2^{a+b}-[2|a+b]{a+b\choose\frac{a+b}{2}}$$

$$S=2^{a+b-1}+[2|a+b]\frac{1}{2}{a+b\choose\frac{a+b}{2}}=2^{a+b-1}+[2|a+b]{a+b-1\choose\frac{a+b}{2}-1}$$

因为 $a,b$ 相差不大,所以可以暴力枚举 $x$ 求和 $\sum_{x=\lfloor\frac{a+b}{2}\rfloor+1}^{a-1}{a+b\choose x}$,加上 $S$ 就是答案。注意判 $a=b$ 的情况。现在问题转化为求大组合数,当然由于题目要求模 $10^k$,我们也只要求大组合数模 $10^k$ 即可。

考虑求这个东西:

$${a\choose b}\bmod 10^k$$

由于 $10^k$ 不是质数,甚至 $10$ 都不是质数,无法使用Lucas定理。因为 $10^k=2^k\times 5^k$,且 $(2,5)=1$,可以算出 ${a\choose b}\bmod 2^k$ 和 ${a\choose b}\bmod 5^k$,然后使用中国剩余定理合并。考虑如何计算 ${a\choose b}\bmod p^k$,其中 $p\in\{2,5\}$,$k\le 9$。

因为 ${a\choose b}=\frac{a!}{b!{a-b}!}$,阶乘中可能有多个质因子 $p$,需要将其提取出来。记 $a!=v_ap^{t_a}$,其中 $p\not\lvert a'$,因为

$$a!=\prod_{i=1}^ai!=\prod_{1\le i\le a,p\not\lvert i}i\cdot\prod_{1\le i\le a,p|i}i=\prod_{1\le i\le a,p\not\lvert i}i\cdot\prod_{i=1}^{\lfloor\frac{a}{p}\rfloor}pi=\lfloor\frac{a}{p}\rfloor!p^{\lfloor\frac{a}{p}\rfloor}\prod_{1\le i\le a,p\not\lvert i}i$$

这个过程可以递归下去,$a$ 会变成 $\lfloor\frac{a}{p}\rfloor,\lfloor\frac{a}{p^2}\rfloor,\lfloor\frac{a}{p^3}\rfloor\cdots$,由此得到

$$a!=\prod_{t=0}^{\lfloor\log_pa\rfloor}\left(p^{\lfloor\frac{a}{p^{t+1}}\rfloor}\prod_{1\le i\le\lfloor\frac{a}{p^t}\rfloor,p\not\lvert i}i\right)$$

于是

$$v_a=\prod_{t=0}^{\lfloor\log_pa\rfloor}\prod_{1\le i\le\lfloor\frac{a}{p^t}\rfloor,p\not\lvert i}i$$

$$t_a=\sum_{t=0}^{\lfloor\log_pa\rfloor}\lfloor\frac{a}{p^{t+1}}\rfloor$$

类似地求出 $v_b,t_b,v_{a-b},t_{a-b}$,可以得到 ${a\choose b}\bmod p^k=\frac{v_a}{v_bv_{a-b}}p^{t_a-t_b-t_{a-b}}\bmod p^k$。这里的 $v_a$ 和 $t_a$ 两部分的计算都是可以优化的:

1、$v_a$ 只需在模 $p^k$ 意义下计算,可以用模意义下的循环节优化:

$$v_a\bmod p=\prod_{t=0}^{\lfloor\log_pa\rfloor}\left(\prod_{q=1}^{\lfloor\frac{a}{p^{k+t}}\rfloor}\prod_{p^k(q-1)+1\le i < p^kq,p\not\lvert i}i\cdot\prod_{\lfloor\frac{a}{p^{k+t}}\rfloor p^k+1\le i\le\lfloor\frac{a}{p^t}\rfloor,p\not\lvert i}i\right)\bmod p$$

对 $i=0,1,\cdots,p^k-1$ 预处理 $P_i=\prod_{1\le j\le i,p\not\lvert j}j$,则

$$v_a\bmod p=\prod_{t=0}^{\lfloor\log_pa\rfloor}P_{p^k-1}^{\lfloor\frac{a}{p^{k+t}}\rfloor}P_{\lfloor\frac{a}{p^t}\rfloor\bmod p^k}\bmod p^k$$

这个预处理的复杂度是 $O(p^k)$,由于 $p^k\le 5^9$,预处理时间完全可以接受。另外,$v_b,v_{a-b}$ 需要计算的是模 $p^k$ 意义下的乘法逆元

2、不用求出 $t_a,t_b,t_{a-b}$,只需求 $t_a-t_b-t_{a-b}$,即

$$t_a-t_b-t_{a-b}=\sum_{t=0}^{\lfloor\log_pa\rfloor}\left(\lfloor\frac{a}{p^{t+1}}\rfloor-\lfloor\frac{b}{p^{t+1}}\rfloor-\lfloor\frac{a-b}{p^{t+1}}\rfloor\right)$$

考虑进位,我们发现 $\lfloor\frac{a}{p^{t+1}}\rfloor=\begin{cases}\lfloor\frac{b}{p^{t+1}}\rfloor+\lfloor\frac{a-b}{p^{t+1}}\rfloor,&a\bmod p^{t+1}\ge b\bmod p^{t+1},\\ \lfloor\frac{b}{p^{t+1}}\rfloor+\lfloor\frac{a-b}{p^{t+1}}\rfloor+1,&a\bmod p^{t+1}< b\bmod p^{t+1}\end{cases}$,因此上式可化简为

$$t_a-t_b-t_{a-b}=\sum_{t=0}^{\lfloor\log_pa\rfloor}[a\bmod p^{t+1}< b\bmod p^{t+1}]$$

分析到这里,我们可以用 $O(\log a)$ 的时间求 ${a\choose b}\bmod p^k$ 了。直接套之前的公式就能以 $O(5^k+(a-b)\log a)$ 的复杂度解决本题了。

但是这样还是太慢,怎么办?我纠结了很长一段时间。。。最后去看了这题BZOJ上#1的whzzt写的题解。。。

原来。。。只要这么搞就行了

$${a\choose b+1}={a\choose b}\frac{a-b}{b+1}$$

预处理逆元以及log以内的 $p$ 的幂,暴力分解+递推就可以优化掉复杂度里的log了。最后就是 $O(5^k+T(a-b))$。$T$ 是数据组数。

#include<cstdio>
#define ll long long
ll pw(ll a,ll b,int m){ll c=1;for(;b;b>>=1)b%2?c=c*a%m:1,a=a*a%m;return c;}
ll inv(int a,int m){return a==1?1:(1+m*(a-inv(m%a,a)))/a%m;}
const int mod2=512,mod5=1953125,mod=mod2*mod5,maxt=60;
void init(int p,int m,ll*fac,ll*invs,ll*pws){
    for(int i=*fac=1;i<m;i++)fac[i]=fac[i-1]*(i%p?i:1)%m;
    invs[m-1]=inv(fac[m-1],m);
    for(int i=m;--i;)invs[i-1]=invs[i]*(i%p?i:1)%m,(invs[i]*=fac[i-1])%=m;
    for(int i=*pws=1;i<maxt;i++)pws[i]=pws[i-1]*p%m;
}
ll fac2[mod2],inv2[mod2],pw2[maxt],fac5[mod5],inv5[mod5],pw5[maxt],K2,K5;
struct num{
    int a,t,p,m;
    void operator*=(ll x){while(x&&x%p==0)x/=p,t++;x%=m;a=a*x%m;}
    void operator/=(ll x){while(x&&x%p==0)x/=p,t--;x%=m;a=a*(p<3?inv2:inv5)[x]%m;}
    int val(){return a*(p<3?pw2:pw5)[t]%m;}
};
num C(ll a,ll b,int p,int m,ll*fac){
    ll P=1;int Q=0,T=0;
    for(ll x=a,y=b,z=a-b,t=1;x;x/=p,y/=p,z/=p,t*=p){
        P=P*fac[x%m]%m*inv(fac[y%m]*fac[z%m]%m,m)%m;
        Q+=a%(m*t)<b%(m*t);T+=a%(p*t)<b%(p*t);
    }
    return(num){P*pw(fac[m-1],Q,m)%m,T,p,m};
}
ll calc(ll a,ll l,ll r){
    num c2=C(a,l,2,mod2,fac2),c5=C(a,l,5,mod5,fac5);
    ll s=0;
    for(ll b=l;b<=r;b++){
        s=(s+c2.val()*K2+c5.val()*K5)%mod;
        c2*=a-b;c2/=b+1;c5*=a-b;c5/=b+1;
    }
    return s;
}
int solve(ll a,ll b,int k){
    int m=1;while(k--)m*=10;
    return(pw(2,a+b-1,m)+(a+b&1?0:calc(a+b-1,a+b-1>>1,a+b-1>>1))+calc(a+b,(a+b)/2+1,a-1)+mod-calc(a+b,a,a+b>>1))%m;
}
int main(){
    init(2,mod2,fac2,inv2,pw2);
    init(5,mod5,fac5,inv5,pw5);
    K2=mod5*inv(mod5%mod2,mod2);
    K5=mod2*inv(mod2,mod5);
    ll a,b;int k;
    while(scanf("%lld%lld%d",&a,&b,&k)!=EOF){
        char fm[6]={'%','0',k+48,'d','\n'};
        printf(fm,solve(a,b,k));
    }
}

评论

immortalCO
钟知AKAKAK、钟知AKAKAK、钟知AKAKAK、钟知AKAKAK。 钟知AKAKAK、钟知AKAKAK、钟知AKAKAK、钟知AKAKAK。 钟知AKAKAK、钟知AKAKAK、钟知AKAKAK、钟知AKAKAK。
zhouyi
前排orz
chentong
钟知AKAKAK、钟知AKAKAK、钟知AKAKAK、钟知AKAKAK。
AntiLeaf
这题被您吐槽成难度偏低了……HE果然是弱省 (好吧其实难度确实高不到哪儿去
AntiLeaf
顺便一提怎么感觉这篇博客像是写到一半没写完啊……
WrongAnswer
是的,长期更新。
zhouyi
$O(n\log ^3 p)$可以强行优化到$O(n\log ^2 p)$吧
OldDriverTree
要不要做做YNOI2017的题啊 题目挺不错的~
liu_runda
D2T2看上去很送分,但是也有点送命的地方,"按50分写有80分"的意思是"80%的数据满足初始最优解<=k",如果在初始最优解<=k的时候忘记乘上阶乘,就会发生人民群众喜闻乐见的代码通过8个大样例之后炸成25分的剧情.
Trinkle
钟知AKAKAK、钟知AKAKAK、钟知AKAKAK、钟知AKAKAK。
immortalCO
钟知AK强(于)猫(的强)闲!
immortalCO
SDOI这个题如果不想的这么一般化代码会简单非常多。。c强t就想的很不一般化,代码就非常的短。。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。