题目链接：点击打开链接
题意：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; }