首页 > 代码库 > UVALive 4887 Soccer 状压+模拟
UVALive 4887 Soccer 状压+模拟
题目链接:点击打开链接
题意:n个球队,m场比赛
下面n行表示n个球队的名字。
下面m场比赛表示该场比赛的2个队得分。
-1表示我们可以任意填。
这种任意填的比赛场数不超过12场。
求:
胜一场球队得2分,平得1分,败得0分。
求每个球队最好名次与最差名字。
每场只有3个状态,最多只有12场,所以状压一下,3^12个状态。
#include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <map> #include <vector> #include <iostream> using namespace std; const int N = 20 + 2; map<string, int> id; vector<int> 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; }
UVALive 4887 Soccer 状压+模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。