简要题解

A

根据等差中项的定义，，所以 ，直接输出即可。

当然如果你 for 循环一个个找那也是能过的。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << 2 * b - a << endl;
    return 0;
}

B

我们按位考虑，注意到一共可操作 位（因为 ），然后对于每一位（设 的第 位为 ），若 ，则为了使最后按位与出来的结果一样， 必须为 ，否则 就为 （为了使 尽量大）。

当然实际上这就是 和 的同或运算，直接输出 LONG_LONG_MAX ^ a ^ b 也可。

#include <bits/stdc++.h>

using namespace std;
long long a, b, ans;

int main() {
    cin >> a >> b;
    ans = LONG_LONG_MAX ^ a ^ b;
    cout << ans << endl;
    return 0;
}

C

一开始可能大家会想二分，但是完全没有必要。

斐波那契数列增长的很快，事实上其只有不到 项是在 ll 范围的，直接暴力判断即可。

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;
using ll = long long;

ll F[105];
int n;

inline ll myabs(ll x) {return x >= 0 ? x : -x;}

int main() {
    F[1] = 1, F[2] = 1;
    FOR(i, 3, 88) F[i] = F[i - 1] + F[i - 2];
    cin >> n;
    while (n --) {
        ll a; cin >> a;
        int ans = 1;
        FOR(i, 1, 88) if (myabs(F[i] - a) < myabs(F[ans] - a))
            ans = i;
        cout << ans << '\n';
    }
    return 0;
}

D

注意到两人可操作的次数一定是 ，所以算出总操作次数后，若其为奇数则一定是至至子胜（轮到苏苏子的时候他一定没办法操作），否则就是苏苏子胜。

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
int n; ll a[maxn];

int main() {
    cin >> n;
    ll ret = 0;
    FOR(i, 1, n) cin >> a[i], ret += (a[i] - i);
    cout << ((ret & 1) ? "ZZZ" : "SSZ") << endl;
    return 0;
}

E

注意到一条长链上的 值一定是 这样的形式，并且整棵树中最大的 值只能有一个，不难发现其为根节点。

于是构造流程如下：

• 先找到根节点，然后引出这条最长的长链。
• 然后从当前最大的 值开始（令其为 ），依次取出 构成一条长链，然后接到树上已有的任意合法节点上（即接上去之后原来的 值不会被破坏）。
• 重复第二步直到构造完这棵树为止。

如果中间的任意一步无法进行下去，报告无解即可。时间复杂度 或 ，取决于实现。

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;
const int maxn = 2e5 + 5;
int n, h[maxn];
vector<int> vec[maxn];

void solve() {
    cin >> n;
    FOR(i, 0, n - 1) vector<int>().swap(vec[i]);
    int maxh = 0;
    FOR(i, 1, n) cin >> h[i], vec[h[i]].emplace_back(i), maxh = max(maxh, h[i]);
    vector<pair<int, int>> E;
    if (vec[maxh].size() > 1) return cout << "-1\n", void();
    int root = vec[maxh].back();
    while (E.size() < n - 1) {
        while (maxh >= 0 && vec[maxh].empty()) --maxh;
        if (maxh < 0) return cout << "-1\n", void();
        int hm = maxh;
        for (int las = root, cur = hm; cur >= 0; --cur) {
            if (vec[cur].empty()) return cout << "-1\n", void();
            int u = vec[cur].back();
            if (u != las) E.push_back({las, u});
            las = u;
            vec[cur].pop_back();
        }
    }
    cout << root << '\n';
    for (auto &p : E) cout << p.first << ' ' << p.second << '\n';
    return;
}

int main() {
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

F

首先不难发现每个公司都是一棵树。

然后只考虑一个公司的话，相当于要对这棵树的拓扑序进行计数（将其视为叶向树），考虑树形 dp。

设 为只考虑 子树的拓扑序个数，转移的话首先 必须在第一个，剩下的随缘归并一下就行，用多重组合数类似的想法就是

预处理阶乘和阶乘逆，按照上面的方式转移即可求出每棵树的方案数 。然后再归并一下啥的就是

（事实上你可以将其看作一个虚拟的根，然后转移跟上面是同构的）。

当然，对于一棵 个节点的树，其拓扑序数量还可以如下计算：

利用上面的 dp 式子，将 除到左边，设 ，则可以归纳得到下式，反正都可以过题。

为了不卡常，数据范围只开到了 ，时间复杂度 或 。

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define DEC(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;
const int maxn = 1e5 + 5, N = 1e5, mod = 1e9 + 7;
int fa[maxn], n, tot, c;
int fac[maxn], ifac[maxn], size[maxn], f[maxn];

int qPow(int base, int exp) {
    int ret = 1;
    for (base %= mod; exp; exp >>= 1, base = 1ll * base * base % mod)
        if (exp & 1) ret = 1ll * ret * base % mod;
    return ret;
}

inline int binom(int n, int m) {return n < m ? 0 : 1ll * fac[n] * ifac[m] * ifac[n - m] % mod;}

vector<int> G[maxn];

void dfs(int u) {
    f[u] = size[u] = 1;
    for (auto &v : G[u]) {
        dfs(v);
        f[u] = 1ll * f[u] * f[v] % mod * ifac[size[v]] % mod;
        size[u] += size[v];
    }
    f[u] = 1ll * f[u] * fac[size[u] - 1] % mod;
    return;
}

int solve(int n) {
    FOR(i, 1, n) vector<int>().swap(G[i]);
    FOR(i, 2, n) cin >> fa[i], G[fa[i]].push_back(i);
    dfs(1);
    return f[1];
}

int main() {
    fac[0] = 1;
    FOR(i, 1, N) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[N] = qPow(fac[N], mod - 2);
    DEC(i, N - 1, 0) ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod;
    int ans = 1;
    cin >> n;
    FOR(i, 1, n) {
        cin >> c;
        tot += c;
        ans = 1ll * ifac[c] * ans % mod * solve(c) % mod;
    }
    cout << 1ll * ans * fac[tot] % mod << endl;
    return 0;
}