2017ACM省赛选拔赛题解

Problem A: 聪明的田鼠

题解：

dp[k][i]表示走了k步，且在第i行的最大值

最后的结果就是走了n+m-2步，且在第n行的值

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 60;
30 // head
31  
32 int n, m;
33 int a[MAXN][MAXN];
34 int dp[MAXN * 2][MAXN];
35  
36 int main() {
37     cin >> n >> m;
38     rep(i, 1, n + 1) rep(j, 1, m + 1) cin >> a[i][j];
39     dp[0][1] = a[1][1];
40     rep(k, 1, n + m - 1) rep(i, max(1, k + 2 - m), n + 1) if (i <= k + 1)
41         dp[k][i] = max(dp[k - 1][i], dp[k - 1][i - 1]) + a[i][k + 2 - i];
42     cout << dp[n + m - 2][n] << endl;
43     return 0;
44 }

Problem B: 软件安装

题解：

线段树区间更新，区间查询

代码：

  1 #include <map>
  2 #include <set>
  3 #include <cmath>
  4 #include <queue>
  5 #include <stack>
  6 #include <cstdio>
  7 #include <string>
  8 #include <vector>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <sstream>
 12 #include <iostream>
 13 #include <algorithm>
 14 #include <functional>
 15 using namespace std;
 16 #define rep(i,a,n) for (int i=a;i<n;i++)
 17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
 18 #define all(x) (x).begin(),(x).end()
 19 #define pb push_back
 20 #define mp make_pair
 21 #define lson l,m,rt<<1  
 22 #define rson m+1,r,rt<<1|1 
 23 typedef long long ll;
 24 typedef vector<int> VI;
 25 typedef pair<int, int> PII;
 26 const ll MOD = 1e9 + 7;
 27 const int INF = 0x3f3f3f3f;
 28 const int MAXN = 5e4 + 7;
 29 // head
 30 
 31 int cover[MAXN << 2];
 32 int lsum[MAXN << 2], rsum[MAXN << 2], msum[MAXN << 2];
 33 
 34 void pushup(int rt, int m) {
 35     lsum[rt] = lsum[rt << 1], rsum[rt] = rsum[rt << 1 | 1];
 36     if (lsum[rt << 1] == m - (m >> 1)) lsum[rt] += lsum[rt << 1 | 1];
 37     if (rsum[rt << 1 | 1] == m >> 1) rsum[rt] += rsum[rt << 1];
 38     msum[rt] = max(max(msum[rt << 1], msum[rt << 1 | 1]), rsum[rt << 1] + lsum[rt << 1 | 1]);
 39 }
 40 
 41 void pushdown(int rt, int m) {
 42     if (cover[rt] != -1) {
 43         cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
 44         lsum[rt << 1] = rsum[rt << 1] = msum[rt << 1] = (cover[rt] ? 0 : m - (m >> 1));
 45         lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = msum[rt << 1 | 1] = (cover[rt] ? 0 : m >> 1);
 46         cover[rt] = -1;
 47     }
 48 }
 49 
 50 void build(int l, int r, int rt) {
 51     cover[rt] = -1;
 52     lsum[rt] = rsum[rt] = msum[rt] = r - l + 1;
 53     if (l == r) return;
 54     int m = (l + r) >> 1;
 55     build(lson);
 56     build(rson);
 57 }
 58 
 59 void update(int L, int R, int x, int l, int r, int rt) {
 60     if (L <= l && r <= R) {
 61         cover[rt] = x;
 62         lsum[rt] = rsum[rt] = msum[rt] = (x ? 0 : r - l + 1);
 63         return;
 64     } 
 65     pushdown(rt, r - l + 1);
 66     int m = (l + r) >> 1;
 67     if (L <= m) update(L, R, x, lson);    
 68     if (R > m) update(L, R, x, rson);
 69     pushup(rt, r - l + 1);
 70 }
 71 
 72 int query(int x, int l, int r, int rt) {
 73     if (l == r) return l;
 74     pushdown(rt, r - l + 1);
 75     int m = (l + r) >> 1;
 76     if (msum[rt << 1] >= x) return query(x, lson);
 77     else if (rsum[rt << 1] + lsum[rt << 1 | 1] >= x) return m - rsum[rt << 1] + 1;
 78     else query(x, rson);
 79 }
 80 
 81 int main() {
 82     int n, m;
 83     cin >> n >> m;
 84     build(1, n, 1);
 85     while (m--) {
 86         int a, b, c;
 87         scanf("%d", &a);
 88         if (a == 1) {
 89             scanf("%d", &b);
 90             if (msum[1] < b) {
 91                 puts("0");
 92                 continue;
 93             }
 94             int ans = query(b, 1, n, 1);
 95             printf("%d
", ans);
 96             update(ans, ans + b - 1, 1, 1, n, 1);
 97         }
 98         else {
 99             scanf("%d%d",&b, &c);
100             update(b, b + c - 1, 0, 1, n, 1);
101         }
102     }
103     return 0;
104 }

Problem C: V型积木

题解：

最长上升子序列，枚举每个最为最低点，分别求左右两边的LIS，复杂度n³

不过学长说可以用树状数组，nlogn就能解决，万能的树状数组。。

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 110;
30 // head
31  
32 int n;
33 int a[MAXN];
34 int dp[MAXN];
35  
36 int main() {
37     int T;
38     cin >> T;
39     while (T--) {
40         cin >> n;
41         rep(i, 0, n) scanf("%d", a + i);
42         int ans = 0;
43         rep(k, 0, n) {
44             memset(dp, 0, sizeof(dp));
45             int sum = 0, t = 0;
46             per(i, 0, k) rep(j, i + 1, k + 1) if (a[i] > a[j]) 
47                 dp[i] = max(dp[i], dp[j] + 1), t = max(t, dp[i]);
48             if (t == 0) continue;
49             sum += t;
50             t = 0;
51             rep(i, k + 1, n) rep(j, k, i) if (a[i] > a[j]) 
52                 dp[i] = max(dp[i], dp[j] + 1), t = max(t, dp[i]);
53             if (t == 0) continue;
54             sum += t;
55             ans = max(ans, sum + 1);
56         }
57         if (ans == 0) cout << "No Solution" << endl;
58         else cout << n - ans << endl;
59     }
60     return 0;
61 }

Problem D: 最佳地址

题解：

最小费用流，建立一个超级源点s和超级汇点t

coal0表示原有的发电厂，coal1表示当前要新建的发电厂

从s到coal0连一条流量为b，费用为0的边

从s到coal1连一条流量为sum-b，费用为0的边因为题目说了全部供应，所以剩下的所有煤矿都要供应到新发电厂

然后coal0和coal1都分别和每个煤矿相连，流量就是煤矿的产量a[i]，费用就是c[0][i]和c[1][i]

最后每个煤矿再连接到t，流量为a[i]，费用为0

然后跑一下最小费用流就可以了

点的标号分别为0-m-1为煤矿 m为coal0 m+1为coal1 m+2为s m+3为t 一共m+4个点

代码：

  1 #include <map>
  2 #include <set>
  3 #include <cmath>
  4 #include <queue>
  5 #include <stack>
  6 #include <cstdio>
  7 #include <string>
  8 #include <vector>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <sstream>
 12 #include <iostream>
 13 #include <algorithm>
 14 #include <functional>
 15 using namespace std;
 16 #define rep(i,a,n) for (int i=a;i<n;i++)
 17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
 18 #define pb push_back
 19 #define mp make_pair
 20 #define all(x) (x).begin(),(x).end()
 21 #define SZ(x) ((int)(x).size())
 22 typedef vector<int> VI;
 23 typedef long long ll;
 24 typedef pair<int, int> PII;
 25 const ll MOD = 1e9 + 7;
 26 const int INF = 0x3f3f3f3f;
 27 const double EPS = 1e-10;
 28 const double PI = acos(-1.0);
 29 const int MAXN = 110;   //看了测试数据，m和n最大不超过100
 30 // head
 31  
 32 int n, b, m, H;
 33 int a[MAXN];
 34 int h[MAXN];
 35 int c[MAXN][MAXN];
 36  
 37 struct edge { int to, cap, cost, rev; };
 38 const int MAX_V = 1e4 + 7;
 39 int V;
 40 vector<edge> G[MAX_V];
 41 int dist[MAX_V];
 42 int prevv[MAX_V], preve[MAX_V];
 43  
 44 void add_edge(int from, int to, int cap, int cost) {
 45     G[from].pb(edge{ to,cap,cost,(int)G[to].size() });
 46     G[to].pb(edge{ from,0,-cost,(int)G[from].size() - 1 });
 47 }
 48  
 49 int min_cost_flow(int s, int t, int f) {
 50     int res = 0;
 51     while (f > 0) {
 52         memset(dist, 0x3f, sizeof(dist));
 53         dist[s] = 0;
 54         bool update = true;
 55         while (update) {
 56             update = false;
 57             rep(v, 0, V) {
 58                 if (dist[v] == INF) continue;
 59                 rep(i, 0, G[v].size()) {
 60                     edge &e = G[v][i];
 61                     if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
 62                         dist[e.to] = dist[v] + e.cost;
 63                         prevv[e.to] = v;
 64                         preve[e.to] = i;
 65                         update = true;
 66                     }
 67                 }
 68             }
 69         }
 70         if (dist[t] == INF) return -1;
 71         int d = f;
 72         for (int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap);
 73         f -= d;
 74         res += d*dist[t];
 75         for (int v = t; v != s; v = prevv[v]) {
 76             edge &e = G[prevv[v]][preve[v]];
 77             e.cap -= d;
 78             G[v][e.rev].cap += d;
 79         }
 80     }
 81     return res;
 82 }
 83  
 84 int main() {
 85     int T;
 86     cin >> T;
 87     while (T--) {
 88         cin >> m >> b >> H >> n;
 89         int sum = 0;
 90         rep(i, 0, m) scanf("%d", a + i), sum += a[i];
 91         rep(i, 0, n) scanf("%d", h + i);
 92         rep(i, 0, m) scanf("%d", &c[0][i]);
 93         PII ans = mp(0, INF);
 94         rep(k, 0, n) {
 95             rep(i, 0, MAX_V) G[i].clear();
 96             rep(i, 0, m) scanf("%d", &c[1][i]);
 97             int coal0 = m, coal1 = m + 1, s = m + 2, t = m + 3;
 98             V = m + 4;
 99             add_edge(s, coal0, b, 0);
100             add_edge(s, coal1, sum - b, 0);
101             rep(i, 0, m) {
102                 add_edge(coal0, i, a[i], c[0][i]);
103                 add_edge(coal1, i, a[i], c[1][i]);
104                 add_edge(i, t, a[i], 0);
105             }
106             int mcf = min_cost_flow(s, t, sum) + H + h[k];
107             if (mcf < ans.second) ans.second = mcf, ans.first = k;
108         }
109         cout << ans.first + 1 << ' ' << ans.second << endl;
110     }
111     return 0;
112 }

Problem E: 寻宝

题解：

从0点(题目中的1，习惯从0开始，所以全都-1计算）跑一下改进版dijkstra

当然求的不是最短路，d[i]表示从0到i的所有路线中每条路线中的权重最小的值的最大值

这个只要稍微修改一下就好了

c[i]存的就是有c[i]个宝藏地点可以携带i个宝藏到达那里，因为最多有k个宝藏，所以超过k的也按k算

最后贪心模拟一下就好了

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 8010;
30 // head
31  
32 const int MAX_V = MAXN;
33 struct edge { int to, cost; };
34 vector<edge> G[MAX_V];
35 int d[MAX_V];
36 int V;
37  
38 void dijkstra() {
39     priority_queue<PII, vector<PII>, greater<PII> > que;
40     d[0] = INF;
41     que.push(PII(INF, 0));
42  
43     while (!que.empty()) {
44         PII p = que.top(); que.pop();
45         int v = p.second;
46         if (d[v] > p.first) continue;
47         rep(i, 0, G[v].size()) {
48             edge e = G[v][i];
49             if (d[e.to] < min(d[v], e.cost)) {
50                 d[e.to] = min(d[v], e.cost);
51                 que.push(PII(d[e.to], e.to));
52             }
53         }
54     }
55 }
56  
57 int n, m, k, w;
58 int a[MAXN], c[MAXN];
59  
60 int main() {
61     scanf("%d%d%d%d", &n, &m, &k, &w);
62     V = n;
63     rep(i, 0, k) {
64         int t;
65         scanf("%d", &t);
66         a[--t] = 1;
67     }
68     while (m--) {
69         int x, y, z;
70         scanf("%d%d%d", &x, &y, &z);
71         x--, y--;
72         G[x].pb(edge{ y,z });
73         G[y].pb(edge{ x,z });
74     }
75     dijkstra();
76     rep(i, 0, n) if (a[i]) c[min(d[i] / w, k)]++;
77     int sum = 0, sur = 0, ans = k;
78     per(i, 1, k + 1) {
79         if (c[i]) sur += c[i] - 1;
80         else if (sur) sur--;
81         else ans--;
82     }
83     cout << ans << endl;
84     return 0;
85 }