Codeforces AIM Tech Round 3 (Div. 1) 题解

幸好没参加，参加了就得回到Div 2。 http://codeforces.com/contest/708/problem/A

题目大意： 给定一个字符串，选择一个非空子串进行前移操作(\(...b->a->z\))，求经过操作后字典序最小的子串

傻吊题，找到第一个两个\(a\)之间串进行操作就可以了，注意\(aa...a\)要特判就行了。

#include<bits/stdc++.h>
using namespace std;
string s;
int bj=0;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='a'&&bj==1) break;
		if(s[i]!='a')
		{
			bj=1;
			s[i]--;
		}
	}
	if(bj==0)
	{
		s[s.size()-1]='z';
	}
	cout<<s;
	return 0;
}

http://codeforces.com/contest/708/problem/B

题目大意： 给出四个数字，代表\(00\)子序列的个数，\(01\)子序列的个数，\(10\)子序列的个数，\(11\)子序列的个数，构造一个符合条件的\(01\)串

其实也挺脑残的，就是有很多坑。 不妨设四个数字分别为\(a,b,c,d\) 对\(a\)和\(d\)来说，我们可以直接知道数字0和数字1的个数。如果数字0的个数为\(p\)，那么显然存在\[\frac{p \times (p-1)}{2}=a\] 于是对于\(a\)和\(d\)，我们只需要知道存不存在对应的解就行了。（注意：为0的时候有多个解....这个很坑） 然后我们可以解出0的个数\(ans0\)和1的个数\(ans1\)，因为这个东西是正反结合的，所以一个合法情况一定存在\(ans1 \times ans0 = b \times c\) 我们只需要贪心满足\(b\)就可以的，剩下的\(d\)一定可以满足。

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d;
long long z,y;
long long ans0,ans1;
int main()
{
	cin>>a>>b>>c>>d;
	if(b==0&&c==0)
	{
		if(a==0&&d==0)
		{
			ans0=1;
		}
		else
		{
			if(a!=0)
			{
				a=a*2;
				z=sqrt(a);
				y=a/z;
				if(z*y!=a)
				{
					cout<<"Impossible";
					return 0;
				}
				if(z+1!=y)
				{
					cout<<"Impossible";
					return 0;
				}
				ans0=y;
			}
			if(d!=0)
			{
				d=d*2;
				z=sqrt(d);
				if(z==0)
				{
					cout<<"Impossible";
					return 0;
				}
				y=d/z;
				if(z*y!=d)
				{
					cout<<"Impossible";
					return 0;
				}
				if(z+1!=y)
				{
					cout<<"Impossible";
					return 0;
				}
				ans1=y;
			}
		}
	}
	else
	{
		a=a*2;
		z=sqrt(a);
		if(z!=0) y=a/z;
		else y=1;
		if(z*y!=a)
		{
			cout<<"Impossible";
			return 0;
		}
		if(z+1!=y)
		{
			cout<<"Impossible";
			return 0;
		}
		ans0=y;
		d=d*2;
		z=sqrt(d);
		if(z!=0) y=d/z;
		else y=1;
		if(z*y!=d)
		{
			cout<<"Impossible";
			return 0;
		}
		if(z+1!=y)
		{
			cout<<"Impossible";
			return 0;
		}
		ans1=y;
	}
	z=b+c;
	y=ans0*ans1;
	if(z!=y)
	{
		cout<<"Impossible";
		return 0;
	}
	long long l;
	l=ans1;
	for(int i=1;i<=ans0;i++)
	{
		while(l>b) cout<<"1",l--;
		cout<<"0";
		b-=l;
	}
	while(l!=0) cout<<"1",l--;
	return 0;
}

http://codeforces.com/contest/708/problem/C

题目大意： 给定一棵树，求每个顶点，可不可以经过至多一次修改边的操作（修改之后要保证仍然是一棵树），成为重心（删除该点，剩余每个联通块的大小不超过\(\frac{n}{2}\)）

树形动态规划。 跟求树的重心那个dp差不多，首先选定一个点为根，对于每个点，维护向下的子树大小，还需要维护每个点向下的，可以删除的最大合法子树的大小（大小不超过\(\frac{n}{2}\)），这样我们可以判断一个子树是否可以在不修改或者一次修改操作之后变得合法。 问题就在于向上的那个子树，对于这个子树，我们可以用\(n-size_i\)，来计算从\(i\)向上的子树的大小，对于删除的最大合法子树，用一次dfs，递归的找父亲节点的其他儿子和父亲节点的向上子树的对应值，之后的判断就很简单了，就判断一下通过一次操作，所有子树能不能合法就行。

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> e[400010];
int pre[400010]={};
int size[400010]={};
int uu[400010]={};
int up[400010]={};
bool cmp(pair<int,int> x,pair<int,int> y)
{
	return x>y;
}
pair<int,int> ff(int pr,int x)
{
	int ans=0;
	int u=0;
	pre[x]=pr;
	pair<int,int> p;
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]!=pr)
		{
			p=ff(x,e[x][i]);
			u=max(u,p.second);
			ans+=p.first;
		}
	}
	ans++;
	size[x]=ans;
	if(ans<=n/2) u=max(ans,u);
	uu[x]=u;
	return make_pair(ans,u);
}
void pan(int x)
{
	vector<pair<int,int> > w;
	w.push_back(make_pair(up[x],x));
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]!=pre[x])
		{
			w.push_back(make_pair(uu[e[x][i]],e[x][i]));
		}
	}
	sort(w.begin(),w.end(),cmp);
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]!=pre[x])
		{
			if(w[0].second==e[x][i]) up[e[x][i]]=max(up[e[x][i]],w[1].first);
			else  up[e[x][i]]=max(up[e[x][i]],w[0].first);
			if(n-size[e[x][i]]<=n/2) up[e[x][i]]=max(up[e[x][i]],n-size[e[x][i]]);
		}
	}
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]!=pre[x])
		{
			pan(e[x][i]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	ff(0,1);
	up[1]=0;
	pan(1);
	/*for(int i=1;i<=n;i++)
	{
		cout<<size[i]<<" "<<uu[i]<<" "<<up[i]<<endl;
	}*/
	for(int i=1;i<=n;i++)
	{
		bool bj=0;
		bool tt=0;
		for(int j=0;j<e[i].size();j++)
		{
			if(e[i][j]!=pre[i])
			{
				if(size[e[i][j]]>n/2&&(size[e[i][j]]-uu[e[i][j]])<=n/2&&bj==0)
				{
					bj=1;
				}
				else if(size[e[i][j]]>n/2)
				{
					cout<<"0 ";
					tt=1;
					break;
				}
			}
			else
			{
				if(n-size[i]>n/2&&(n-size[i]-up[i])<=n/2&&bj==0)
				{
					bj=1;
				}
				else if(n-size[i]>n/2)
				{
					cout<<"0 ";
					tt=1;
					break;
				}
			}
		}
		if(tt==0) cout<<"1 ";
	}
	return 0;
}

http://codeforces.com/contest/708/problem/D

题目大意： 给定一个网络流流量图（不一定合法），可以对每个边的流量和流量上限进行修改，使这个图合法，修改代价是所有边修改后的值和修改前的值的差的绝对值的和，求最小的代价,使这个图合法，就是让每个点的流量平衡（流入等于流出)

直接搬运叉姐题解...

捕获

这里解释一下为什么n到1要连一条流量为无穷费用为0的边，因为点1和点n的流量本身是不平衡的，两个一起的流量应该是平衡的，所以应该加一条边平衡他俩的流量。

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

const int inn=1000000007;

class Network{
public:   
	typedef long long VAL;
	static const int SIZE=1005;
	static const int INF=1000000007;
	typedef struct ARC{
		int t,c;
		VAL w;
		ARC *o;
	} *PTR;
	ARC arc[200005];
	PTR now[SIZE],e[SIZE];
	int cnt[SIZE],l[SIZE],r[SIZE],edge;
	VAL sum;
	void clear(){
		memset(e,edge=sum=0,sizeof(e));
	}
	ARC &REV(PTR x){
		return arc[(x-arc)^1];
	}
	int flow(int S,int T){
		return spfa_johnson(S,T,INF);
	} 
	PTR add_edge(int x,int y,int c,VAL w=0){
		e[x]=&(arc[edge++]=(ARC){
			y,c,+w,e[x]
		});
		e[y]=&(arc[edge++]=(ARC){
			x,0,-w,e[y]
		});
		return e[x];
	}
	int aug(int S,int T,int &can){
		int x,z=T,use=can;
		for(x=S;x!=T;x=now[x]->t) if(use>now[x]->c) use=now[z=x]->c;
		for(x=S;x!=T;x=now[x]->t){
			now[x]->c-=use;
			REV(now[x]).c+=use;
			sum+=use*now[x]->w;
		}
		can-=use;
		return z;
	}
	int spfa_johnson(int S,int T,int can){
		if(S==T) return can;
		int in=can,x,m;
		VAL phi[SIZE],len[SIZE],MAXW=1000000007;
		memset(l,0,sizeof(l));
		fill_n(phi,SIZE,MAXW);
		phi[r[0]=T]=0;
		for(int i=m=0;i<=m;i++)
		{
			l[x=r[i%SIZE]]=0;
			for(PTR u=e[x];u;u=u->o){
				if(phi[x]+REV(u).w>=phi[u->t]||!REV(u).c) continue;
				phi[u->t]=phi[x]+REV(u).w;
				if(!l[u->t]) l[r[++m%SIZE]=u->t]=1;
			}
		}
		do{
			typedef pair<VAL,int> TPL;
			priority_queue<TPL> q;
			fill_n(len,SIZE,MAXW);
			memset(l,0,sizeof(l));
			q.push(TPL(len[T]=0,T));
			while(q.size()){
				x=q.top().second;
				q.pop();
				if(!l[x]) l[x]=1;
				else continue;
				for(PTR u=e[x];u;u=u->o){
					if(!REV(u).c||l[u->t]) continue;
					VAL at=len[x]+phi[x]+REV(u).w-phi[u->t];
					if(at>=len[u->t]) continue;
					len[u->t]=at;
					now[u->t]=&REV(u);
					q.push(TPL(-at,u->t));
				} 
			}
			for(x=0;x<SIZE;x++) phi[x]+=len[x];
		}while(phi[S]<MAXW&&aug(S,T,can)!=T);
		return in-can;
	}
} net;
int n,m;
long long ans=0;
int u,v,c,f;
int fei[110]={};
int main()
{
	scanf("%d%d",&n,&m);
	net.clear();
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&c,&f);
		fei[u]-=f;
		fei[v]+=f;
		if(f<=c)
		{
			net.add_edge(u,v,c-f,1);
			net.add_edge(u,v,inn,2);
			net.add_edge(v,u,f,1);
		}
		else
		{
			ans+=f-c;
			net.add_edge(v,u,f-c,0);
			net.add_edge(u,v,inn,2);
			net.add_edge(v,u,c,1);
		}
	}
	net.add_edge(n,1,inn,0);
	for(int i=1;i<=n;i++)
	{
		if(fei[i]>0)
		{
			net.add_edge(n+1,i,fei[i],0);
		}
		else net.add_edge(i,n+2,-fei[i],0);
	}
	net.flow(n+1,n+2);
	cout<<ans+net.sum;
	return 0;
}