首页 > 代码库 > D11
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都改完了！你居然连那个妹纸都不如！你就是个傻逼傻逼傻逼..
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。