2017 ACM/ICPC Asia Regional Shenyang Online

不想去听老师读PPT上的公式，来统一更一下网络赛的情况。。。。。

A string string string

后缀数组，连续k个后缀的LCP - max（第一个后缀与上一个后缀的Height，最后一个后缀与下一个后缀的Height）。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#define ws WS
using namespace std;
const int MAXN=2e5+50;
int n,k;
int Sa[MAXN];
int Rank[MAXN];
int Heigh[MAXN];
int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];
int cmp(int *r,int a,int b,int l){
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void get_sa(char *r,int *Sa,int n,int m){
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++)
        ws[i]=0;
    for(i=0;i<n;i++)
        ws[x[i]=r[i]]++;
    for(i=1;i<m;i++)
        ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)
        Sa[--ws[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        for(p=0,i=n-j;i<n;i++)
            y[p++]=i;
        for(i=0;i<n;i++)
            if(Sa[i]>=j)
                y[p++]=Sa[i]-j;
        for(i=0;i<n;i++)
            wv[i]=x[y[i]];
        for(i=0;i<m;i++)
            ws[i]=0;
        for(i=0;i<n;i++)
            ws[wv[i]]++;
        for(i=1;i<m;i++)
            ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--)
            Sa[--ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[Sa[0]]=0,i=1;i<n;i++)
            x[Sa[i]]=cmp(y,Sa[i-1],Sa[i],j)?p-1:p++;
    }
}
void get_heigh(char *s,int n){
    int k=0;
    for(int i=1;i<=n;i++) Rank[Sa[i]]=i;
    for(int i=0;i<n;i++)
    {
        if(k)k--;
        int j=Sa[Rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        Heigh[Rank[i]]=k;
    }
}
int dp[MAXN][35];
void ST(){
    int tmp=(int)(log((double)n)/log(2.0));
    for(int j=1;j<=tmp;j++)
    for(int i=1;i<=n;i++){
        dp[i][j]=0;
    }
    for(int i=1;i<=n;i++) dp[i][0]=Heigh[i];
    for(int j=1;j<=tmp;j++)
    for(int i=1;i<=n;i++){
        dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    }
}
int LCP(int L,int H){
    int k=(int)(log((double)H-L+1)/log(2.0));
    return min(dp[L][k],dp[H-(1<<k)+1][k]);
}

char s[MAXN];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&k);
        scanf("%s",s);
        n=strlen(s);
        get_sa(s,Sa,n+1,150);
        get_heigh(s,n);
        Heigh[n+1]=0;
        ST();
        if(k==1){
            long long ans=0;
            for(int i=1;i<=n;i++){
                ans+=Sa[i]+1-max(Heigh[i],Heigh[i+1]);
            }
            printf("%lld
",ans);
            continue;
        }
        long long ans=0;
        for(int i=1;i<=n-k+1;i++){
            int tmp=LCP(i+1,i+k-1);
            ans+=max(0,tmp-max(Heigh[i],Heigh[i+k]));
        }
        printf("%lld
",ans);
    }

    return 0;
}

B cable cable cable

保证每个颜色至少出现在（m-k+1）个屏幕上即可。

C happy happy happy

unsolved

D array array array

分别最长不下降子序列和最长不上升子序列

F number number number

矩阵快速幂 f[2*n+3]-1

F gems gems gems

最长的步伐不超过sqrt(n)，所以dp[i][j]代表走到第i个位置当前步伐为j，因为最后结束情况很多，所以倒过来做，最后答案就是dp[1][1]。

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e4+5;

int n;
int a[MAXN];
int sum[MAXN];
int dp[MAXN][205];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        memset(dp,0,sizeof(dp));
        for(int i=n;i>=1;i--)
        for(int k=1;k*(k+1)/2<=n;k++){
            if(i+k-1<=n){
                dp[i][k]=sum[i+k-1]-sum[i-1]-dp[i+k][k];
            }
            if(i+k<=n){
                dp[i][k]=max(dp[i][k],sum[i+k]-sum[i-1]-dp[i+k+1][k+1]);
            }
        }
        printf("%d
",dp[1][1]);
    }

    return 0;
}

G mustedge mustedge mustedge

一开始写了个nlognlogn的居然忘了树剖加线段树有两个log，T到死，最后还是刚过去了。

1.双连通缩点，然后树剖修改权值。树上边权一开始为1，每次添加操作为将路径上的边权修改为0，查询操作则是查询路径上的和。

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;

int n,m;
struct Edge{
    int to,Next;
}edge[MAXN*2];
int tot;
int head[MAXN];
inline void init(int tt){
    tot=0;
    for(int i=0;i<=tt;i++) head[i]=-1;
}
inline void addedge(int u,int v){
    edge[tot].to=v;
    edge[tot].Next=head[u];
    head[u]=tot++;
}
int top;
int block;
int index;
int dfn[MAXN];
int low[MAXN];
int Stack[MAXN];
int belong[MAXN];
int instack[MAXN];
void tarjan(int u,int fa){
    int v;
    low[u]=dfn[u]=++index;
    Stack[top++]=u;
    instack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].Next){
        v=edge[i].to;
        if(v==fa) continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        block++;
        while(1){
            v=Stack[--top];
            instack[v]=0;
            belong[v]=block;
            if(u==v) break;
        }
    }
}
void solve(int tt){
    for(int i=0;i<=tt;i++)
        dfn[i]=instack[i]=0;
    index=top=block=0;
    tarjan(1,0);
}

Edge e[MAXN*2];
int cnt;
int first[MAXN];
int deep[MAXN];
int Top[MAXN];
int son[MAXN];
int num[MAXN];
int fa[MAXN];
int p[MAXN];
int pos;
inline void pre(int tt){
    pos=1;
    cnt=0;
    for(int i=0;i<=tt;i++)
        son[i]=first[i]=-1;
}
void addedge_new(int u,int v){
    e[cnt].to=v;
    e[cnt].Next=first[u];
    first[u]=cnt++;
}
void dfs1(int u,int par,int d){
    deep[u]=d;
    fa[u]=par;
    num[u]=1;
    for(int i=first[u];i!=-1;i=e[i].Next){
        int v=e[i].to;
        if(v==par) continue;
        dfs1(v,u,d+1);
        num[u]+=num[v];
        if(son[u]==-1||num[v]>num[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int sp){
    Top[u]=sp;
    p[u]=pos++;
    if(son[u]==-1) return;
    dfs2(son[u],sp);
    for(int i=first[u];i!=-1;i=e[i].Next){
        int v=e[i].to;
        if(v!=son[u] && v!=fa[u])
            dfs2(v,v);
    }
}

#define lson (id*2)
#define rson (id*2+1)
#define mid ((l+r)/2)
int lazy[MAXN*4],tre[MAXN*4];
inline void push_up(int id){
    tre[id]=tre[lson]+tre[rson];
}
inline void build(int id,int l,int r){
    lazy[id]=0;
    if(l==r){
        if(l==1) tre[id]=0;
        else tre[id]=1;
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(id);
}
inline void push_down(int id){
    lazy[lson]=lazy[rson]=1;
    tre[lson]=tre[rson]=0;
    lazy[id]=0;
}
inline void update(int id,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        tre[id]=0;
        lazy[id]=1;
        return;
    }
    if(lazy[id]) push_down(id);
    if(ql<=mid)
        update(lson,l,mid,ql,qr);
    if(mid+1<=qr)
        update(rson,mid+1,r,ql,qr);
    push_up(id);
}
inline int query(int id,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return tre[id];
    if(lazy[id]) push_down(id);
    int res=0;
    if(ql<=mid)
        res+=query(lson,l,mid,ql,qr);
    if(mid+1<=qr)
        res+=query(rson,mid+1,r,ql,qr);
    return res;
}

inline void build_tree(){
    pre(block);
    for(int u=1;u<=n;u++){
        for(int i=head[u];i!=-1;i=edge[i].Next){
            int v=edge[i].to;
            if(belong[u]==belong[v]) continue;
            addedge_new(belong[u],belong[v]);
        }
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,block);
}

inline void change(int u,int v){
    int f1=Top[u],f2=Top[v];
    while(f1!=f2){
        if(deep[f1]<deep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        update(1,1,block,p[f1],p[u]);
        u=fa[f1]; f1=Top[u];
    }
    if(v!=u){
        if(deep[u]<deep[v]) swap(u,v);
        update(1,1,block,p[son[v]],p[u]);
    }
}
inline int Query(int u,int v){
    int f1=Top[u],f2=Top[v];
    int res=0;
    while(f1!=f2){
        if(deep[f1]<deep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        res+=query(1,1,block,p[f1],p[u]);
        u=fa[f1]; f1=Top[u];
    }
    if(v!=u){
        if(deep[u]<deep[v]) swap(u,v);
        res+=query(1,1,block,p[son[v]],p[u]);
    }
    return res;
}
inline void fun(){
    int q;
    scanf("%d",&q);
    while(q--){
        int op,u,v;
        scanf("%d%d%d",&op,&u,&v);
        u=belong[u]; v=belong[v];
        if(op==1){
            change(u,v);
        }
        else{
            printf("%d
",Query(u,v));
        }
    }
}

int main(){
    int t;
    scanf("%d",&t);
    int T=t;
    while(t--){
        printf("Case #%d:
",T-t);
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        solve(n);
        build_tree();
        fun();
    }

    return 0;
}

2.先跑出一棵树，把剩下的边看作添加操作。每次添加操作，用并查集向上合并，每条边最多只会合并一次，并用树状数组维护从dfs序，每次合并将子树的值减一。查询操作就是sum(in[u])+sum(out[u])-sum(lca)*2。

#include <bits/stdc++.h>
using namespace std;
const int MAX_V=1e5+5;
const int MAX_LOG=19;

int depth[MAX_V];

int f[MAX_V];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
void pre(int n){
    for(int i=0;i<=n;i++) f[i]=i;
}

struct Edge{
    int to,Next;
} edge[MAX_V*2];
int tot;
int head[MAX_V];
void addedge(int u,int v){
    edge[tot].to=v;
    edge[tot].Next=head[u];
    head[u]=tot++;
}
void init_new(int n){
    tot=0;
    for(int i=0;i<=n;i++) head[i]=-1;
}
int root;
int fa[MAX_LOG][MAX_V];
void dfs(int u,int par,int d){
    fa[0][u]=par;
    depth[u]=d;
    for(int i=head[u];i!=-1;i=edge[i].Next){
        int v=edge[i].to;
        if(v==par) continue;
        dfs(v,u,d+1);
    }
}
void init(int n){
    root=1;
    dfs(root,-1,1);
    for(int k=0;k+1<MAX_LOG;k++){
        for(int v=1;v<=n;v++){
            fa[k+1][v]=fa[k][fa[k][v]];
        }
    }
}
int LCA(int u,int v){
    if(depth[u]>depth[v]) swap(u,v);
    for(int k=MAX_LOG-1;k>=0;k--){
        if((depth[v]-depth[u])&(1<<k)){
            v=fa[k][v];
        }
    }
    if(u==v) return u;
    for(int k=MAX_LOG-1;k>=0;k--){
        if(fa[k][u]!=fa[k][v]){
            u=fa[k][u];
            v=fa[k][v];
        }
    }
    return fa[0][v];
}

int n,m,q;
struct Query{
    int op,u,v;
} que[MAX_V*2];
int num;

int c[MAX_V];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=val;
    }
}
int sum(int x){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)){
        res+=c[i];
    }
    return res;
}

int cnt;
int in[MAX_V],out[MAX_V];
int dfs2(int u){
    in[u]=++cnt;
    for(int i=head[u];i!=-1;i=edge[i].Next){
        int v=edge[i].to;
        if(v==fa[0][u]) continue;
        dfs2(v);
    }
    out[u]=cnt;
}

void solve(){
    cnt=0; dfs2(1);
    for(int i=1;i<=n;i++) c[i]=0;
    for(int i=1;i<=n;i++){
        add(in[i],1); add(out[i]+1,-1);
    }
    pre(n);
    for(int i=0;i<num;i++){
        int op=que[i].op;
        int u=que[i].u;
        int v=que[i].v;
        int lca=LCA(u,v);
        if(op==1){
            u=find(u); v=find(v);
            while(find(u)!=find(lca)){
                add(in[u],-1); add(out[u]+1,1);
                int par=fa[0][u];
                merge(u,par);
                u=find(u);
            }
            while(find(v)!=find(lca)){
                add(in[v],-1); add(out[v]+1,1);
                int par=fa[0][v];
                merge(v,par);
                v=find(v);
            }
        }
        else{
            printf("%d
",sum(in[u])+sum(in[v])-sum(in[lca])*2);
        }
    }
}

int from[MAX_V],to[MAX_V];
int main(){
    int t;
    scanf("%d",&t);
    int T=t;
    while(t--){
        scanf("%d%d",&n,&m);
        init_new(n);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&from[i],&to[i]);
        }
        num=0; pre(n);
        for(int i=1;i<=m;i++){
            int u=from[i];
            int v=to[i];
            if(find(u)==find(v)){
                que[num++]=(Query){1,u,v};
            }
            else{
                addedge(u,v);
                addedge(v,u);
                merge(u,v);
            }
        }
        printf("Case #%d:
",T-t);
        init(n);
        scanf("%d",&q);
        while(q--){
            int op,u,v;
            scanf("%d%d%d",&op,&u,&v);
            que[num++]=(Query){op,u,v};
        }
        solve();
    }

    return 0;
}

H transaction transaction transaction

两遍dfs，分别从下到上和从上到下维护买的最小值和买的最大值即可

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL MAXN=1e5+5;

LL n;
LL a[MAXN];

struct node{
    LL to,cost;
};
vector<node> g[MAXN];

LL dp1[MAXN],dp2[MAXN];
void dfs1(LL u,LL fa){
    dp1[u]=a[u]; dp2[u]=a[u];
    for(LL i=0;i<g[u].size();i++){
        LL v=g[u][i].to;
        LL w=g[u][i].cost;
        if(v==fa) continue;
        dfs1(v,u);
        dp1[u]=max(dp1[u],dp1[v]-w);
        dp2[u]=min(dp2[u],dp2[v]+w);
    }
}
void dfs2(LL u,LL fa){
    for(LL i=0;i<g[u].size();i++){
        LL v=g[u][i].to;
        LL w=g[u][i].cost;
        if(v==fa) continue;
        dp1[v]=max(dp1[v],dp1[u]-w);
        dp2[v]=min(dp2[v],dp2[u]+w);
        dfs2(v,u);
    }
}
int main(){
    LL t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(LL i=1;i<=n;i++){
            g[i].clear();
            scanf("%lld",&a[i]);
        }
        for(LL i=1;i<n;i++){
            LL u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            g[u].push_back((node){v,w});
            g[v].push_back((node){u,w});
        }
        dfs1(1,0);
        dfs2(1,0);
        LL ans=0;
        for(LL i=1;i<=n;i++)
            ans=max(ans,dp1[i]-dp2[i]);
        printf("%lld
",ans);
    }

    return 0;
}

I cube cube cube

unsolved

J ping ping ping

虽然是原题，然而当时并没有补。

贪心的做法，把所有询问排序按照lca从深到浅排序。每个询问如果端点都被标记则不计数，否则把lca的子树都给标记了并且答案++。

#include <bits/stdc++.h>
using namespace std;

const int MAX_V=10005;
const int MAX_LOG=32;
vector<int> g[MAX_V];
int root;
int fa[MAX_LOG][MAX_V];
int depth[MAX_V];
void addedge(int u,int v){
    g[u].push_back(v);
    g[v].push_back(u);
}
void dfs(int u,int pre,int d){
    fa[0][u]=pre;
    depth[u]=d;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==pre) continue;
        dfs(v,u,d+1);
    }
}
void init(int n){
    root=1;
    dfs(root,-1,0);
    for(int k=0;k+1<MAX_LOG;k++){
        for(int v=1;v<=n;v++){
            fa[k+1][v]=fa[k][fa[k][v]];
        }
    }
}
int LCA(int u,int v){
    if(depth[u]>depth[v]) swap(u,v);
    for(int k=MAX_LOG-1;k>=0;k--){
        if((depth[v]-depth[u])&(1<<k)){
            v=fa[k][v];
        }
    }
    if(u==v) return u;
    for(int k=MAX_LOG-1;k>=0;k--){
        if(fa[k][u]!=fa[k][v]){
            u=fa[k][u];
            v=fa[k][v];
        }
    }
    return fa[0][v];
}

int n,p;
int vis[MAX_V];
void dfs2(int u){
    if(vis[u]) return;
    vis[u]=1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa[0][u]) continue;
        dfs2(v);
    }
}
struct node{
    int u,v,lca;
};
vector<node> tt;
bool cmp(node x,node y){
    return depth[x.lca]>depth[y.lca];
}

int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n+1;i++) g[i].clear();
        for(int i=1;i<=n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u+1,v+1);
        }
        init(n+1);
        tt.clear();
        memset(vis,0,sizeof(vis));
        scanf("%d",&p);
        while(p--){
            int u,v;
            scanf("%d%d",&u,&v);
            u++,v++;
            tt.push_back((node){u,v,LCA(u,v)});
        }
        sort(tt.begin(),tt.end(),cmp);
        int ans=0;
        for(int i=0;i<tt.size();i++){
            int u=tt[i].u;
            int v=tt[i].v;
            int lca=tt[i].lca;
            if(vis[u]||vis[v]) continue;
            else{
                ans++;
                dfs2(lca);
            }
        }
        printf("%d
",ans);
    }

    return 0;
}

K triangulation triangulation triangulation

unsolved

L card card card

把串加倍一次，直接从前往后扫，扫到小于0的地方就停止，期间保证扫到的长度不超过n，记录最大值。