题解：P17202 DKM OI Round 1 - 小猫的考试

_pig_ · 2026-08-04 20:33:32 · 题解

险些被出题组带走了。/ch

我们凭直觉考虑让一个点尽量晚一点被影响（进入循环），所以我们先把一个点设为 n，然后在它旁边连上 0\sim n-1。这样显然不够，我们还要让这些邻居也晚一点变小，所以考虑给每一个邻居也用同样的方法建更多邻居。

然后你发现这样子直到每个叶子都变成 0，你建出来的树就是一个 不动点（经过变换后不会变化的状态），并且恰好有 2^n 个点。那么我们稍微扰动，把最深的一个叶子设成 1，这样它就会慢慢变化了。

可是非常不幸，这样恰好会在第 x=n-1 时进入循环，只有 70 分。所以我们充分发扬乱搞精神，考虑把剩下的点用神秘方法接到树上，最后发现在扰动的叶子上接一串 01010101... 就可以了。

Update on 2026.8.5：

由于赛场上着急过题用的乱搞，实际上可以正常一点。

扰动不需要直接给最后一个叶子加上，可以在这个叶子后面加一个扰动点，也设置为 0，那么他就可以多跑一轮了。

::::success[乱搞]

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair <int, int> pii;
random_device rd;
mt19937 rnd (rd ());
// int rand(int l, int r)
// {
//     return rnd () % (r - l + 1) + l;
// }
int n = 200000, a[200010];
vector <pii> v;
int main()
{
    a[1] = 17;
    int cur = 1;
    for (int i = 1; i <= (1 << 17); i++)
    {
        for (int j = 0; j < a[i] && cur < n; j++)
        {
            a[++cur] = j;
            v.push_back ({i, cur});
        }
    }
    a[1 << 17] = 1;
    for (int i = (1 << 17) + 1; i <= n; i++) a[i] = a[i - 1] ^ 1, v.push_back ({i - 1, i});
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "\n";
    for (pii t : v) cout << t.x << " " << t.y << "\n";
    return 0;
}

::::

::::success[正解]

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair <int, int> pii;
random_device rd;
mt19937 rnd (rd ());
// int rand(int l, int r)
// {
//     return rnd () % (r - l + 1) + l;
// }
int n = 200000, a[200010];
vector <pii> v;
int main()
{
    a[1] = 17;
    int cur = 1;
    for (int i = 1; i <= (1 << 17); i++)
    {
        for (int j = 0; j < a[i] && cur < n; j++)
        {
            a[++cur] = j;
            v.push_back ({i, cur});
        }
    }
    a[1 << 17] = 0;
    a[(1 << 17) + 1] = 0;
    v.push_back ({1 << 17, (1 << 17) + 1});
    for (int i = (1 << 17) + 2; i <= n; i++) a[i] = 1, v.push_back ({1, i});
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "\n";
    for (pii t : v) cout << t.x << " " << t.y << "\n";
    return 0;
}

::::