发布于

CF1098B Nice table

话说考场上这题距离正解只差一步了，可惜我走错方向变成枚举左上角的block然后瞎鸡儿乱搞求min了。
事实上这一题猜到结论之后可以想到另一个更科学的做法。
具体来说，可以考虑，要么是行上两种字符交替出现而列上随意，要么是列上两种字符交替出现而行上随意。
所以我们可以枚举这些信息，然后检验一下即可。
顺便提一句，这一题的数据范围真的是恶意满满。考场上是瞎jb哈希，但是现在个人觉得还是string比较科学。

#include<iostream>
#include<cstdio>
#include<cstring>

#define MAXN 300005
char lst[6][2]={{'A','G'},{'A','C'},{'A','T'},{'C','T'},{'G','T'},{'C','G'}};
std::string ch[MAXN],out[MAXN];
int n,m,cnt[MAXN][2],val[MAXN][6][2],nw[2];

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=m;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[i][k-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[i][k-1]);
			}
			val[i][j][0]=(int)(nw[0]>=nw[1]);
			cnt[j][0]+=std::min(nw[0],nw[1]);
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=n;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[k][i-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[k][i-1]);
			}
			val[i][j][1]=(int)(nw[0]>=nw[1]);
			cnt[j][1]+=std::min(nw[0],nw[1]);
		}
	}
	int ans=0x3f3f3f3f;
	int pi,pj;
	for(int i=0;i<2;++i){
		for(int j=0;j<6;++j){
			ans=(cnt[j][i]<ans)?pi=i,pj=j,cnt[j][i]:ans;
		}
	}
	if(!pi){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				putchar(lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][0])]); 
			}
			puts("");
		}
	}else{
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				out[j]+=lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][1])];
			}
		}
		for(int i=1;i<=n;++i){
			std::cout<<out[i]<<std::endl;
		}
	}
}

int main(){
	init();
	return 0;
}
发布于

lp2597 ZJOI2012 灾难

这一题的思路还是比较清晰的。虽然可以当作支配树模板，但是事实上可以上一个LCA来代替支配树。
具体来说，就是把有多个食物的消费者连到它所有食物的LCA。然后计算一遍子树大小就好了。
注意连点之前要先拓扑排序。 

#include<iostream>
#include<cstdio>
#include<queue>

#define Swap(A,B) (A^=B^=A^=B)

struct ee{
	int v;
	int nxt;
}e[2500005];
//h，树上的节点。g，拓扑排序的节点。to，每个节点的所有父亲。 
int h[70000],g[70000],et=0,dep[70000],fa[70000][18],in[70000],to[70000],sz[70000],loc[70000];
int n,tp=0;
inline void add(int *H,int U,int V){
	if(U==V){
		return;
	}
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void srt(){
	std::queue<int> q;
	for(int i=1;i<=n;++i){
		if(!in[i]){
			q.push(i);
		}
	}
	int p=0;
	while(!q.empty()){
		p=q.front();
		q.pop();
		loc[++tp]=p;
		for(int i=g[p];i;i=e[i].nxt){
			--in[e[i].v];
			if(!in[e[i].v]){
				q.push(e[i].v);
			}
		}
	}
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		Swap(X,Y);
	}
	for(int i=17;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i]; 
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=17;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
inline void prpr(){
	int nw=0;
	for(int i=1,j;i<=n;++i){
		j=loc[i];
		nw=e[to[j]].v;
		for(int k=to[j];k;k=e[k].nxt){
			nw=lca(nw,e[k].v);
		}
//		请注意这里的nw可能不存在任何父亲节点。 
		add(h,nw,j);
		fa[j][0]=nw;
		dep[j]=dep[nw]+1;
		for(int k=1;k<=17;++k){
			fa[j][k]=fa[fa[j][k-1]][k-1];
		}
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
		sz[X]+=sz[e[i].v];
	}
	++sz[X];
}
void init(){
	scanf("%d",&n);
	int x; 
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		while(x){
			++in[i];
			add(g,x,i);
			add(to,i,x);
			scanf("%d",&x);
		}
	}
	srt();
	prpr();
	dfs(0);
	for(int i=1;i<=n;++i){
		printf("%d\n",sz[i]-1);
	}
}

int main(){
	init();
	return 0;
}
发布于

lp3615 如厕计划

观察题面我们可以发现，如果男性比女性多的话，显然是无法符合要求的；否则，女性使用男女通用单间的个数不应该超过男女性的人数差。
我们不妨把部分的男女性人数差个女性视为男性——这是一种贪心的做法。于是就把女性多于男性的情况归约成了男性和女性相同的情况。
在这种情况下，任何时候都不应该有女性进入男女通用单间。这也就意味着，如果令男性为1，女性为-1，那么在任何时候，数列的前缀和都应该保证为大于等于-1。
然而，要保证一个前缀和始终大于某个数是很难维护的——这是因为位于后面的信息我们无法得到。我们考虑维护后缀和，这样就可以预先得到位于后面的信息了。
于是，我们考虑对每一段计算它的贡献。 

#include<iostream>
#include<cstdio>
#include<cstring>

inline long long Max(long long A,long long B){
	return A>B?A:B;
}
inline long long Min(long long A,long long B){
	return A<B?A:B;
}

long long n,m;
int len;
char ch[200005];
long long dlt=0,a[200005],mx[200005],l[200005];
void init(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		len=strlen(ch+1);
		scanf("%lld",&l[i]);
		for(int j=len;j>=1;--j){
			a[i]+=(ch[j]=='M'?1:-1); 
			mx[i]=Max(mx[i],a[i]);
		}
		dlt+=a[i]*l[i];
	}
	if(dlt>0){
		puts("-1");
		return ;
	}
	long long nw=0,ans=1;
	for(int i=m;i>=1;--i){
		if(a[i]>0){
			ans=Max(ans,(l[i]-1)*a[i]+nw+mx[i]);
		}else{
			ans=Max(ans,nw+mx[i]);
		}
		nw+=l[i]*a[i];
	}
	printf("%lld",ans-1);
}

int main(){
	freopen("queue.in","r",stdin);
	freopen("queue.out","w",stdout);
	init();
	return 0;
}