Japanese Student Championship 2021

前言：这场的题解由于蓝桥杯比赛拖延几天才发

关于本篇题解，目前还是有部分题没有解答出来正在加油补题ing

补题链接：Here

A - Competition

题意：给定 代表的意义为，超市一以 Y 元卖 X 克食料包

现在超市二的一包食料包重 克，请问超市二的售价为多少才能比超市一便宜

思路：

理解一下题意就容易发现：

B - Xor of Sequences

给定两个严格上升的整数序列 A，B，现求仅出现在A和B的数字，最后结果升序打印

思路：

由于两个序列数据范围不大，直接暴力循环即可

然后赛后看了一下高rank的代码发现了一个函数：set_symmetric_difference

set_symmetric_difference 可构造区间S1,S2的对称差集（出现于S1但不出现于S2的元素以及出现于S2但不出现于S1的元素）;返回值为指向输出区间的尾端。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> A(n), B(m);
    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;
    vector<int> C;
    set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C));
    for (int x : C) cout << x << " ";
}

C - Max GCD 2

题意：给定一个区间，问 求问最大的 #card=math&code=gcd%28x%2Cy%29)

说实话，比赛的时候还真没想到这个方法。

思路：

由于数对 #card=math&code=%28x%2Cy%29) 的个数最多 ，所以我们不可能计算每一对 #card=math&code=%28x%2Cy%29) ，相反的、并考虑是非问题“是否存在一对 #card=math&code=%28x%2Cy%29) 使得 %20%3D%20c#card=math&code=gcd%20%28x%EF%BC%8Cy%29%20%3D%20c)？”

因为 是最大公约数，所以 都应该是 的倍数，相反如果在 区间中 的倍数多于两个值，则可以选择 使得 %20%3D%20c#card=math&code=gcd%28x%2Cy%29%20%3D%20c) 成立

由于 所以运行速度会足够快

把上面的话转化为数学表达式：A ~ B 之间 C 的倍数 = （C 的倍数在 ~ 之间） - （C 的倍数在 ~ 之间）=

再转化一下就是检查

void solve() {
    int A, B;
    cin >> A >> B;
    for (int c = B;; c--)
        if ((A + c - 1) / c < B / c) {
            cout << c << endl;
            return;
        }
}

D - Nowhere P

给定质数 ，求有多少序列 #card=math&code=%28A_1%2CA_2%2C%5Cdots%2CA_N%29) 满足：

%0A#card=math&code=%5Cforall%20i%5Cin%5B1%2Cn%5D%5Cmathbb%7BN%7D%2C%5Csum%7Bj%20%3D%201%7D%5Ei%20A_j%20%5Cnot%20%5Cequiv%200%5C%20%28mod%5C%20P%29%0A)

显然，当 时答案为 ，对应合法序列为 %2C(2)%2C%5Cdots%2C(p%20-%201)#card=math&code=%281%29%2C%282%29%2C%5Cdots%2C%28p%20-%201%29)

之后在这些合法序列后插入新数时，每个序列都有且仅有一个数使得这个数插入后该序列非法（该数即为 %5C%20mod%5C%20p#card=math&code=%28-%5Csum_ia_i%29%5C%20mod%5C%20p)

故答案为：(p-2)%5E%7BN-1%7D#card=math&code=%28p%20-1%29%28p-2%29%5E%7BN-1%7D)

跑 qpow 的时候记得取模

const int mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll ans = 1;
    a %= mod;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) ans = ans * a % mod;
    return ans;
}
void solve() {
    ll N, P;
    cin >> N >> P;
    cout << (P - 1) * qpow(P - 2, N - 1) % mod;
}

E - Level K Palindrome

本题所有的字符串均指只由小写英文字母构成的字符串

对字符串 ,

• 定义其反转为: #card=math&code=%5Coperatorname%7Brev%7D%28s%29), 则 是回文串 #card=math&code=s%20%3D%20rev%28s%29)
• 运算定义为字符串的拼接
• 定义字符串上的变换为：将其中某一字符替换为一小写英文字母

定义 阶回文串如下:

• 空串，非回文串为 阶回文串
• 对 阶非空回文串 定义 #card=math&code=s%20%2B%20rev%28s%29) 为 阶回文串
• 对 阶非空回文串 和单个字符 #card=math&code=s%20%2B%20c%20%2B%20rev%28s%29) 为 阶回文串

给一字符串 问至少经几次变换可使其恰好为 阶回文串

解题思路

显然，若有解则 不可能过大

待补

F - Max Matrix

有一个长为 的全零序列 和长为 的全零序列 ,对其做如下操作

• 将 中的某个数赋一个值
• 将 中的某个数赋一个值

这两种操作一共进行 次，要求每次操作后都要输出

待补

G - Spanning Tree

有n个点，考虑以这n个点为顶点，满足如下条件的所有图:

• 无向图

• 给出一个矩阵

  • 若 ,则点 和点 间没有边
  • 若 ,则点 和点 间没有边
  • 若 ,则为上述两种情况的任-种

求这些图中树的个数

思路

首先，考虑所以已经存在的边构成的图，如果有环了，则答案一定为0,否则森林中的每个树都可缩成一个点，之后用矩阵树定理即可

H - Shipping

给一个带权无向图，求满足如下条件的子图的最小边权和

%20%5Cnot%3D%20%E2%88%9E%0A#card=math&code=%5Cforall%20%5Cin%5B1%2CM%5D_%5Cmathbb%7BN%7D%2Cdis%28x_i%2Cy_i%29%20%5Cnot%3D%20%E2%88%9E%0A)