CF 222 (DIV 1)

我是bfs出一颗树，然后删掉树后面的k个结点。

其实也可以直接bfs出一块连通的s - k个点，其余的.打X就可以了。

很水的题目。

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2013-12-29 23:26:26
 4 File Name     :E:2013ACMCF比赛CF222A.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 char str[550][550];
21 bool vis[550][550];
22 int n,m,k;
23 pair<int,int> p[510*510];
24 int cnt;
25 int Move[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
26 queue<pair<int,int> >q;
27 void bfs(int x0,int y0)
28 {
29     memset(vis,false,sizeof(vis));
30     cnt = 0;
31     while(!q.empty())q.pop();
32     q.push(make_pair(x0,y0));
33     vis[x0][y0] = true;
34     p[cnt++] = make_pair(x0,y0);
35     while(!q.empty())
36     {
37         pair<int,int> tmp = q.front();
38         q.pop();
39         for(int i = 0;i < 4;i++)
40         {
41             int x = tmp.first + Move[i][0];
42             int y = tmp.second + Move[i][1];
43             if(x < 0 || y < 0 || x >= n || y >= m)continue;
44             if(vis[x][y])continue;
45             if(str[x][y] ==  '#')continue;
46             p[cnt++] = make_pair(x,y);
47             vis[x][y] = true;
48             q.push(make_pair(x,y));
49         }
50     }
51 }
52 
53 int main()
54 {
55     //freopen("in.txt","r",stdin);
56     //freopen("out.txt","w",stdout);
57     while(cin>>n>>m>>k)
58     {
59         for(int i = 0;i < n;i++)
60             scanf("%s",str[i]);
61         int x0 , y0 = -1;
62         for(int i = 0;i < n;i++ )
63         {
64             if(y0 != -1)break;
65             for(int j = 0;j < m;j++)
66                 if(str[i][j] == '.')
67                 {
68                     x0 = i;y0 = j;
69                     break;
70                 }
71         }
72         bfs(x0,y0);
73         for(int i = 0;i < k;i++)
74         {
75             int x = p[cnt-1-i].first;
76             int y = p[cnt-1-i].second;
77             str[x][y] = 'X';
78         }
79         for(int i = 0;i < n;i++)
80             cout<<str[i]<<endl;
81     }
82     return 0;
83 }

B：

题目很长，自己看吧！

使用二分+判断就可以了。复杂度大概是n * log(10^9)*log(n).

二分天数，在1~m 的范围二分。

天数为mid天时候，判断。按照a的大小，从大到小，在满足b>=a的里面，找出一个c最小的，然后连续删掉mid个a.

最后判断总价。

使用优先队列写的，用set也可以。

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013-12-29 23:57:57
  4 File Name     :E:2013ACMCF比赛CF222B.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 const int MAXN = 100010;
 21 int a[MAXN];
 22 int b[MAXN];
 23 int c[MAXN];
 24 int n,m,s;
 25 
 26 struct node
 27 {
 28     int x, y;
 29     int index;
 30     friend bool operator < (node a, node b)
 31     {
 32         return a.y > b.y; //结构体中，y小的优先级高
 33     }
 34 };
 35 priority_queue<node>q;
 36 
 37 //适用于正负整数
 38 template <class T>
 39 inline bool scan_d(T &ret) {
 40    char c; int sgn;
 41    if(c=getchar(),c==EOF) return 0; //EOF
 42    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
 43    sgn=(c=='-')?-1:1;
 44    ret=(c=='-')?0:(c-'0');
 45    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
 46    ret*=sgn;
 47    return 1;
 48 }
 49 
 50 node nn[MAXN];
 51 bool cmp(node a,node b)
 52 {
 53     return a.x > b.x;
 54 }
 55 int AA[MAXN];
 56 bool cmp11(int t1,int t2)
 57 {
 58     return a[t1] > a[t2];
 59 }
 60 int BB[MAXN];
 61 
 62 bool check(int pp)
 63 {
 64     while(!q.empty())q.pop();
 65     int i = 0,j = 0;
 66     long long ret = 0;
 67     while(i < m)
 68     {
 69         while(j < n && nn[j].x >= a[i])
 70         {
 71             q.push(nn[j]);
 72             j++;
 73         }
 74         if(q.empty())return false;
 75         node tmp = q.top();
 76         q.pop();
 77         ret += tmp.y;
 78         if(ret > s)return false;
 79         int ccc = pp;
 80         while(ccc && i < m)
 81         {
 82             ccc--;
 83             BB[AA[i]] = tmp.index;
 84             i++;
 85         }
 86     }
 87     return true;
 88 }
 89 
 90 
 91 int main()
 92 {
 93     //freopen("in.txt","r",stdin);
 94     //freopen("out.txt","w",stdout);
 95     while(scanf("%d%d%d",&n,&m,&s) == 3)
 96     {
 97         for(int i = 0;i < m;i++)
 98         {
 99             scan_d(a[i]);
100         }
101         for(int i = 0;i < n;i++)
102             scan_d(b[i]);
103         for(int i = 0;i < n;i++)
104             scan_d(c[i]);
105         for(int i = 0;i < m;i++)
106             AA[i] = i;
107         sort(AA,AA+m,cmp11);
108         sort(a,a+m);
109         reverse(a,a+m);
110         for(int i = 0;i < n;i++)
111         {
112             nn[i].x = b[i];
113             nn[i].y = c[i];
114             nn[i].index = i+1;
115         }
116         sort(nn,nn+n,cmp);
117         if(check(m) == false)
118         {
119             printf("NO
");
120             continue;
121         }
122         int l = 1, r = m;
123         int ans;
124         while(l <= r)
125         {
126             int mid = (l + r)/2;
127             if(check(mid))
128             {
129                 ans = mid;
130                 r = mid -1;
131             }
132             else l = mid+1;
133         }
134         check(ans);
135         printf("YES
");
136         for(int i = 0;i  < m;i++)
137         {
138             printf("%d",BB[i]);
139             if(i < m-1)printf(" ");
140             else printf("
");
141         }
142     }
143     return 0;
144 }

C：

比较有意思的题目。

其实s数组从大到小排序以后，只和前m大的数有关的，后面的无关。

m<=20

一种是复杂度为 m * m * 2^m 的算法，虽然复杂度比较大，可以勉强在CF上跑过去。

使用dp[20][1<<20], dp[i][j] 表示前m个s数组存在情况为j时候，处理到第i步。

答案就是dp[0][(1<<m)-1]

然后就是枚举当前步是取哪一个，或者去掉哪一个，或者忽略这个操作。

代码如下（不建议看，复杂度大）

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2013-12-30 1:06:58
 4 File Name     :E:2013ACMCF比赛CF222C.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 const int INF = 0x3f3f3f3f;
21 
22 int s[110];
23 int n,m;
24 struct Node
25 {
26     char op[10];
27     int id;
28 };
29 Node node[100];
30 bool used[100];
31 int a[100];
32 int cnt;
33 int dp[22][1<<20];
34 int loc[1<<22];
35 
36 int bit[22];
37 int main()
38 {
39     //freopen("in.txt","r",stdin);
40     //freopen("out.txt","w",stdout);
41     for(int i = 0;i <= 21;i++)
42         loc[1<<i] = i;
43     for(int i = 0;i < 22;i++)
44         bit[i] = 1<<i;
45     while(cin>>n)
46     {
47         for(int i = 0;i < n;i++)
48             cin>>s[i];
49         sort(s,s+n);
50         reverse(s,s+n);
51         cnt = 0;
52         scanf("%d",&m);
53         for(int i = 0;i < m;i++)
54         {
55             scanf("%s%d",node[i].op,&node[i].id);
56         }
57         int tot = (1<<m);
58         memset(dp,0,sizeof(dp));
59         for(int i = m-1;i >= 0;i--)
60             for(int j = 0;j < tot;j++)
61             {
62                 if(j == 0)
63                 {
64                     continue;
65                 }
66                 if(node[i].id == 1)dp[i][j] = -INF;
67                 else dp[i][j] = INF;
68                 for(int id  = 0;id < m;id++)
69                 {
70                     if((j & bit[id]) == 0)continue;
71 
72                     if(node[i].id == 1)
73                     {
74                         if(node[i].op[0] == 'p')
75                             dp[i][j] = max(dp[i][j],max(dp[i+1][j],dp[i+1][j ^ bit[id]] + s[id]));
76                         else dp[i][j] = max(dp[i][j],max(dp[i+1][j],dp[i+1][j ^ bit[id]]));
77                     }
78                     else
79                     {
80                     
81                         if(node[i].op[0] == 'p')
82                             dp[i][j] = min(dp[i][j],min(dp[i+1][j],dp[i+1][j ^ bit[id]] - s[id]));
83                         else dp[i][j] = min(dp[i][j],min(dp[i+1][j],dp[i+1][j ^ bit[id]]));
84                     }
85                 }
86             }
87         printf("%d
",dp[0][tot-1]);
88     }
89     return 0;
90 }

View Code

其实操作根本不会被忽略，每一步肯定要操作的。

所以状态可以减少一维，直接dp[i], 根据i中多少个0，就知道取了多少个了。

这样复杂度降为 m * 2^m

写起来也很方便

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2013-12-30 2:22:12
 4 File Name     :E:2013ACMCF比赛CF222CC.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 
21 const int INF = 0x3f3f3f3f;
22 int s[110];
23 int n,m;
24 struct Node
25 {
26     char op[10];
27     int id;
28 }node[22];
29 int dp[1<<20];
30 bool vis[1<<20];
31 
32 int solve(int st)
33 {
34     if(vis[st])return dp[st];
35     vis[st] = true;
36     int cnt = 0;
37     for(int i = 0;i < m;i++)
38         if((st & (1<<i)) == 0)
39             cnt++;
40     if(st == 0)return dp[st] = 0;
41     if(node[cnt].id == 1)
42     {
43         dp[st] = -INF;
44         for(int i = 0;i < m;i++)
45             if(st & (1<<i))
46             {
47                 if(node[cnt].op[0] == 'p')
48                     dp[st] = max(dp[st],solve(st ^ (1<<i)) + s[i]);
49                 else dp[st] = max(dp[st],solve(st ^ (1<<i)));
50             }
51     }
52     else
53     {
54         dp[st] = INF;
55         for(int i = 0;i < m;i++)
56             if(st & (1<<i))
57             {
58                 if(node[cnt].op[0] == 'p')
59                     dp[st] = min(dp[st],solve(st ^ (1<<i)) - s[i]);
60                 else dp[st] = min(dp[st],solve(st ^ (1<<i)));
61             }
62     }
63     return dp[st];
64 }
65 
66 int main()
67 {
68     //freopen("in.txt","r",stdin);
69     //freopen("out.txt","w",stdout);
70     while(cin>>n)
71     {
72         for(int i = 0;i < n;i++)
73             cin>>s[i];
74         sort(s,s+n);
75         reverse(s,s+n);
76         cin>>m;
77         for(int i = 0;i < m;i++)
78             scanf("%s%d",node[i].op,&node[i].id);
79         memset(vis,false,sizeof(vis));
80         printf("%d
",solve((1<<m) - 1));
81     }
82     return 0;
83 }

D ：

待补中

E：

待补中