Codeforces - 1181B - Split a Number

https://codeforces.com/contest/1181/problem/B

从中间拆开然后用大数搞一波。

当时没想清楚奇偶是怎么弄，其实都可以，奇数长度字符串的中心就在len/2，偶数长度字符串的中心恰好是len/2和len/2-1。

但是要是作为末尾指针的位置来说的话

奇数长度字符串：把中心分给后半串，那么分割点是len/2。把中心分给前半串，那么分割点是len/2+1。

偶数长度字符串：分割点是len/2。

注意子串的取法，其实最方便的还是传头尾指针进去。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read() {

    int x=0;

    int f=0;

    char c;

    do {

        c=getchar();

        if(c=='-')

            f=1;

    } while(c<'0'||c>'9');

    do {

        x=(x<<3)+(x<<1)+c-'0';

        c=getchar();

    } while(c>='0'&&c<='9');

    return f?-x:x;

}

inline void _write(int x) {

    if(x>9)

        _write(x/10);

    putchar(x%10+'0');

}

inline void write(int x) {

    if(x<0) {

        putchar('-');

        x=-x;

    }

    _write(x);

    putchar('\n');

}

struct BigInt {

    const static int mod=10000;

    const static int DLEN=4;

    int a[30005],len;

    BigInt() {

        memset(a,0,sizeof(a));

        len=1;

    }

    BigInt(int v) {

        memset(a,0,sizeof(a));

        len=0;

        do {

            a[len++]=v%mod;

            v/=mod;

        } while(v);

    }

    BigInt(const char *s) {

        memset(a,0,sizeof(a));

        int L=strlen(s);

        len = L/DLEN;

        if(L%DLEN)

            len++;

        int index=0;

        for(int i=L-1; i>=0; i-=DLEN) {

            int t=0;

            int k=i-DLEN+1;

            if(k<0)

                k=0;

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

                t=t*10+s[j]-'0';

            a[index++] = t;

        }

    }

    BigInt operator+(const BigInt &b)const {

        BigInt res;

        res.len=max(len,b.len);

        for(int i=0; i<res.len; i++) {

            res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0);

            res.a[i+1]+=res.a[i]/mod;

            res.a[i]%=mod;

        }

        if(res.a[res.len] > 0)

            res.len++;

        return res;

    }

    BigInt operator*(const BigInt &b)const {

        BigInt res;

        for(int i=0; i<len; i++) {

            int up = 0;

            for(int j=0; j<b.len; j++) {

                int temp=a[i]*b.a[j]+res.a[i+j]+up;

                res.a[i+j]=temp%mod;

                up=temp/mod;

            }

            if(up != 0)

                res.a[i+ b.len]=up;

        }

        res.len=len+b.len;

        while(res.a[res.len-1]==0&&res.len>1)

            res.len--;

        return res;

    }

    bool operator>(const BigInt &b)const {

        if(len>b.len)

            return true;

        else if(len==b.len) {

            int ln=len-1;

            while(a[ln]==b.a[ln]&&ln>=0)

                ln--;

            if(ln>=0&&a[ln]>b.a[ln])

                return true;

            else

                return false;

        } else

            return false;

    }

    void output() {

        printf("%d",a[len-1]);

        for(int i = len-2; i >=0 ; i--)

            printf("%04d",a[i]);

        printf("\n");

    }

};

char s[100005];

char t[100005];

int main() {

#ifdef Yinku

    freopen("Yinku.in","r",stdin);

    //freopen("Yinku.out","w",stdout);

#endif // Yinku

    int l;

    scanf("%d%s",&l,s);

    int m1=l/2;

    int m2=l/2+1;

    int h1=m1;

    while(s[h1]=='0')

        h1--;

    int h2=m2;

    while(h2<l&&s[h2]=='0')

        h2++;

    strncpy(t,s,h1);

    t[h1]='\0';

    BigInt a(t);

    strcpy(t,s+h1);

    BigInt b(t);

    BigInt c=a+b;

    strncpy(t,s,h2);

    t[h2]='\0';

    a=BigInt(t);

    strcpy(t,s+h2);

    b=BigInt(t);

    BigInt c2=a+b;

    if(c>c2)

        c2.output();

    else

        c.output();

}

巴特西

Codeforces - 1181B - Split a Number - 贪心

最新文章

热门文章