CF 222 (DIV 1)

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

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

很水的题目。

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-12-29 23:26:26

 File Name     :E:\2013ACM\CF比赛\CF222\A.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 char str[][];

 bool vis[][];

 int n,m,k;

 pair<int,int> p[*];

 int cnt;

 int Move[][] = {{,},{,-},{,},{-,}};

 queue<pair<int,int> >q;

 void bfs(int x0,int y0)

 {

     memset(vis,false,sizeof(vis));

     cnt = ;

     while(!q.empty())q.pop();

     q.push(make_pair(x0,y0));

     vis[x0][y0] = true;

     p[cnt++] = make_pair(x0,y0);

     while(!q.empty())

     {

         pair<int,int> tmp = q.front();

         q.pop();

         for(int i = ;i < ;i++)

         {

             int x = tmp.first + Move[i][];

             int y = tmp.second + Move[i][];

             if(x <  || y <  || x >= n || y >= m)continue;

             if(vis[x][y])continue;

             if(str[x][y] ==  '#')continue;

             p[cnt++] = make_pair(x,y);

             vis[x][y] = true;

             q.push(make_pair(x,y));

         }

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     while(cin>>n>>m>>k)

     {

         for(int i = ;i < n;i++)

             scanf("%s",str[i]);

         int x0 , y0 = -;

         for(int i = ;i < n;i++ )

         {

             if(y0 != -)break;

             for(int j = ;j < m;j++)

                 if(str[i][j] == '.')

                 {

                     x0 = i;y0 = j;

                     break;

                 }

         }

         bfs(x0,y0);

         for(int i = ;i < k;i++)

         {

             int x = p[cnt--i].first;

             int y = p[cnt--i].second;

             str[x][y] = 'X';

         }

         for(int i = ;i < n;i++)

             cout<<str[i]<<endl;

     }

     return ;

 }

B：

题目很长，自己看吧！

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

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

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

最后判断总价。

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

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-12-29 23:57:57

 File Name     :E:\2013ACM\CF比赛\CF222\B.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 const int MAXN = ;

 int a[MAXN];

 int b[MAXN];

 int c[MAXN];

 int n,m,s;

 struct node

 {

     int x, y;

     int index;

     friend bool operator < (node a, node b)

     {

         return a.y > b.y; //结构体中，y小的优先级高

     }

 };

 priority_queue<node>q;

 //适用于正负整数

 template <class T>

 inline bool scan_d(T &ret) {

    char c; int sgn;

    if(c=getchar(),c==EOF) return ; //EOF

    while(c!='-'&&(c<''||c>'')) c=getchar();

    sgn=(c=='-')?-:;

    ret=(c=='-')?:(c-'');

    while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');

    ret*=sgn;

    return ;

 }

 node nn[MAXN];

 bool cmp(node a,node b)

 {

     return a.x > b.x;

 }

 int AA[MAXN];

 bool cmp11(int t1,int t2)

 {

     return a[t1] > a[t2];

 }

 int BB[MAXN];

 bool check(int pp)

 {

     while(!q.empty())q.pop();

     int i = ,j = ;

     long long ret = ;

     while(i < m)

     {

         while(j < n && nn[j].x >= a[i])

         {

             q.push(nn[j]);

             j++;

         }

         if(q.empty())return false;

         node tmp = q.top();

         q.pop();

         ret += tmp.y;

         if(ret > s)return false;

         int ccc = pp;

         while(ccc && i < m)

         {

             ccc--;

             BB[AA[i]] = tmp.index;

             i++;

         }

     }

     return true;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     while(scanf("%d%d%d",&n,&m,&s) == )

     {

         for(int i = ;i < m;i++)

         {

             scan_d(a[i]);

         }

         for(int i = ;i < n;i++)

             scan_d(b[i]);

         for(int i = ;i < n;i++)

             scan_d(c[i]);

         for(int i = ;i < m;i++)

             AA[i] = i;

         sort(AA,AA+m,cmp11);

         sort(a,a+m);

         reverse(a,a+m);

         for(int i = ;i < n;i++)

         {

             nn[i].x = b[i];

             nn[i].y = c[i];

             nn[i].index = i+;

         }

         sort(nn,nn+n,cmp);

         if(check(m) == false)

         {

             printf("NO\n");

             continue;

         }

         int l = , r = m;

         int ans;

         while(l <= r)

         {

             int mid = (l + r)/;

             if(check(mid))

             {

                 ans = mid;

                 r = mid -;

             }

             else l = mid+;

         }

         check(ans);

         printf("YES\n");

         for(int i = ;i  < m;i++)

         {

             printf("%d",BB[i]);

             if(i < m-)printf(" ");

             else printf("\n");

         }

     }

     return ;

 }

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]

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

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

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-12-30 1:06:58

 File Name     :E:\2013ACM\CF比赛\CF222\C.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 int s[];

 int n,m;

 struct Node

 {

     char op[];

     int id;

 };

 Node node[];

 bool used[];

 int a[];

 int cnt;

 int dp[][<<];

 int loc[<<];

 int bit[];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     for(int i = ;i <= ;i++)

         loc[<<i] = i;

     for(int i = ;i < ;i++)

         bit[i] = <<i;

     while(cin>>n)

     {

         for(int i = ;i < n;i++)

             cin>>s[i];

         sort(s,s+n);

         reverse(s,s+n);

         cnt = ;

         scanf("%d",&m);

         for(int i = ;i < m;i++)

         {

             scanf("%s%d",node[i].op,&node[i].id);

         }

         int tot = (<<m);

         memset(dp,,sizeof(dp));

         for(int i = m-;i >= ;i--)

             for(int j = ;j < tot;j++)

             {

                 if(j == )

                 {

                     continue;

                 }

                 if(node[i].id == )dp[i][j] = -INF;

                 else dp[i][j] = INF;

                 for(int id  = ;id < m;id++)

                 {

                     if((j & bit[id]) == )continue;

                     if(node[i].id == )

                     {

                         if(node[i].op[] == 'p')

                             dp[i][j] = max(dp[i][j],max(dp[i+][j],dp[i+][j ^ bit[id]] + s[id]));

                         else dp[i][j] = max(dp[i][j],max(dp[i+][j],dp[i+][j ^ bit[id]]));

                     }

                     else

                     {

                         if(node[i].op[] == 'p')

                             dp[i][j] = min(dp[i][j],min(dp[i+][j],dp[i+][j ^ bit[id]] - s[id]));

                         else dp[i][j] = min(dp[i][j],min(dp[i+][j],dp[i+][j ^ bit[id]]));

                     }

                 }

             }

         printf("%d\n",dp[][tot-]);

     }

     return ;

 }

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

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

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

写起来也很方便

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-12-30 2:22:12

 File Name     :E:\2013ACM\CF比赛\CF222\CC.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 int s[];

 int n,m;

 struct Node

 {

     char op[];

     int id;

 }node[];

 int dp[<<];

 bool vis[<<];

 int solve(int st)

 {

     if(vis[st])return dp[st];

     vis[st] = true;

     int cnt = ;

     for(int i = ;i < m;i++)

         if((st & (<<i)) == )

             cnt++;

     if(st == )return dp[st] = ;

     if(node[cnt].id == )

     {

         dp[st] = -INF;

         for(int i = ;i < m;i++)

             if(st & (<<i))

             {

                 if(node[cnt].op[] == 'p')

                     dp[st] = max(dp[st],solve(st ^ (<<i)) + s[i]);

                 else dp[st] = max(dp[st],solve(st ^ (<<i)));

             }

     }

     else

     {

         dp[st] = INF;

         for(int i = ;i < m;i++)

             if(st & (<<i))

             {

                 if(node[cnt].op[] == 'p')

                     dp[st] = min(dp[st],solve(st ^ (<<i)) - s[i]);

                 else dp[st] = min(dp[st],solve(st ^ (<<i)));

             }

     }

     return dp[st];

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     while(cin>>n)

     {

         for(int i = ;i < n;i++)

             cin>>s[i];

         sort(s,s+n);

         reverse(s,s+n);

         cin>>m;

         for(int i = ;i < m;i++)

             scanf("%s%d",node[i].op,&node[i].id);

         memset(vis,false,sizeof(vis));

         printf("%d\n",solve((<<m) - ));

     }

     return ;

 }

D ：

待补中

E：

待补中

巴特西

CF 222 (DIV 1)

最新文章

热门文章