【BZOJ 3033】太鼓达人

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3033
神犇题解:http://blog.csdn.net/clover_hxy/article/details/56003661

解题报告

这个东西,看一看样例,感觉答案是$2^k$,然后写一发无脑贪心就过了

不过这题的证明非常妙妙啊:

考虑将每一个$0 \sim 2^{k+1}-1$的数看成一个点,标号为这个数
把在这个数末尾或者开头加$0/1$看作边
那么每个点度数恰好为$4$,并且整个图显然连通
那么这图显然存在欧拉回路,那么就能够一笔画

于是在这个图上贪心走就可以了

Code

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

const int N = 3000;

int n,k,arr[N];
set<int> S;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int get(int p) {
	int ret = 0;
	for (int i=0;i<k;i++) ret += (1 << i) * arr[p + i];
	return ret; 
}

int main() {
	k = read(); n = 1 << k;
	for (int i=1;i<=k;i++) arr[i] = 0; S.insert(0);
	for (int i=n;i>n-k;i--) arr[i] = 1, S.insert(get(i));
	for (int i=2;i<=n-k;i++) {
		if (S.count(get(i))) arr[i+k-1] = 1;
		S.insert(get(i));
	}
	printf("%d ",n);
	for (int i=1;i<=n;i++) printf("%d",arr[i]);
	return 0;
}

【Codeforces 723E】One-Way Reform

题目传送门:http://codeforces.com/contest/723/problem/E
官方题解:http://codeforces.com/blog/entry/47502

出度与入度相等 => 欧拉回路
有度数为偶数的点 => 两两配对之后加一条边
此时所有点的度数都为偶数,每一个连通子图存在欧拉回路
于是可以用随便定向,只有用网络流来的得出可行解

现在唯一的问题就是证明度数为奇数的点一定是偶数对了:
一条边贡献两个度 => 总度数为偶数
若度数为奇数的点有奇数个 => 总度数为奇数
矛盾 => 度数为奇数的点不可能有奇数个

【BZOJ 2095】[Poi2010] Bridges

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2095

这个题目啊!瞄一眼就知道是二分吧?
接下来就是给你一些有向边&无向边,让你判断是否存在欧拉回路

对于有向边,没有悬念,直接记录对于出度入度的贡献
只与有向边嘛,不妨先随便定一个向,然后考虑使用网络流进行调整
具体细节可以参见:http://blog.csdn.net/wzq_qwq/article/details/48651379

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT; 
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v, int f) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
} 

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(0);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
			dis[to[i]] = dis[w] + 1;
			que.push(to[i]);
		}
	}
	
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) {
		return f;
	} else {
		int ret = 0;
		for (int &i=cur[w],tmp;i && f;i=nxt[i]) { 
			if (dis[to[i]] == dis[w] + 1) {
				tmp = DFS(to[i], min(f, flow[i]));
				ret += tmp; f -= tmp;
				flow[i] -= tmp; flow[i^1] += tmp;
			}
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

inline bool judge(int lim){
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(head,0,sizeof(head));
	S = 0; T = N - 1; TT = 1;
	int tot = 0;
	
	for (int i=1;i<=m;i++) {
		if (lim < edge[i].w1) {
			continue;
		} else if (lim < edge[i].w2) {
			in[edge[i].v]++;
			out[edge[i].u]++;
		} else {
			in[edge[i].v]++;
			out[edge[i].u]++;
			Add_Edge(edge[i].u, edge[i].v, 2);
		}
	}
	
	for (int i=1;i<=n;i++) {
		if (abs(in[i]-out[i]) & 1) {
			return false;
		} else if (in[i] < out[i]) {
			Add_Edge(S,i,out[i]-in[i]);	
			tot += out[i] - in[i];
		} else if (in[i] > out[i]) {
			Add_Edge(i,T,in[i]-out[i]);
		}
	}
	
	return Dinic() == tot;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w1 = read();	
		edge[i].w2 = read();
		if (edge[i].w1 > edge[i].w2) {
			swap(edge[i].w1, edge[i].w2);
			swap(edge[i].u, edge[i].v);
		}
		MX = max(MX, edge[i].w2);
		MN = min(MN, edge[i].w1);
	}
	
	int l = MN, r = MX, mid, ret = -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	if (~ret) printf("%d\n",ret);
	else puts("NIE");
	return 0;
}