首页 > 代码库 > Topcoder SRM 637 (Div.2)

Topcoder SRM 637 (Div.2)

2024-07-29 03:33:36   221人阅读

A.GreaterGameDiv2

不能更水

 1 #line 7 "GreaterGameDiv2.cpp" 2 #include<cstdio> 3 #include <cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<iostream> 7 #include<algorithm> 8 #include<set> 9 #include<map>10 #include<stack>11 #include<string>12 #include <ctime>13 #include<vector>14 #include<queue>15 #include <cctype>16 #include<sstream>17 #define eps 0.00000118 #define ALL(x) x.begin(),x.end()19 #define INS(x) inserter(x,x.begin())20 #define clr(x,a) memset(x,a,sizeof(x))21 #define sz(x) (int)x.size()22 #define pb push_back23 #define mp make_pair24 using namespace std;25 typedef long long LL;26 int n,m;27 class GreaterGameDiv228 {    29     public:30     int calc(vector <int> s, vector <int> t)31     {32         int i,j,k;33         int ans=0;34         for (i=0;i<s.size();i++)35         {36             if (s[i]>t[i]) ans++;37         }38         return ans;39     }40 };
View Code

B.PathGameDiv2

贪心策略，使得这条路转完次数尽量小（因为转一次就多占一个格子），那么主人公一直往前走，直到遇见墙才转弯，求出路径再求答案就容易了。注意要枚举一下起始点，可以是第一行，也可以是第二行

 1 #include<cstdio> 2 #include <cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<set> 8 #include<map> 9 #include<stack>10 #include<string>11 #include <ctime>12 #include<vector>13 #include<queue>14 #include <cctype>15 #include<sstream>16 #define eps 0.00000117 #define ALL(x) x.begin(),x.end()18 #define INS(x) inserter(x,x.begin())19 #define clr(x,a) memset(x,a,sizeof(x))20 #define sz(x) (int)x.size()21 #define pb push_back22 #define mp make_pair23 using namespace std;24 typedef long long LL;25 int n,m;26 class PathGameDiv227 {28     public:29     int calc(vector <string> board)30     {31         int i,j,k;32         string a=board[0],b=board[1];33         int len=a.size();34         int flag=0;35         int ans=0;36         if (board[0][0]==‘.‘)37         {38 39             for (i=0;i<len;i++)40             {41                 if (i!=len-1&&board[flag][i+1]==‘#‘)42                 {43                     flag=!flag;44                 }else45                 if (board[flag^1][i]==‘.‘)46                 {47                     ans++;48                 }49             }50         }51         int ans2=0;52         if (board[1][0]==‘.‘)53         {54             flag=1;55             for (i=0;i<len;i++)56             {57                 if (i!=len-1&&board[flag][i+1]==‘#‘)58                 {59                     flag=!flag;60                 }else61                 if (board[flag^1][i]==‘.‘)62                 {63                     ans2++;64                 }65             }66         }67         return max(ans,ans2);68     }69 };
View Code

C.ConnectingGameDiv2

给一个n*m（均小于等于50）的地图，图中用不同的符号划分为多个区域，每个区域中 相邻点一定有一个公共边，

现有一个标记操作，一次标记只能标记一个区域中的全部点，

求至少标记多少个点（注意是点） 使得不存在一条路径，从图最上端沿未标记点走到地图最下端。

 

最短路径问题

首先是构图，每一块区域可以化为一个点，点的权值是这个区域的面积，然后对于区域i，如果区域j与之相邻①，则从图中的点i向点j连一条边，

这样现在问题就转化为：从原地图最左端开始到最右端结束，选一条路径，且点权值和最小。

1.这是多起点，多终点的问题，所以需要添加一个虚拟的起点与终点，虚拟起点与各个起点连一条边，各个终点与虚拟起点连一条边

2.将点权化为边权，对于点i，我们将以点i为起点边的权值规定为点的权值。

因为点数并不是很多，跑一发弗洛伊德算法即可。

①注意这道题有一个神奇的坑点：所选的区域并不一定是相邻的，比如说这样：

显然这样也是满足题意的，也就是说我们需要定义另一种区域相邻，即在八个相邻即可，而不是原来的四个方向相邻。

 1 #include<cstdio> 2 #include <cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<set> 8 #include<map> 9 #include<stack>10 #include<string>11 #include <ctime>12 #include<vector>13 #include<queue>14 #include <cctype>15 #include<sstream>16 #define eps 0.00000117 #define ALL(x) x.begin(),x.end()18 #define INS(x) inserter(x,x.begin())19 #define clr(x,a) memset(x,a,sizeof(x))20 #define sz(x) (int)x.size()21 #define pb push_back22 #define mp make_pair23 using namespace std;24 typedef long long LL;25 int n,m;26 class ConnectingGameDiv227 {28     int dis[260][260],sum[260],start,finish,left,right;29     vector <string> grid;30     public:31     void addedge(int i,int j,int x, int y)32     {33         if (x<0||y<0||x>=n||y>=m) return;34         int a=(int)grid[i][j];35         int b=(int)grid[x][y];36         dis[a][b]=min(dis[a][b],sum[a]);37         dis[b][a]=min(dis[b][a],sum[b]);38     }39     40     int getmin(vector <string> board)41     {42         grid=board;43         int i,j,k;44         n=board.size();45         m=board[0].size();46         memset(sum,0,sizeof(sum));47         for (i=0;i<n;i++)48         {49             for (j=0;j<m;j++)50             {51                 sum[(int)board[i][j]]++;52             }53         }54         for (i=0;i<260;i++)55         {56             for (j=0;j<260;j++)57             {58                 dis[i][j]=100000;59             }60         }61         for (i=0;i<260;i++) dis[i][i]=0;62         start=0;63         finish=1;64         for (i=0;i<n;i++)65         {66             left=(int)board[i][0];67             right=(int)board[i][m-1];68             dis[start][left]=0;69             dis[right][finish]=sum[right];70         }71         for (i=0;i<n;i++)72         {73             for (j=0;j<m;j++)74             {75                 addedge(i,j,i+1,j);76                 addedge(i,j,i-1,j);77                 addedge(i,j,i,j+1);78                 addedge(i,j,i,j-1);79                 80                 addedge(i,j,i+1,j+1);81                 addedge(i,j,i-1,j-1);82                 addedge(i,j,i+1,j-1);83                 addedge(i,j,i-1,j+1);84             }85         }86         for (k=0;k<260;k++)87         {88             for (i=0;i<260;i++)89             {90                 for (j=0;j<260;j++)91                 {92                     if (i==j||j==k||i==k) continue;93                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);94                 }95             }96         }97         return dis[start][finish];98     }99 };
View Code

==================================

第一次用，TC客户端的插件，怎么说呢，相当方便。省去了每次粘类名的麻烦，它都给自动生成，而且测试也简单的多。

总之这次比赛还算满意的，虽然比赛后仍是灰名，但rating涨了104，也是醉了，还没有绿名。

这次写了两道题，第三道因为写的略微麻烦没有写完，嘛，反正最后也是参考了别人的代码才得以简化的。

【一点经验】图论题目如果点少的话还是尽量用邻接矩阵，这样也不容易出错，代码写的也快，尤其是对TC这种短时间的比赛

Topcoder SRM 637 (Div.2)


联系
我们