首页 > 代码库 > 2014.first

2014.first

2024-07-27 12:12:47   217人阅读

之后就按照自己的直觉，整理了第一套，难度为简单，差不多比2013noipday1水一点...先练练手而已

 

T1 vijos1196吃糖果游戏

博弈论

依题意，我们可知，如果去分数目为2,3,7,8必输，分4,5,6必赢，或是有出现1则必赢

以此类推，多写几个我们会发现n mod 5=0,1,4则先手必赢

然后依照以上思路模拟，注意一下精度即可

附上代码：

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;string a,b;int s[10001],l;void into(string c){    l=c.size();	memset(s,0,sizeof(s));	for(int i=l;i>0;i--){		s[l-i+1]=c[i-1]-‘0‘;	}}int chu(){	int r;	for(int i=l;i>=1;i--){		r=(s[i+1]*10+s[i])%5;		s[i]/=5;	}	return r;}int main(){	//freopen("data.txt","r",stdin);	for(int i=1;i<=10;i++){		cin>>a>>b;        into(a);        int x=chu();        into(b);        int y=chu();        if(x==0 || x==1 || x==4 || y==0 || y==1 || y==4) printf("Matrix67\n");        else printf("Shadow\n");	}	return 0;}

 感觉博弈论的题目，大多就是找找原理，找不到原理的时候，看看有没有什么规律

规律的话，大多就是什么mod x=....,或是x的倍数之类的

 

T2:vijos1070

求次小生成树问题

第一次写次小生成树，大概的思路也很简单

就是求出最小生成树之后，暴力枚举每一条最小生成树的边，把它删掉，再求一遍最小生成树

所求的就是次小生成树了

最后比较答案即可

代码：

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int maxn=501;const long long inf=1234567891011;int n,m;struct node{	int x,y,z;}f[maxn*maxn];int fa[maxn],x,y,z,tot=1;long long ans=0;int mark,u,v;int a[maxn*maxn];long long minx=inf;bool cmp(const node &a,const node &b){	return a.z<b.z?1:0;}int find(int x){	if(fa[x]==x) return x;else return fa[x]=find(fa[x]);}long long sst(int x){	for(int i=1;i<=n;i++) fa[i]=i;	int k=0;	ans=0;	for(int i=1;i<=m;i++){    	u=f[i].x;    	v=f[i].y;    	if(find(u)!=find(v) && i!=x){    		k++;    		fa[find(u)]=find(v);    		ans+=f[i].z;    	}    	if(k==n-1) break;    }    if(ans<0 || k<n-1) return inf; else return ans;}int main(){	//freopen("data.txt","r",stdin);	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++) fa[i]=i;	for(int i=1;i<=m;i++){		scanf("%d%d%d",&x,&y,&z);	    f[i].x=x;		f[i].y=y;		f[i].z=z; 	}	sort(f+1,f+m+1,cmp);	int k=0,i=1;    for(i=1;i<=m;i++){    	u=f[i].x;    	v=f[i].y;    	if(find(u)!=find(v)){    		k++;    		fa[find(u)]=find(v);    		ans+=f[i].z;    		a[k]=i;    	}    	if(k==n-1) break;    }    printf("Cost: %ld\n",ans);    for(int i=1;i<=n-1;i++){    	if(minx>sst(a[i])) 		minx=sst(a[i]);    }    if(minx==inf) printf("Cost: -1"); else printf("Cost: %ld",minx);	return 0;}

 

T3：vijos1119

最短路问题

感觉挺简单的，很明显的最短路问题，在同个矩形里的：距离乘上铁路费，不同矩形的：距离*航行的费用，然后就最短路

 

纠结了一下，在一个矩形中已知任意三个点如何求第四个点的坐标

TAT...写了特别长的代码，

大概是先求出这三个点到相邻点的距离，找出矩形的长宽，然后找一个在对角线上的点，向四个方向扩展长宽，看扩展的点到对角线另一点的距离是否满足长或宽

= = 希望以后能找到更好的办法吧

 

由于数据很小s<=100;

点的个数就是n<=400;

我用了比较简单的floyd..

 

但是不懂哪里写错了！WA了两个点！样例都没过

QAQ..调了好久好久，感觉自己的思路和代码没有错啊....

 

先扔在这里好了，搞不好自己哪天能够发现错误呢

 #include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; const int maxn=101; const double inf=1234567; const int hx[5]={1,1,-1,-1},hy[5]={1,-1,1,-1}; int S,T,A,B; int x,y,z,tot=0; double maxx; struct node{  int x,y,v,num; }f[maxn]; double dist[maxn*4][maxn*4]; bool flag[maxn*4][maxn*4];  double d(int a,int b){ 	double temp=sqrt((f[a].x-f[b].x)*(f[a].x-f[b].x)+(f[a].y-f[b].y)*(f[a].y-f[b].y)); 	return temp; } double max(double a,double b){ 	return a>b?a:b; } int main(){  freopen("data.txt","r",stdin);  memset(flag,true,sizeof(flag));  scanf("%d%d%d%d",&S,&T,&A,&B);  for(int i=1;i<=S;i++){   scanf("%d%d%d%d%d%d%d",&f[tot+1].x,&f[tot+1].y,&f[tot+2].x,&f[tot+2].y,&f[tot+3].x,&f[tot+3].y,&z);            double a=d(tot+1,tot+2),b=d(tot+2,tot+3),c=d(tot+3,tot+1);      int xx,yy,dx,dy;            maxx=max(a,max(b,c));      if(a!=maxx){      	 dx=abs(f[tot+1].x-f[tot+2].x);      	 dy=abs(f[tot+1].y-f[tot+2].y);      	 xx=tot+3;      	 if(b==maxx) yy=tot+2;      	 if(c==maxx) yy=tot+1;      }      else 	  if(b!=maxx){      	 dx=abs(f[tot+2].x-f[tot+3].x);      	 dy=abs(f[tot+2].y-f[tot+3].y);      	 xx=tot+1;      	 if(a==maxx) yy=tot+2;      	 if(c==maxx) yy=tot+3;      }      int tempx,tempy;      for(int j=0;j<4;j++){      	 tempx=f[xx].x+hx[j]*dx;      	 tempy=f[xx].y+hy[j]*dy;      	 double l=sqrt((tempx-f[yy].x)*(tempx-f[yy].x)+(tempy-f[yy].y)*(tempy-f[yy].y));      	 if(a==maxx){      	 	if(l==c || l==b){      	 		f[tot+4].x=tempx;      	 		f[tot+4].y=tempy;      	 		break;      	 	}      	 }else if(b==maxx){      	 	if(l==a || l==c){      	 		f[tot+4].x=tempx;      	 		f[tot+4].y=tempy;      	 		break;      	 	}      	 }      }            f[tot+3].v=f[tot+2].v=f[tot+1].v=f[tot+4].v=z;      f[tot+3].num=f[tot+2].num=f[tot+1].num=f[tot+4].num=i;      tot+=4;  }  memset(dist,24,sizeof(dist));  for(int k=1;k<=tot;k++)      for(int i=1;i<=tot;i++)         for(int j=1;j<=tot;j++){         	double d1=d(i,k);         	double d2=d(k,j);         	if(flag[i][k]){         	   if(f[i].num==f[k].num) dist[i][k]=d1*f[i].v;         	   else dist[i][k]=d1*T;         	   flag[i][k]=false;         	}			if(flag[k][j]){			   if(f[k].num==f[j].num) dist[k][j]=d2*f[k].v;         	   else dist[k][j]=d2*T;         	   flag[k][j]=false;         	}			if(dist[i][j]>dist[i][k]+dist[k][j]){			   dist[i][j]=dist[i][k]+dist[k][j];               flag[i][j]=false;			}		 }  int a=(A-1)*4+1;  int b=(B-1)*4+1;  double ans=123456789.0;  for(int i=a;i<=a+3;i++)     for(int j=b;j<=b+3;j++){     	if(ans>dist[i][j]) ans=dist[i][j];     }  printf("%.2f",ans);  return 0; }

 

2014.first


联系
我们