Loading... ## 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啥初始化炸了~~。最终在我们不懈的努力下发现了如下规律： ```cpp 0 0 1 1 2 3 2 3 4 5 6 4 5 6 7 8 9 10 11 7 8 9 10 11 12 13 14 15 16 17 18 19 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 33 34 35 36 37 38 39 40 41 42 43 44 45 ``` 以上为当$n$为**任意值**的$1\sim100$位的答案。我们可以惊喜的发现这题和$n$没关系了,接下来，我们可以就通过找规律做这道题。 这道题需要写高精度（最恶心的点） ### Code 因为极其恶心人所有还是放一下代码（ ```cpp #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 月 22 日 © 允许规范转载 打赏 赞赏作者 赞 0 End.
1 条评论
压行的艺术（