Codeforces Round #583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)

原题链接：http://codeforces.com/contest/1214

A - Optimal Currency Exchange（暴力/枚举）

#include
using namespace std;

int n,e,d;
int main()
{
	while(~scanf("%d%d%d",&n,&d,&e)){
		e*=5;
		int ans=n;
		for(int i=0;i*e=m||s[x][y]=='#'||vis[x*m+y]||vis[(n-1)*m+m-1])
		return;
	vis[x*m+y]=1;
	dfs(x+1,y);//down
	dfs(x,y+1);//right
}
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		for(int i=0;i>s[i];
		int ans=0;
		memset(vis,0,sizeof(vis));
		dfs(1,0);//down
		if(vis[(n-1)*m+m-1]) ans++;
		vis[(n-1)*m+m-1]=0;
		dfs(0,1);//right
		if(vis[(n-1)*m+m-1]) ans++;
		couty]&b[a])!=b[pre->y]) ans.insert(pii(pre->y, a));
		}
		if(nxt!=s.end()){
			ok++;
			if((b[a]&b[nxt->y])!=b[a]) ans.insert(pii(a, nxt->y));
		}
		if(ok==2){
			if(ans.count(pii(pre->y, nxt->y))) ans.erase(pii(pre->y, nxt->y));
		}}
		if(!ans.empty()){
			int x1=ans.begin()->x, x2=ans.begin()->y;
			if(x1>x2) swap(x1, x2);
			int y1=(b[x1]&(b[x2]^pre[m]))._Find_first();
			int y2=(b[x2]&(b[x1]^pre[m]))._Find_first();
			if(y1>y2) swap(y1, y2);
			printf("%d %d %d %d\n", x1, y1, x2, y2);
		}
		else puts("-1");
	}
	
	return 0;
}

H - Tiles Placement（lca/构造/树）

参考了Eric Sunli Chen.巨巨代码。 题意：给定一棵树，用k个颜色为树上每个点染色，使得任意链长为k的链上结点颜色各不相同。 题解：找出树上直径u–v，直径d，对于树上任意结点i，其要么在直径上，要么在直径的某个点的分支上，令 d u = d i s ( u , i ) , d v = d i s ( v , i ) du=dis(u,i),dv=dis(v,i) du=dis(u,i),dv=dis(v,i)。如果i在u–v直径上，直接按着u–v上染色顺序染色；如果i不在u–v直径上，且此时du>=k&&dv>=k，那么此时i无论染成何种颜色，都会冲突，无解；如果du>=dv，优先将i染色为u链上的颜色，因为i和u链可能构成k长的链；类似，如果dui)u=p[u][i]; if(u==v)return u; for(int i=20;i>=0;i--)if(p[u][i]!=p[v][i])u=p[u][i],v=p[v][i]; return p[u][0]; } int getdist(int u,int v)//u--v结点数 { return deep[u]+deep[v]-deep[getlca(u,v)]*2+1; } int getfar(int u) { int ret=0,d=0; for(int i=1;id){ d=nd; ret=i; } } return ret; } int ans[maxn]; int main() { while(~scanf("%d%d",&n,&k)){ init(); int u,v; for(int i=1;i=dv) ans[i]=du%k;//i和u可能构成k链 else ans[i]=((ans[v]-dv+1)%k+k)%k;//i和v可能构成k链 } if(!flag) puts("No"); else{ puts("Yes"); for(int i=1;i