hdu刷题1

1002 大数加法

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

    char a[],b[];

    int c[];

    int n;

    cin>>n;

    for(int w=;w<=n;w++)

    {

        int i=,k=,j=;

        memset(c,,sizeof(c));

        cin>>a>>b;

        int l1=strlen(a);

        int l2=strlen(b);

        l1--,l2--;

        while()

        {

            c[k]=c[k]+(a[l1]+b[l2]-''-'');

            l1--;

            l2--;

            k++;

            if(l1==-||l2==-) break;

        }

        if(l1==-&&l2!=-)

        {

            while(l2!=-){

            c[k]=c[k]+(b[l2]-'');

            k++;

            l2--;

            }

        }

        else if(l1!=-&&l2==-)

        {

            while(l1!=-){

            c[k]=c[k]+(a[l1]-'');

            k++;

            l1--;

            }

        }

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

        {

            if(c[i]>=&&i!=k-)

            {

                c[i+]+=c[i]/;

                c[i]%=;

            }

            else if(c[i]>=&&i==k-)

            {

                c[i+]+=c[i]/;

                c[i]%=;

                k++;

            }

        }

        cout<<"Case "<<w<<":"<<endl;

        cout<<a<<" + "<<b<<" = ";

        if(w!=n)

        {

                for(i=k-;i>=;i--)

            {

                cout<<c[i];

            }

            cout<<endl;

            cout<<endl;

        }

        else{

                for(i=k-;i>=;i--)

            {

                cout<<c[i];

            }

            cout<<endl;

        }

    }

 }

1003 简单采用了dp的思想吧，这一个与上一个有关系，关键是找到这个关系

#include<iostream>

#include<string.h>

using namespace std;

int a[];

int dp[];

int main()

{

    int t;

    cin>>t;

    for(int i=;i<=t;i++)

    {

        int n;

        cin>>n;

        for(int j=;j<=n;j++) cin>>a[j];

        memset(dp,,sizeof(dp));

        int s=,l=,r=;

        int maxsum=a[];

        dp[]=a[];

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

        {

            if(dp[k-]>=)

            dp[k]=dp[k-]+a[k];

            else

            {

                dp[k]=a[k];

                s=k;

            }

            if(dp[k]>maxsum)

            {

                maxsum=dp[k];

                l=s;

                r=k;

            }

        }

        printf("Case %d:\n",i);

        printf("%d %d %d\n", maxsum, l, r);

        if(i!=t) printf("\n");

    }

}

1005 定义 f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给出A B 和N 求f（n）思路就是找规律如果循环中出现了两个连续的1 则说明循环出现

#include<bits/stdc++.h>

using namespace std;

int x[];

int main()

{

    int a,b,c;

    while(cin>>a>>b>>c)

    {

        if(a==&&b==&&c==) break;

        memset(x,,sizeof(x));

        x[]=,x[]=;

        int i;

        for(i=;i<=;i++)

        {

                x[i]=(x[i-]*a+x[i-]*b)%;

                if(x[i]==&&x[i-]==) break;

        }

        c=c%(i-);

        x[] = x[i-];

        cout<<x[c]<<endl;

    }

}

1007

给n个点的坐标，求距离最近的一对点之间距离的一半。

第一行是一个数n表示有n个点，接下来n行是n个点的x坐标和y坐标。实数。

emmmm 这个分治思想比较好吧

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

int n;

struct node  {

  double x;

  double y;

}p[];  

int a[]; 

double cmpx(node a,node b)  {

  return a.x<b.x;

} 

double cmpy(int a,int b)  {

  return p[a].y<p[b].y;

}  

double dis(node a,node b)  {

  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}  

double find(int l,int r){

     if(r==l+)  //如果只有一个或者两个点直接求最短长度

      return dis(p[l],p[r]);

     if(l+==r)

      return min(dis(p[l],p[r]),min(dis(p[l],p[l+]),dis(p[l+],p[r])));  //递归求解

     int mid=(l+r)>>;  //从中间分开，进行分治

     double ans=min(find(l,mid),find(mid+,r));  //寻找左右两边最小值

     int i,j,cnt=;

     for(i=l;i<=r;i++){  //统计距离中点距离小于ans的点

       if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans)

          a[cnt++]=i;

     }

     sort(a,a+cnt,cmpy);  //对y轴进行排序

     for(i=;i<cnt;i++){  //查找是否存在最小的点

       for(j=i+;j<cnt;j++){

         if(p[a[j]].y-p[a[i]].y>=ans) break;

         ans=min(ans,dis(p[a[i]],p[a[j]]));

       }

     }

     return ans;

}  

int main(){

    int i;  

    while(scanf("%d",&n)!=EOF){

      if(!n) break;

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

       scanf("%lf %lf",&p[i].x,&p[i].y);

      sort(p,p+n,cmpx);

      printf("%.2lf%\n",find(,n-)/);

    }

    return ;

}

1010

深搜再加上奇偶剪枝

#include<iostream>

#include<string.h>

using namespace std;

char a[][];

int n,m,t;

int dx[]={,,,-};

int dy[]={,-,,};

int sx,sy,ex,ey;

int f=;

int abs(int x)

{

    return x<?-a:x;

}

void dfs(int x,int y,int tt)

{

    if(x==ex&&y==ey&&tt==t)

    {

        f=;

        return ;

    }

    int temp=(t-tt)-(abs(x-ex)+abs(y-ey));//在这一点(我能走的步数)减去(这一点我到终点的最小步数)如果不是偶数或者小于零，则不能走到

    if(temp<||temp&) return ;

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

    {

        int xx=x+dx[i];

        int yy=y+dy[i];

        if(a[xx][yy]!='X'&&xx>=&&xx<n&&yy>=&&yy<m)

        {

            a[xx][yy]='X';

            DFS(xx,yy,tt+);

            a[xx][yy]='.';

            if(flag)return ;

        }

    }

}

int main()

{

    while(cin>>n>>m>>t)

    {

        if(n==&&m==) break;

        int wall=;

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

        {

            for(int j=;j<m;j++)

            {

                cin>>a[i][j];

                if(a[i][j]=='S') sx=i,sy=j;

                else if(a[i][j]=='D') ex=i,ey=j;

                else if(a[i][j]=='X') wall++;

            }

        }

        if(n*m-wall<=t)

        {

            cout<<"NO"<endl;

            continue;

        }

        f=;

        a[sx][sy]='X';

        dfs(sx,sy,);

        if(f==) cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return ;

}

1011

树形dp

#include<iostream>

#include<string.h>

using namespace std;

int dp[][];

int a[][];

int value[];

int p[];

int v,n,vis[];

int max(int a1,int a2)

{

    return a1>a2?a1:a2;

}

int dfs(int now,int pre)//now 是当前节点 pre是上一个节点

{

    int tem=(value[now]+)/;    //tem是这个节点需要的士兵

    for(int k=tem;k<=v;k++)

    {

        dp[now][k]=p[now];    //dp[now][tem++]=p[now]  意思是不管这个节点派多少大于tem士兵 得到的p都是一样

    }

    for(int i=;i<=n;i++)    //遍历每个节点

    {

        if(a[now][i]==&&i!=pre)    //如果是now连着的下一个地点  并且下一个地点不是自己

        {

            dfs(i,now);    //再次搜索。。。搜到底了时

            for(int j=v;j>=tem;j--)//j是排出的士兵数

            {

                for(int k=;k<=j-tem;k++)//j-tem是

                {

                    dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[i][k]);//k的范围为1-（j-tem），因为你至少要留下tem个士兵来攻打当前节点，i为该节点的子节点

                }

            }

        }

    }

    return ;

}

int main()

{

    while(cin>>n>>v)

    {

        if(n==-&&v==-) break;

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

        cin>>value[i]>>p[i];

        memset(a,,sizeof(a));

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

        {

            int t1,t2;

            cin>>t1>>t2;

            a[t1][t2]=;

            a[t2][t1]=;

        }

        if(v==)

        {

            cout<<""<<endl;

            continue;

        }

        memset(dp,,sizeof(dp));

        dfs(,-);

        cout<<dp[][v]<<endl;

    }

    return ;

}

1016

输入n 输出一个素数环，就是相邻数为素数的一个环

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int p[];

int a[],vis[];

int ans[];

int cnt;

int n;

void dfs(int s,int step)

{

    if(step==n)

    {

        if(p[+ans[n-]]==)

        {

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

            {

                if(i==) cout<<ans[i];

                else cout<<" "<<ans[i];

            }

            cout<<endl;

            return;

        }

        else return ;

    }

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

    {

        if(!vis[i]&&p[i+s]==)

        {

            vis[i]=;

            ans[step]=i;

            dfs(i,step+);

            vis[i]=;

        }

    }

}

int main()

{

    memset(p,,sizeof(p));

    p[]=;

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

    {

        if(p[i]==)

        {

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

            p[j]=;

        }

    }

//    for(int i=1;i<=20;i++) cout<<p[i]<<endl;

    int ii=;

    while(cin>>n){

        for(int i=;i<=n;i++) a[i]=i;

        printf("Case %d:\n",ii);

        ans[]=;

        vis[]=;

        dfs(,);

        ii++;

        cout<<endl;

    }

}

1018

输入一个数，然后输出这个数阶乘有多少位

竟然还有log10（x）....123456=1.23456×10^5 两边同时求对数log10(123456)=5+0.x.....

#include<iostream>

#include<math.h>

using namespace std;

int main()

{

    int n,test,ans=;

    double t;

    cin>>test;

    while(test--)

    {

        cin>>n;

        t=;

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

        {

            t+=log10(i*1.0);

        }

        ans+=(int)t+;

        cout<<ans<<endl;

        ans=;

    }

    return ;

 }

巴特西

hdu刷题1

最新文章

热门文章