2021.08.20 比赛日记

smallfang

2021 年 08 月 22 日

1693 次浏览

1 条评论

194字数

算法笔记

2021.08.20 比赛记录

T3

题目简述

有一系列的字符串，我们知道了第一个字符串是$a$,第二个是$b$。后面的每一个是前面的两个拼合组成。

$f[1]=a,f[2]=b,f[i]=f[i-1]+f[i-2]$先给定$n,m$求$f[n]$前$m$项的权值，权值定义为最大使得前缀子字符串后缀子字符串相等。同时要保证$val<|s|$(||表示(string)s的长度)(例:$abcab$, $val=2$. $aaaa, val=3$). 其中$n≤1000$

思路与做法

我们可以先尝试的进行暴力求解，由于其数据范围n≤1000（但是由于斐波那契数列的原因F[1000]的数有100位左右）,所以最多跑到30.~~跑100啥初始化炸了~~。最终在我们不懈的努力下发现了如下规律：

以上为当$n$为任意值的$1\sim100$位的答案。我们可以惊喜的发现这题和$n$没关系了,接下来，我们可以就通过找规律做这道题。

这道题需要写高精度（最恶心的点）

Code

因为极其恶心人所有还是放一下代码（

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 4e2 + 5, N = 1000, MOD = 258280327;
typedef unsigned long long ull;

struct bign{int len,s[MAXN];bign(){memset(s,0,sizeof(s));len=1;}bign(int num){*this=num;}bign(const char*num){*this=num;}bign operator=(const int num){char s[MAXN];sprintf(s,"%d",num);*this=s;return *this;}bign operator=(const char*num){for(int i=0;num[i]=='0';num++);len=strlen(num);for(int i=0;i<len;i++)s[i]=num[len-i-1]-'0';return*this;}bign operator+(const bign&b)const{bign c;c.len=0;for(int i=0,g=0;g||i<max(len,b.len);i++){int x=g;if(i<len)x+=s[i];if(i<b.len)x+=b.s[i];c.s[c.len++]=x%10;g=x/10;}return c;}bign operator+=(const bign&b){*this=*this+b;return*this;}void clean(){while(len>1&&!s[len-1])len--;}bign operator*(const bign&b){bign c;c.len=len+b.len;for(int i=0;i<len;i++){for(int j=0;j<b.len;j++){c.s[i+j]+=s[i]*b.s[j];}}for(int i=0;i<c.len;i++){c.s[i+1]+=c.s[i]/10;c.s[i]%=10;}c.clean();return c;}bign operator*=(const bign&b){*this=*this*b;return*this;}bign operator-(const bign&b){bign c;c.len=0;for(int i=0,g=0;i<len;i++){int x=s[i]-g;if(i<b.len)x-=b.s[i];if(x>=0)g=0;else{g=1;x+=10;}c.s[c.len++]=x;}c.clean();return c;}bign operator-=(const bign&b){*this=*this-b;return*this;}bign operator/(const bign&b){bign c,f=0;for(int i=len-1;i>=0;i--){f=f*10;f.s[0]=s[i];while(f>=b){f-=b;c.s[i]++;}}c.len=len;c.clean();return c;}bign operator/=(const bign&b){*this=*this/b;return*this;}bign operator%(const bign&b){bign r=*this/b;r=*this-r*b;r.clean();return r;}bign operator%=(const bign&b){*this=*this%b;return*this;}bool operator<(const bign&b){if(len!=b.len)return len<b.len;for(int i=len-1;i!=-1;i--){if(s[i]!=b.s[i])return s[i]<b.s[i];}return false;}bool operator>(const bign&b){if(len!=b.len)return len>b.len;for(int i=len-1;i!=-1;i--){if(s[i]!=b.s[i])return s[i]>b.s[i];}return false;}bool operator==(const bign&b){return!(*this>b)&&!(*this<b);}bool operator!=(const bign&b){return!(*this==b);}bool operator<=(const bign&b){return*this<b||*this==b;}bool operator>=(const bign&b){return*this>b||*this==b;}string str()const{string res="";for(int i=0;i<len;i++)res=char(s[i]+'0')+res;return res;}};

bign num = 0, sum[N], a[N], f[N], c[N], fd[N];


int main()
{
    bign a,b;
    f[0] = 0, f[1] = 2, f[2] = 2, fd[1] = 1, fd[2] = 1;
    sum[0] = 0;
    sum[1] = 2;
    sum[2] = 4;
    string t1,t2;
    for (int i = 3; i <= 1000; i ++ )
    {
        f[i] = f[i - 1] + f[i - 2];
        fd[i] = f[i] / "2";
        sum[i] = f[i] + sum[i - 1];
        //cout << f[i] << endl;
    }
    int T;
    cin >> T;
    while (T -- )
    {
        int n;
        string x;
        cin >> n >> x;
        bign m;
        for(int i=0;i<x.size();i++)m.s[x.size()-i-1]=x[i]-'0';
        m.len=x.size();
        //cout<<m.str()<<"-"<<endl;
        int i = 0;
        num = 0;
        for (i = 1; i <= 1000; i ++ )
        {
            //cout << sum[i] << "--" << m << endl;
            if (sum[i] >= m)
            {
                i --;
            
            //    cout << i << "-" << endl;
                break;
            }
            //cout << f[i] << " " << t1 << endl;
            num = num + fd[i];
        }
        //cout << m << " " << sum[i] << endl;
        bign ts = m - sum[i];
        if (ts > fd[i + 1])
        {
            ts = ts - fd[i + 1];
        }
        cout << ((ts + num - "1")%MOD).str()  << endl;
        
    }
    return 0;
}

跑的贼慢, 呜呜呜呜。

2021.08.20 比赛日记