Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

log(1<<64)*20的复杂度怎么能tls呢?!

Posted by highkobe at 2009-04-08 00:00:05 on Problem 3725
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<set>
using namespace std;
const int INF=0x7fffffff;
const double eps=(1.0e-9);
const double PI=atan2(0.0,-1.0);
typedef long long int64;
int64 m,k;
int64 dig[20],n;
int64 base[20];
int64 solve(int64 now)
{
    int64 dit[20],i;
    int64 cur=now,d[20];
    if(now<m)
    return 0;
    for(i=1;;i++)
    {
        dit[i]=cur%10;
        cur/=10;
        if(cur==0)
        break;
    }
    int nn=i;
    //intf("n----%d nn----%d\n",n,nn);
    d[n]=m;
    for(i=n+1;i<=nn;i++)
    d[i]=10*d[i-1];
    for(i=n-1;i>=1;i--)
    {
        d[i]=d[i+1]/10;
    }
    int64 ans=0;
    for(i=nn;i>=1;i--)
    {
        if(now<d[i])
        ans+=now-base[i]+1;
        else
        {
            ans+=d[i]-base[i];
            if(d[i]<=m)
            ans++;
        }
    }
    return ans;
}
int main()
{
    int64 bases;
    int64 i;
    base[1]=1;
    for(i=2;i<=20;i++)
    base[i]=10*base[i-1];
    for( bases=1,i=1;i<=18;bases*=10,i++)
    ;
    while(cin>>k>>m)
    {
        int64 now=m;
        for(i=1;;i++)
        {
            dig[i]=now%10;
            now/=10;
            if(now==0)
            break;
        }
        n=i;
        int64 r,l,mid,flag=0,ans;
        l=0;
        r=9*bases; 
        while(l<=r)
        {
            mid=(l+r)/2;
            int64 now=solve(mid);
            if(now==k)
            {
                flag=1;
                ans=mid;
                break;
            }
            else if(now<k)
                l=mid+1;
            else
            r=mid-1;
        }
        if(flag==1)
        cout<<ans<<endl;
        else
        cout<<0<<endl;
    }
    return 0;
}
                

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator