3/6
这场比赛没什么高手玩啊！！两题就100+，本来是三题的，这评判系统真是*了狗了！！！
╭(╯^╰)╮。
题B 联想专卖店大促销
题意：略
题解：其实是一道简单的贪心题，看着case量还以为要推什么公式，构造一个最优策略→_→，做法就是：如果有机械键盘就优选这个，然后呢，如果u盘大于鼠标的话，那么就优先采用u盘的套餐二，否则就采用套餐一，直到不够机械键盘为止，然后就是剩下两个套餐交替的情况了。
1 /*zhen hao*/
2 #include <bits/stdc++.h>
3 using namespace std; 4
5 #define lson l, m, rt*2
6 #define rson m + 1, r, rt*2+1
7 #define xx first
8 #define yy second
9
10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13
14 int main() { 15 // freopen("case.in", "r", stdin);
16 int T; 17 cin >> T; 18 while (T--) { 19 int a, b, c, res = 0; 20 scanf("%d%d%d", &a, &b, &c); 21 while (c) { 22 if (a < 1 || b < 1) break; 23 a--; b--; c--; res++; 24 if (a > b) { 25 if (a < 2 || b < 1) break; 26 a -= 2; b--; 27 res++; 28 } 29 else { 30 if (a < 1 || b < 2) break; 31 a --; b -= 2; 32 res++; 33 } 34 } 35 int t = min(a, b) / 3; 36 res += t * 2; 37 a -= t * 3; 38 b -= t * 3; 39 if (a >= 1 && b >= 2 || a >= 2 && b >= 1) res++; 40 printf("%d\n", res); 41 } 42 return 0; 43 }
题E 微信钱包付款
题意：略
题解：推一下就可以发现规律，只要所有数值加起来可以被3整除，就说明存在一种方案，否则没有。方案采用给出来的数除以3即可。懒得写大数，直接开java。
1 import java.math.BigInteger; 2 import java.util.Scanner; 3
4 public class Main { 5
6 public static void main(String args[]) { 7 String s = new String(); 8 Scanner in = new Scanner(System.in); 9 s = in.next(); 10 int sum = 0; 11 for (int i = 0; i < s.length(); i++) { 12 sum += s.charAt(i) - '0'; 13 } 14 if (sum % 3 != 0) { 15 System.out.println("-1"); 16 } else { 17 BigInteger b = new BigInteger(s); 18 b = b.divide(new BigInteger("3")); 19 System.out.println(b + " " + b + " " + b); 20 } 21 } 22
23 }
题F 菜鸟物流的运输网络
题意：略
题解：一道经典的网络流题目，具体可以看紫书网络流专题。原题是求两条不交叉的路使得路径的和最大，这里是找出一条这样的路即可。构图方法是建立一个超级源点s，然后s连到a和b，然后汇点设为mid，除了mid的其他点都拆成两个点，然后输出路径即可。我因为数组开小了没过这道题，明明是re却显示答案错误，mdzz。只能说这网站做得太简陋了，应该直接跳到另外一个页面给我们看结果的。。。。。。
1 /*zhen hao*/
2 #include <bits/stdc++.h>
3 using namespace std; 4
5 const int maxn = 410; 6 const int inf = 1e9; 7
8 struct Edge { 9 int from, to, cap, flow; 10 }; 11
12 struct EK { 13 int n, m; 14 vector<Edge> edges; 15 vector<int> G[maxn]; 16 int a[maxn]; 17 int p[maxn]; 18
19 void init(int n) { 20 for (int i = 0; i < n; i++) G[i].clear(); 21 edges.clear(); 22 } 23
24 void add_edge(int u, int v, int cap) { 25 edges.push_back((Edge){u, v, cap, 0}); 26 edges.push_back((Edge){v, u, 0, 0}); 27 m = edges.size(); 28 G[u].push_back(m - 2); 29 G[v].push_back(m - 1); 30 } 31
32 int max_flow(int s, int t) { 33 int flow = 0; 34 for (;;) { 35 memset(a, 0, sizeof a); 36 queue<int> Q; 37 Q.push(s); 38 a[s] = inf; 39 while (!Q.empty()) { 40 int x = Q.front(); Q.pop(); 41 for (int i = 0; i < (int)G[x].size(); i++) { 42 Edge& e = edges[G[x][i]]; 43 if (!a[e.to] && e.cap > e.flow) { 44 p[e.to] = G[x][i]; 45 a[e.to] = min(a[x], e.cap - e.flow); 46 Q.push(e.to); 47 } 48 } 49 if (a[t]) break; 50 } 51 if (!a[t]) break; 52 for (int u = t; u != s; u = edges[p[u]].from) { 53 edges[p[u]].flow += a[t]; 54 edges[p[u] ^ 1].flow -= a[t]; 55 } 56 flow += a[t]; 57 } 58 return flow; 59 } 60 }; 61
62 EK ek; 63
64 vector<int> ans; 65
66 void dfs(int u, int t, int n) { 67 if (u >= 1 && u <= n) ans.push_back(u); 68 if (u == t) return; 69 for (int i = 0; i < (int)ek.G[u].size(); i++) { 70 Edge& e = ek.edges[ek.G[u][i]]; 71 // cout << e.flow << ' ' << e.cap << ' ' << e.from << ' ' << e.to << endl;
72 if (e.cap > 0 && e.flow == e.cap) { 73 dfs(e.to, t, n); break; 74 } 75 } 76 } 77
78 int main() { 79 // freopen("case.in", "r", stdin);
80 int T; 81 cin >> T; 82 while (T--) { 83 int n, m, a, b, mid; 84 scanf("%d%d", &n, &m); 85 scanf("%d%d%d", &a, &b, &mid); 86 ek.init(2 * n + 1); 87 for (int i = 0; i < m; i++) { 88 int u, v; 89 scanf("%d%d", &u, &v); 90 ek.add_edge(u + n, v, 1); 91 ek.add_edge(v + n, u, 1); 92 } 93 for (int i = 1; i <= n; i++) { 94 if (i != mid) 95 ek.add_edge(i, i + n, 1); 96 } 97 int src = 0, end = mid; 98 ek.add_edge(src, a, 1); 99 ek.add_edge(src, b, 1); 100 // cout << ek.max_flow(src, end) << endl;
101 ek.max_flow(src, end); 102 ans.clear(); 103 dfs(a, mid, n); 104 printf("%d", a); 105 for (int i = 1; i < (int)ans.size(); i++) printf(" %d", ans[i]); 106 ans.clear(); 107 dfs(b, mid, n); 108 for (int i = ans.size() - 2; i >= 0; i--) printf(" %d", ans[i]); 109 puts(""); 110 } 111 return 0; 112 }