ZJU 3768 - Continuous Login (二分 + DFSID)

题意

给出一个目标值,只能用连续的和拼出来。输出最少的连续和。

思路

DFSID出奇迹。

一开始最后一个数也是线性搜过去,TLE了。剪了一下1500ms。

后来最后一个数改成$logn$级别的查询竟然变成了10ms!

代码

vector<int> ans, arr;
map<int, int> mp;
int depth;
 
bool DFS(int curPos, int sum, int curDep)
{
    if (curDep == depth)
    {
        if (sum == 0) return true;
        return false;
    }
    if (depth - curDep == 1)
    {
        if (mp.count(sum))
        {
            ans.push_back(mp[sum]);
            return true;
        }
        return false;
    }
    for (int i = curPos; i >= 1; i--)
    {
        if (arr[i] * (depth-curDep) < sum) break;
        if (arr[i] > sum) continue;
        ans.PB(i);
        if (DFS(i, sum-arr[i], curDep+1)) return true;
        ans.pop_back();
    }
    return false;
}
 
int main()
{
    //ROP;
    arr.PB(0);
    for (int i = 1, sum = 0; sum <= MAXN; i++)
    {
        sum += i;
        arr.PB(sum);
        mp[sum] = i;
    }
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ans.clear();
        int n;
        scanf("%d", &n);
        depth = 1;
        int startPos = upper_bound(arr.begin(), arr.end(), n) - arr.begin()-1;
        while (!DFS(startPos, n, 0)) depth++;
        for (int i = 0; i < SZ(ans); i++)
            if (!i) printf("%d", ans[i]);
            else printf(" %d", ans[i]);
        puts("");
    }
    return 0;
}

Powered by Jekyll and Theme by solid