A.GreaterGameDiv2
不能更水
#line 7 "GreaterGameDiv2.cpp"
#include<cstdio>
#include <cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<string>
#include <ctime>
#include<vector>
#include<queue>
#include <cctype>
#include<sstream>
#define eps 0.000001
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define clr(x,a) memset(x,a,sizeof(x))
#define sz(x) (int)x.size()
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
int n,m;
class GreaterGameDiv2
{
public:
int calc(vector <int> s, vector <int> t)
{
int i,j,k;
int ans=;
for (i=;i<s.size();i++)
{
if (s[i]>t[i]) ans++;
}
return ans;
}
};
B.PathGameDiv2
贪心策略，使得这条路转完次数尽量小（因为转一次就多占一个格子），那么主人公一直往前走，直到遇见墙才转弯，求出路径再求答案就容易了。注意要枚举一下起始点，可以是第一行，也可以是第二行
#include<cstdio>
#include <cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<string>
#include <ctime>
#include<vector>
#include<queue>
#include <cctype>
#include<sstream>
#define eps 0.000001
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define clr(x,a) memset(x,a,sizeof(x))
#define sz(x) (int)x.size()
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
int n,m;
class PathGameDiv2
{
public:
int calc(vector <string> board)
{
int i,j,k;
string a=board[],b=board[];
int len=a.size();
int flag=;
int ans=;
if (board[][]=='.')
{ for (i=;i<len;i++)
{
if (i!=len-&&board[flag][i+]=='#')
{
flag=!flag;
}else
if (board[flag^][i]=='.')
{
ans++;
}
}
}
int ans2=;
if (board[][]=='.')
{
flag=;
for (i=;i<len;i++)
{
if (i!=len-&&board[flag][i+]=='#')
{
flag=!flag;
}else
if (board[flag^][i]=='.')
{
ans2++;
}
}
}
return max(ans,ans2);
}
};
C.ConnectingGameDiv2
给一个n*m（均小于等于50）的地图，图中用不同的符号划分为多个区域，每个区域中 相邻点一定有一个公共边，
现有一个标记操作，一次标记只能标记一个区域中的全部点，
求至少标记多少个点（注意是点） 使得不存在一条路径，从图最上端沿未标记点走到地图最下端。
最短路径问题
首先是构图，每一块区域可以化为一个点，点的权值是这个区域的面积，然后对于区域i，如果区域j与之相邻①，则从图中的点i向点j连一条边，
这样现在问题就转化为：从原地图最左端开始到最右端结束，选一条路径，且点权值和最小。
1.这是多起点，多终点的问题，所以需要添加一个虚拟的起点与终点，虚拟起点与各个起点连一条边，各个终点与虚拟起点连一条边
2.将点权化为边权，对于点i，我们将以点i为起点边的权值规定为点的权值。
因为点数并不是很多，跑一发弗洛伊德算法即可。
①注意这道题有一个神奇的坑点：所选的区域并不一定是相邻的，比如说这样：
显然这样也是满足题意的，也就是说我们需要定义另一种区域相邻，即在八个相邻即可，而不是原来的四个方向相邻。
#include<cstdio>
#include <cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<string>
#include <ctime>
#include<vector>
#include<queue>
#include <cctype>
#include<sstream>
#define eps 0.000001
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define clr(x,a) memset(x,a,sizeof(x))
#define sz(x) (int)x.size()
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
int n,m;
class ConnectingGameDiv2
{
int dis[][],sum[],start,finish,left,right;
vector <string> grid;
public:
void addedge(int i,int j,int x, int y)
{
if (x<||y<||x>=n||y>=m) return;
int a=(int)grid[i][j];
int b=(int)grid[x][y];
dis[a][b]=min(dis[a][b],sum[a]);
dis[b][a]=min(dis[b][a],sum[b]);
} int getmin(vector <string> board)
{
grid=board;
int i,j,k;
n=board.size();
m=board[].size();
memset(sum,,sizeof(sum));
for (i=;i<n;i++)
{
for (j=;j<m;j++)
{
sum[(int)board[i][j]]++;
}
}
for (i=;i<;i++)
{
for (j=;j<;j++)
{
dis[i][j]=;
}
}
for (i=;i<;i++) dis[i][i]=;
start=;
finish=;
for (i=;i<n;i++)
{
left=(int)board[i][];
right=(int)board[i][m-];
dis[start][left]=;
dis[right][finish]=sum[right];
}
for (i=;i<n;i++)
{
for (j=;j<m;j++)
{
addedge(i,j,i+,j);
addedge(i,j,i-,j);
addedge(i,j,i,j+);
addedge(i,j,i,j-); addedge(i,j,i+,j+);
addedge(i,j,i-,j-);
addedge(i,j,i+,j-);
addedge(i,j,i-,j+);
}
}
for (k=;k<;k++)
{
for (i=;i<;i++)
{
for (j=;j<;j++)
{
if (i==j||j==k||i==k) continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
return dis[start][finish];
}
};
==================================
第一次用，TC客户端的插件，怎么说呢，相当方便。省去了每次粘类名的麻烦，它都给自动生成，而且测试也简单的多。
总之这次比赛还算满意的，虽然比赛后仍是灰名，但rating涨了104，也是醉了，还没有绿名。
这次写了两道题，第三道因为写的略微麻烦没有写完，嘛，反正最后也是参考了别人的代码才得以简化的。
【一点经验】图论题目如果点少的话还是尽量用邻接矩阵，这样也不容易出错，代码写的也快，尤其是对TC这种短时间的比赛