思路:

本题的模型转换十分巧妙:

仅考虑空格移动,注意到空格移动的路径事实上是黑白相间,且不自交的路径.

这样我们黑白染色变成二分图,转化为二分图上的博弈问题.

显然的性质是从一个点出发先手必胜当且仅当这个点是二分图最大匹配的必须点.

若这个点没有匹配点,先手必败;否则将这个点的匹配点的匹配点设为0,删除这个点,并从这个点的匹配点开始增广.若能够增广,显然这个点不是必须点.

这样只需增广\(O(K)\)次,时间复杂度\(O(KN^4)\).

(另外本沙茶终于明白匈牙利算法是怎回事了...)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define N 41
int ano[N*N];
bool changed[N*N];
 
int head[N*N],next[N*N<<2],end[N*N<<2];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
bool del[N*N];
inline bool dfs(int x){
    if(del[x])return 0;
    for(int j=head[x];j;j=next[j]){
        if(!changed[end[j]]&&!del[end[j]]){
            changed[end[j]]=1;
            if(!ano[end[j]]||dfs(ano[end[j]])){
                ano[x]=end[j],ano[end[j]]=x;
                return 1;
            }
        }
    }
    return 0;
}
 
char s[N];
int map[N][N],lab[N][N];
inline int hash(char c){
    if(c=='X')return 0;
    if(c=='O')return 1;
    return 2;
}
 
inline int getdis(int x,int y){
    return x>y?x-y:y-x;
}
 
#define Q 2010
bool win[Q];
 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
     
    register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)map[i][j]=hash(s[j]);
    }
     
    int x,y;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(map[i][j]==2)
                x=i,y=j;
     
    int id=0;
    map[x][y]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if((((getdis(i,x)+getdis(j,y))%2)^map[i][j])==0)
                lab[i][j]=++id;
     
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)if(lab[i][j]){
            if(lab[i-1][j])addedge(lab[i][j],lab[i-1][j]);
            if(lab[i+1][j])addedge(lab[i][j],lab[i+1][j]);
            if(lab[i][j-1])addedge(lab[i][j],lab[i][j-1]);
            if(lab[i][j+1])addedge(lab[i][j],lab[i][j+1]);
        }
     
    for(i=1;i<=id;++i)
        if(!ano[i])memset(changed,0,sizeof changed),dfs(i);
 
    int steps;
    scanf("%d",&steps);
    steps<<=1;
    for(i=1;i<=steps;++i){
        if(ano[lab[x][y]]){
            int t=ano[lab[x][y]];
            ano[lab[x][y]]=ano[t]=0;
            del[lab[x][y]]=1;
            memset(changed,0,sizeof changed);
            win[i]=!dfs(t);
        }
        else{
            del[lab[x][y]]=1;
            win[i]=0;
        }
        scanf("%d%d",&x,&y);
    }
     
    int re=0;
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])++re;
    }
    printf("%d\n",re);
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])
            printf("%d\n",(i+1)>>1);
    }
    return 0;
}

思路:

对于每次询问,暴力枚举所有编辑距离为1的串,然后用Trie判断存不存在并判重.

妈呀这是\(O(10000*26*20*20)=10^8\),居然也能过.

其实用Hash感觉就好多了.

有没有更好的方法?目前没想出来.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

int ch[200010][26],end[200010],vis[200010],cnt;
char s[21],ss[22];

int tclock;
inline bool judge(int len){
	int p=0;
	for(int i=0;i<len;++i){
		if(!ch[p][ss[i]-'a'])return 0;
		p=ch[p][ss[i]-'a'];
	}
	if(!end[p])return 0;
	if(vis[p]!=tclock)return vis[p]=tclock,1;else return 0;
}

int main(){
	int n,m;scanf("%d%d",&n,&m);
	register int i,j,k;
	
	int len,p,y;
	while(n--){
		scanf("%s",s);
		len=strlen(s),p=0;
		for(i=0;i<len;++i){
			y=s[i]-'a';
			if(!ch[p][y])ch[p][y]=++cnt;
			p=ch[p][y];
		}
		end[p]=1;
	}
	
	int id;
	while(m--){
		scanf("%s",s);
		len=strlen(s);
		
		p=0;
		bool find=1;
		for(i=0;i<len;++i){
			y=s[i]-'a';
			if(!ch[p][y]){find=0;break;}
			else p=ch[p][y];
		}
		if(find&&end[p]){puts("-1");continue;}
		
		int re=0;
		++tclock;
		
		if(len>1){
			for(i=0;i<len;++i){
				id=0;
				for(j=0;j<i;++j)ss[id++]=s[j];
				for(j=i+1;j<len;++j)ss[id++]=s[j];
				re+=judge(len-1);
			}
		}
		for(i=0;i<len;++i)for(j=0;j<26;++j)if(j!=s[i]-'a'){
			memcpy(ss,s,sizeof s),ss[i]='a'+j;
			re+=judge(len);
		}
		for(i=0;i<=len;++i)for(j=0;j<26;++j){
			id=0;
			for(k=0;k<i;++k)ss[id++]=s[k];
			ss[id++]='a'+j;
			for(k=i;k<len;++k)ss[id++]=s[k];
			re+=judge(len+1);
		}
		
		printf("%d\n",re);
	}
	return 0;
}

思路:

首先将颜色分段.

令\(f[i][j]\)表示第\(i\)段到第\(j\)段全部清除最小的代价.

转移一:

\[f[i][j]=\min_{k=i}^{j-1}f[i][k]+f[k+1][j]\]

转移二:

\(i=j\),直接转移

转移三:

\(col[i]=col[j]\),\(f[i][j]=f[i+1][j-1]+blabla...\)

可是这样是不一定对的.

(做到这里在OJ上就可以AC了.)

他不能处理三个离散的珠子合并的情况.

比如1 2 2 1 3 3 1.

正确答案应该是2.

我们加一步判断,如果区间两端都是只有一个的话,尝试在区间中寻找同样颜色的,然后合并.

由于数据问题,这样判断是会WA的.但是这应该是正确答案.

(在OJ上可以AC的代码)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 510
int a[N],col[N],cnt[N],id;
 
int f[N][N];
int main(){
    int n;scanf("%d",&n);
    register int i,j,k,p;
    for(i=1;i<=n;++i)scanf("%d",&a[i]);
    for(i=1;i<=n;){
        col[++id]=a[i],cnt[id]=1;
        for(j=i;j!=n&&a[j]==a[j+1];++j,++cnt[id]);
        i=j+1;
    }
     
    for(k=1;k<=id;++k){
        for(i=1;i+k-1<=id;++i){
            j=i+k-1;
            if(i==j)f[i][j]=(cnt[i]>=3?1:(3-cnt[i]));
            else{
                f[i][j]=~0U>>1;
                for(p=i;p<j;++p)f[i][j]=min(f[i][p]+f[p+1][j],f[i][j]);
                if(k>=3&&col[i]==col[j])f[i][j]=min(f[i][j],f[i+1][j-1]+((cnt[i]+cnt[j]>=3)?0:(3-cnt[i]-cnt[j])));
            }
        }
    }
     
    printf("%d\n",f[1][id]);
    return 0;
}

思路:

首先将图黑白二染色变成二分图.

然后求出一组最大匹配.

如果某个点不在匹配中,那么先手选择这个点.

那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.

那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.

最后总是后手无路可走.因此先手必胜.

因此如果某个点不是最大匹配的必须点.就可以选择这个点.

如何找出这个呢?

在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.

证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)

(注意总点数要开2W,我不知道为什么)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=20010;
    static const int E=V<<2;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        //printf("%d %d %d\n",a,b,f);
        addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        int re=0,ins,Min,i,u=S;
        bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){
                stk[top++]=cur[u]=ins,u=end[ins];
            }
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
#define N 110
char s[N];
int lab[N][N],x[N*N],y[N*N];
 
int res[N*N],nums;
 
bool vis[N*N];
inline void bfs(int S,bool rev){
    static int q[N*N];
    int fr=0,ta=0;
    memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S;
    while(fr^ta){
        int i=q[fr++];
        for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]])
            vis[Stg.end[j]]=1,q[ta++]=Stg.end[j];
    }
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j;
    }
     
    int S=0,T=cnt+1,num0=0,num1=0;
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){
        if((i+j)&1){
            ++num1;
            Stg.make(S,lab[i][j],1);
            if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF);
            if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF);
            if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF);
            if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF);
        }
        else
            ++num0,Stg.make(lab[i][j],T,1);
    }
     
    if(num0==0&&num1==0){
        puts("LOSE");
        return 0;
    }
     
    int re=Stg.Maxflow(S,T);
     
    /*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j])
        printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/
    if(num0==num1&&re==num0){
        puts("LOSE");
        return 0;
    }
    puts("WIN");
     
    bfs(S,0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    bfs(T,1);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    sort(res+1,res+nums+1);
     
    for(i=1;i<=nums;++i){
        printf("%d %d\n",x[res[i]],y[res[i]]);
    }
     
    return 0;
}

思路:

暴力枚举答案,然后将点分层,边总是从该层连向下一层.

然后判断最大流是不是满足题意.

具体连边看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=50*100;
    static const int E=2450*100*2;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V],gap[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        bfs(T),memcpy(cur,head,sizeof cur);
        int re=0,Min,ins,i,u=S;
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]];
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){stk[top++]=cur[u]=ins,u=end[ins];}
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
struct Edge{
    int u,v,f;
}E[2510];
 
#define get(x,dep) ((dep-1)*n+x)
int main(){
    int n,m,T;scanf("%d%d%d",&n,&m,&T);
    register int i,j;
    for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f);
     
    int re;
    for(re=1;;++re){
        Stg.reset();
        for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f);
        for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF);
        for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF);
        int now=Stg.Maxflow(0,n*(re+1)+1);
        //printf("%d\n",now);
        if(now>=T)break;
    }
     
    printf("%d\n",re);
     
    return 0;
}

思路:

AC自动机的Fail树有很多奇妙的性质.

例如串\(a\)是串\(b\)在Fail树上的祖先,那么\(a\)在\(b\)中应该出现\(dep[b]-dep[a]\)次.

(不过好像跟这题没什么关系)
 

把Alice的\(n\)个字符串插入AC自动机.

然后每插入一个修改串,都动态维护一下每个自动机中的节点,如果出现在修改串中,则该节点答案+1.

我们用修改串在自动机上走,每走到一个节点,我们都想要这个节点在Fail树上到根的路径上的答案均+1.

遗憾的是,这样有可能重复!

利用树链的并.

将所有要处理的节点按照dfs序排序,然后首先把它们到根的路径+1.

随后将相邻两个节点的LCA到根的路径-1.

非常科学.

怎么加?树链剖分?等TLE吧.

直接将标记累加在节点上,询问时就询问子树内的标记之和.

这样只需用树状数组维护DFS序即可.

可惜卡常数!

用倍增LCA会超时.

于是我们换用RMQlca,并用ZKW线段树维护.

估计ST表预处理也会超时.

反正总算还是水过去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
  
#define N 2002010
int ch[N][26],fail[N],ins[N],cnt;
char s[N];
  
int head[N],next[N],end[N];
inline void addedge(int a,int b){
    static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;
}
  
int in[N],out[N],dep[N],tclock;
void dfs(int x){
    in[x]=++tclock;
    for(int j=head[x];j;j=next[j])
        dep[end[j]]=dep[x]+1,dfs(end[j]);
    out[x]=tclock;
}
 
namespace Lca_system{
    int Seq[N<<1],a[8383608],M,ins[N],cnt;
    inline void build_dfs(int x){
        ins[x]=++cnt;
        Seq[cnt]=x;
        for(int j=head[x];j;j=next[j]){
            build_dfs(end[j]);
            Seq[++cnt]=x;
        }
    }
    inline int Min(int x,int y){
        if(x==-1||y==-1)return x==-1?y:x;
        return dep[x]<dep[y]?x:y;
    }
    inline void init(){
        build_dfs(0);
        for(M=1;M<cnt+2;M<<=1);
        memset(a,-1,sizeof a);
        for(int i=1;i<=cnt;++i)a[M+i]=Seq[i];
        for(int i=M-1;i>=1;--i)a[i]=Min(a[2*i],a[2*i+1]);
    }
    inline int ask(int tl,int tr){
        int re=-1;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)re=Min(re,a[tl^1]);
            if(tr&1)re=Min(re,a[tr^1]);
        }
        return re;
    }
    inline int lca(int x,int y){
        x=ins[x],y=ins[y];
        if(x>y)swap(x,y);
        return ask(x,y);
    }
}
 
int seq[N],num;
  
int A[N];
inline void modify(int x,int c){
    for(;x<=cnt+1;x+=x&-x)A[x]+=c;
}
inline int ask(int x){
    int re=0;for(;x;x-=x&-x)re+=A[x];return re;
}
  
inline bool cmp(const int&x,const int&y){return in[x]<in[y];}
  
inline int git(){
    int c,re;
    while(!isdigit(c=getchar()));
    re=c-'0';
    while(isdigit(c=getchar()))re=(re<<1)+(re<<3)+c-'0';
    return re;
}
char buf[100010*6],*o=buf;
inline void print(int x){
    static int s[100];int top=0;
    if(!x)*o++=48;else{for(;x;x/=10)s[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+s[i];}
    *o++='\n';
}
int main(){
    int n=git();
    register int i,j;
      
    int len,p;
    for(i=1;i<=n;++i){
        scanf("%s",s);
        len=strlen(s),p=0;
        for(j=0;j<len;++j){
            if(!ch[p][s[j]-'a'])ch[p][s[j]-'a']=++cnt;
            p=ch[p][s[j]-'a'];
        }
        ins[i]=p;
    }
      
    queue<int>q;
    for(i=0;i<26;++i)if(ch[0][i])q.push(ch[0][i]);
    int u,v,r;
    while(!q.empty()){
        u=q.front(),q.pop();
        for(i=0;i<26;++i)if((v=ch[u][i])){
            q.push(v);
            for(r=fail[u];r&&!ch[r][i];r=fail[r]);
            fail[v]=ch[r][i];
        }
    }
      
    for(i=1;i<=cnt;++i)addedge(fail[i],i);
    dep[0]=1,dfs(0);
    Lca_system::init();
      
    int Q=git();
      
    int qte,x;
    while(Q--){
        qte=git();
        if(qte==1){
            scanf("%s",s);
            len=strlen(s),p=0,num=0;
            for(i=0;i<len;++i){
                while(p&&!ch[p][s[i]-'a'])p=fail[p];
                p=ch[p][s[i]-'a'];
                if(p)seq[++num]=p;
            }
            sort(seq+1,seq+num+1,cmp);
            for(i=1;i<=num;++i)modify(in[seq[i]],1);
            for(i=1;i<num;++i)modify(in[Lca_system::lca(seq[i],seq[i+1])],-1);
        }
        else{
            x=git();
            print(ask(out[ins[x]])-ask(in[ins[x]]-1));
        }
    }
      
    fwrite(buf,1,o-buf,stdout);
    return 0;
}

思路:

首先发现如果根确定的话,我们要求的答案就是根和关键点们组成的虚树的边长之和的2倍减去根到所有关键点的距离最大值.

这个应该不难理解.

然后觉得虚树很难处理,就抛弃虚树,弄了一个繁琐至极的两遍dp.(这个我就不写是怎么dp的啦,大家应该都会.)

然后看到某个题解说最上面说的那个东西bfs就行.

如何呢?

一个关键的性质:树上距离一个点最远的点必定是直径的一端!这个想想很显然.

然后就简单了.

下面是我的傻叉dp:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 1ll<<59
 
#define N 500010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int c){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=c;}
inline void make(int a,int b,int c){addedge(a,b,c),addedge(b,a,c);}
 
bool c[N];
 
long long max_dis[N],cnt[N],total_dis[N];
inline void dp1(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dp1(end[j],x);
    cnt[x]=c[x],max_dis[x]=c[x]?0:-INF,total_dis[x]=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        cnt[x]+=cnt[end[j]];
        max_dis[x]=max(max_dis[x],max_dis[end[j]]+len[j]);
        total_dis[x]+=total_dis[end[j]]+(cnt[end[j]]?1ll:0ll)*len[j];
    }
}
 
long long re[N];
long long seq[N],pre[N],suc[N],g[N];
inline void dp2(int x,int fa,int fadis){
    long long real_total_dis,real_max_dis;
    if(x==1)real_total_dis=total_dis[x],real_max_dis=max_dis[x];
    else{
        real_total_dis=total_dis[x]+total_dis[fa]+(cnt[fa]?1ll:0ll)*fadis;
        real_max_dis=max(max_dis[x],max_dis[fa]+fadis);
    }
    re[x]=real_total_dis*2-real_max_dis;
     
    int num=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)seq[++num]=max_dis[end[j]]+len[j];
    pre[0]=suc[num+1]=-INF;
    for(int i=1;i<=num;++i)pre[i]=max(seq[i],pre[i-1]);
    for(int i=num;i>=1;--i)suc[i]=max(seq[i],suc[i+1]);
     
    num=0;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        ++num;
        g[end[j]]=max(pre[num-1],suc[num+1]);
    }
     
    int real_cnt=cnt[x];
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        total_dis[x]=real_total_dis-total_dis[end[j]];
        if(cnt[end[j]])total_dis[x]-=len[j];
        max_dis[x]=g[end[j]];
        if(x!=1)max_dis[x]=max(max_dis[x],max_dis[fa]+fadis);
        if(c[x])max_dis[x]=max(max_dis[x],0ll);
        cnt[x]=real_cnt-cnt[end[j]]+cnt[fa];
         
        dp2(end[j],x,len[j]);
    }
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    if(m==0){puts("0");return 0;}
    int a,b,x;
    for(i=1;i<n;++i)scanf("%d%d%d",&a,&b,&x),make(a,b,x);
     
    while(m--)scanf("%d",&x),c[x]=1;
    dp1(1,-1);
    dp2(1,-1,0);
     
    for(i=1;i<=n;++i)printf("%lld\n",re[i]);
    return 0;
}

思路:

首先有一个性质:当前的矩形必定可以被划分成两个子矩形.

无脑dp.

记录四个状态表示当前矩形的四条边是不是原来的大矩形的边.

然后记忆化搜索即可.

(要非常注意常数优化)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 1ll<<60
 
#define N 310
long long f[2][2][2][2][N][N];
int n,m,k;
 
inline long long calc(int w,int h,int a,int b,int c,int d){
    if(w>h){
        swap(w,h);
        int aa=c,bb=d,cc=b,dd=a;
        a=aa,b=bb,c=cc,d=dd;
        if(a>b)swap(a,b);
        if(c>d)swap(c,d);
    }
    if(f[a][b][c][d][w][h]!=-1)return f[a][b][c][d][w][h];
    if(!a&&!b&&!c&&!d)return f[a][b][c][d][w][h]=INF;
    long long re=(long long)(w*h-k)*(w*h-k);
    if(a+b+c>0&&a+b+d>0)
        for(int i=1;i<w;++i)re=min(re,calc(i,h,a,b,c,0)+calc(w-i,h,a,b,0,d));
    if(a+c+d>0&&b+c+d>0)
        for(int i=1;i<h;++i)re=min(re,calc(w,i,a,0,c,d)+calc(w,h-i,0,b,c,d));
    return f[a][b][c][d][w][h]=re;
}
 
int main(){
    scanf("%d%d%d",&n,&m,&k);
    register int i,j;
     
    memset(f,-1,sizeof f);
    printf("%lld",calc(n,m,1,1,1,1));
     
    return 0;
}

思路:

首先不难想到排序后dp,可是这样就\(O(n^2)\)超时了.

一开始想的是按照列从前往后做,然后给每一个之前的列维护一个单调队列.可是发现这样是\(O(m^3)\)的.

我们可以注意到一条性质:由于\(a,b>0\)时,\((a+b)^2>a^2+b^2\),且价值均\(>0\),所以路径上相邻两个点形成的矩形中不能存在别的点.

也就是说对于之前的每一列,只有最下面的才有用.

我们在扫的时候顺便记录一下这个就好了.

时间复杂度\(O(nm)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 200010
#define M 1010
struct Pos{
	int x,y,lab;
	bool operator<(const Pos&B)const{return x<B.x||(x==B.x&&y<B.y);}
}P[N];

int w[N],f[N],g[M],x[N],y[N];
inline int sqr(int x){return x*x;}

int main(){
	int n,m;scanf("%d%d",&n,&m);register int i,j;
	
	for(i=1;i<=n;++i)scanf("%d%d",&P[i].x,&P[i].y),x[i]=P[i].x,y[i]=P[i].y,P[i].lab=i,scanf("%d",&w[i]);
	sort(P+1,P+n+1);
	
	f[P[1].lab]=w[P[1].lab],g[1]=P[1].lab;
	for(i=2;i<=n;++i){
		f[P[i].lab]=-1<<30;
		for(j=1;j<=P[i].y;++j)if(g[j])f[P[i].lab]=max(f[P[i].lab],f[g[j]]+w[P[i].lab]-sqr(P[i].y-j)-sqr(P[i].x-x[g[j]]));
		g[P[i].y]=P[i].lab;
	}
	
	for(i=1;i<=n;++i)if(x[i]==m&&y[i]==m)printf("%d",f[i]);
	return 0;
}

利用一下对偶原理建模什么的都非常裸,就放一下代码吧.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define INF ~0U>>1
 
struct Solver{
    static const int N=10010;//变量个数
    static const int M=1010;//限制个数
    int n,m;
    int B[M];//基变量集合
    int NB[N];//非基变量集合
    f2 c[N],v;//目标函数的各项系数以及常数
    f2 A[M][N],b[N];//限制的系数
     
    Solver(){}
    Solver(int _n,int _m):n(_n),m(_m){}
     
    void debug(){
        puts("Function");
        printf("Maximize ");
        for(int i=1;i<=n;++i){
            if(i>1)putchar('+');
            printf("%.2lfx_%d",c[i],NB[i]);
        }
        printf("+%.2lf\n",v);
         
        puts("Limits");
        for(int i=1;i<=m;++i){
            printf("x_%d",B[i]);
            for(int j=1;j<=n;++j)printf("+%.2lfx_%d",A[i][j],NB[j]);
            printf("<=%.2lf\n",b[i]);
        }
    }
     
    inline void pivot(int l,int e){//转轴操作,将第l个基变量与第e个非基变量进行交换
        int i,j,k;
         
        //更改第l个限制,得到x_e与x_l的关系式
        b[l]/=A[l][e];
        for(i=1;i<=n;++i)if(i!=e)A[l][i]/=A[l][e];
        A[l][e]=1/A[l][e];
         
        //将x_e带入,更改剩余的所有限制
        for(i=1;i<=m;++i)if(i!=l&&A[i][e]!=0){
            b[i]-=b[l]*A[i][e];
            for(j=1;j<=n;++j)if(j!=e)A[i][j]-=A[i][e]*A[l][j];
            A[i][e]=-A[i][e]*A[l][e];
        }
         
        //更改目标函数
        v+=c[e]*b[l];
        for(i=1;i<=n;++i)if(i!=e)c[i]-=c[e]*A[l][i];
        c[e]=-c[e]*A[l][e];
        swap(B[l],NB[e]);
    }
    inline f2 solve(){//得到线性规划的最优解,或者返回无界区域
        int i,j,l,e,lim;
         
        while(1){
            for(e=0,i=1;i<=n;++i)if(c[i]>0){e=i;break;}//寻找最小标号的可行非基变量
            if(e==0)return v;//如果不存在这样的非基变量,则已经是最优解,直接返回
             
            //寻找最紧的上界
            for(lim=INF,i=1;i<=m;++i)if(A[i][e]>0&&lim>b[i]/A[i][e])l=i,lim=b[i]/A[i][e];
            if(lim==INF)return INF;//没有限制,返回无界区域
            else pivot(l,e);//否则进行转轴操作
        }
    }
}Complex;
 
void output(){Complex.debug();}
 
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    register int i,j;
     
    Complex.n=m,Complex.m=n;
    int x;
    for(i=1;i<=n;++i)scanf("%d",&x),Complex.b[i]=x;
     
    int l,r;
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&l,&r,&x);
        for(j=l;j<=r;++j)Complex.A[j][i]=1;
        Complex.c[i]=x;
    }
     
    for(i=1;i<=Complex.n;++i)Complex.NB[i]=i;
    for(i=1;i<=Complex.m;++i)Complex.B[i]=Complex.n+i;
     
    //Complex.debug();
     
    printf("%d",(int)Complex.solve());
 
    return 0;
}

233剩下的两道题目也很类似.