D11

=-=感觉今天的题目好难...

主要是没有碰到过，所以会觉得不懂怎么写..

其实现在想想,T1，T2,T3其实都好水..T1其实没有做过还真不会，有做过的话就是个大水题了

T2找最小环..超级裸的，但是自己不会打=-=

T3直接FLOYD...+判断障碍物是否有在同一条线上

今天按理来说只有T4会比较难一些..DP+贪心

T1:模拟+数学思想

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int d,n,m,k,t;

int minx=123456,miny=123456,sum=123456;

int ansx[10001],ansy[10001],tot[1001][1001],a[100001],b[100001];

int main(){

	freopen("manhattan.in","r",stdin);

	freopen("manhattan.out","w",stdout);

	scanf("%d%d",&d,&n);

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

		scanf("%d%d",&a[i],&b[i]);

		if(a[i]<minx) minx=a[i];

		if(b[i]<miny) miny=b[i];

    }

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

            t=(a[i]-minx)%d+1;//这一段是关键

            k=(b[i]-miny)%d+1;//就是%d看看是否要拆除

            ansx[t]++;//记录个数

            ansy[k]++;

            tot[t][k]++;

    }

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

       for(int j=1;j<=d;j++){//横坐标上要拆的个数+纵坐标上的-重复算的

       	    if(ansx[i]+ansy[j]-tot[i][j]<sum) sum=ansx[i]+ansy[j]-tot[i][j];

       }

    printf("%d",sum);

	return 0;

}

T2：裸的最小环

网上的模板代码简直在逗我..坑死我了

后面翻了翻书，发现代码很简单明了的..

主要的部分是

for (int k=1; k<=n; ++k)

	{

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

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

	      ans=Min(ans,f[i][j]+g[j][k]+g[k][i]);//个人感觉是在找环吧

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

	    for (int j=1; j<=n; ++j)

	      if ((i!=j)&&(j!=k)&&(i!=k))

	        f[i][j]=Min(f[i][k]+f[k][j],f[i][j]);//FLOYD求最短路

	}

自己略理解了一下..或许也不是特别正确吧

有时间好好的刷几题试试看好了

附上代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int g[1001][1001],f[1001][1001];

int Min(int a,int b) { return a<b?a:b; }

int main ()

{

	freopen("heart.in","r",stdin);

	freopen("heart.out","w",stdout);

	int n,m;

	memset(g,27,sizeof(g));

	memset(f,27,sizeof(f));

	scanf("%d%d",&n,&m);

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

	  {

		 int x,y;

		 scanf("%d%d",&x,&y);

		 scanf("%d",&g[x][y]);

		 g[y][x]=g[x][y];

		 f[x][y]=f[y][x]=g[x][y];

	  }

	int ans=21474836;

	for (int k=1; k<=n; ++k)

	{

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

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

	      ans=Min(ans,f[i][j]+g[j][k]+g[k][i]);

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

	    for (int j=1; j<=n; ++j)

	      if ((i!=j)&&(j!=k)&&(i!=k))

	        f[i][j]=Min(f[i][k]+f[k][j],f[i][j]);

	}

	if (ans==21474836)

	  printf("He will never come back.");

	  else printf("%d",ans);

	fclose(stdin); fclose(stdout);

}

T3：floyd求最短路问题

其实这一题我看题的第一时间有想到求最短路问题，但是一想到要判断是否有障碍物这个细节，就各种不想打

=-=这应该算是我之前的一种烦躁的病吧...一定要改过来啊..

其实我要是真打起来的话，极有可能用DIJK..什么算法求最短路，上面的那个细节也不一定处理得正确->或许当时就是这么想的嗯！

看了别人的程序之后发现这里的细节处理非常简单:

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

		scanf("%d%d",&x2,&y2);

		for(int j=0;j<=n;j++)

		   for(int k=0;k<j;k++){

		   	   double a,b,c,d;

		   	   a=abs(x[j]-x[k]);

		   	   b=abs(y[j]-y[k]);

		   	   c=abs(x[j]-x2);

		   	   d=abs(y[j]-y2);

		   	   if((b/a==d/c) && Max(x[j],x[k])>=x2 && Min(x[j],x[k])<=x2 && Max(y[j],y[k])>=y2 && Min(y[j],y[k])<=y2)

		   	      dis[j][k]=dis[k][j]=INF;

		   }

	}

在判断完斜率是否相等之后，看看那个障碍物是否在两个端点之间即可..

感觉这个方法很常用到..MARK一下..

附上完整代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int INF=123456789;

int x0,y0,n,m,x2,y2;

double dis[1001][1001];

int x[10001],y[10001];

int Min(int a,int b)

{

    return a<b?a:b;

}

int Max(int a,int b)

{

    return a<b?b:a;

}

int main(){

	freopen("brazil.in","r",stdin);

	freopen("brazil.out","w",stdout);

	memset(dis,63,sizeof(dis));

	scanf("%d%d%d%d",&x0,&y0,&n,&m);

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

		scanf("%d%d",&x[i],&y[i]);

		dis[i][0]=sqrt((x[i]-x0)*(x[i]-x0)+(y[i]-y0)*(y[i]-y0))*2;

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

		    dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

	}

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

		scanf("%d%d",&x2,&y2);

		for(int j=0;j<=n;j++)

		   for(int k=0;k<j;k++){

		   	   double a,b,c,d;

		   	   a=abs(x[j]-x[k]);

		   	   b=abs(y[j]-y[k]);

		   	   c=abs(x[j]-x2);

		   	   d=abs(y[j]-y2);

		   	   if((b/a==d/c) && Max(x[j],x[k])>=x2 && Min(x[j],x[k])<=x2 && Max(y[j],y[k])>=y2 && Min(y[j],y[k])<=y2)

		   	      dis[j][k]=dis[k][j]=INF;

		   }

	}

	for(int k=2;k<=n;k++)

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

	        for(int j=0;j<=n;j++){

	        	if(i!=j && j!=k && i!=k)

	        	dis[i][j]=Min(dis[i][j],dis[i][k]+dis[k][j]);

	        }

	printf("%.0lf",dis[1][0]);

	return 0;

}

顺便提一下floyd的一个小地方..

我不懂为什么一直会忘记掉dis[i][j]记录的是第i个点到第j个点的距离=-=

不要有一天傻逼打错了嗯

T4:DP+贪心

=-=不知道这样的T4自己什么时候才能改完！

HPY都改完了！你居然连那个妹纸都不如！你就是个傻逼傻逼傻逼..

巴特西

D11

T1:模拟+数学思想

T2：裸的最小环

T3：floyd求最短路问题

T4:DP+贪心

最新文章

热门文章