首页 > 代码库 > D10

D10

2024-07-13 03:52:03   211人阅读

=-=今天被dev-c++坑到死..简直
晚上准备怒装liunx..

T1：数论

一开始碰到的是T1的运算符优先问题吧..maybe..但是我加上括号了还是WA啊..后面把式子拆开写才A了..次奥
附上代码以此为戒：
错误代码
m=(e-s)/t+1;ans=((2+(m-1)*d)*m)/2;tot+=ans;
 正确的代码！
m=(e-s)/t+1;ans=2+(m-1)*d;ans*=m;ans/=2;tot+=ans;
呵呵我一脸啊..简直
真是不懂怎么了...

T2：正解 DP

骗分：DFS+剪枝

表示还是很感谢这一题..让我学会了用DFS打暴力，算是有所领会了吧

但是dev-c++和PSACAL在写DFS上有些差异，就是在于
int search(int x,int y,int t){	if(t==n+1){		tot=x*x*x*x+y;		if(tot<minx) minx=tot;		return minx;	}else{		search(x+a[t],y,t+1);		search(x,y+b[t],t+1);	}	return minx;}
 p不需要最后的return minx;

QAQ可是c++要是没有写这一行，就会没有返回值

以及最后调用 search(0,0,0)

坑爹的是dev-c++不会显示这样的错误，于是就出现了手动输入数据可以得出正确答案，但是用cena就是过不去的情况...
悲愤啊...
MARK:    如果自己用linux不习惯，还是得用dev-c++的话，    记得要开-wall    具体位置在tool-compiler options-settings-warnings-YES

 

对于正解：DP

 

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int INF=2147483247;long long n,m,t,a[100],b[100],f[100][151],minx,ans = INF,tot;//f[i][j]表示前i个路段，使用j个红苹果的时候，使用青苹果最少的个数 int main(){	freopen("travel.in","r",stdin);	freopen("travel.out","w",stdout);	memset(f,63,sizeof(f));	scanf("%d%d",&t,&n);	for(int i=1;i<=n;i++){		scanf("%d%d",&a[i],&b[i]);	}	f[0][0]=0;//初始化 	f[1][a[1]]=0;//	f[1][0]=b[1];//	for(int i=2;i<=n;i++)	   for(int j=0;j<=150;j++){	   	  if(j-a[i]>=0) f[i][j]=min(f[i-1][j]+b[i],f[i-1][j-a[i]]);	   	  else f[i][j]=f[i-1][j]+b[i];	   }	for(int i=0;i<=150;i++){		if(ans>f[n][i] + i*i*i*i) ans=f[n][i]+i*i*i*i;	}	printf("%lld",ans);}
 mark几个地方：
  1.这个的主要思想是01背包，不过要注意这里有后效性，不能直接套用；
  2.故这里要注意一下初始化
  3.j-a[i]的情况要讨论..注意
  4.最后记得for一遍过去，得出答案
  5.当然最重要的，还是要会写状态转移方程..以及..DP就是这么回事..要有自信嗯！

T3：BFS
其实仔细分析会发现这是一题很简单的广搜啊...
只不过是个三维坐标而已...
和二维的一样打就可以了...
不过我的程序不懂为什么会WA..
这里附上错误的代码，希望自己有一天可以发现错误啊><
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int dx[6]={-1,0,0,0,0,1},dy[6]={0,1,0,0,-1,0},dz[6]={0,0,1,-1,0,0};int d1[1000001],d2[1000001],d3[1000001];long long n,m,l,w,h,tot=0;long long f[51][51][51];bool vis[51][51][51];int abs(int x){	return x<0?-x:x;}void search(int i,int j,int k){	int h=1,w=1;	int x,y,z,xx,yy,zz;	vis[i][j][k]=0;	d1[h]=i;d2[h]=j;d3[h]=k;	while(h<=w){		x=d1[h];y=d2[h];z=d3[h];		for(int i=0;i<=5;i++){			xx=x+dx[i];			yy=y+dy[i];			zz=z+dz[i];			if(abs(f[xx][yy][zz]-f[x][y][z])<=n && vis[xx][yy][zz] && xx<=l && yy<=w && zz<=h && xx>=0 && yy>=0 && zz>=0){			    vis[xx][yy][zz]=0;			    w++;				d1[w]=xx;				d2[w]=yy;				d3[w]=zz;				}					}		h++;	}}int main(){	//freopen("engineer.in","r",stdin);freopen("engineer.out","w",stdout);	scanf("%d%d%d",&l,&w,&h);	scanf("%d",&n);	memset(vis,true,sizeof(vis));	for(int i=1;i<=l;i++)	   for(int j=1;j<=w;j++)	      for(int k=1;k<=h;k++) scanf("%d",&f[i][j][k]);	for(int i=1;i<=l;i++)	   for(int j=1;j<=w;j++)	      for(int k=1;k<=h;k++){	      	 if(vis[i][j][k]){	      	 	tot++;	      	 	search(i,j,k);	      	 }	      }	printf("%d",tot);	return 0;} 
T4：spfa
先对feli作BFS，找出feli到每个地方的最短距离，然后模拟japan行动判断什么时候两人相遇。相遇的时间，就是花去的最短时间。 

注意内存限制..只有1M
今天本来想改完的...可惜时间又浪费了

哼！连hpy都改完了..我也应该要改完！
一定要在xc回来之后，让他刮目相看啊.....






























        

            
                
                  
                
                

                    联系

                    我们