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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

将a串和b串 与 a+b 用一样的方式处理(二分值+标记位置),扫描表示方式还是会不唯一

Posted by 2861077568 at 2019-01-03 13:29:32 on Problem 2116
#include <cstdio>
#include <cstring>
#include <string.h>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
char a[100],b[100];
ll f[70];
int vc[100],va[100],vb[100];
void init()
{
    f[0] = 1,f[1] = 2;
    for(int i = 2; i < 65; ++i)
        f[i] = f[i-1] + f[i-2];
}
void StrReverse(char s[])
{
    int r = strlen(s)-1;
    int l = 0;
    while(l<r) swap(s[l++],s[r--]);
}
int main()
{
    init();
    while(~scanf("%s %s",a,b))
    {
        memset(va,0,sizeof(va));
        memset(vb,0,sizeof(vb));
        memset(vc,0,sizeof(vc));
        ll c = 0,aa = 0,bb = 0;
        StrReverse(a),StrReverse(b);
        for(int i = 0; i < strlen(a); ++i){
            if(a[i] == '1')
                aa += f[i],c += f[i];
        }
        for(int i = 0; i < strlen(b); ++i){
            if(b[i] == '1')
                bb += f[i],c += f[i];
        }
        int la = 0,lb = 0, lc = 0;
        if(!aa) la = 1;
        if(!bb) lb = 1;
        if(!aa && !bb) lc = 1;
        while(aa)
        {
            int pos = lower_bound(f,f+65,aa) - f;
            if(f[pos] > aa) pos -= 1;
            va[pos] = 1;
            aa -= f[pos];
            if(!la) la = pos+1;
        }
        while(c)
        {
            int pos = lower_bound(f,f+65,c) - f;
            if(f[pos]>c) pos -= 1;
            vc[pos] = 1;
            c -= f[pos];
            if(!lc) lc = pos+1;
        }
        while(bb)
        {
            int pos = lower_bound(f,f+65,bb) - f;
            if(f[pos] > bb) pos -= 1;
            vb[pos] = 1;
            bb -= f[pos];
            if(!lb) lb = pos + 1;
        }
        for(int i = 1; i <= lc+2-la; ++i) putchar(' ');
        for(int i = la - 1; ~i ; --i) cout<<va[i];
        putchar('\n');
        putchar('+');
        for(int i = 1; i < lc+2-lb; ++i) putchar(' ');
        for(int i = lb - 1; ~i ; --i) cout<<vb[i];
        putchar('\n');
        printf("  ");
        for(int i = 1; i <= lc; ++i) putchar('-');
        printf("\n  ");
        for(int i = lc-1; ~i; --i) cout<<vc[i];
        printf("\n\n");
    }
    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