BNU28897 Grandpa's Walk
单纯的把图里的所有最高点搜出来就行了，很简单的一道题。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int s[55][55];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int ans = 0;
void dfs(int x,int y)
{
int q = 0;
for(int i=0; i<4; i++)
{
if(x + dx[i] >=0&&x + dx[i] < n&&y+dy[i] >= 0&&y + dy[i] < m)
{
if(s[x + dx[i]][y + dy[i]] < s[x][y])
{
q = 1;
dfs(x+dx[i],y+dy[i]);
}
}
}
if(q == 0)
{
ans++;
}
}
int main()
{
int t,cas = 0;
scanf("%d",&t);
while(t--)
{
cas++;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
scanf("%d",&s[i][j]);
}
}
ans = 0;
int q;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
q = 0;
for(int k=0; k<4; k++)
{
if(i + dx[k] >=0&&i + dx[k] < n&&j+dy[k] >= 0&&j + dy[k] < m)
{
if(s[i + dx[k]][j + dy[k]] > s[i][j])
{
q = 1;
break;
}
}
}
if(q == 0)
{
dfs(i,j);
}
}
}
printf("Case #%d: %d\n",cas,ans);
}
return 0;
}
bnu28898 Let's Go Green
最初被我认定为是一道树DP，但是发现实际上搜点就可以，先求出所有点的自行车通过量与最大连接值sum和max
如果sum=max表示这是边缘的点，是自行车的出发点，则ans += sum。
如果sum>max，则是中继节点，肯定会有有边缘的自行车通过这里，我们只要计算以这里为起点的自行车的量就可以了。
因为所有点都被当做起点，所以最后答案必为两倍（终点也成起点了），除以二就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>
using namespace std;
#define N 100005
int n,ans;
struct node
{
int sum,ma;
} s[N];
int main()
{
int t,cas = 0;
scanf("%d",&t);
while(t--)
{
cas++;
scanf("%d",&n);
memset(s,0,sizeof(s));
int a,b,c;
for(int i=0; i<n-1; i++)
{
scanf("%d%d%d",&a,&b,&c);
s[a].sum += c;
s[b].sum += c;
s[a].ma = max(s[a].ma,c);
s[b].ma = max(s[b].ma,c);
}
ans = 0;
for(int i=1; i<=n; i++)
{
//cout<<s[i].sum<<'a'<<s[i].ma<<endl;
if(s[i].sum == s[i].ma)
{
ans += s[i].sum;
}
else
{
int mi = s[i].sum - s[i].ma;
if(s[i].ma >= mi)
{
ans += s[i].ma - mi;
}
else
{
ans += s[i].sum % 2;
}
}
}
printf("Case #%d: %d\n",cas,ans / 2);
}
return 0;
}
bnu 28905 Tiling
被题目给出的图给坑了，得到了学长的提示才知道原来横着一条也是可以的
发现这点之后剩下的问题就不大了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>
using namespace std;
int gcd(int x,int y)
{
if(y == 0) return x;
return gcd(y,x%y);
}
int main()
{
int t,cas = 0;
scanf("%d",&t);
int a,b,c,d,e,f,g,h,i;
while(t--)
{
cas++;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
g = abs(a*d-b*c);
h = abs(a*f-b*e);
i = abs(c*f-d*e);
//cout<<g<<' '<<h<<' '<<i<<endl;
printf("Case #%d: %d\n",cas,gcd(g,gcd(h,i)));
}
return 0;
}
bnu28995 Fix the Pond
题意是给出一张图，图上有许多可以旋转的小棒（小棒会阻拦人行动，小棒位置固定，间隔排列）。小棒可以旋转，问至少需要旋转多少个小棒才能实现图全连通。
因为对于任何一个未连通的分块，我们只要旋转对应的任意一个小棒就能实现连通，所以问要旋转几个小棒就是在问有多少个分块，因为给出的图是600*600，直接搜会暴（主要是系统内栈的空间），所以用BFS+queue+pair，来压缩空间。
题目本身不难，但是因为小棒本身并不是图上的点，所以判断条件写的很蛋疼，来来回回改了好久。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>
using namespace std;
#define N 605
char s[N][N];
int n;
int h,v;
bool used[N][N];
int dx[5] = {0,0,1,-1};
int dy[5] = {1,-1,0,0};
void bfs(int x,int y)
{
used[x][y] = true;
queue< pair< int , int > > Queue;
Queue.push( make_pair(x,y) );
while(!Queue.empty())
{
pair<int,int>u=Queue.front(),v;
Queue.pop();
for(int i=0; i<4; i++)
{
x=u.first;
y=u.second;
int xx=u.first+dx[i];
int yy=u.second+dy[i];
if(xx<0||yy<0||xx>=2*n||yy>=2*n+1||used[xx][yy])
continue;
int x1=min(x,xx),x2=max(x,xx);
int y1=min(y,yy),y2=max(y,yy);
if(i<2)
{
if(y1%2==1)
{
if(x==0||x==2*n-1||s[x - (x + 1)%2][(y-1)/2]=='H')
{
Queue.push(make_pair(xx,yy));
used[xx][yy]=1;
}
}
else
{
if(y2==2*n||s[x - x % 2][y2/2]=='H')
{
Queue.push(make_pair(xx,yy));
used[xx][yy]=1;
}
}
}
else
{
if(x1%2==1)
{
if(y==0||s[x1-(x1 + 1)%2][(y-1)/2]=='V')
{
Queue.push(make_pair(xx,yy));
used[xx][yy]=1;
}
}
else
{
if(y==2*n||s[x1][y2/2]=='V')
{
Queue.push(make_pair(xx,yy));
used[xx][yy]=1;
}
}
}
}
}
}
int main()
{
while(scanf("%d",&n) != EOF)
{
getchar();
for(int i=0; i<n*2-1; i++)
{
scanf("%s",&s[i]);
}
h = n * 2;
v = h + 1;
memset(used,false,sizeof(used));
int ans = -1;
for(int i=0; i<h; i++)
{
for(int j=0; j<v; j++)
{
if(!used[i][j])
{
ans++;
bfs(i,j);
/*for(int ii=0; ii<h; ii++)
{
for(int jj=0; jj<v; jj++)
{
cout<<used[ii][jj];
}
cout<<endl;
}*/
}
}
}
printf("%d\n",ans);
}
return 0;
}