​ 很荣幸第一次办官方比赛就能轮到这么特殊的一场。恰好是为数不多的周四练习赛，又是 Qcjj 结婚后的第一场练习赛！

​ 算是返璞归真的一场，没有考察太过高级的算法。不过思维难度很高，总体题目难度也偏高了 QAQ

​ 那么接下来是题解部分 ~

A - I Wanna Win the Cards

​ 草莓酱：呃啊，原来这游戏不公平啊，蓝莓酱你坏坏 o(╥﹏╥)o

​ 显然轮到某方时，其必须取至少 张、至多 张种族值不为 的卡牌。

​ 那么结论显而易见，当 能够被 整除时，草莓酱才必胜（无论蓝莓酱之前怎么取牌，草莓酱总能够抽牌使得双方拿到的种族值不为 的牌数量和为 ）；否则蓝莓酱必胜（蓝莓酱抽牌使得剩余的种族值不为 的卡牌数量为 的倍数即可）。

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, k;
        cin >> n >> k;
        if (n % (k + 1) == 0)
            cout << "Strawberry\n";
        else
            cout << "Blueberry\n";
    }
    return 0;
}

B - I Wanna Make It Palindromic

​ 家人们谁懂啊，看到序列不是回文就手痒想改，但金币超贵的！

​ 首先，如果与某个位置对应的位置处的数字和该处相同，那么显然这个数字是不需要动的。接下来只考虑需要修改的位置。

​ 在选定 后，对于一对需要修改的位置 ，无非就四种情况： 都不属于 （需要改两次），仅 属于 （需要改一次），仅 属于 （需要改一次）， 都属于 （需要改一次，不过要考虑重复计算）。显然我们可以计算出序列中需要修改的位置对数 ，需要修改的位置为 的总数 ，需要修改的位置为 的总数 与需要修改的一对位置恰好都属于 的总数 ，那么对于某一个 ， 就是答案，我们只需要枚举 即可。

​ 总时间复杂度 。当然，还有不少神奇做法也可以通过本题。

#include <bits/stdc++.h>
using namespace std;

const int N = 400 + 15;
const int M = 2e5 + 5;
int t = 1, n;
int s[M];
int arr[N][N];
int tot[N];
int pairs;

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> s[i];
            s[i] += 200;
        }
        pairs = 0;
        for (int i = 0; i <= 400; i++)
        {
            tot[i] = 0;
            for (int j = i + 1; j <= 400; j++)
                arr[i][j] = 0;
        }
        for (int i = 0; i < n / 2; i++)
            if (s[i] != s[n - 1 - i])
                pairs++, tot[s[i]]++, tot[s[n - 1 - i]]++, arr[min(s[i], s[n - 1 - i])][max(s[i], s[n - 1 - i])]++;
        int res = pairs * 2;
        for (int i = 0; i <= 400; i++)
            for (int j = i + 1; j <= 400; j++)
            {
                int tmp = tot[i] + tot[j] - arr[i][j];
                res = min(res, tmp + (pairs - tmp) * 2);
            }
        cout << res << '\n';
    }
    return 0;
}

彩蛋：如果将负数视为大写字母，正数视为小写字母，那么样例 的前两组测试数据恰好分别对应 和 :)

C - I Wanna Beat the Joke

​ 或许是打表做法最有用的一集：）

​ 对于某个数 ，设 为满足 的最大的 。显然当且仅当 为奇数时，。

​ 我们只要知道前 个正整数有多少个数满足该条件即可，不满足条件的数会提供 的贡献，而满足条件的数不会提供贡献。

​ 时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int t, n, tot;
    cin >> t;
    while (t--)
    {
        cin >> n, tot = 0;
        for (int now = 4; now <= n; now *= 16) // 枚举4^k(k为奇数)
            tot += (n / now) / 4 * 3 + (n / now) % 4;
        cout << 2 * (n - tot) << '\n';
    }
    return 0;
}

Another Solution：容斥 的幂次也能通过，只要思路对怎么写都行。

D - I Wanna Jump the Furthest

​ 跟我一起——蹦蹦跳跳，阳光在照耀；蹦蹦跳跳，我们没烦恼……

​ 在看题解之前，建议先看一看这些提示思考一下：

​ 提示 ：从第二次 “树上跳点” 开始，每次一定是跳 直径。

​ 提示 ：树的所有直径的中点重合，这些点被称为树的 中心（至少 个，至多 个）。

​ 提示 ：似乎存在 奇偶性 问题？有没有反例？如果有，什么时候直接考虑奇偶性会出问题？

​ （虽然接下来有较多分类讨论，但是先想清楚这 点会清晰的多，直接写会比较乱）

​

​ 以下为题解部分：

​ 先说做法，再给证明。先从 号点进行第一次 ，求解出一开始能够到哪些点，记这些点的集合为 。

​ 任选 ，从 出发进行第二次 ，求解出第二次操作后能够到哪些点，记这些点的集合为 。

​ 如果 ，说明从第二次 “树上跳点” 操作开始， 的每一个点都可以被选到（不过 ，因此可不加特判）；否则，说明存在奇偶性问题，奇数次操作时，只能抵达 中的点；偶数次操作时，只能抵达 中的点。时间复杂度 。

​ 接下来是证明。可以发现除了第一次 “树上跳点” 操作外，其余的 “树上跳点” 操作都一定在跳直径。直径有一个关键结论是：若树上所有边边权均为正，则树的所有直径中点重合（这些基础结论的证明可以参考 oi-wiki）。接下来按直径奇偶性讨论一下：

​ *1 直径长度为偶数。那么此时，所谓直径的 “中点” 其实是一条边（也就是树的两个中心之间的边）。

​ 显然每次都必定会从这条边的一端到另一端，因此从 中不管选哪个 出发去求 都是等价的，且必定有 。只有奇数次操作才能到 中的点，偶数次操作才能到 中的点。

​ 另外， 和 分别为完全包含两侧点的点集，因此 包含了所有直径端点，即所有可能选点。

​ *2 直径长度为奇数，此时树只有一个中心 。 一定包含了除了 所在子树外的所有直径的端点（特别地， 时 就是所有直径的端点）。 中的点性质相同（正如前述，都是除了 所在子树外的直径端点），因此从 中不管选哪个 出发去求 都是等价的。

​ 现在，我们统计一下 的深度达到最大的子树数量。

​ 【1】如果 ，或者 不在其中一个深度达到最大的子树内，那么 将包含所有直径的端点，此时显然满足 而且随时可以走到这些端点中的任意一个。接下来不再考虑该情况。

​ 【2】如果这样的子树有 棵，那么由于之前仅有一个子树中的直径端点不在 中，因此无论怎么选 ，求得的 必定与 有交集。此时，我们就既可以选择从 直接前往 ，也可以选择先前往 ，下一步再前往 或者 。选择不同的 时，由于 所处的子树不同， 也会不同。以上的选择覆盖了所有情况，即证得从第二次 “树上跳点” 操作开始， 的每一个点都可以被选到的结论。

​ 【3】如果这样的子树只有 棵，而且 在其中一个最大子树内，那么 、 一定分别对应了这唯二子树中的直径端点， ，每次 “树上跳点” 操作时都将不得不从一个集合跳到另一个集合，因此就有了奇偶性问题。

另外， 最多只会遗漏一个子树中的直径端点，而这些点必定会在 中出现，因此 包含了所有直径端点，即所有可能选点。证毕。本题的另一种做法写在了标程下方作为补充。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int T, n, k;
vector<int> g[N];
int dis[N];
bool tag[N][2];
vector<int> points;

void bfs(int pos)
{
    for (int i = 1; i <= n; i++)
        dis[i] = -1;
    dis[pos] = 0, points.clear();
    int mxdep = -1;
    queue<int> que;
    que.push(pos);
    while (que.size())
    {
        int now = que.front();
        que.pop();
        if (dis[now] > mxdep)
            mxdep = dis[now], points.clear();
        points.push_back(now);
        for (int i : g[now])
            if (dis[i] == -1)
                dis[i] = dis[now] + 1, que.push(i);
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            g[i].clear(), tag[i][1] = tag[i][0] = 0;
        for (int i = 1; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v), g[v].push_back(u);
        }
        bfs(1);
        for (int i : points)
            tag[i][1] = 1;
        bfs(points[0]);
        bool t = 0;
        for (int i : points)
        {
            tag[i][0] = 1;
            if (tag[i][1])
                t = 1;
        }
        if (t)
            for (int i = 1; i <= n; i++)
                cout << (tag[i][0] | tag[i][1]) << ' ';
        else
            for (int i = 1; i <= n; i++)
                cout << tag[i][k % 2] << ' ';
        cout << '\n';
    }
    return 0;
}

​ Another Solution：做 次 。第一次 时，从点 出发，求解可达点集合 ；第二次 时，任选 ，确定直径长度 与第二次操作可达点集合 。第三次 时，任取 ，接下来设 为以 为根的子树内，深度达到最大（即 ）的子树数量。

​ 首先要注意彻底处理完某个点 后，如果 ，则需要设置 ，防止同一子树重复计算贡献。

​ 然后维护 。遇到深度为 的点 时，，否则计算 （ 为满足 的点）。完成 的计算后，需要检查 是否为唯一中心（比较 与 ），如果是唯一中心，即可判断唯一中心存在 个最大深度子树。

​ 不过只做到这里会遗漏直径长度为奇数时【1】的情况，怎么办呢？我们可以比较一下 和 （注意！这里的 是第一次求 时得到的深度）。如果 ，即可说明直径长度为奇数，而且 初始不在唯一中心的任何一个最大深度子树内（或者 就是唯一中心）。底层原理和上面的标程其实是一样的，时间复杂度 。

E - I Wanna Explore the Forest

​ 世界那么大，我想去看看！诶，布豪，这么多条路，我该怎么回去啊 QAQ

​ 我们一起来看看这片森林有什么性质。

​ 设第 次操作的 为 ，再设 。

​ 首先，虽然点数很大，但是在第一次变化操作后，整张图将只剩下 个联通块，且每个联通块中的点编号满足模 同余。

​ 那这个性质能否保持下来呢？其实是可以的，用数学归纳法证明即可（其实手模一下可以很容易地猜出这个结论）。

在第 轮时（假设第 轮时结论成立），新的最大公约数为 。我们对一对满足模 同余的 ，即满足 的位置进行分析。根据裴蜀定理，存在整数 ，满足，因此也就存在整数 ，满足 ，即可以通过组合步长 与 生成步长 ，因此 联通。同理，若 不同余，那也就无法找到对应的 ，即 不联通。

​ 于是证得 重要结论：在第 次操作后，整张图被划分成 个联通块，且每个联通块中的点编号满足模 同余。

​ 由于每次合并之后，所有联通块满足同余，因此在第 次操作后，所有联通块中的最小的点一定分别为 。而在第 次连边中，显然也只有这些点连出去的边才有可能成功建立，因此我们只需要存前 个点的信息即可。

​ 编号大于 的点在第一次变化之后就不会再发生连边，因为 最大为 ，所以之后最多只会发生 次连边。又因为 恒成立，因此之后的连边不会涉及到编号超过 的点。

​ 也就是说，整棵森林长得像这个样子：

​ 那么对于编号不超过 的点，怎么建边呢？第一次可以特殊处理。从第二次开始，我们可以一直尝试建边，如果成功则继续，如果失败则说明 与 已经联通，那么后续由于模 的周期性，对于 ， 与 也已经属于同一联通块，建边全部失败。所以只要一直尝试建边直到失败即可，或者说，只需要建立前 条边即可。

​ 建边逻辑图示如下（样例 / 样例 的情况）：

​ 然后我们来看最短路径的询问。我们只需要设 为根节点，对于编号不超过 的点， 即为答案，也就是要维护 。 确定后就不会变化，可使用 动态解决。

​ 最后怎么处理编号大于 的点呢？我们再看一次这张图：

​ 我们只需要找到此时的 在哪个点 对应的拖尾中（例如点 均在 的拖尾中），同时求出 与 间的距离 ，最后用 即可求出答案。

​ 浅浅分析一下时间复杂度： 看似很暴力（直接从被更新的点扩展更新 ），但一个点不会与太多点有直接连边（原因：对于某个点，第一次变化至多连两条，第二次变化开始只有当 减小时才可能连边，且每次连边至多两条， 作为所有 的 ，减少次数有限）。设 为第 个点 被更新时的度，则时间复杂度 。

​ 或者：也可以在每次 改变时，通过 直接重跑所有点的 。每个点也不会被跑很多次。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int M = 4e5; // 一共需要处理4e5个点的情况
int x, q, p, op, m, M1, G;
vector<int> g[M + 5];
int dep[M + 5];

void dfs(int pos, int from) // 动态维护dep
{
    if (dep[pos] >= 0 || dep[from] == -1)
        return;
    dep[pos] = dep[from] + 1;
    for (int i : g[pos])
        if (dep[i] == -1)
            dfs(i, pos);
}

void Addedge(int u, int v) // 加边的同时动态维护dep
{
    g[u].push_back(v), dfs(u, v);
    g[v].push_back(u), dfs(v, u);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> q >> p;
    for (int i = 1; i <= M; i++)
        dep[i] = -1;
    dep[p] = 0;
    while (q--)
    {
        cin >> op >> m;
        m = x ^ m;
        if (op == 1)
        {
            if (!M1)
            {
                M1 = m, G = m;
                for (int i = 1; i <= M - M1; i++)
                    Addedge(i, i + M1);
            }
            else
            {
                int NewG = __gcd(G, m);
                for (int i = 1; i <= G - NewG; i++)
                    Addedge(i, i + m);
                G = NewG;
            }
        }
        else
        {
            if (!M1) // 不要忘了还没变化时的特判，否则查询编号超过4e5的点时会出错
            {
                cout << (m == p ? 0 : -1) << "\n";
                continue;
            }
            int res = 0;
            if (m > M) // 计算所在拖尾以及到拖尾头部(范围：4e5-m1+1~4e5)的距离
            {
                int head = M - (M % M1 - m % M1 + M1) % M1; // 计算拖尾头部(范围：4e5-m1+1~4e5)的位置
                res = (m - head) / M1;
                m = head;
            }
            if (dep[m] == -1)
                cout << "-1\n", x = 0;
            else
                cout << dep[m] + res << '\n', x = dep[m] + res;
        }
    }
    return 0;
}

F - I Wanna Play I Wanna

​ 我向往自由！我要谈恋爱！——逍遥散人（曾经找不到对象，不过现在也找到属于他的幸福了）

​ 根据 “羁绊” 在所选宝石中的出现次数，我们将所有的 “羁绊” 分类为—— ”羁绊“、 ”羁绊“ 和 ”羁绊“。定义 “升级” 操作为：将 ”羁绊“ 变成 ”羁绊“（实力值增加 ，在下文中我们将其称为 ” 升级“），或者将 ”羁绊“ 变成 ”羁绊“（实力值增加 ，在下文中我们将其称为 ” 升级“）。

​ 显然，每次选取宝石时，都会执行恰好 次 “升级”。

​ 另外我们发现，如果我们对于任意两颗宝石 ，满足 时就在它们之间连边，那么就会形成许多环，且每个宝石都一定在某个环内。

​ 以样例 1 为例：

​ 为了让 “升级” 操作的收益最大化，我们需要尽可能地选择其中收益较大的那种升级方式。

​ ① 当 时：尽可能凑收益更高的 升级。

​ 当 比较小时，显然在环中一个隔着一个取宝石的方式是最优的，此时每次 “升级” 操作都是收益较大的 升级。某个环的大小为 时，该环中即可取 个宝石。此时，每取一颗宝石的收益为 。

如果这样取完之后，仍然需要继续取宝石，则可以先考虑奇环。此时我们还可以从每个奇环中取恰好 颗宝石，使得在被迫将一次 “升级” 机会用给收益较小的 升级的同时，还能执行一次 升级。此时，每取一颗宝石的收益为 。

如果上述操作结束后，仍然需要继续取宝石，则此时已经没有办法执行 升级，只能进行 升级。此时，每取一颗宝石的收益为 。

​ 以上计算只需要分别统计奇环与偶环的个数与大小即可完成，时间复杂度 。

​ ② 当 时：尽可能凑收益更高的 升级。

​ 为了尽量不将升级机会浪费给收益较小的 升级，我们要尽可能把整个环都取干净。假设某个环（设大小为 ）中的宝石能够被全部取出，那么在这 次选取宝石带来的 次升级机会中，有 次升级机会给了 升级，还有 次升级机会全都给了 升级，显然这样做在所有凑 升级的方法中效率最高（毕竟 升级的前提是 升级，先要有一次 “羁绊” 升级为 “羁绊” 才可能有 “羁绊” 升级为 “羁绊”）。

​ 于是任务就变成了：判断是否有一种取 颗宝石的方法，使得选取的 颗宝石恰好占满了某些环。为方便后续说明，我们将问题的表述变成：找到一个最大的 ，满足 ，且 恰好是某些环的大小之和。这样就变成了一个背包问题。如用 背包求解，时间复杂度最坏可以达到 （每个环大小均为 ，共有 个环），无法接受。

​ 怎么优化这个 ？有以下优化方法：

​ ① 环大小的种类一定不会太多，若要出现 种大小不同的环，则至少需要 颗宝石，显然是不可能的，也就是说环大小的种类数不会超过 。据此我们可以用多重背包求解，优化至此时间复杂度大致为 。

​ ② 的状态只有 “能取到” (1) 和 “不能取到” (0) 两种，考虑 bitset 优化，时间复杂度进一步降低到 。

​ ③ 剪枝：若 ，则在 计算时暂时令 。

​ 实测：必须考虑多重背包，②、③的优化使用任意一个即可

​ 如果确实存在满足上述条件的取法，即 ，那么显然实力值为 。

​ 如果不满足，即 ，则我们可以先将这 颗宝石取好（即选取 颗宝石恰好占满某些环）。那么对于还没有取宝石的那些环，大小必定都大于 ，此时只需要选取其中一个环，连续选取 颗宝石即可。最终只会有 个 “羁绊” ，其余的被 “升级” 过的 “羁绊” 均为 “羁绊”， 升级次数最大化。显然实力值为 。

​ TIPS：本题中的 状态仅有 和 ，单调队列常数相比仅使用 的做法更大，因此单调队列优化反而运行效率更低。

#include <bits/stdc++.h>
using namespace std;

const int N = 1.2e6 + 10;
int n, k;
long long res, p[3]; // p3(女神异闻录3)真好玩嗷(不是)
int a[N], pb[N], tot[N];
bool vis[N];
bitset<N / 2> dp;

void dfs(int pos) // 可以拿并查集替代
{
    int now = pos, now_siz = 0;
    do
    {
        now = pb[a[now]];
        vis[now] = 1, now_siz++;
    } while (now != pos);
    tot[now_siz]++;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k >> p[0] >> p[1] >> p[2];
    res = p[0] * n, dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;
        a[i] = u, pb[v] = i;
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i);
    if (2 * p[1] > p[0] + p[2]) // 凑1"羁绊"
    {
        for (int i = 2; i <= n; i++)
        {
            int c = min(k, (i / 2) * tot[i]);
            res += (p[1] - p[0]) * c * 2, k -= c;
        }
        for (int i = 1; i <= n; i += 2)
        {
            int c = min(k, tot[i]);
            res += (p[2] - p[0]) * c, k -= c;
        }
        for (int i = 2; i <= n; i++)
        {
            int c = min(k, (i / 2) * tot[i]);
            res += (p[2] - p[1]) * c * 2, k -= c;
        }
    }
    else // 凑2"羁绊", bitset优化二进制多重背包
    {
        vector<int> goods;
        for (int i = 1; i <= n; i++)
            if (tot[i])
            {
                int now = 1, cur = tot[i];
                while (cur >= now)
                {
                    cur -= now, goods.push_back(i * now);
                    now <<= 1;
                }
                if (cur)
                    goods.push_back(i * cur);
            }
        for (int i : goods)
            dp |= (dp << i);
        if (dp[min(k, n - k)])
            res += (p[2] - p[0]) * k;
        else
            res += (p[2] - p[0]) * (k - 1) + (p[1] - p[0]) * 2;
    }
    cout << res << '\n';
    return 0;
}