RCC 2014 Warmup (Div. 2) 解题报告

题意：给n个球队，每个球队之间只能有一场比赛。要求构造一个每个球队只胜k场。

思路：直接暴力，标记一下就可以了。

代码如下：

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-04-17 23:25
 5  * Filename     : RCC_2014_W_A.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 1010;
34 int Map[LEN][LEN];
35 
36 int main()
37 {
38     //freopen("in.txt", "r", stdin);
39 
40     int n, m;
41     while(scanf("%d%d", &n, &m)!=EOF){
42         memset(Map, 0, sizeof Map);
43         int ans = 1, anscnt = 0;
44         for(int i=0; i<n; i++){
45             int cnt = 0;
46             for(int j=0; j<n; j++){
47                 if(Map[i][j] != 0 || i==j) continue;
48                 if(cnt == m) break;
49                 Map[i][j] = 1;
50                 Map[j][i] = -1;
51                 cnt++;anscnt ++;
52             }
53             if(cnt != m) {
54                 ans = 0;
55                    break;        
56             }
57         }
58         if(!ans) printf("-1
");
59         else {
60             printf("%d
", anscnt);     
61             for(int i=0; i<n; i++)
62                 for(int j=0; j<n; j++)
63                     if(Map[i][j] == 1)
64                         printf("%d %d
", i+1, j+1);
65         }
66 
67     }
68     return 0;
69 }

View Code

Problem B Cunning Gena

思路：状压DP dp[i]表示状态为i时的最小花费。先对朋友要求显示器数量排序。然后开始DP（和背包比较像）

代码如下：

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-04-17 23:25
 5  * Filename     : RCC_2014_W_B.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
33 const double eps = 1E-6;
34 const int LEN = 21;
35 ll dp[1<<21];
36 struct F{
37     int cost, mon, st;
38 }f[101];
39 
40 bool cmp(F a, F b){
41     return a.mon < b.mon;
42 }
43 
44 int main()
45 {
46 //    freopen("in.txt", "r", stdin);
47 
48     int n, m, b, tn, tc, tm, tmp; 
49     while(scanf("%d%d%d", &n, &m, &b)!=EOF){
50         for(int i=0; i<n; i++){
51             scanf("%d%d%d", &f[i].cost, &f[i].mon, &tn);
52             f[i].st = 0;
53             for(int j=0; j<tn; j++){
54                 scanf("%d", &tmp);
55                 f[i].st |= (1 << (tmp-1));
56             }
57         }
58         sort(f, f+n, cmp);
59         for(int i=0; i<(1<<21); i++) dp[i] = LINF;
60         dp[0] = 0;
61         ll ans = LINF;
62         for(int i=0; i<n; i++){
63             for(int j=(1 << m)-1; j>=0; j--){
64                 dp[j|f[i].st] = min(dp[j|f[i].st], dp[j] + f[i].cost);
65             }
66             ans = min(dp[(1<<m)-1]+(ll)f[i].mon*(ll)b, ans);
67         }
68         if(ans == LINF) printf("-1
");
69         else printf("%I64d
", ans);
70     }
71     return 0;
72 }

View Code