20180810 提高 练习赛

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

inline int rd(){int ch,ret,nag=0;while(!isdigit(ch=getchar()))nag=ch==‘-‘;ret=ch-‘0‘;while(isdigit(ch=getchar()))ret=ret*10+ch-‘0‘;return nag?-ret:ret;}

struct Point {
	int x, y, id;
	inline bool operator< (const Point & res) const {
		return x == res.x ? y < res.y : x < res.x;
	}
	inline void rd(int i) {
		x = ::rd(); y = ::rd(); id = i;
	}
} a[100005];

int main() {
	int n = rd();
	for (int i = 0; i < n; i++) a[i].rd(i);
	sort(a, a+n);
	for (int i = 0; i < 6; i++) printf(i == 5 ? "%d" : "%d ", a[i].id+1);
	puts("");
	return 0;
}

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

int n, m, q, a[1005][1005], dp[1005][1005];
bool vis[1005][1005];

const int INF = 0x3f3f3f3f;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int dfs(int x, int y) {
	if (vis[x][y]) return dp[x][y];
	int ans = 0;
	for (int i=0; i<4; i++) {
		int nx = dx[i] + x, ny = dy[i] + y;
		if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
		if (a[nx][ny] < a[x][y]) continue;
		if (a[nx][ny] == a[x][y]) { ans = INF; break; }
		ans = max(ans, dfs(nx, ny) + 1);
	}
	return dp[x][y] = ans;
}

int main() {
	// freopen("nagame.in", "r",stdin);
	// freopen("nagame.out", "w",stdout);
	scanf("%d%d", &n,&m);
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf("%d", &a[i][j]);
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (!vis[i][j]) dfs(i, j);
	scanf("%d", &q);
	while(q--) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		printf("%s\n", dp[x][y]>=z ? "= =" : "> <");
	}
	return 0;
}

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

inline int rd(){int ch,ret,nag=0;while(!isdigit(ch=getchar()))nag=ch==‘-‘;ret=ch-‘0‘;while(isdigit(ch=getchar()))ret=ret*10+ch-‘0‘;return nag?-ret:ret;}

int n, m, e=0, ans1=0, ans0=0, hed[100005], use[100005], spn[100005];
struct edge {
	int to, nxt;
} edges[200005];
struct rawedge {
	int x, y;
	inline void rd() { x = ::rd(); y = ::rd(); }
} A[200005];
struct UnionSet {
	int fa[100005];
	void I(int n) {
		for (int i=1; i<=n; i++) fa[i] = i;
	}
	int f(int x) {
		return fa[x] = (x == fa[x] ? x : f(fa[x]));
	}
	void u(int x, int y) {
		x = f(x), y = f(y);
		if (x == y) return;
		fa[x] = y;
	}
} S;
const int P = 1000000007;
int dp[100005][2], color[100005];
vector<int> U;

inline void addedge(int x, int y) {
	edges[e] = (edge){y, hed[x]};
	hed[x] = e++;
}
void findGenerateTree() {
	S.I(n);
	for (int i=1; i<=m; i++) if (S.f(A[i].x) != S.f(A[i].y)) {
		use[i] = 1, S.u(A[i].x, A[i].y), addedge(A[i].x, A[i].y), addedge(A[i].y, A[i].x);
	}
}
void dfs(int x, int fa) {
	dp[x][0] = dp[x][1] = 1;
	for (int e=hed[x]; e!=-1; e=edges[e].nxt) {
		int y = edges[e].to;
		if (y != fa) {
			dfs(y, x);
			dp[x][0] = 1ll * dp[x][0] * (dp[y][0] + dp[y][1]) % P;
			dp[x][1] = 1ll * dp[x][1] * dp[y][0] % P;
		}
	}
	if (spn[x] == 1) dp[x][1] = 0;
	else if (spn[x] == 2) dp[x][0] = 0;
}

int main() {
	// freopen("akekure.in", "r",stdin);
	// freopen("akekure.out", "w",stdout);
	n = rd(); m = rd();
	for (int i=1; i<=n; i++) hed[i] = -1;
	for (int i=1; i<=m; i++) A[i].rd();
	findGenerateTree();
	int ans = 0;
	for (int i=1; i<=m; i++) if (!use[i]) U.push_back(i);
	assert(U.size() == (m - n + 1));
	for (int i=0; i<(1 << (m - n + 1)); i++) {
		memset(spn, 0, sizeof(spn));
		bool fail = 0;
		for (int j=0; j<U.size(); j++) if (i & (1 << j)) {
			if (spn[A[U[j]].x] > 1) { fail = 1; break; }
			spn[A[U[j]].x] = 1;
		} else {
			if (spn[A[U[j]].x] == 1 || spn[A[U[j]].y] > 1) { fail = 1; break; }
			spn[A[U[j]].x] = 2;
			spn[A[U[j]].y] = 1;
		}
		if (fail) continue;
		dfs(1, 0);
		(ans += (dp[1][0] + dp[1][1]) % P) %= P;
	}
	printf("%d\n", ans);
	return 0;
}