欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

hdu刷题

程序员文章站 2023-01-12 12:53:56
1002 大数加法 #include #include using namespace std; int main() { char a[1002],b[1002]; int c[1002]; int n; cin>>n; for(int w=1;w<=n;w+ ......

1002  大数加法

hdu刷题
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    
    char a[1002],b[1002];
    int c[1002];
    int n;
    cin>>n;
    for(int w=1;w<=n;w++)
    {
        int i=0,k=0,j=0;
        memset(c,0,sizeof(c));
        cin>>a>>b;
        int l1=strlen(a);
        int l2=strlen(b);
        l1--,l2--;
    
        while(1)
        {
        
            c[k]=c[k]+(a[l1]+b[l2]-'0'-'0');
            l1--;
            l2--;
            k++;
            if(l1==-1||l2==-1) break;
        }
        if(l1==-1&&l2!=-1) 
        {
            while(l2!=-1){
            c[k]=c[k]+(b[l2]-'0');
            k++;
            l2--;
            }
        }
        else if(l1!=-1&&l2==-1) 
        {
            while(l1!=-1){
            c[k]=c[k]+(a[l1]-'0');
            k++;
            l1--;
            }
        }
        for(i=0;i<k;i++)
        {
            if(c[i]>=10&&i!=k-1)
            {
                c[i+1]+=c[i]/10;
                c[i]%=10;
            }
            else if(c[i]>=10&&i==k-1)
            {
                c[i+1]+=c[i]/10;
                c[i]%=10;
                k++;
            }
        }
    
        cout<<"Case "<<w<<":"<<endl;
        cout<<a<<" + "<<b<<" = ";
        if(w!=n) 
        {
                for(i=k-1;i>=0;i--)
            {
                cout<<c[i];
            }
            cout<<endl;
            cout<<endl;
        }
        else{
                for(i=k-1;i>=0;i--)
            {
                cout<<c[i];
            }
            cout<<endl;
        }
    }
 } 
View Code

 

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

hdu刷题
#include<iostream>
#include<string.h>
using namespace std;
int a[100002];
int dp[100002]; 
int main()
{
    
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n;
        cin>>n;
        for(int j=1;j<=n;j++) cin>>a[j];
        
        memset(dp,0,sizeof(dp));
        int s=1,l=1,r=1;
        int maxsum=a[1];
        dp[1]=a[1];
        for(int k=2;k<=n;k++)
        {
            if(dp[k-1]>=0)
            dp[k]=dp[k-1]+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");
    }
}
View Code

 

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  则说明循环出现

hdu刷题
#include<bits/stdc++.h>
using namespace std;
int x[10000];
int main()
{
    
    int a,b,c;
    while(cin>>a>>b>>c)
    {
        if(a==0&&b==0&&c==0) break;
        memset(x,0,sizeof(x));
        x[1]=1,x[2]=1;
        int i;
        for(i=3;i<=1000;i++)
        {
                x[i]=(x[i-1]*a+x[i-2]*b)%7;
                if(x[i]==1&&x[i-1]==1) break; 
        }
        c=c%(i-2);
        x[0] = x[i-2];
        cout<<x[c]<<endl;
        
    }
}
View Code

1007

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

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

emmmm  这个分治思想比较好吧

hdu刷题
#include<iostream>  
#include<cmath>  
#include<algorithm>  
using namespace std;  
int n;  
struct node  {  
  double x;  
  double y;  
}p[100005];  
 
int a[100005]; 
 
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+1)  //如果只有一个或者两个点直接求最短长度 
      return dis(p[l],p[r]);  
     if(l+2==r)  
      return min(dis(p[l],p[r]),min(dis(p[l],p[l+1]),dis(p[l+1],p[r])));  //递归求解
     int mid=(l+r)>>1;  //从中间分开,进行分治 
     double ans=min(find(l,mid),find(mid+1,r));  //寻找左右两边最小值 
     int i,j,cnt=0;  
     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=0;i<cnt;i++){  //查找是否存在最小的点 
       for(j=i+1;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=0;i<n;i++)  
       scanf("%lf %lf",&p[i].x,&p[i].y);  
      sort(p,p+n,cmpx);  
      printf("%.2lf%\n",find(0,n-1)/2);  
    }  
    return 0;  
}  
View Code

1010

深搜再加上奇偶剪枝

hdu刷题
#include<iostream>
#include<string.h>
using namespace std;
char a[10][10];
int n,m,t;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int sx,sy,ex,ey;
int f=0;
int abs(int x)
{
    return x<0?-a:x;
}
void dfs(int x,int y,int tt)
{
    if(x==ex&&y==ey&&tt==t)
    {
        f=1;
        return ;
    }
    
    int temp=(t-tt)-(abs(x-ex)+abs(y-ey));//在这一点(我能走的步数)减去(这一点我到终点的最小步数)如果不是偶数或者小于零,则不能走到 
    if(temp<0||temp&1) return ;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(a[xx][yy]!='X'&&xx>=0&&xx<n&&yy>=0&&yy<m)
        {
            a[xx][yy]='X';
            DFS(xx,yy,tt+1);
            a[xx][yy]='.';
            if(flag)return ;
        }
    }
}
int main()
{
    while(cin>>n>>m>>t)
    {
        if(n==0&&m==0) break;
        int wall=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;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=0;
        a[sx][sy]='X';
        dfs(sx,sy,0);
        if(f==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
} 
View Code

1011

树形dp

hdu刷题
#include<iostream>
#include<string.h>
using namespace std;
int dp[105][105];
int a[105][105];
int value[105];
int p[105];
int v,n,vis[105];
int max(int a1,int a2)
{
    return a1>a2?a1:a2;
}
int dfs(int now,int pre)//now 是当前节点 pre是上一个节点 
{
    int tem=(value[now]+19)/20;    //tem是这个节点需要的士兵 
    for(int k=tem;k<=v;k++)
    {
        dp[now][k]=p[now];    //dp[now][tem++]=p[now]  意思是不管这个节点派多少大于tem士兵 得到的p都是一样 
    }
    for(int i=1;i<=n;i++)    //遍历每个节点 
    {
        if(a[now][i]==1&&i!=pre)    //如果是now连着的下一个地点  并且下一个地点不是自己 
        {
            dfs(i,now);    //再次搜索。。。搜到底了时 
            for(int j=v;j>=tem;j--)//j是排出的士兵数 
            {
                for(int k=1;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 0;
}
int main()
{
    while(cin>>n>>v)
    {
        if(n==-1&&v==-1) break;
        
        for(int i=1;i<=n;i++)
        cin>>value[i]>>p[i];
        
        memset(a,0,sizeof(a));
        
        for(int j=0;j<n-1;j++)
        {
            int t1,t2;
            cin>>t1>>t2;
            a[t1][t2]=1;
            a[t2][t1]=1;
        }
        if(v==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        memset(dp,0,sizeof(dp));
        dfs(1,-1);
        cout<<dp[1][v]<<endl;
    }
    return 0;
}
View Code

1016

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

hdu刷题
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int p[1000];
int a[100],vis[100];
int ans[100];
int cnt;
int n;
void dfs(int s,int step)
{
    if(step==n)
    {
        if(p[1+ans[n-1]]==0)
        {
            for(int i=0;i<n;i++)
            {
                if(i==0) cout<<ans[i];
                else cout<<" "<<ans[i];
            }
            cout<<endl;
            return;
        }
        else return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&p[i+s]==0)
        {
            vis[i]=1;
            ans[step]=i;
            dfs(i,step+1);
            vis[i]=0;
        }
    }
}
int main()
{
    memset(p,0,sizeof(p));
    p[1]=1;
    for(int i=2;i<=800;i++)
    {
        if(p[i]==0)
        {
            for(int j=i*2;j<800;j+=i)
            p[j]=1;
        }
    }
//    for(int i=1;i<=20;i++) cout<<p[i]<<endl;
    int ii=1;
    while(cin>>n){
        for(int i=1;i<=n;i++) a[i]=i;
        printf("Case %d:\n",ii);
        ans[0]=1;
        vis[1]=1;
        dfs(1,1);
        ii++;
        cout<<endl;
    }
    
}
View Code

1018

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

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

hdu刷题
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int n,test,ans=0;
    double t;
    cin>>test;
    while(test--)
    {
        cin>>n;
        t=0;
        for(int i=2;i<=n;i++)
        {
            t+=log10(i*1.0);
        }
        ans+=(int)t+1;
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
 } 
View Code