loj #6722「CodePlus #7」神秘序列 题解 二分法

    技术2022-07-11  86

    题目描述 题目地址:https://loj.ac/problem/6722

    整个文章尝试从0开始一点点地分析,如果想直接看到最终的可以ac的思路,可以直接跳转到正解部分

    文章目录

    子任务1,2子任务3二分 子任务4清奇解正解二分上限

    子任务1,2

    结果形式已知,所以我们很容易想到倒推。 一次正向操作是:将 a i a_i ai变成 0, 前面的全加1。那一次逆向的操作便是:把 0 变成 a i a_i ai,前面的全减1。 那逆向操作哪个0呢? 拿最简单的举个例子: 原始序列: 1 2 结果序列: 0 0 如果我们首先把第一个0变成 1 好像没啥问题 如果我们首先把第二个0变成 2 那第一个的0就得减去1 。0减去1是多少呢? 当从正向操作2时,前面的都得加个1,什么加1会是0呢? -1 然而a非负所以我们只能把第一个0变成1 其他的时候也类似,把第一个0变成i。 这时我们第一个算法(逆向模拟)便出现了: 不断地把第一个0变成i,执行一次逆向操作,n+k次后如果 a n a_n an变成了n则找到了原序列。 (当在n个数字中找不到0时则让n+=1,可以先随便设置个上限比如2*k,如果大于这个上限了就不找了,说明不存在) 这个算法时间复杂度我感觉差不多是O((n+k)*n)(后面我们会知道n=O( k \sqrt k k )) 官方题解说是O(klogk)(虽然我不知道这是怎么算出来的但还是以官方的为准吧) 由于时间复杂度较高我们只能通过前两个子任务 代码:https://github.com/dq116/codeplus-7/blob/master/p3/secret2.cpp

    子任务3

    这个时候我们可以尝试挖掘一下其中的数学关系

    (ps:下面的 a i a_i ai既指第序列的第i个元素也指第i个元素的值)

    我们考虑 a i a_i ai的操作次数 x i x_i xi

    我们设后面的元素的总的操作次数是 c i c_i ci

    后面的元素的操作会使 a i a_i ai+=1

    操作 a i a_i ai一次相当于把 a i a_i ai减小了 i i i

    那么可以得 a i + c i = i ⋅ x i a_i+c_i=i\cdot x_i ai+ci=ixi

    如果我们知道 c i c_i ci的话那么我们可以算出来 a i = i − ( c i   m o d   i ) a_i=i-(c_i\ mod\ i) ai=i(ci mod i)

    ( c i   m o d   i ) (c_i\ mod\ i) (ci mod i) 不为0时 a i a_i ai的结果是确定的

    但当​​​​​​​ ( c i   m o d   i ) (c_i\ mod\ i) (ci mod i) 为0时 a i a_i ai就可能是 i或者0

    因为子任务3里的 a i a_i ai不等于i

    所以我们可以这么分析

    为了得到 c i c_i ci,我们得从后往前分析(从最后一个元素开始算)

    a n a_n an对应的 c n c_n cn为0

    所以 a n = n a_n=n an=n x n = 1 x_n=1 xn=1

    c n − 1 = ( n + k ) − 1 c_{n-1}=(n+k)-1 cn1=(n+k)1

    a n − 1 = ( n − 1 ) − ( c n − 1   m o d   i ) a_{n-1}=(n-1) -(c_{n-1}\ mod\ i) an1=(n1)(cn1 mod i)

    x n − 1 = ( c n − 1 + a n − 1 ) / i x_{n-1}=(c_{n-1}+a_{n-1})/i xn1=(cn1+an1)/i

    我们就可以一直这么递推下去 所以给定一个n我们就可以算出来总共所需要的操作次数num

    二分

    总操作次数n+k 我们可以分成两部分考虑 其中的n是必须的因为每个数至少做一次操作 还剩下一个k,根据我们之前逆向模拟的思想,k是随着n的增大而增大的 即总次数与n成正比例关系,所以我们可以尝试一下二分法 上限初值我们可以先设一个比较大的数:maximum=2e6下限初值设为minimum=2 令 n1=mid=(maximum+minimum)/2 算得num与n1+k比较一下如果num<n1+k num=n1+k1 不等式两边同时消去 n1 所以比的其实是k 即 k1<k k1小说明n1小 那么提高下限:令minimum=mid n1= mid=(maximum+minimum)/2 num>n1+k的情况同理 直到num==n1+k 此时的n1便是我们要找的n 通过这种方法我们能通过子任务三 时间复杂度:O(nlogn) 代码:https://github.com/dq116/codeplus-7/blob/master/p3/secret3.cpp

    子任务4清奇解

    子任务4并没有 a i ≠ i a_i\ne i ai=i 的限制 所以当 ( c i   m o d   i ) = = 0 (c_i\ mod\ i)==0 (ci mod i)==0时, a i a_i ai就可能有两个值了 这样其实也能做,但会麻烦一些 这篇博客对这种方法有一些解释,这篇博客实现了这种方法(并没有对这种方法进行讲解,也没有注释) 我曾经问过第一篇博客的博主请他关于其中的:“先钦定第一个不确定的 a i a_i ai为0,后面遇到的决策点都钦定为i”再解释一下,他给我的回复是这样的:

    感受一下当前面(从后往前做,指实际上的后面)操作的位确定时,这一位选0的所有方案,和这一位选i的所有方案,它们之间是不相交的。如果遇到的决策点都将它们钦定为i,那么最终的操作方案数就会尽量大。目前做到的这个决策点选0,后面的都选i,恰是这一位选0或i的临界状态。

    因为他并没有实现这种方法所以再细节的也不太清楚了,我也没继续细问下去 感兴趣的同学可以根据那两篇博客研究一下(我尝试过但因为实在看不懂第二篇博客的代码最后放弃了)

    正解

    从后往前分析似乎行不通 那我们可以尝试一下从前往后分析(这时你可能会怀疑,从前往后与从后往前有差别吗?别急听我慢慢道来) 从前往后分析的话我们就能知道 a i a_i ai自身与后面的元素的总操作次数: r i r_i ri了 注意这里与上面的差别: r i r_i ri是包括自身操作次数的, c i c_i ci是不包括的 也就是说 r i = c i + x i r_i=c_i+x_i ri=ci+xi(其中 c i c_i ci a i a_i ai之后的元素的总操作次数, x i x_i xi a i a_i ai的操作次数) 拿第一步举例: 从后往前: 知道 c n c_n cn=0但是 x n x_n xn不知道 从前往后:知道 r 1 = n + k r_1=n+k r1=n+k 但是 c 1 c_1 c1不知道

    表示方法1: 我们可以思考一下这 r i r_i ri次的构成 首先由于 a i a_i ai的初值,我们需要后面操作 i − a i i-a_i iai次使 a i a_i ai增加到 i i i,然后再操作一次 a i a_i ai使 a i a_i ai变成0 剩下的次数便是后面的元素每操作i次, a i a_i ai操作一次 即剩下的次数中每i+1次有一次是操作 a i a_i ai 所以 x i = ⌊ r i i + 1 ⌋ + α x_i=\left\lfloor\frac{r_i}{i+1}\right\rfloor+\alpha xi=i+1ri+α 其中当 r i   m o d   ( i + 1 ) ≠ 0 r_i\ mod\ (i+1)\ne0 ri mod (i+1)=0 α = 1 \alpha=1 α=1 r i   m o d   ( i + 1 ) = = 0 r_i\ mod\ (i+1)==0 ri mod (i+1)==0 a i = = i a_i==i ai==i 0 0 0的情况,不需要+1) 或者这样表示: x i = ⌈ r i i + 1 ⌉ x_i=\left\lceil\frac{r_i}{i+1}\right\rceil xi=i+1ri

    t i = ( r i − 1 ) m o d ( i + 1 ) t_i=(r_i-1)mod(i+1) ti=(ri1)mod(i+1) t i + a i = i t_i+a_i=i ti+ai=i a i = i − t a_i=i-t ai=it r i r_i ri在mod(i+1)下的意义就是由于使 a i a_i ai由初值变成i然后再变成0所进行的操作次数 r i − 1 r_i-1 ri1就是减去由i变成0的那一次操作 就得到了在第一次操作 a i a_i ai之前, a i a_i ai后面的元素的操作次数:t

    表示方法2: 我们也可以列这样的等式: a i + ( r i − x i ) = i ⋅ x i a_i+(r_i-x_i)= i\cdot x_i ai+(rixi)=ixi 0 ≤ a i = ( i + 1 ) ⋅ x i − r i ≤ i 0\le a_i= (i+1)\cdot x_i-r_i\le i 0ai=(i+1)xirii r i i + 1 ≤ x i ≤ r i + i i + 1 \frac{r_i}{i+1}\le x_i \le \frac{r_i+i}{i+1} i+1rixii+1ri+i 夹在这里面的整数 x i x_i xi只有一个: x i = ⌊ r i + i i + 1 ⌋ x_i=\left\lfloor\frac{r_i+i}{i+1}\right\rfloor xi=i+1ri+i a i = ( i + 1 ) ⋅ x i − r i a_i=(i+1)\cdot x_i-r_i ai=(i+1)xiri

    以上两种表示都是等价的,都表明我们可以直接算出 x i x_i xi a i a_i ai来。 之后我们可以参照子任务3的方式二分即可 时间复杂度:O(nlogn)

    这个时候我们可以考虑一下最初得由从后往前转战从前往后时的疑惑了 这两种方式究竟有什么区别? 直观上来看我们用 r i − x i r_i-x_i rixi替换了 c i c_i ci 当我们用 r i − x i r_i-x_i rixi计算 x i x_i xi时相当改变了 x i x_i xi的系数,这种改变是因为 r i − x i r_i-x_i rixi中包含了 x i x_i xi,而 c i c_i ci只是个常数,所以说这种转换给我提供了更多的信息,我想这可能是用 r i − x i r_i-x_i rixi可以直接确定 x i x_i xi而用 c i c_i ci则不能的原因吧。

    二分上限

    现在我们来到了最后一关 如何确定n的上限? 首先我们可以估算一下n的数量级 有两种思路: 1.多试几个数(根据处理子任务1,2时逆向模拟算法的思想我们能得知:任给一个k总能找到一个n满足条件) 肉眼可见:n的数量级≈ k \sqrt k k 2.官方题解说因为有 a i ≤ i a_i\le i aii的限制,所以很容易想到n+k差不多是n方级别的(???我反正不太理解) 当我确定好了数量级之后 按最大的 k ≤ e 12 k\le e12 ke12则n最大的量级为e6 令maximun=常数*e6 这个常数随便写一个就行,可以写比较大的9,最小别小于2就行,因为有的n逼近2e10 或者多输出几个 n 2 ( n + k ) \frac{n^2}{(n+k)} (n+k)n2看一下大致的比例 甚至可以用数学推导去算的,这篇论文指出 当 n → ∞ n\to\infty n时,有 n 2 ( n + k ) \frac{n^2}{(n+k)} (n+k)n2∼π 如果范围卡的准确,那就相当于省去了二分寻找n的开销,那时间复杂度就降到了O(n)也就是O( k \sqrt k k ) 正解代码:

    #include <iostream> #include <cstdlib> #include <math.h> #define ll long long using namespace std; ll k; int n_max = 2e6; int minimum = 2; int maximum = n_max; int mid; int *a = (int *)malloc(sizeof(int) * n_max); int judge(int n) { ll r = n + k; ll x = -1; for (int i = 1; i < n + 1; i++) { x = ceil((double)r / (i + 1)); a[i] = i - (r - 1) % (i + 1); r -= x; if (r == 0 && i == n) return 0; if (r == 0) return 1; } return -1; } bool dichotomy(int minimum, int maximum) { while (minimum <= maximum) { mid = (minimum + maximum) / 2; int r = judge(mid); if (r == -1) minimum = mid + 1; else if (r == 1) { maximum = mid - 1; } else return true; } return false; } int main() { cin >> k; bool result = -1; result = dichotomy(minimum, maximum); int n = mid; if (result) { cout << n << endl; for (int i = 1; i < n + 1; i++) { cout<<a[i]<<' '; } } else { cout << "Daydream!" << endl; } }
    Processed: 0.013, SQL: 9