题解#

先考虑只有一种权值的情况。显然此时若 $n$ 为奇数，则先手必胜，否则先手必败。

然后考虑多种权值。发现若所有权值的出现次数均为偶数，则先手必败，否则先手仅需选择最大的出现次数为奇数的权值，即可令后手进入必败状态。

于是仅需检查是否有一种权值出现次数为奇数即可。

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    if (any_of(cnt.begin(), cnt.end(), [](const pair<int, int> &x) {
        return x.second % 2 == 1;
    })) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

题解#

令 $[y,x]$ 均为 $1$，从 $y - 1, x + 1$ 开始，分别向左右构造成 $-1/1$ 交替的形式。

前缀和满足如下形式：

• $1,0,1,0,1_y,2_x,1,0,1,...$

• $-1,0,-1,0_y,1_x,0,1,...$

后缀和满足如下形式：

• $...,0,1,2_y,1_x,0,1,0,1$

• $...,1,0,1_y,0_x,-1,0,-1$

$x, y$ 均满足要求

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    int x, y;
    cin >> x >> y;
    vector<int> ans(n + 1);
    for (int i = y; i <= x; i++) {
        ans[i] = 1;
    }
    for (int i = x + 1; i <= n; i++) {
        ans[i] = -ans[i - 1];
    }
    for (int i = y - 1; i >= 1; i--) {
        ans[i] = -ans[i + 1];
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

题解#

打表发现在第二次操作后，数组一定单调递增，且除了最大的权值外每种权值至少出现 $2$ 次，每次操作后，数组右移一位。

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    ll sum = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int j = 1; j <= 2; j++) {
        int tmp = 0;
        map<int, int> mp;
        for (int i = 1; i <= n; i++) {
            sum += a[i];
            mp[a[i]]++;
            if (mp[a[i]] >= 2) {
                tmp = max(tmp, a[i]);
            }
            a[i] = tmp;
        }
    }
    ll tmp = 0;
    for (int i = 1; i <= n; i++) {
        tmp += a[i];
    }
    for (int i = n; i >= 1; i--) {
        sum += tmp;
        tmp -= a[i];
    }
    cout << sum << '\n';
}

题解#

当访问到普通房间时，步数 $+ 1$，如果访问到特殊房间，则步数 $+ 1$ 后翻倍，显然访问到特殊房间后，回到该房间需要重新走相同的路程

代码#

void idol_produce(int testCase) { 
    /*Code Here*/
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1;i <= k; i ++){
        int x;
        cin >> x;
        a[x] = 1;
    }
    ll ans = 0;
    for(int i = 1;i <= n; i++){
        ans ++;
        if(a[i]) ans *= 2;
    }
    cout << ans << '\n';
}

题解#

显然，由于 $2 \times 2$ 只能对相邻两行进行，对于 $(i, i + 1)$ 行，至多只进行 $1$ 次 $2 \times 2$ 操作，否则使用 $2$ 次覆盖行操作一定更优。

故考虑 $dp$ ，令 $dp_{i,0/1/2}$ 表示覆盖了前 $i$ 行，且第 $i$ 行用 $2 \times 2$ 覆盖了第 $i + 1$ 行的 $0 / 1-2/ 3-4$ 个格子的最小操作数

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<vector<int> > dp(n + 1, vector<int>(3, INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
        else dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;
        if (a[i] <= 2) {
            dp[i][0] = min(dp[i][0], dp[i - 1][1]);
            dp[i][1] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;
        } else if (a[i] <= 4) {
            dp[i][1] = dp[i - 1][2] + 1;
            dp[i][2] = dp[i - 1][1] + 1;
        }
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
}

题解#

对于树高根号分治，目标是把老鼠逼到一条链上，最后二分找到位置

• 先对一个叶子节点进行 $\sqrt{5000} = 70$ 次无效询问，这样所有树高小于 $70$ 的点必然不存在老鼠

• 对于树高大于 $70$ 的，从根节点开始递归询问。对于一个节点的儿子，只有树高大于 $70$ 才被询问，小于 $70$ 的直接跳过即可

  询问为真或者只有一个儿子的时候就直接递归进去，为假就下一个儿子因此这样的询问最多 $70$ 次。

• 最后二分即可完成，注意每次查询失败的时候，左右边界都要向根偏移一个位置

代码#

const int N = 70;

int ask(int x) {
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}

# define answer(x) do { cout << "! " << x << endl; return;} while (0)

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    vector<int> father(n + 1, 0), h(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa) -> void {
        for (auto v: e[u]) {
            if (v == fa) {
                continue;
            }
            father[v] = u;
            dfs(v, u);
            h[u] = max(h[u], h[v] + 1);
        }
    };
    dfs(1, 0);
    int tmp = find(h.begin() + 1, h.end(), 0) - h.begin();
    for (int i = 1; i <= N; i++) {
        if (ask(tmp) == 1) {
            answer(tmp);
        }
    }
    function<int(int)> dfs2 = [&](int u) -> int {
        vector<int> son;
        for (auto v: e[u]) {
            if (v == father[u] || h[v] < N) {
                continue;
            }
            son.emplace_back(v);
        }
        if (son.empty()) {
            return u;
        }
        for (auto x: son) {
            if (x == son.back() || ask(x) == 1) {
                return dfs2(x);
            }
        }
        assert(false);
    };
    int end = dfs2(1);
    vector<int> a;
    for (int i = end; i != 0; i = father[i]) {
        a.emplace_back(i);
    }
    reverse(a.begin(), a.end());
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (ask(a[mid]) == 1) {
            l = mid;
        } else {
            r = mid - 1;
            l = max(0, l - 1);
            r = max(0, r - 1);
        }
    }
    answer(a[l]);
}