传智杯 2022 初赛 E 题解

chen_zhe · 2022-11-27 09:39:16 · 题解

题意简述：给一个数列 [0],[0,1,0,-1,0],[0,1,2,1,0,-1,-2,-1,0]\dots，求这个数列的第 k 项是多少，q 次询问。

碎碎念：本来这个题是普及月赛 T2。

解法：

设一个 0,1,\dots,x-1,x,x-1,\dots,-x+1,-x,-x+1,\dots,0 被称为 x 阶金字塔。

则一个 x 阶金字塔的长度为 4x+1。前 u 个金字塔的长度为 \sum \limits_{i=0}^{u-1} (4i+1)=2u^2-u。

则相当于找到一个 t，使得 2t^2-t\leq k，且 2(t+1)^2-(t+1)>k。容易发现 t 可被二分。这样我们相当于可以获取，k 这一项在哪个金字塔上，以及距离这个金字塔开头有多少距离 k'。

而一个 x 阶金字塔可以被分为三段：一开始的上升段（0,1,\dots,x），中间的下降段（x-1,x-2,\dots,-x），以及最后的上升段（-x+1,-x+2,\dots 0），可以通过 k' 的大小知道在哪一段上，进而求出 a_k 具体是多少。

事实上，这个数据范围是我故意设置的。2(t+1)^2-(t+1)=k，当 k=4\times10^{18} 时，t \approx 1.4\times 10^9，因此二分右边界要开到大约 1.5\times 10^9 的范围，这个时候 mid=(l+r)/2 就可能爆 int。而如果要用求根公式，\Delta\approx 9+4\times2\times4\times 10^{18}\approx 3.2\times10^{19}，会爆 unsigned long long。

参考代码：

#include <iostream>
using namespace std;
int main()
{
    int q;
    cin >> q;
    while (q--)
    {
        long long k,l=1,r=2e9,ans=0;
        cin >> k;
        while (l<=r)
        {
            long long mid=(l+r)/2;
            if ((long long)mid*mid*2-mid>=k)
            {
                r=mid-1;
                ans=mid;
            }
            else
                l=mid+1;
        }
        ans--;
        long long len=ans*ans*2-ans;
        k-=len+1;
        if (k<=ans)
            cout << k << endl;
        else if (k<=3*ans)
            cout << 2*ans-k << endl;
        else
            cout << -4*ans+k << endl;

    }
    return 0;
}