课后自主练习(高精度)1082. 猜猜猜 naive《编程思维与实践》个人学习笔记

题目

课后自主练习(高精度)1082. 猜猜猜 naive《编程思维与实践》个人学习笔记

思路

显然,长度为1的时候只有一种可能
长度为2的时候,如果1、2单词一致,只有一种可能,1、2单词不一致,那就可以有四种可能

当长度大于等于2的时候
除了s[0]和s[len-1]外,中间的数都得考虑前后的影响
于是我们就特别判断一下首位和末尾

若s[0] == s[1] 可能的情况为1种
s[0]!=s[1]可能的情况为两种
对于末尾的情况同理

于是我们开始讨论s[1]到s[length-1]的情况
倘若是aaa型,那么自然是只有1种符合要求的情况
如果是aab,baa,abat,中间可以变a和b 2种情况(其中aba可能会重复计算,所以只需要判定前两个即可)
如果是abc型,那么中间的满足要求的可以是a,b,c,三种情况

代码(大整数类)

#include<iostream>

using namespace std;
#include<iostream>
#include<cctype>
#include<cstring>

const int MAXN = 3000;

class big
{
public:
    int dig[MAXN];
    int sign;
    int LEN;
    
//public:
    

    big();
    big(string s);
    big(const char *c);
    big(long long a);

    big &operator=(const big& b);
    big operator+(big b);
    big operator*(big b);
    big operator+=(big b);

    bool operator==(int a);
    

    void out();
    void carry();
    void test();


    bool com(long long a);

};//

void big::test()
{
    cout << sign << " " << LEN << endl;
    out();cout << endl;

}
void big::out()
{
    int l = MAXN - 1;
    while(dig[l] == 0 && l > 0)//注意0的情况
        l--;
    cout << ((sign == 1) ? "" : "-");
    for(;l >= 0; l--)
        cout << dig[l];
    //cout <<endl;
}
void big::carry()
{
    bool flag = 0;

    for(int i = 0; i < this->LEN; i++)
    {
        if(this->dig[i] >= 10)
        {
            this->dig[i + 1] += this->dig[i] / 10;
            this->dig[i] %= 10;
            if(i == LEN - 1)
                LEN++; 
        }
        else if(this->dig[i] < 0)
        {
            while(this->dig[i] < 0)
            {
                this->dig[i + 1]--;
                this->dig[i] += 10;
            }
            flag = 1;
        }
    }
    if(flag)
    {
        while(dig[LEN - 1] == 0 && LEN - 1 >= 0)
            LEN--;
        if(LEN == 0)
            LEN = 1;
    }
    

}//

big::big()
{
    LEN = 1;
    sign = 1;
    memset(dig,0,sizeof(dig));
}
big::big(string s)
{
    memset(dig,0,sizeof(dig));
    LEN = 0;
    int len = s.length();
    for(int i = len - 1; i >= 0; i--)
    {
        switch(s[i])
        {
            case '+':
            sign = 1;break;
            case '-':
            sign = -1;break;
            default:
            dig[LEN++] = s[i] - '0';
            break;
        }
    }
    if(sign != -1)sign = 1;
}
big::big(long long a)
{
    memset(dig,0,sizeof(dig));
    LEN = 0;
    sign = ((a >= 0) ? 1 : -1);

    if(a < 0)
        a = -a;

    while(a)
    {
        dig[LEN++] = a % 10;
        a /= 10;
    }
    if(sign != -1)sign = 1;
}
big::big(const char *c)
{
    memset(dig,0,sizeof(dig));
    LEN = 0;
    int len = strlen(c);
    for(int i = len - 1; i >= 0; i--)
    {
        switch(c[i])
        {
            case '+':
            sign = 1;break;
            case '-':
            sign = -1;break;
            default:
            dig[LEN++] = c[i] - '0';
        }
    }
    if(sign != -1)sign = 1;
}

big& big::operator=(const big & b)
{
    this->sign = b.sign;
    this->LEN = b.LEN;
    for(int i = 0; i < LEN;i++) 
    {
        this->dig[i] = b.dig[i];
    }
    return *this;
}
big big::operator+(big b)
{
    
    if(this->sign * b.sign == -1)
    {
        if(b.LEN > this->LEN)
        {
            for(int i = 0; i < b.LEN; i++)
                b.dig[i] -= this->dig[i];
            b.carry();
            return b;
        }
        else if(b.LEN < this->LEN)
        {
            for(int i = 0; i < this->LEN; i++)
                this->dig[i] -= b.dig[i];
            this->carry();
            return *this;
        }
        else
        {
            bool flag = true;
            for(int i = b.LEN - 1; i >= 0; i--)
            {
                if(this->dig[i] > b.dig[i])
                {flag = true;break;}
                else if(this->dig[i] < b.dig[i])
                {flag = false;break;}
            }

            if(flag)
            {
                for(int i = 0; i < this->LEN; i++)
                    this->dig[i] -= b.dig[i];
                this->carry();
                return *this;
            }
            else
            {
                for(int i = 0; i < b.LEN; i++)
                    b.dig[i] -= this->dig[i];
                b.carry();
                return b;
            }
        }
    }
    else
    {   
        int mlen = ((this->LEN > b.LEN) ? this->LEN : b.LEN);
        for(int i = 0; i < mlen; i++)
            this->dig[i] += b.dig[i];
        this->carry();
    }
    return *this;
}
big big::operator*(big b)
{
    big B;
    B.sign = this->sign * b.sign;
    for(int i = 0; i < b.LEN; i++)
    {
        for(int j = 0; j < this->LEN; j++)
        {
            B.dig[i + j] += this->dig[j] * b.dig[i];
            B.LEN = i + j + 1;//注意长度
            B.carry();
        }
    }
    return B;
}

bool big::operator==(int a)
{
    if(a * sign < 0)
        return false;
    if(a < 0)
        a = -a;


    int alen = 0;
    int dlen = MAXN;
    while(dig[dlen - 1] == 0 && dlen - 1 >= 0)
        dlen--;
    if(dlen == 0)
        dlen++;
    int temp = a;
    if(temp == 0)
        alen = 1;
    while(temp)
    {
        alen++;
        temp/=10;
    }

    if(dlen != alen)
        return false;

    temp = 0;
    for(int i = 0; i < alen; i++)
    {
        if(a % 10 != dig[i])
            return false;
        a/=10;
        temp++;
    }   
    return true;
}



void out(big R, big I)
{
    if(R==0)
    {
        if(I==0)
            cout << "0";
        else if(I==1)
            cout << "i";
        else if(I==-1)
            cout << "-i";
        else
        {
            I.out();
            cout << 'i';
        }
    }
    else
    {
        R.out();
        if(I==0){}
        else if(I==1)
            cout << "+i";
        else if(I==-1)
            cout << "-i";
        else
        {
            cout << ((I.sign == 1) ? "+" : "");
            I.out();
            cout << 'i';
        }
    }
    
    
}


代码(主体)

const int MOD = 1e9+7;
typedef long long ll;

big func(string a)
{
    int len = a.length();
    if(len == 1)    return 1;
    if(len == 2)    return ((a[0] == a[1]) ? 1 : 4);

    big r{1};
    if(a[0] != a[1])    r = 2;
    for(int i = 1; i < len - 1; i++)
    {
        big c{1};
        if(a[i] != a[i - 1])    c=c+1;
        if(a[i] != a[i + 1] && a[i - 1] != a[i + 1])    c=c+1;
        r = (r * c) ;
    }
    if(a[len - 1] != a[len - 2]) r = r * 2;
    return r;

}

//
int main()
{
    string s;
    cin >> s;
    func(s).out();
}
上一篇:Windows ® Installer. V 5.0.15063.0 参数说明


下一篇:利用HttpWebRequest下载资源