CF1131

这么早的CF已经很少见了,不过我还是大力掉分。
我好菜啊.jpg


CF1131A
观察题意,随便推个式子提交就AC了。
打卡题。


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

int a,b,c,d,ans=0;
void init(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	ans=a+b*2+c+d*2+std::abs(a-c)+4;
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131B
一道比较简单的题,但是如果脑残了会非常难。
反正我脑残以后是瞎jb写了二十七个特判死活PP不了。
当然仔细理解题意会发现还是比较简单的——当且仅当上一个的终止状态是平局态的时候,答案会有额外的统计。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,a[100005],b[100005],ans=1;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a[i],&b[i]);
		ans+=max(0,min(a[i],b[i])-max(a[i-1],b[i-1])+1);
		if(a[i-1]==b[i-1]){
			--ans;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131C
比B简单,普通构造题。
第一个直观的感觉是从小到大排列,但是仔细想想觉得那样不一定更优。
所以考虑到FJ省冬令营ZZQ讲的构造技巧,可以上一个奇偶排序。
于是AC此题。


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

int n,a[100005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i+=2){
		printf("%d ",a[i]);
	} 
	for(int i=n;i>=1;--i){
		if(!(i&1)){
			printf("%d ",a[i]);
		}
	}
}
int main(){
	init();
	return 0;
}


CF1131D
一道细节题,车站分级弱化版。
如果没有等于号,直接拓扑排序就可以通过。
但是等于号比较蛋疼。
会发现等于号得到的东西都是相同等级的,所以可以考虑用并查集维护。
两个坑点:首先要考虑记录访问过的点的次数来判是否无解,因为可能存在一个独立的环。
然后更新答案应该要按照最后一个更新,而非第一个。这是由这个解法的基本特性,也就是解集是所有约束条件的并集这一特性决定的。


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

int n,m,in[2005];
char ch[1005][1005];

int f[2005];
inline int fa(int X){
	return f[X]==X?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
bool mp[2005][2005];
queue<int> q;
bool vis[2005];
int ans[2005];
inline bool srt(){
	for(int i=1;i<=n+m;++i){
		if(!in[i]){
			q.push(i);
			ans[i]=1;
			vis[i]=1;
		}
	}
	int cnt=0; 
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		++cnt;
		for(int i=1;i<=n+m;++i){
			if(mp[p][i]){
				if(!in[fa(i)]){
					return 0;
				}else{
					--in[fa(i)];
					if(!in[fa(i)]){
						q.push(fa(i));
						ans[fa(i)]=min(ans[p]+1,ans[fa(i)]);
					}
				}
			}
		}
	}
	return cnt==n+m;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i]+1;
	}
	for(int i=1;i<=n+m;++i){
		f[i]=i,ans[i]=0x3f3f3f3f;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(ch[i][j]=='<'){
				mp[i][n+j]=1;
			}
			if(ch[i][j]=='>'){
				mp[n+j][i]=1;
			}
			if(ch[i][j]=='='){
				uni(i,n+j);
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		if(fa(i)!=i){
			for(int j=1;j<=n+m;++j){
				mp[fa(i)][j]|=mp[i][j];
				mp[i][j]=0;
			}
			for(int j=1;j<=n+m;++j){
				if(mp[j][i]){
					mp[j][fa(i)]=1;
					mp[j][i]=0;
				}
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		for(int j=1;j<=n+m;++j){
			if(mp[i][j]){
				++in[j];
			}
		}
	}
	if(!srt()){
		puts("No");
		return;
	}else{
		puts("Yes");
		for(int i=1;i<=n;++i){
			printf("%d ",ans[fa(i)]);
		}
		puts("");
		for(int i=n+1;i<=n+m;++i){
			printf("%d ",ans[fa(i)]);
		}
	}
	
	
}
int main(){
	init();
	return 0;
}


CF1131F
这道题和D题有一点神似。
我们维护每一个已经弄好的连续块的左端点和右端点,每次访问到这个块就直接连接到它的父亲。
这个过程用并查集完成,使得可以直接搜索到整个块的端点。每一次直接把前一个块接在后一个块的左边就好了。
把每个连接记录一下最后输出即可。


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

struct ee{
	int v;
	int nxt;
}e[300005];
int h[150005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,l[150005],r[150005];
int f[150005];
inline int fa(int X){
	return X==f[X]?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		l[i]=r[i]=i,f[i]=i;
	}
	int a,b;
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		a=fa(a),b=fa(b);
		add(r[a],l[b]);
		uni(a,b);
		l[b]=l[a];
	}
	a=l[fa(1)],b=0;
	printf("%d ",a);
	for(int i=1;i<n;++i){
		for(int j=h[a];j;j=e[j].nxt){
			if(e[j].v!=b){
				printf("%d ",e[j].v);
				b=a,a=e[j].v;
				break;
			}
		}
	}
}
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;
}

lp2805 NOI2009 植物大战僵尸

仔细阅读题意,我们发现,这道题本质上就是一个约束类问题:对于每一株植物,都存在一些植物,需要消灭掉它们才能消灭它。
故而,它就变成了一个这样的问题:存在一些植物,其中的一些要消灭了另外一些之后才能消灭,问收益最大化的方法。
如果我们对每一棵植物建点,然后从一棵植物向它的约束植物连边,那么问题就转化为:一张有向图,每个点都有点权,请选中其中的某些点,使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是,从源点向正权点连权值为点权的边;从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么,答案就是总权值减去最小割。


下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点,连向汇点的边被割掉表示选中这个点。
那么,最终的结果必然是一个闭合子图。
这是因为,对于这张图的最小割,当你选中一个节点之后,这个点的所有后继负权节点都一定被割掉/选中了(根据割的性质显然);
这个点的所有后继正权节点都一定不被割/选中了(根据最小割的性质,割掉这些边没有意义)。
并且,任何一个闭合子图的选法都至少可以对应一个割法。
这是因为,对于原图中的某一种连接方法,都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时,根据我们此前的定义,最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而,答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的,故而最小割可以得到最优答案。


PS:
这一题应当考虑死锁情况,想象一个无限攻击力和攻速的豌豆射手。(不考虑连样例都过不了)(但是尽管这样还是能够拿到80分)
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记,然后令这些点在网络流中不存在。
然而,如果我们直接写一个拓扑排序的话,还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想,因为这张图上每一条有向边的终点一旦被删去,那么它的所有前驱也都是不能存在的。
故而,对反图进行拓扑排序找环并删去才能符合题目的要求。


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

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

int main(){
	init();
	return 0;
}

lp1983 NOIP2013 车站分级

看到\(DAG\),立刻可以考虑上一个拓扑排序。
将偏序关系转化为邻接矩阵即可。

#include<iostream>
#include<cstdio>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,s[1005][1005],in[1005],ans=0;
bool map[1005][1005],a[1005],d[1005],used[1005];
queue <int> q;

void re(){
	while(1){
		bool bo=0;
		for(int i=1;i<=n;i++){
			if(!in[i]&&!used[i]){
				q.push(i);
				used[i]=1;
				bo=1;
			}
		}
		if(!bo){
			break;
		}
		while(!q.empty()){
			int p=q.front();
			q.pop();
			for(int i=1;i<=n;i++){
				if(map[p][i]){
					map[p][i]=0;
					in[i]--;
				}
			}
		}
		ans++;
	}
}

int init(){
	memset(in,0,sizeof(in));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&s[i][0]);
		memset(a,0,sizeof(a));
		for(int j=1;j<=s[i][0];j++){
			scanf("%d",&s[i][j]);
			a[s[i][j]]=1;
		}
		for(int j=s[i][1];j<=s[i][s[i][0]];j++){
			if(!a[j]){
				for(int k=1;k<=s[i][0];k++){
					//map(i,j)表示i<j
					if(!map[j][s[i][k]]){
						map[j][s[i][k]]=1;
						in[s[i][k]]++;
					}
				}
			}
		}
	}
}

int main(){
	init();
	re();
	printf("%d",ans);
}

 

 

CF510C

因为维护的是偏序关系,很容易可以发现是拓扑排序裸题。
一个字母写错了调了半天。
可以用堆维护字典序。


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int in[30],n,len[1005],at=0,ss[30];
bool mp[30][30];
char ch[105][105];
char ans[30];
inline void CMP(const int &A,const int &B){
    int le=Min(len[A],len[B]);
    for(int i=1;i<=le;++i){
        if(ch[A][i]!=ch[B][i]){
            if(!mp[ch[A][i]-'a'][ch[B][i]-'a']){
                mp[ch[A][i]-'a'][ch[B][i]-'a']=1;
                ++in[ch[B][i]-'a'];
            }
            return;
        }
    }
    if(len[A]>len[B]){
        puts("Impossible");
        exit(0);
    }
}
priority_queue< int,vector<int>,greater<int> > q;
inline void srt(){
    for(int i=0;i<26;++i){
        if(!in[i]){
            q.push(i);
        }
    }
    int p;
    while(!q.empty()){
        p=q.top();
        q.pop();
        ans[++at]=p+'a';
        for(int i=0;i<26;++i){
            if(mp[p][i]){
                --in[i];
                if(!in[i]){
                    q.push(i);
                }
            }
        }
    }
    if(at<26){
        puts("Impossible");
        exit(0);
    }
    ans[++at]='\0';
}
void init(){
    scanf("%d",&n);
    memset(mp,0,sizeof(mp));
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;++i){
        cin>>ch[i]+1;
        len[i]=strlen(ch[i]+1);
    }
    for(int i=1;i<n;++i){
        CMP(i,i+1);
    }
    srt(); 
    cout<<ans+1;
}
int main(){
    init();
    return 0;
}