89 条题解

  • 4
    @ 2017-09-06 16:36:44
    n = int(raw_input())
    print int(bin(n).replace('1','0',1), 2)<<1|1
    
    • @ 2018-09-04 15:08:24

      这也太秀了吧,大神能讲讲原理吗?

  • 3
    @ 2018-11-04 20:59:17

    基本思路:
    1、减治法,找到递推公式
    2、字符串模拟
    设m为总人数,J(m)为最后存活编号,存在递推关系:
    J(m) = 2J(m/2)+-1,其中当m为偶数时-1,当m为奇数时+1。边界条件:J(1)=1.
    然后定义字符串的乘法、除法和+1、-1算法,利用递归函数即可求解。
    具体算法参照Levitin《算法设计与分析基础》

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    //int Joseph(int x)
    //{
    //    if (x == 1) return 1;
    //    else{
    //        if(x % 2) return 2 * Joseph(x/2) + 1;
    //        else return 2 * Joseph(x/2) - 1;
    //    }
    //}用整数来解释算法:基于递推的约瑟夫算法
    char* Div2(char x[], int n);//÷2算法
    char* Mult2(char x[], int n);//×2算法
    int ModEven(char c);   //判断是否为奇数
    char* Joseph(char x[], char cmp[], int n);//核心算法
    char* Min1(char x[], int n);//-1算法
    char* Plus1(char x[], int);//+1算法
    
    int main()
    {
        int n, p;
        char x[101] = {0};
        char *target;
        x[100] = '\0';
        gets(x);
        for(n = 0; x[n] != '\0'; n++); //n为位数
        char cmp[101] = {0};
        int i;
        for(i = 0; i < 100; i++){
            cmp[i] = '0';
        }
        cmp[n] = '\0'; cmp[n - 1] = '1';    //初始化比较字符串cmp
        target = Joseph(x, cmp, n);
        for(i = 0; i < n; i++){
            if(target[i] != '0') break;
        }
        for(p = i; p < n; p++){             //删除前面不需要的占位0
            printf("%c", target[p]);
        }
        printf("\n");
        return 0;
    }
    
    int ModEven(char c)
    {                                   // 判断该数是否为奇数
        int d = (c - '0') % 2;
        if (d) return 1;
        else return 0;
    }
    
    char* Mult2(char x[], int n)        //定义字符串乘以2的算法
    {
        int last, add = 0;   //最后一位的指标
        int unit;
        for(last = n - 1; last >= 0; last--){
            unit = 2 * (x[last] - '0');
            x[last] = unit % 10 + add + '0';
            if(unit > 9) add = 1;
            else add = 0;
        }
        return x;
    }
    
    char* Div2(char x[], int n)         //定义字符串除以2的算法
    {
        int first, pre = 0;
        int tmp;
        for(first = 0; first < n; first++){
            tmp = x[first] - '0';
            x[first] = (pre * 10 + x[first] - '0') / 2 + '0';
            pre = (pre*10 + tmp) % 2;
        }
        return x;
    }
    
    char* Joseph(char x[], char cmp[], int n)       //核心函数
    {
        char *tmp;
        char judgetmp;
        if(strcmp(cmp, x) == 0){
            return cmp;
            }//边界条件:J(1) = 1;
        else{
            judgetmp = x[n - 1];
            tmp = Mult2(Joseph(Div2(x, n), cmp, n), n);
            if(ModEven(judgetmp) == 0){
                return Min1(tmp, n);
            }
            if(ModEven(judgetmp) == 1){
                return Plus1(tmp, n);
            }
        }
        return x;
    }
    
    char* Min1(char x[], int n)                 //减一算法
    {
        int last = n - 1;
        if(x[last] == '0'){
            for(x[last] = '9'; last > 0;){
                if(x[--last] == '0'){
                    x[last] = '9';
                }
                else{
                    x[last] -= 1;
                    break;
                }
            }
        }else x[last] = x[last] - 1;
        return x;
    }
    
    char* Plus1(char x[], int n)            //加一算法
    {
        int last = n - 1;
        if(x[last] == '9'){
            for(x[last] = '0'; last >= 0;){
                if(x[--last] == '9'){
                    x[last] = '0';
                }
                else{
                    x[last] += 1;
                }
            }
        }
        else{
            x[last] += 1;
        }
        return x;
    }
    
    
  • 2
    @ 2017-08-18 10:32:25

    这个题实际上是有通项公式的,具体推导请看《具体数学》
    J(2^m+K)=2*K+1
    2^m+k是总人数,函数的结果是剩下的人的编号
    设总人数为n
    所以你只需要知道n展开成二进制之后的形式,并且把第一个“1”给置位成“0”
    那么得到的结果就是k了
    故:
    结果=2*(~(1<<(位数-1))&n)+1;

    import java.math.BigInteger;
    import java.util.Scanner;
    public class Main {
        static Scanner in = new Scanner(System.in);
        public static void main(String[] args) {
            BigInteger n;
            n=in.nextBigInteger();
            BigInteger i=BigInteger.valueOf(1).shiftLeft(n.bitLength()-1);
            BigInteger answer=i.not().and(n).multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1));
            System.out.println(answer);
        }
    }
    
    
  • 1
    @ 2018-08-04 07:06:22

    高精度+递推

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    string s;
    struct bignum {
        int len;
        int a[201];
        bignum() {
            len=0;
            memset(a,0,sizeof a);
        }
        void operator=(bignum x) {
            len=x.len;
            FOR(i,len) a[i]=x.a[i];
        }
        bool operator==(bignum x) {
            if (len!=x.len) return 0;
            FOR(i,len) if (a[i]!=x.a[i]) return 0;
            return 1;
        }
        bool operator<(bignum x) {
            if (len<x.len) return 1;
            else if (len>x.len) return 0;
            for (int i=len;i>=1;i--) {
                if (a[i]<x.a[i]) return 1;
                else if (a[i]>x.a[i]) return 0;
            }
            return 0;
        }
        bool operator<=(bignum x) {
            return (*this)<x||(*this)==x;
        }
        bignum operator+(bignum x) {
            bignum res;
            res.len=max(x.len,len);
            FOR(i,res.len) {
                res.a[i]+=a[i]+x.a[i];
                if (res.a[i]>9) {
                    res.a[i+1]+=res.a[i]/10;
                    res.a[i]%=10;
                }
            }
            if (res.a[res.len+1]) res.len++;
            return res;
        }
        bignum operator-(bignum x) {
            bignum res;
            res.len=max(x.len,len);
            FOR(i,res.len) res.a[i]=a[i]-x.a[i];
            FOR(i,res.len) {
                if (res.a[i]<0) {
                    res.a[i+1]--;
                    res.a[i]+=10;
                }
            }
            while (res.len>1&&!res.a[res.len]) res.len--;
            return res;
        }
        bignum operator*(bignum x) {
            bignum res;
            res.len=len+x.len-1;
            FOR(i,len) FOR(j,x.len) {
                res.a[i+j-1]+=a[i]*x.a[j];
            }
            FOR(i,res.len) {
                if (res.a[i]>9) {
                    res.a[i+1]+=res.a[i]/10;
                    res.a[i]%=10;
                }
            }
            if (res.a[res.len+1]) res.len++;
            return res;
        }
        bignum operator/(bignum x);
        
    } ten[101],num[10];
    bignum bignum::operator/(bignum x) {
        // 要保证能整除 
        bignum res,tmp;
        res.len=tmp.len=1;
        for (int i=100;i>=0;i--) {
            for (int j=9;j>=1;j--) {
                if (x*(tmp+ten[i]*num[j])<=(*this)) {
                    tmp=tmp+ten[i]*num[j];
                    res.a[i+1]=j;
                    res.len=max(res.len,i+1);
                    break;
                }
            }
        }
        return res;
    }
    void print(bignum x) {
        for (int i=x.len;i>=1;i--) cout<<x.a[i];
        cout<<endl;
    }
    bignum f(bignum x,int k) {
        if (x==num[1]) return num[1];
        if (k==0) {
            if (x.a[1]%2==0) {
                return num[2]*f(x/num[2],0)-num[1];
            } else {
                return num[2]*f((x+num[1])/num[2],1)-num[1];
            }
        } else {
            return f(x-num[1],0)+num[1];
        }
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        REP(i,0,9) num[i].len=1,num[i].a[1]=i;
        ten[0].len=1,ten[0].a[1]=1;
        ten[1].len=2,ten[1].a[1]=0,ten[1].a[2]=1;
        REP(i,2,100) ten[i]=ten[i-1]*ten[1];
    
        string s2;
        cin>>s;
        //cin>>s2;
        bignum x,y;
        x.len=s.size();
        //y.len=s2.size();
        for (int i=0;i<s.size();i++) x.a[x.len-i]=s[i]-'0';
        //for (int i=0;i<s2.size();i++) y.a[y.len-i]=s2[i]-'0';
        print(f(x,0));
        return 0;
    }
    
  • 1
    @ 2018-04-19 14:36:00

    公式就不多说了,各位大佬已经说得很明白了
    不过本题高精度实在是恶心,再加上我并不是特别熟练,代码写了170+行,有些地方有些冗杂
    上代码:

    #include <iostream>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <memory.h>
    using namespace std;
    
    class BigInt{
    public:
        int *a;
        int len;
    public:
        BigInt(){}
        BigInt(string s){
            this->len = s.length();
            a = new int[len+1];
            for (int i = 1; i <= len; ++i)
                a[i] = s[len - i] - '0';
            a[0] = 0;
        }
        BigInt(int n){
            this->len = n;
            a = new int[n+1];
            memset(a,0, sizeof(a));
        }
        void show(){
            int k = len;
            while(a[k] == 0)
                k--;
            for (int i = k; i >= 1; --i) {
                cout << a[i];
            }
            cout << endl;
        }
        BigInt operator /(int b){
            BigInt r(len);
            for (int i = 1; i <= len; ++i) {
                r.a[i] = a[i];
            }
            int m;
            for (int i = r.len; i >= 1; --i) {
                m = r.a[i] % b;
                r.a[i] /= b;
                r.a[i-1] += m*10;
            }
            r.a[0] = m;
            int n = 0;
            for (int k = len; r.a[k] == 0 ; k--) {
                n++;
            }
            r.len -= n;
            return r;
        }
        int operator %(int b){
            BigInt r(len);
            for (int i = 1; i <= len; ++i) {
                r.a[i] = a[i];
            }
            r = r / b;
            return r.a[0];
        }
        BigInt operator +(BigInt b){
            int l = max(this->len , b.len);
            BigInt n1(l);
            BigInt n2;
            for (int i = 0; i <= l; ++i) {
                n1.a[i] = 0;
            }
            if(l == this->len)
            {
                for (int i = 1; i <= b.len; ++i) {
                    n1.a[i] = b.a[i];
                }
                n2 = *this;
            }
            else{
                for (int i = 1; i <= this->len; ++i) {
                    n1.a[i] = this->a[i];
                }
                n2 = b;
            }
            BigInt c(l+1);
            for (int i = 1; i <= l+1; ++i) {
                c.a[i] = 0;
            }
            for (int i = 1; i <= l; ++i) {
                c.a[i] += n1.a[i] + n2.a[i];
                c.a[i+1] += c.a[i] / 10;
                c.a[i] %= 10;
            }
            if(c.a[l+1] == 0)
                c.len --;
            return c;
        }
        BigInt operator *(int b){
            BigInt r(len+1);
            r.a[len+1] = 0;
            for (int i = 1; i <= len; ++i) {
                r.a[i] = a[i];
            }
            for (int i = 1; i <= len; ++i) {
                r.a[i] *= b;
            }
            for (int i = 1; i <= len; ++i) {
                r.a[i+1] += r.a[i] / 10;
                r.a[i] %= 10;
            }
            if(r.a[len+1] == 0)
                r.len --;
            return r;
        }
        bool operator >(BigInt n){
            if(this->len > n.len)
                return true;
            for (int i = len; i >= 1; --i) {
                if(this->a[i] == n.a[i])
                    continue;
                return this->a[i] > n.a[i]?true:false;
            }
        }
    };
    
    BigInt pow(int a,int n){
        BigInt r("1");
        for (int i = 0; i < n; ++i) {
            r = r*a;
        }
        return r;
    }
    
    BigInt to_binary(BigInt n){
        queue<int> q;
        int m;
        while(n.len > 0) {
            m = n % 2;
            q.push(m);
            n = n / 2;
        }
        int len = q.size();
        BigInt r(len);
        for (int i = 1; i <= len; ++i) {
            r.a[i] = q.front();
            q.pop();
        }
        return r;
    }
    
    BigInt to_demcital(BigInt n){
        BigInt r("0");
        for (int i = 1; i <= n.len; ++i) {
            r = r + pow(2,i-1) * n.a[i];
        }
        return r;
    }
    
    int main()
    {
        string s;
        cin >> s;
        BigInt a(s);
        BigInt b = to_binary(a);
        for (int i = b.len; i >= 1; --i) {
            if(b.a[i] == 1){
                b.a[i] = 0;
                break;
            }
        }
        BigInt ans = to_demcital(b);
        ans = ans * 2;
        ans.a[1]++;
        ans.show();
    
        return 0;
    }
    
  • 1
    @ 2017-10-10 21:13:46

    公式为:ans=2*(n-2^k)+1(k为使2^k小于n的最大整数)
    使用高精度加减乘运算以上公式即可。
    公式由来:当n为2的整数倍时,最后留下的人一定是1;
    当n不为2的整数倍时,设n=2^k+t(任何一个正整数都可以用2^k+t(t为任意正整数)来表示),
    即去掉t个人后为n=2的整数倍情况,而每一次去掉第m(m<=t)的人的编号为2*m(报到2的出列),
    所以方程移项再加1即为所求ans。
    整个公式就推出来了。

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    const int maxn=101;

    int l=1,len;
    int a[maxn],t[maxn];
    string s;

    bool cmp()
    {
    int f=1;
    if(l<len)
    return true;
    if(l>len)
    return false;
    for(int i=len;i>=1;i--)
    {
    if(t[i]<a[i])
    return true;
    if(t[i]>a[i])
    return false;
    if((t[i]==a[i])&&(i==1))
    return true;
    }
    }

    void cf()
    {
    for(int i=1;i<=l;i++)
    t[i]=2*t[i];
    for(int i=1;i<=l;i++)
    {
    if(t[i]>=10)
    {
    t[i+1]+=t[i]/10;
    t[i]%=10;
    }
    }
    if(t[l+1]>0)
    l++;
    }

    void add()
    {
    a[1]+=1;
    for(int i=1;i<=len;i++)
    if(a[i]>=10)
    {
    a[i+1]+=a[i]/10;
    a[i]%=10;
    }
    if(a[len+1]>0)
    len++;
    }

    void jf()
    {
    for(int i=1;i<=len;i++)
    {
    if(a[i]<t[i])
    {
    a[i+1]--;
    a[i]+=10;
    }
    a[i]=a[i]-t[i];
    }
    if(a[len]==0)
    len--;
    }

    main()
    {
    memset(a,0,sizeof(a));
    memset(t,0,sizeof(t));
    cin>>s;
    len=s.size() ;
    for(int i=0;i<len;i++)
    a[len-i]=s[i]-'0';
    if((len==1)&&(a[1]<=2))
    cout<<'1'<<endl;
    else if((len==1)&&(a[1]==3))
    cout<<'3'<<endl;
    else
    {
    t[1]=2;
    while(1)
    {
    cf();
    if(!cmp())
    break;
    }
    for(int i=1;i<=len;i++)
    a[i]=a[i]*2;
    for(int i=1;i<=len;i++)
    if(a[i]>=10)
    {
    a[i+1]+=a[i]/10;
    a[i]%=10;
    }
    if(a[len+1]>0)
    len++;
    jf();
    add();
    while(a[len]==0)
    len--;
    for(int i=len;i>=1;i--)
    cout<<a[i];
    cout<<endl;
    }
    return 0;
    }

  • 0
    @ 2018-04-10 20:10:55

    从1开始手推大概十几个就能摸索出规律了,把N变成二进制后,去掉首位,余下部分乘2加1就ok。

    #include <stdio.h>
    #include <string.h>
    
    char tpc;
    int idx;
    int a[400],bin[400];
    
    bool scancheck(char x);
    void getBinary(int x[400],int bin[400]);
    void overturn(int x[400]);
    void getTen(int bin[400],int a[400]);
    void incTen(int a[400],int tp[400]);
    
    
    int main(){
        
        while (true){
            scanf("%c",&tpc);
            if (!scancheck(tpc)) break;
            idx++;
            a[idx]=tpc-'0';
        }
        a[0]= idx;
        overturn(a);
        getBinary(a,bin);   
        
        if (bin[0]==1){
            printf("%d",1);
            return 0;
        }
        bin[bin[0]]=0;
        bool flag=false;
        while((bin[bin[0]]==0)&&(!flag)) {
            bin[0]--;
            if (bin[0]==0) flag=true;
        }
        if (flag) bin[0]=1;
        bin[0]++;
        for (int i=bin[0];i>1;i--) bin[i]=bin[i-1];
        bin[1]=1;
        
        getTen(bin,a);
        
        for (int i=a[0];i>0;i--) printf("%d",a[i]);
        
        return 0;
        
    } 
    
    bool scancheck(char x){
        if (x>'9') return false;
        if (x<'0') return false;
        return true;
    }
    
    void getBinary(int a[400],int bin[400]){
        //memset(bin,0,sizeof(bin));
        bool flag=false;
        int idx=0;
        while (!flag){
            idx++;
            bin[idx]=a[1]%2;
            for (int i=a[0];i>0;i--){
                if (a[i]%2==1) a[i-1]+=10;
                a[i]/=2;
            }
            while ((a[a[0]]==0)&&(!flag)) {
                a[0]--;
                if (a[0]==0) flag=true;
            }
        }
        bin[0]=idx; 
        return;
    }
    
    void getTen(int bin[400],int a[400]){
        memset(a,0,sizeof(a));
        int tp[400];
        memset(tp,0,sizeof(tp));
        tp[0]=1; tp[1]=1;
        int idx=0;
        while (true){
            idx++;
            if (bin[idx]==1) incTen(a,tp);  
            
            if (idx==bin[0]) break;
            for (int i=1;i<=tp[0];i++) tp[i]*=2;
            for (int i=1;i<=tp[0];i++){
                if (tp[i]>9){
                    tp[i+1]++;
                    tp[i]-=10;
                }
            }
            if (tp[tp[0]+1]>0) tp[0]++; 
        }
        return;
    }
    
    void incTen(int a[400],int tp[400]){
        int maxLen=a[0]>tp[0]?a[0]:tp[0];
        for (int i=1;i<=maxLen;i++) {
            a[i]+=tp[i];
            if (a[i]>9){
                a[i+1]++;
                a[i]-=10;
            }
        }
        a[0]=maxLen;
        if (a[a[0]+1]>0) a[0]++;
        return;
    }
    
    void overturn(int x[400]){
        int y[400];
        for (int i=1;i<=x[0];i++) y[i]=x[x[0]+1-i];
        y[0]=x[0];
        for (int i=0;i<=y[0];i++) x[i]=y[i];
        return;
    }
    
  • 0
    @ 2017-11-04 14:46:29

    额啊,虽然说我很蒟蒻,但是我恶心的代码居然过了。。开心
    注意公式Ans=2*(n-2^k)+1 其中 2^k<=n<2^(k+1)
    恶心的高精度
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    char st[1005];
    int k[100005],t[100005],a[100005],n;
    bool com()
    {
    if (a[0]>k[0]) return true;
    if (k[0]>a[0]) return false;
    if (a[0]==k[0])
    for (int i=1; i<=a[0]; i++) if (a[i]<k[i+1]) return false; else if (a[i]>k[i+1]) return true;
    }
    void cheng()
    {
    int l=n+1,x=0;
    for (int i=0; i<=l; i++) t[i]=k[i];
    for (int i=l; i>=l-k[0]+1; i--) {
    k[i]=k[i]*2+x;
    x=k[i]/10;
    k[i]%=10;
    }
    while (x>0) {
    k[0]++; k[l-k[0]+1]=x%10; x/=10;
    }
    }
    void jian()
    {
    for (int i=n; i>=1; i--) {
    k[i+1]+=a[i]-t[i+1];
    if (k[i+1]<0) k[i+1]+=10,k[i]--;
    k[i]+=k[i+1]/10;
    k[i+1]%=10;
    }
    k[0]=n+1; int i=1;
    while (k[i]==0 && k[0]>0) i++,k[0]--;
    }
    int main()
    {
    gets(st+1);
    n=strlen(st+1);
    for (int i=1; i<=n; i++) a[i]=st[i]-48;
    a[0]=n;
    k[0]=1; k[n+1]=1;
    while (com()){
    cheng();
    }
    memset(k,0,sizeof(k));
    jian();
    cheng();
    k[n+1]++;
    int i=n+1;
    while (k[i]>9) k[i-1]+=k[i]/10,k[i]%=10,i--;
    while (k[n-k[0]+1]!=0) k[0]++;
    for (int i=n+2-k[0]; i<=n+1; i++) printf("%d",k[i]);
    return 0;
    }

  • 0
    @ 2017-07-26 01:32:03

    犯了个很蠢的错误,调试了半天……
    很有意思的题目,不知道谁能把这个题目的规律证明一下- -
    感觉写的代码思路比较清晰,很好看
    cpp
    #include <iostream>
    #include <string>
    #include <cmath>
    #include <cstring>
    using namespace std;
    const long mod=100000000;
    const long d=8;
    const long list[]={1,10,100,1000,10000,100000,1000000,10000000};
    struct gjd{
    long num[102],n;
    } a,b1,b2,c;
    gjd multi_two(gjd x)
    {
    long g,i;
    g=0;
    for (i=1;i<=x.n;i++){
    x.num[i]=x.num[i]*2+g;
    g=x.num[i]/mod;
    x.num[i]%=mod;
    }
    if (g>0) {x.n++; x.num[x.n]=g;}
    return x;
    }
    bool compare(gjd t1,gjd t2) //To judge whether t1 bigger than t2, if it is, return true, else return false.
    {
    long i;
    if (t1.n>t2.n) return true;
    else if (t1.n<t2.n) return false;
    else {
    for (i=t1.n;i>=1;i--){
    if (t1.num[i]>t2.num[i]) return true;
    else if (t1.num[i]<t2.num[i]) return false;
    }
    return false;
    }
    }
    gjd _minus(gjd x,gjd y){
    long i;
    for (i=1;i<=x.n;i++){
    x.num[i]-=y.num[i];
    if (x.num[i]<0) {x.num[i]+=mod; x.num[i+1]--;}
    }
    if (x.num[x.n]==0) x.n--;
    return x;
    }
    gjd _add(gjd x,gjd y){
    gjd t;
    long g,i,len;
    if (x.n>y.n) len=x.n;
    else len=y.n;
    g=0;
    for (i=1;i<=len;i++){
    t.num[i]=x.num[i]+y.num[i]+g;
    g=t.num[i]/mod;
    t.num[i]%=mod;
    }
    t.n=len;
    if (g>0) {t.n++; t.num[t.n]=g;}
    return t;
    }
    main()
    {
    long i,j,len;
    string t;
    cin>>t;
    len=t.size();
    for (i=0;i<len;i++){
    if (i%d==0) a.n++;
    a.num[a.n]=(t[len-i-1]-'0')*list[i%d]+a.num[a.n];
    }
    memset(b1.num,0,sizeof(b1.num));
    b1.n=1;
    b2=b1;
    b1.num[1]=1;
    c=b1;
    while (compare(a,b1)){
    b2=b1;
    c=multi_two(c);
    b1=_add(b1,c);
    }
    b1=_minus(a,b2);
    b2=multi_two(b1);
    b2.num[1]--;
    i=1;
    while (b2.num[i]<0){
    b2.num[i]+=mod;
    i++;
    b2.num[i]--;
    }
    if (b2.num[b2.n]==0) b2.n--;
    cout<<b2.num[b2.n];
    for (i=b2.n-1;i>=1;i--){
    if (b2.num[i]==0) len=7;
    else len=7-long (log10(b2.num[i]));
    for (j=1;j<=len;j++) cout<<0;
    cout<<b2.num[i];
    }
    }

  • 0
    @ 2017-02-21 11:46:23

    手写了会 发现了个规律 如果有错误欢迎大佬指正
    除了n=1时 特判输出1
    当 2^i <= n <= 2^(i+1) 时
    输出 (n-2^i)*2+1
    不过还没代码实现

  • 0
    @ 2016-11-17 20:22:01

    #include <cstdio>
    #include <cstring>
    #define Q 1000
    #define clear(a) memset(a,0,Q*sizeof(int))

    void input(int a[]){
    clear(a);
    char c[120];
    scanf("%s",c);
    int len=1,k=1;
    for(int i=strlen(c)-1;i>=0;i--){
    if(k==10000)
    k=1,len++;
    a[len]+=k*(c[i]-'0');
    k*=10;
    }
    a[0]=len;
    }

    void f2(int a[]){
    int c[Q],len=a[0]+1;
    clear(c);
    for(int i=1;i<=len;i++){
    c[i]+=a[i]+a[i];
    c[i+1]+=c[i]/10000;
    c[i]%=10000;
    }
    while(len>1&&c[len]==0)len--;
    c[0]=len;
    memcpy(a,c,Q*sizeof(int));
    }

    void minus(int a[],int b[]){
    for(int i=1;i<=a[0];i++){
    if(a[i]>=b[i])
    a[i]-=b[i];
    else
    a[i]+=10000-b[i],a[i+1]-=1;
    }
    int len=a[0];
    while(len>1&&a[len]==0)len--;
    a[0]=len;
    }

    void output(int a[]){
    printf("%d",a[a[0]]);
    for(int i=a[0]-1;i>=1;i--)
    printf("%04d",a[i]);
    }

    int big(int a[],int b[]){
    if(a[0]!=b[0])
    return a[0]>b[0];
    for(int i=a[0];i>=1;i--)
    if(a[i]!=b[i])
    return a[i]>b[i];
    return 0;
    }

    int main(){
    int x[Q],x1[Q]={1,1},x2[Q]={1,2},q[Q]={1,1};
    input(x);
    while(1){
    if(big(x2,x)){
    minus(x1,q);
    minus(x,x1);
    f2(x);
    minus(x,q);
    output(x);
    return 0;
    }
    f2(x1);
    f2(x2);
    }
    return 0;
    }

  • 0
    @ 2016-08-09 23:36:07
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    string str;
    int start[600],ans[600],res[600];
    int oldBase, newBase;
    void change(string str)
    {
        int i,len = str.size();
        start[0] = len;
        for(i=1;i<= len;i++)
        {
            if(str[i-1] >= '0' && str[i-1] <= '9')
            {
                start[i] = str[i-1] - '0';
            }
        }
    }
    
    void solve()
    {
        memset(res,0,sizeof(res));
        int y,i,j;
        while(start[0] >= 1)
        {
            y=0;
            i=1;
            ans[0]=start[0];
            while(i <= start[0])
            {
                y = y * oldBase + start[i];
                ans[i++] = y/newBase;
                y %= newBase;
            }
            res[++res[0]] = y;
            i = 1;
            while((i<=ans[0]) && (ans[i]==0)) i++;
            memset(start,0,sizeof(start));
            for(j = i;j <= ans[0];j++)
                start[++start[0]] = ans[j];
            memset(ans,0,sizeof(ans));
        }
    }
    
    void output()
    {
        int i;
        for(i = res[0];i >= 1;--i)
            cout << res[i];
    }
    
    void convert(){
        int i;
        str="";
        for (i=res[0]-1;i>=1;--i) str+=res[i]+'0';
        str+=res[res[0]]+'0';
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin >> str;
        oldBase=10;
        newBase=2;
        change(str);
        solve();
        convert();
        oldBase=2;
        newBase=10;
        change(str);
        solve();
        output();
        return 0;
    }
    
    

    测试数据 #0: Accepted, time = 0 ms, mem = 584 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 584 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 584 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 584 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    Accepted, time = 0 ms, mem = 584 KiB, score = 100
    去你大爷的高精度!!!改了半个小时才改出个丑陋的程序,但好歹是0ms的!!!

  • 0
    @ 2016-07-15 20:22:55

    首先我写了一个程序,就想过3个点。
    提交了后,我又想着打个表试试,说不定能得些分。
    然后把程序挂起,打了个表,结果发现了规律。
    部分表:
    //--------------------------------------------------------------------
    1,
    1,3,
    1,3,5,7,
    1,3,5,7,9,11,13,15,
    1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,
    1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,
    //---------------------------------------------------------------------
    发现第一行1,第二行2个,第三行4个。第n行2^(n-1)个
    第n行开头为第2^(n-1)个数
    每行第k个数的值为2*k-1

    思路:
    高精度x低精度,每次乘完,比较一次n与上一行末尾的数、n与下一行开头的数的大小
    得到n在不在该行中,不在就继续乘
    如果在该行中,那么n就是该行第(n-上一行末尾的序号)个(高精度减法)
    然后2k-1 得到结果 (高精度减法,乘法)
    注:计算上一行末尾,即(2^n)-1时,直接在a[1] 减1即可。因为2的乘方末尾最小为2

    代码
    ```c++
    #include <cstdio>
    #include <cstring>

    int bigger(int a[],int b[]){
    if(a[0]!=b[0])
    return a[0]>b[0];
    int flag=999;
    for(int i=a[0];i>=1;i--)
    if(a[i]!=b[i]){
    flag=a[i]>b[i];
    break;
    }
    if(flag==999)
    return 0;
    return flag;
    }

    int read(int a[]){
    char c[1000];
    scanf("%s",c);
    int n=1,len=strlen(c),k=1;
    for(int i=0;i<len;i++){
    if(k==10000){
    k=1;
    n++;
    }
    a[n]+=k*(c[len-i-1]-'0');
    k*=10;
    }
    a[0]=n;
    }

    int addx(int a[],int b[],int c[]){
    int len=a[0]>b[0]?a[0]:b[0];
    for(int i=1;i<=len;i++){
    c[i]+=a[i]+b[i];
    c[i+1]+=c[i]/10000;
    c[i]%=10000;
    }
    len++;
    while(c[len]==0&&len>1)
    len--;
    c[0]=len;
    }

    int minusx(int a[],int b[],int c[]){
    int len=a[0];
    for(int i=1;i<=len;i++){
    c[i]+=a[i]-b[i];
    if(c[i]<0){
    c[i]+=10000;
    c[i+1]-=1;
    }
    }
    while(c[len]==0&&len>1)
    len--;
    c[0]=len;
    }

    void mult(int a[],int x){
    int len,temp,k=0;
    for(int i=1;i<=a[0]||k;i++){
    temp=a[i]*x+k;
    k=temp/10000;
    a[i]=temp%10000;
    len=i;
    }
    while(a[len]==0&&len>1)
    len--;
    a[0]=len;
    }

    void output(int a[]){
    printf("%d",a[a[0]]);
    for(int i=a[0]-1;i>=1;i--)
    printf("%04d",a[i]);
    }

    int main(){
    int n[100]={0};
    read(n);
    int flag;
    int temp[100],base[100]={1,1};
    while(1){
    flag=1;
    base[1]--;
    flag*=bigger(n,base);
    base[1]++;
    memcpy(temp,base,sizeof(temp));//存放上一次

    mult(base,2);
    flag*=bigger(base,n);
    if(flag)
    break;
    }
    int c[100]={0};
    temp[1]--;
    minusx(n,temp,c);
    mult(c,2);
    int m[100]={1,1};
    memset(temp,0,sizeof(temp));
    minusx(c,m,temp);
    output(temp);
    return 0;
    }

    **附上打表代码**
    c++
    #include <cstdio>
    #include <ctime>
    #include <cstring>

    int vis[10001]={0};

    int main(){
    freopen("output.txt","w",stdout);
    for(int z=1;z<=10000;z++){
    memset(vis,0,sizeof(vis));
    int n,count=0;
    n=z;
    int now=1,next=1,kill=0;
    while(count<n-1){
    do
    next=(next-1+1)%n+1;
    while(vis[next]);
    if(kill){
    count++;
    vis[now]=1;
    kill=0;
    }
    else
    kill=1;
    now=next;
    }
    for(int i=1;i<=n;i++)
    if(!vis[i])
    printf("%d,",i);
    }
    return 0;
    }
    ```

  • 0
    @ 2016-06-22 21:09:04

    鄙人高精不好请见谅。。。
    测试数据 #0: Accepted, time = 0 ms, mem = 808 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 808 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 808 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 808 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    Accepted, time = 0 ms, mem = 808 KiB, score = 100
    -------------------------------华丽的分割线-------------------------------
    ``` pascal
    type int=longint;
    var
    s:string;
    i,ls,t,f:int;
    a,b,c:array[0..110]of int;
    ff:boolean;
    procedure double;
    var
    i:int;
    begin
    for i:=1 to ls+1 do
    begin
    a[i]:=b[i];
    b[i]:=0;
    end;
    for i:=1 to ls+1 do
    begin
    b[i]:=b[i]+a[i]*2;
    if b[i]>=10 then
    begin
    b[i+1]:=b[i+1]+(b[i] div 10);
    b[i]:=b[i] mod 10;
    end;
    end;
    end;

    begin
    readln(s); ls:=length(s);
    for i:=1 to ls do val(s[ls+1-i],c[i]);
    b[1]:=1; f:=0; ff:=true;
    repeat
    double;
    until (b[ls]>=c[ls]) or (b[ls+1]>0);
    if (b[ls]=c[ls]) and (b[ls+1]=0) then
    for i:=ls-1 downto 1 do if b[i]>c[i] then
    begin
    f:=1;
    break;
    end else if b[i]<c[i] then
    begin
    f:=2;
    break;
    end;
    for i:=1 to ls do if b[i]<>c[i] then ff:=false;
    if ff then
    begin
    writeln(1);
    halt;
    end;
    if f=2 then for i:=1 to ls+1 do a[i]:=b[i];
    fillchar(b,sizeof(b),0);
    for i:=1 to ls+1 do if c[i]<a[i] then
    begin
    b[i]:=c[i]+10-a[i];
    dec(c[i+1]);
    end else b[i]:=c[i]-a[i];
    double;
    inc(b[1]);
    for i:=1 to ls+1 do if b[i]>=10 then
    begin
    b[i+1]:=b[i+1]+(b[i] div 10);
    b[i]:=b[i] mod 10;
    end;
    t:=ls+2;
    while b[t]<=0 do dec(t);
    for i:=t downto 1 do write(b[i]);
    writeln;
    readln;
    end.
    ```
    健全的灵魂,寄宿生在健全的精神上,和健全的肉体上!!!

  • 0
    @ 2016-05-09 13:21:12

    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int N=100+5;
    int a[N],b[N]={0},c[N]={1,2},ans[N];
    char ss[N];
    bool pd(int h1[],int h2[]) //如果h1的数<=h2 则返回true

    {
    if(h1[0]<h2[0]) return true;
    if(h1[0]>h2[0]) return false;
    for(int i=h1[0];i>=1;i--)

    if(h1[i]==h2[i]) continue;
    else return h1[i]>h2[i]?false:true;
    return true;
    }
    void turn_over()
    {
    int len=strlen(ss);
    for(int i=0;i<len;i++)
    a[i+1]=ss[len-i-1]-'0';
    a[0]=len;
    }
    void mul(int s[])
    {
    for(int i=1;i<=b[0];i++) s[i]*=2;
    for(int i=1;i<=s[0]+1;i++)
    {s[i+1]+=s[i]/10;s[i]%=10;}
    if(s[s[0]+1]) s[0]++;
    }
    void take()
    {
    for(int i=1;i<=a[0];i++)
    {
    if(a[i]<b[i]) {a[i]+=10;a[i+1]--; }
    ans[i]=a[i]-b[i];
    }
    int i;
    for(i=a[0]+1;ans[i]==0;i--); if(i<=0) i=1; ans[0]=i;
    }
    void add()
    {
    ans[1]++;
    for(int i=1;i<=ans[0]+1;i++)
    {ans[i+1]+=ans[i]/10;ans[i]%=10;}
    if(ans[ans[0]+1]) ans[0]++;
    }
    int main()
    {
    scanf("%s",ss);
    if(ss[0]=='1' && strlen(ss)==1) {printf("1");return 0; }
    turn_over();
    while(pd(b,a) && pd(c,a))
    {
    memcpy(b,c,sizeof(b));
    mul(c);
    }
    take(); mul(ans);add();
    for(int i=ans[0];i>=1;i--) printf("%d",ans[i]);
    return 0;
    }

  • 0
    @ 2016-04-02 21:17:20

    通过一个模拟的程序找到了规律
    设数列 an,a1=3,an=2*a(n-1)+1 .(递归定义,方便代码实现)
    输入t
    如果 t<=3 直接输出结果就好了
    否则 找出这样的i,使得ai<n<=a(i+1)
    ans = (n-ai)*2 - 1;

    c++代码:
    #include<bits/stdc++.h>
    using namespace std;
    struct BN{
    int len,s[205];
    BN(){
    len = 0;
    memset(s,0,sizeof(s));
    }
    BN operator -(const BN &x) const
    {
    BN y;
    y.len = len;
    for (int i = 1;i <= len;i++)
    {
    y.s[i] += s[i] - x.s[i];
    if (y.s[i] < 0)
    y.s[i] += 10,y.s[i+1] --;
    }
    while (y.s[y.len] == 0&&y.len > 1) y.len--;
    return y;
    }
    bool operator >=(const BN &x) const
    {
    if (len != x.len) return len > x.len;
    for (int i = len;i >= 1;i--)
    if (s[i] != x.s[i]) return s[i] > x.s[i];
    return true;
    }
    }a[400];
    BN mul2(const BN &x)
    {
    BN y;
    y.len = x.len;
    for (int i = 1;i <= y.len; i++)
    {
    y.s[i] += x.s[i] * 2;
    if (y.s[i] > 9) y.s[i] -= 10,y.s[i+1] ++;
    }
    if (y.s[y.len+1]) y.len++;
    return y;
    }
    BN convert(string s)
    {
    BN y;
    y.len = s.length();
    for (int i = 0;i < y.len;i++)
    y.s[y.len - i] = s[i] - '0';
    return y;
    }
    void plus1(BN &y)
    {
    y.s[1] ++;
    for (int i = 1;y.s[i] >= 10;i++)
    y.s[i] -= 10,y.s[i+1] ++;
    if (y.s[y.len+1] != 0) y.len++;
    }
    void minus1(BN &y)
    {
    y.s[1] --;
    for (int i = 1;y.s[i] < 0;i++)
    y.s[i] += 10, y.s[i+1] --;
    if (y.s[y.len] == 0) y.len--;
    }
    void print(const BN &y)
    {
    for (int i = y.len;i >= 1;i--)
    cout << y.s[i];
    cout << endl;
    }
    int main()
    {
    int i;
    string s;
    BN n,ans;
    cin >> s;
    n = convert(s);

    if (n.len == 1 && n.s[1] <= 3)
    {
    if (n.s[1] <= 2) cout << 1 << endl;
    else cout << 3 << endl;
    return 0;
    }

    a[0].len = 1,a[0].s[1] = 3;
    for ( i = 1;;i++)
    {
    a[i] = mul2(a[i-1]);
    plus1(a[i]);
    if (a[i] >= n) break;
    }
    i--;
    ans = mul2(n - a[i]) ;
    minus1(ans);
    print(ans);
    return 0;
    }
    代码实现不难,主要是高精度
    注意高精度声明时要初始化所有位上的数字为0,要不然进位会有问题(这点坑死我了!!)
    还有 谁能严格证明或者不用归纳法直接推导出这个规律?有的回复一下谢谢

  • 0
    @ 2016-03-03 14:02:39

    python万岁。参见楼下公式,不会证明,只能找规律...

    n = int(raw_input())
    left = 0
    right = 1000
    while left < right-1:
    mid = (left+right)/2
    if 2**mid > n:
    right = mid-1
    else:
    left = mid
    if 2**right <= n:
    k = right
    else:
    k = left
    print 2*(n-2**k)+1

  • 0
    @ 2016-03-01 14:44:21

    当M=2时约瑟夫问题的解:
    求出不大于N的最大的2的整数次幂,记为2^k,最后一个去死的人是2(N-2^k)+1

    import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            BigInteger x = in.nextBigInteger();
            StringBuffer res = new StringBuffer(x.toString(2));
            res.deleteCharAt(0);
            res.append("0");
            x = new BigInteger(res.toString(),2);
            System.out.println(x.add(BigInteger.ONE));
            in.close();
        }
    }
    
    • @ 2016-08-09 23:13:40

      最后一个去死的人。。。你这话讲的

  • 0
    @ 2015-07-27 10:54:51

    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:39:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<=strlen(s)-1;i++)
    ^
    测试数据 #0: Accepted, time = 0 ms, mem = 388 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 384 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 388 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 384 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 384 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 384 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 384 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 388 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 384 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 384 KiB, score = 10
    Accepted, time = 30 ms, mem = 388 KiB, score = 100

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    char s[1100];
    int num10[1100]; //存10十进制数
    int num2[20100]; //存2进制数
    int num_2[5010]; //存2的多次方
    int max_2=1;
    int ans[1100];
    int maxans=1;
    void aplus()
    {
    int in=0,i;
    for(i=1;i<=max_2||in;i++)
    {
    ans[i]+=num_2[i]+in;
    in=ans[i]/10;
    ans[i]%=10;
    }
    maxans=max(maxans,i-1);
    }
    void multiply()
    {
    int in=0,i;
    for(i=1;i<=max_2||in;i++)
    {
    num_2[i]*=2;
    num_2[i]+=in;
    in=num_2[i]/10;
    num_2[i]%=10;
    }
    max_2=max(max_2,i-1);
    }
    int main()
    {
    scanf("%s",s);
    for(int i=0;i<=strlen(s)-1;i++)
    num10[i+1]=s[strlen(s)-1-i]-'0';
    int now=1,maxnow=strlen(s);
    for(;maxnow;)
    {
    if(num10[1]%2==0)
    num2[now++]=0;
    else num2[now++]=1;
    int next=0;
    int k=1;
    for(int i=maxnow;i>0;i--)
    {
    if(num10[i]==1&&i==maxnow&&k)
    {
    k=0;
    next=10;
    maxnow--;
    continue;
    }
    num10[i]+=next;
    next=num10[i]%2*10;
    num10[i]/=2;

    }
    }
    now-=2;
    for(;now>0&&!num2[now];now--);
    for(int i=now;i>0;i--)
    num2[i+1]=num2[i];
    num2[1]=1;
    now++;
    num_2[1]=1;
    for(int i=1;i<=now;i++)
    {
    if(num2[i]==1)
    aplus();
    multiply();
    }
    for(int i=maxans;i>0;i--)
    printf("%d",ans[i]);
    }

  • 0
    @ 2010-07-25 21:15:55

    又一个81行……

    第n个数:n=2^m-x;

    则结果就是:2*x+1;

    找与n最接近的2的整数次幂数,再两个数相减,外加一些7788的计算,就AC乐!

信息

ID
1095
难度
6
分类
其他 | 数学 点击显示
标签
(无)
递交数
2092
已通过
596
通过率
28%
上传者