集训队作业孪生项链解题报告

1、孪生项链解题报题意简m 的合法二进制串，求它在所有长度不超过 n 的合法二进制串中的后继；二、求长度恰好为 k算法分 进制串Ss0s1s2 sl1，把它顺时针写成一圈，首尾相连。不失一般性，假设从位置0k(1 k l k 是满足条件的最小值)开始顺时针得到的二进制串是相等的，即 si s(ik)modl 。由此，可以得到s0 sk sik s(i1)kmodl(ik l ，且i 是满足条件的最大值)。因为ik l ，所以(i1)kmodl i1)kl ik lk kk 又是满足条件的最小值，因此(i1)kmodl0，即k|l。所以，S就是由子串Ts0s1s2 sk1k现 次构成的，必要性得证。

2、l任务一：为了保证得到的串字典序刚好大于原串，且满足，把长度为 m 的RR nR n 位，设QQ011。其实这一步就是对一个二进制数加 1，并去掉结果后面所有的 0。此时，Q 即所求二进制串。从步骤中，可以保证结果的最优性和，具体的证明从略。本任务的时间复杂度为O(n)，空间复杂度为O(n。任务二：这个任务直接考虑较为复杂可以分步间接地考虑。设 fi 表示长度为 且满足性质2 的二进制串的总数，根据性质2 有递推关系 ifk k因为每个最小表示都对应着数量与串的长度相等的二进制串。本任务的时间复杂度为O(ck2，空间复杂度为O(c k，其中c c 为高精度运算的时间和空间常数1 源程#incl

3、ude #include #include #include usingnamespacestd;ifstream fin(twins.in); /classofbigclassbigint: bigint() bigint(intn)for(;n!=0;n/=base) push_back(n%bigint&operator+=(constbigint&n)if(size()resize(size() + 1);for(inti=0;isize();i+) (*this)i += ni;returnbigint&operator-=(constbigint&n)for(inti=0;i=0;

4、i-m=m*base+(*this)i; (*this)i = m / n;m%=returnfriendostream&operator(ostream&,conststaticconstintbase=10000; static const int width = 4; bigint& simplify() for(inti=0;isize();if(*this)i=(*this)i-=(*this)i+while(!empty()&back()=0) returnostream&operator(ostream&os,constbigint&n)returnos0; os =0;i-ossetfill(0)setw(bigint:width)nmk; fin s;/Subtask1:thesuccessivestringfor(;r.length()+s.length()n;r+=r+=s.substr(0,n-r.erase(r.rfind(0)+rr.length()-1=/Subtask2:thenumberofk-beadbigintt=bigint*f=newbigintk+1; f1 = 2;for(inti=2;i=