【考后总结】8 月 CSP-S 模拟赛 9

I want to break free

I want to break free

I want to break free from your lies

You're so self satisfied I don't need you

I've got to break free

God knows, God knows I want to break free

I've fallen in love

I've fallen in love for the first time

And this time I know it's for real

I've fallen in love yeah

God knows God knows I've fallen in love

It's strange but it's true

I can't get over the way you love me like you do

But I have to be sure

When I walk out that door

Oh how I want to be free baby

Oh how I want to be free

Oh how I want to break free

But life still goes on

I can't get used to living without living without

Living without you by my side

I don't want to live alone hey

God knows got to make it on my own

So baby can't you see

I've got to break free

I've got to break free

I want to break free yeah

I want, I want, I want, I want to break free

int n;
struct edge{
    int to,nxt;
}e[maxn];
int head[maxn],cnt;
inline void add_edge(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int fa[maxn],siz[maxn],mxsiz[maxn],ct[maxn];
void dfs(int u,int f){
    fa[u]=f,siz[u]=1,mxsiz[u]=0;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        dfs(v,u);
        siz[u]+=siz[v],mxsiz[u]=max(mxsiz[u],siz[v]);
    }
    ct[u]=u;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        int x=ct[v];
        while(x!=u){
            if(max(mxsiz[fa[x]],siz[u]-siz[fa[x]])<max(mxsiz[x],siz[u]-siz[x])) x=fa[x];
            else break;
        }
        if(max(mxsiz[x],siz[u]-siz[x])<max(mxsiz[ct[u]],siz[u]-siz[ct[u]])) ct[u]=x;
    }
}

int main(){
    freopen("cent.in","r",stdin);
    freopen("cent.out","w",stdout);
    n=read();
    for(int u,v=2;v<=n;++v){
        u=read();
        add_edge(u,v);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i) printf("%d\n",ct[i]);
    return 0;
}

int n,m;
int pw[26];
char s[255][255];
int sum[255][255],xorsum[255][255];
int ch[255],now[505],D[505];
int ans;
inline void check(int u,int d){
    if(u>d) return;
    int len=2*(d-u+1)+1;
    now[1]=mod+1;
    for(int i=u;i<=d;++i) now[2*(i-u+1)]=ch[i],now[2*(i-u+1)+1]=mod+1;
    for(int i=1,l,r=-1;i<=len;++i){
        int j=(l+r)-i,k;
        if(i>r) k=0;
        else k=min(D[j],r-i+1);
        while(i+k<=len&&i-k>=1&&now[i-k]==now[i+k]) ++k;
        D[i]=k;
        ans+=D[i]/2;
        if(i+k-1>r) l=i-k+1,r=i+k-1;
    }
}

int main(){
    freopen("pal.in","r",stdin);
    freopen("pal.out","w",stdout);
    pw[0]=1;
    for(int i=1;i<26;++i) pw[i]=1ll*pw[i-1]*base%mod;
    n=read(),m=read();
    for(int i=1;i<=n;++i){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;++j){
            sum[i][j]=(sum[i][j-1]+pw[s[i][j]-'a'])%mod;
            xorsum[i][j]=xorsum[i][j-1]^(1<<(s[i][j]-'a'));
        }
    }
    for(int l=1;l<=m;++l){
        for(int r=l;r<=m;++r){
            int last=0;
            for(int i=1;i<=n;++i){
                int range_sum=(sum[i][r]-sum[i][l-1]+mod)%mod,range_xor=xorsum[i][r]^xorsum[i][l-1];
                if(__builtin_popcount(range_xor)>1){
                    check(last+1,i-1);
                    last=i;
                    continue;
                }
                ch[i]=range_sum;
            }
            check(last+1,n);
        }
    }
    printf("%d\n",ans);
    return 0;
}

int n,k,m;
struct edge{
    int u,v,w;
    bool mark;
    edge()=default;
    edge(int u_,int v_,int w_,bool mark_):u(u_),v(v_),w(w_),mark(mark_){}
    bool operator<(const edge &rhs)const{
        return w<rhs.w;
    }
}e[maxn<<1];

int bel[maxn];
int find(int x){
    if(x==bel[x]) return x;
    else return bel[x]=find(bel[x]);
}
vector<int> E[maxn];
inline void Kruskal(){
    for(int i=1;i<=n;++i) bel[i]=i;
    sort(e+1,e+k+m+1);
    for(int i=1,u,v;i<=k+m;++i){
        u=e[i].u,v=e[i].v;
        int fu=find(u),fv=find(v);
        if(fu==fv) continue;
        bel[fv]=fu;
        E[u].push_back(v),E[v].push_back(u);
        e[i].mark=true;
    }

}

int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int top[maxn],dfn[maxn],dfncnt;
void dfs1(int u,int f,int d){
    fa[u]=f,dep[u]=d,siz[u]=1;
    int maxson=-1;
    for(int v:E[u]){
        if(v==f) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>maxson) son[u]=v,maxson=siz[v];
    }
}
void dfs2(int u,int t){
    top[u]=t,dfn[u]=++dfncnt;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int v:E[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

int val[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
    int tag[maxn<<2];
    void build(int rt,int l,int r){
        if(l==r) return tag[rt]=inf,void();
        build(lson),build(rson);
    }
    inline void push_down(int rt){
        if(tag[rt]){
            tag[rt<<1]=tag[rt<<1|1]=tag[rt];
            tag[rt]=0;
        }
    }
    void update(int rt,int l,int r,int pl,int pr,int k){
        if(pl<=l&&r<=pr) return tag[rt]=k,void();
        push_down(rt);
        if(pl<=mid) update(lson,pl,pr,k);
        if(pr>mid) update(rson,pl,pr,k);
    }
    void dfs(int rt,int l,int r){
        if(l==r) return val[l]=tag[rt],void();
        push_down(rt);
        dfs(lson),dfs(rson);
    }
#undef mid
#undef lson
#undef rson
}S;

inline void update(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        S.update(1,1,n,dfn[top[v]],dfn[v],w);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    if(u!=v) S.update(1,1,n,dfn[u]+1,dfn[v],w);
}

ll ans;

int main(){
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);
    n=read(),k=read(),m=read();
    for(int i=1,u,v;i<=k;++i){
        u=read(),v=read();
        e[i]=edge(u,v,0,false);
    }
    for(int i=1,u,v,w;i<=m;++i){
        u=read(),v=read(),w=read();
        e[k+i]=edge(u,v,w,false);
    }
    Kruskal();
    dfs1(1,0,0);
    dfs2(1,1);
    S.build(1,1,n);
    for(int i=k+m;i>k;--i){
        if(e[i].mark) continue;
        update(e[i].u,e[i].v,e[i].w);
    }
    S.dfs(1,1,n);
    for(int i=1;i<=k;++i){
        int now=max(dfn[e[i].u],dfn[e[i].v]);
        if(val[now]==inf) return printf("-1\n"),0;
        ans+=val[now];
    }
    printf("%lld\n",ans);
    return 0;
}

int n,m;
int a[maxn],b[maxn];

inline bool check_slope_a(int x,int y,int z){
    ll lhs=1ll*(a[y]-a[x])*(z-y),rhs=1ll*(a[z]-a[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_b(int x,int y,int z){
    ll lhs=1ll*(b[y]-b[x])*(z-y),rhs=1ll*(b[z]-b[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_ab(int x,int y,int l,int r){
    ll lhs=1ll*(a[y]-a[x])*(r-l),rhs=1ll*(b[r]-b[l])*(y-x);
    return lhs<rhs;
}

int sta[maxn],topa;
int stb[maxn],topb;

ll ans;

int main(){
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i) b[i]=read();
    sta[++topa]=1;
    for(int i=2;i<=n;++i){
        while(topa>1&&check_slope_a(sta[topa-1],sta[topa],i)) --topa;
        sta[++topa]=i;
    }
    stb[++topb]=1;
    for(int i=2;i<=m;++i){
        while(topb>1&&check_slope_b(stb[topb-1],stb[topb],i)) --topb;
        stb[++topb]=i;
    }
    int i=1,j=1;
    while(i<topa||j<topb){
        if(i==topa){
            ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
            ++j;
        }
        else if(j==topb){
            ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
            ++i;
        }
        else{
            if(check_slope_ab(sta[i],sta[i+1],stb[j],stb[j+1])){
                ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
                ++i;
            }
            else{
                ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
                ++j;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}