依旧涨Rating ovo（但是能不能让我打集训比赛的时候也涨涨Rating）

T1 最大权值

本题正解思路小总结：

• 发现本题是一道找规律可做的题目，直接看大样例即可
• 出题人：骗你的没有大样例
• 既然如此，本题的规律一定是比较简单的。我们可以先写一个深搜暴力，输出一些小值的答案，总结出规律：当 $n$ 为奇数，答案就是 $n$；当 $n$ 为偶数，答案为 $n+1$。
• 特判一下 $1$ 的答案为 $0$ 的情况。
• 然后按照规律写出入门代码即可。

本题代码短一点就不放链接了（100pts）

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    freopen("maxval.in","r",stdin);
    freopen("maxval.out","w",stdout);
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        int n;
        scanf("%lld",&n);
        if(n&1&&n!=1)
        {
            printf("%lld\n",n);
        }
        else if(n!=1)
        {
            printf("%lld\n",n+1);
        }
        else
        {
            printf("0\n");
        }
    }
    return 0;
}

T2 配对

如题解所说，本题只需要发现DFS生成树后基本上就结束了。

但是实际上我发现这个东西也用了俩小时，还是有难度的QAQ（对我来说）

本题正解思路小总结：

• 利用 DFS 生成树遍历图，将边分为树边与回边，并在回溯过程中处理配对。
• 对于每个节点 $u$，收集所有与其相连且尚未匹配的边（包括子边和回边），存入 unpaired 列表。
• 若 unpaired 数量为奇数，则取出一条边与父边配对，确保父边被使用且当前节点剩余边数为偶数。
• 将剩余的 unpaired 边两两配对，由于它们均与节点 $u$ 相连，因此每对边共享顶点 $u$，满足题目要求。
• 用 matched 数组标记已配对的边，ans 数组记录配对关系，避免重复处理。
• 输出时只输出 $i < ans[i]$ 的配对，保证每对边仅输出一次。
• 由于图连通且 $m$ 为偶数，该算法能保证所有边均被合法配对，时间复杂度为 $O(n+m)$。

100pts

T3 随机打乱

12pts

作为一个蒟蒻来说，dfs暴力才是我的最爱ovo

很难的一题，使xzy大佬都没提交代码qwq

本题正解思路小总结：

• 将每个二元组 $(a_i, b_i)$ 转化为区间 $[l_i, r_i] = [\min(a_i, b_i), \max(a_i, b_i)]$，并记录其对应的加入值 $x_i$。
• 根据期望的线性性质，总期望 $E(|S|)$ 等于每个二元组被加入集合 $S$ 的概率之和。
• 定义 $dp[l][r]$ 表示当前处理区间为 $[l, r]$ 时对答案的期望贡献，利用区间DP从小到大枚举所有可能的 $l$ 和 $r$。
• 预处理 ve1[l] 和 ve2[r]，分别按左端点升序和右端点降序排序，以便快速统计包含当前区间的区间数量 cnt[l]。
• 状态转移方程为 $dp[l][r] = 1 + inv[cnt[l]] \times (f1[l] + f2[r])$，其中 $1$ 表示当前区间自身的贡献，f1 和 f2 分别统计来自左右两侧的DP贡献。
• 利用快速幂预处理逆元 $inv[i]$，将概率计算转化为模意义下的乘法，避免除法精度问题。
• 最终答案即为 $dp[1][2n]$，算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$，适用于 $n \le 3000$ 的数据范围。

订正

T4 猜数

居然是稀客交互题

作为T4交互题，难度还是没有NOIP T4那么高，还是能订正的。

本题正解思路小总结：

• 由题意，需在最多 4 次查询内猜出 $1 \sim 10^{18}$ 的正整数 $x$，每次查询返回 $x$ 除以 $y$ 的商或余数。
• 代码采用中国剩余定理（CRT）思想，预设模数 $m_1=755, m_2=3019, m_3=4558689, m_4=10390824978704$ 来逐步缩小 $x$ 的范围。
• 若首次查询 $m_1$ 返回余数，则继续用更大模数获取余数，通过 crt 合并同余方程，直到模数乘积足够大以唯一确定 $x$。
• 若中途某次返回商，则利用商更新下界 $L$，并在剩余查询中通过计算候选值 $x_1, x_2, \dots$ 并查询特定值来区分。
• 若首次查询 $m_1$ 返回商，则说明 $x$ 较大，转而使用小模数 $4, 7, 27$ 获取余数，或利用商确定下界后在候选区间内二分。
• 代码中的 first_cand(L) 返回满足当前同余条件且大于等于下界 $L$ 的最小候选值，确保在无法唯一确定时返回尽可能大的值以获取更高得分。
• 最终返回确定的 $x$ 或满足条件的最大候选值，充分利用 4 次查询机会实现满分（$x \ge 18$ 对应 $10^{18}$ 范围）。

订正