程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVALive 4887 Soccer 狀壓+模擬

UVALive 4887 Soccer 狀壓+模擬

編輯：C++入門知識

UVALive 4887 Soccer 狀壓+模擬

題目鏈接：點擊打開鏈接

題意：n個球隊，m場比賽

下面n行表示n個球隊的名字。

下面m場比賽表示該場比賽的2個隊得分。

-1表示我們可以任意填。

這種任意填的比賽場數不超過12場。

求：

勝一場球隊得2分，平得1分，敗得0分。

求每個球隊最好名次與最差名字。

每場只有3個狀態，最多只有12場，所以狀壓一下，3^12個狀態。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 20 + 2;

map id;
vector l, r;
char s[200], ss[200];

int n;
int base[N], tob[N], put[N], rank[N];
int mx[N], mi[N];
string name[N];

bool cmp(int x, int y) {
	return tob[x] > tob[y];	
}

void upmx(int& z, int x) {
	if (z == -1)
		z = x;
	else if (z < x)
		z = x;
}

void upmi(int& z, int x) {
	if (z == -1)
		z = x;
	else if (z > x)
		z = x;	
}

void dfs(int dep) {
	if (dep == l.size()) {
		for (int i = 1; i <= n; ++i) {
			rank[i] = i;
			tob[i] = base[i];
		}
		for (int i = 0; i < l.size(); ++i) {
			if (put[i] == 0) {
				++ tob[l[i]];
				++ tob[r[i]];
			} else if (put[i] == 1) {
				tob[l[i]] += 3;
			} else 
				tob[r[i]] += 3;
		}
		sort(rank + 1, rank + 1 + n, cmp);
		int cur = 1;
		upmx(mx[rank[1]], 1);
		upmi(mi[rank[1]], 1);
		for (int i = 2; i <= n; ++i) {
			if (tob[rank[i]] != tob[rank[i - 1]])
				cur = i;
			upmx(mx[rank[i]], cur);
			upmi(mi[rank[i]], cur);
		}
	} else {
		put[dep] = 0;
		dfs(dep + 1);
		put[dep] = 1;
		dfs(dep + 1);
		put[dep] = 2;
		dfs(dep + 1);
	}
}

void pu(int x) {
	if (x == 1)
		printf("1st");
	else if (x == 2) {
		printf("2nd");
	} else if (x == 3) {
		printf("3rd");
	} else {
		printf("%dth", x);
	}
}

int main() {
	int m, a, b, x, y, len, cas = 0;
	while (~scanf("%d%d", &n, &m)) {
		if (0 == n && 0 == m)
			break;
		if (cas == 0)
			cas = 1;
		else
			puts("");
		id.clear();
		for (int i = 1; i <= n; ++i) {
			cin >> name[i];
			id[name[i]] = i;
		}
		
		memset(base, 0, sizeof base);
		l.clear();
		r.clear();
		while (m -- > 0) {
			scanf("%s vs %s %d %d", s, ss, &a, &b);
			len = strlen(ss);
			ss[--len] = '\0';
			x = id[s];
			y = id[ss];
			if (a == -1) {
				l.push_back(x);
				r.push_back(y);
			} else {
				if (a == b) {
					++ base[x];
					++ base[y];
				} else if (a > b)
					base[x] += 3;
				else if (b > a)
					base[y] += 3;
			}
		}
		
		memset(mx, -1, sizeof mx);
		memset(mi, -1, sizeof mi);
		dfs(0);
		for (int i = 1; i <= n; ++i) {
			printf("Team ");
			cout << name[i];
			printf(" can finish as high as ");
			pu(mi[i]);
			printf(" place and as low as ");
			pu(mx[i]);
			puts(" place.");
		}
	}
	return 0;
}