Problem A: Playing with Dice (378A)
题目大意：两个人猜数1~6，给出a和b，然后随机丢一个色子，问说接近a的可能，相等的可能，以及接近b的可能。
解题思路：完完全全的签到题。
#include#include #include int main() { int a, b; int x = 0, y = 0, z = 0; scanf("%d%d", &a, &b); for (int i = 1; i <= 6; i++) { if (abs(i - a) > abs(i - b)) z++; else if (abs(i - a) == abs(i - b)) y++; else x++; } printf("%d %d %d\n", x, y, z); return 0; }
Problem B: Semifinals (378B)
题目大意：有两场半决赛，每场各有n各人参加，现在有一个k值，表示说半决赛的前k名可以直接晋级总决赛，因为要选出n个人参加决赛，所以2*（n -k）要在剩下的人中选前2*（n-k)名，k的取值范围为0~n/2，问说那些人是有可能晋级决赛的。
解题思路：直接按照k = 0和k = n / 2的方案去选，就包括了所有可以晋级的人选，两种极端。
#include#include const int N = 100005; int n, a[N], b[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]); int p = 0, q = 0, k = n / 2; for (int i = 0; i < n; i++) { if (a[p] < b[q]) p++; else q++; } for (int i = 0; i < n; i++) { if (i < p || i < k) printf("1"); else printf("0"); } printf("\n"); for (int i = 0; i < n; i++) { if (i < q || i < k) printf("1"); else printf("0"); } printf("\n"); return 0; }
Problem C: Maze (377A)
题目大意：给出一张图，将k个位置置为X，使得剩下的空位置仍能联通。
解题思路：暴力。因为题目肯定保证有答案，所以水了很多，但是它可能一开始就有不连通的块，所以先用BFS找出所有的联通块，然后按照面积从小到大排序，用DFS进行填充。
#include#include #include #include using namespace std; const int N = 505; const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; int n, r, l, k, v[N][N]; char g[N][N]; void init() { scanf("%d%d%d", &r, &l, &k); n = 0; memset(v, 0, sizeof(v)); for (int i = 0; i < r; i++) scanf("%s", g[i]); } void dfs(int x, int y) { for (int i = 0; i < 4; i++) { int a = x + dir[i][0], b = y + dir[i][1]; if (a < 0 || a >= r || b < 0 || b >= l) continue; if (v[a][b] || g[a][b] == '#') continue; v[a][b] = 1; dfs(a, b); } if (k) { k--; v[x][y] = 2; } } int main() { init(); for (int i = 0; i < r; i++) { for (int j = 0; j < l; j++) if (v[i][j] == 0 && g[i][j] == '.') { dfs(i, j); } } for (int i = 0; i < r; i++) { for (int j = 0; j < l; j++) { if (v[i][j] == 2) printf("X"); else printf("%c", g[i][j]); } printf("\n"); } return 0; }
Problem D: Preparing for the Contest (377B)
题目大意：有n个人，m个病毒，s张通行证，然后给出m个病毒的等级，n个人的等级，以及n个人去杀病毒所需要的通行证数量，问所最少花费几天可以杀光病毒，并输出每个病毒被那一个人所清理。PS：人要杀病毒必须等级大于等于病毒，一个人只需支付一次通行证。
解题思路：二分+贪心+优先队列。二分天数，贪心判断，每次用可以杀除当前最高等级病毒中通行证所需最少的。杀mid个大的病毒，优先队列进行优化。
#include#include #include #include using namespace std; const int N = 100005; struct state { int id, val, pass; friend bool operator <(const state& a, const state& b) { return a.pass > b.pass; } }p[N], bug[N]; int n, m, s; bool cmp(const state& a, const state& b) { return a.val > b.val; } void init() { scanf("%d%d%d", &n, &m, &s); for (int i = 0; i < m; i++) { scanf("%d", &bug[i].val); bug[i].id = i; } for (int i = 0; i < n; i++) scanf("%d", &p[i].val); for (int i = 0; i < n; i++) { scanf("%d", &p[i].pass); p[i].id = i; } sort(p, p + n, cmp); sort(bug, bug + m, cmp); } bool judge(int k) { int a = 0, b = 0, sum = s; priority_queue que; while (b < m) { while (a < n) { if (p[a].val >= bug[b].val) que.push(p[a]); else break; a++; } if (que.empty()) return false; state c = que.top(); que.pop(); if (sum < c.pass) return false; sum -= c.pass; b += k; } return true; } void put(int k) { int a = 0, b = 0; int ans[N]; priority_queue que; while (b < m) { while (a < n) { if (p[a].val >= bug[b].val) que.push(p[a]); else break; a++; } state c = que.top(); que.pop(); int t = min(m, b + k); for (int i = b; i < t; i++) ans[bug[i].id] = c.id + 1; b += k; } printf("%d", ans[0]); for (int i = 1; i < m; i++) printf(" %d", ans[i]); printf("\n"); } void solve() { if (!judge(m)) { printf("NO\n"); return; } int l = 0, r = m; while (l < r) { int mid = (l + r) / 2; if (judge(mid)) r = mid; else l = mid + 1; } printf("YES\n"); put(r); } int main() { init(); solve(); return 0; }
Problem E: Captains Mode (377C)
题目大意：dota2游戏选择英雄，先给出n个英雄的力量值，然后给出m个操作，p/b num，p代表第num个玩家可以选择一个英雄，b 代表第num个玩家可以封掉一个英雄，即谁都不可以选，然后两队选完之后，比较说两队英雄总力量值的差，两人都按照最优方案去选择。
解题思路：dp+位运算+贪心。首先选择英雄的时候，肯定是选择能量值最大的。其次m<= 20，也就是说不管是p还b，最多也就操作到20个英雄，所以将英雄按照力量值从大到小排序，选20个进行处理即可。
然后最多20个英雄，就可以用一个二进制数来表示，1表示不可选，0表示可选。碰到玩家1选择就加上能力值最大的英雄，玩家2选就剪掉能力值最大的英雄。如果碰到封除英雄，如果玩家1封，就要选策略中尽量大的，如果玩家2选，就要选择尽量小的。
#include#include #include using namespace std; const int N = (1 << 20) + 5; const int M = 105; const int INF = 0x3f3f3f3f; int n, m, v[N], h[M], order[M][2], rec[N]; bool cmp(const int& a, const int& b) { return a > b; } void init() { memset(v, 0, sizeof(v)); char ch; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &h[i]); sort(h, h + n, cmp); scanf("%d%*c", &m); for (int i = 0; i < m; i++) { scanf("%c %d%*c", &ch, &order[i][0]); order[i][1] = (ch == 'p' 1 : 0); } n = min(n, 20); } int dp(int s, int d) { if (v[s]) return rec[s]; if (d >= m) return 0; int& ans = rec[s]; v[s] = 1; ans = 0; while (d < m) { if (order[d][1]) { int id; for (id = 0; id < n; id++) if ((s & (1 << id)) == 0) break; s += (1 << id); order[d][0] == 1 ans += h[id] : ans -= h[id]; } else { int tmp = order[d][0] == 1 -INF : INF; for (int i = 0; i < n; i++) if ((s & (1 << i)) == 0) { int t = dp(s + (1 << i), d+1); if (order[d][0] == 1) tmp = max(tmp, t); else tmp = min(tmp, t); } ans += tmp; break; } d++; } return ans; } int main () { init(); printf("%d\n", dp(0, 0)); return 0; }