牛客小白月赛55题解

 其实真的很希望发题解的时候...能带上题目...

链接： https://ac.nowcoder.com/acm/contest/38630/A

至至子今天刚学习了等差中项。两个数 x 和 y 的等差中项定义为 x+y/2。

现在至至子想考验你，他会给你两个正整数 a 和 b，让你求一个 c 使得 b 为 a 和 c 的等差中项。

------------------------------------------------------------------------------------------------------------------------------------------

模拟

a,b=map(int,input().split())
print(b+b-a)

链接： https://ac.nowcoder.com/acm/contest/38630/B
至至子很喜欢按位与运算。
他会给你两个正整数 a,b，想让你回答他一个整数 c。为了避免 c 过大而搞坏他的脑子，他要求 c<2^63。
由于他喜欢按位与运算，所以请让 c 满足 a&c=b&c（其中 & 为按位与运算）并且让 c 尽可能地大。
可以发现这一定是有解的。

------------------------------------------------------------------------------------------------------------------------------------------

用2^63-1减去二者异或即可

模拟

a,b=map(int,input().split())
x=pow(2,63)-1
print(x-a^b)

链接： https://ac.nowcoder.com/acm/contest/38630/C
至至子很喜欢斐波那契数列，斐波那契数列 Fn
至至子会进行 T 次询问，每次询问给定一个数 ai ，他想让你找到斐波那契数列中距离 ai 最近的一项，即求一个正整数 x 使得在满足 ∣Fx−ai∣ 最小的基础上 x 尽量小。

------------------------------------------------------------------------------------------------------------------------------------------

打表+二分查找

注意1e18的枚举

ll i, n, m, x, y, len, A[106] = { 0,1 }, a, b, c;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    for (m = 2; A[m - 1] <= 1e18; ++m)A[m] = A[m - 1] + A[m - 2];

    ++m;

    for (cin >> n; n; --n) {
        cin >> x;

        y = lower_bound(A, A + m, x) - A;

        a = A[y - 1], b = A[y];

        if (x - a <= b - x)cout << y - 1 << endl;
        else cout << y << endl;
    }

链接： https://ac.nowcoder.com/acm/contest/38630/D
至至子和苏苏子玩游戏。
给定一个序列 a，长度为 n，且满足 1≤a1<a2<⋯<an。
两人轮流对序列进行操作，至至子先手。每人每次选择一个 aia_iai 并让其减一，要求不破坏 1≤a1<a2<⋯<an 的性质，无法操作者输。
假设至至子和苏苏子都绝顶聪明，那么请同样聪明绝顶的你告诉我，最后谁能赢。

------------------------------------------------------------------------------------------------------------------------------------------

显然考虑最终结果为： 1 2 3...

则求可以操作的次数： m (每次读入的数 - i)

由奇偶性定胜负

博弈论

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    for (ll n = read(), i = 1, m = 0; i <= n; ++i)m += read() - i;

    puts(m&1?"ZZZ":"SSZ");
}

链接： https://ac.nowcoder.com/acm/contest/38630/E
对于 n 个节点有根树（点的编号从 1 到 n），我们设节点 u 的“长链长度”为 hu
即对于叶子节点，其 h 值为 0，否则为所有儿子节点中最大的 h 值 +1。

现给定一棵树的 h1,h2,⋯,hn，请还原该树的形态，或报告无解。如有多棵满足限制的树，输出任意一棵即可，详见输出格式。

其中，叶子节点指没有子节点的节点， son(u) 表示 uuu 节点的儿子节点构成的集合。

------------------------------------------------------------------------------------------------------------------------------------------

用二维表模拟，二维表A[i][j]表示有个i个儿子的数组中第j个数

若拥有最大儿子节点不止一个orA[i]<A[i+1]前面i个的无法支持起后面i+1个节点则输出-1否则模拟输出（注意边界问题）

注意每次的数组清空

思维题

ll n, m, t, a, b, c, d, i, j, N = 1e5 + 2;

vector<vector<ll>>A;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    A.resize(N << 1);

    for (t = read(); t; --t) {
        d = -1;

        for (n = read(), i = 1; i <= n; ++i)c = read(), A[c].push_back(i), d = max(c, d);

        a = d;

        if (A[d].size() > 1)d = -1;
        else for (i = 0; i < d; ++i)if (A[i].size() < A[i + 1].size()) d = -1;

        if (d == -1) cout << -1 << endl;
        else {
            cout << A[a].back() << endl;

            for (i = a - 1; i != -1; --i) for (j = 0; j < A[i].size(); ++j)
                cout << A[i + 1][min(j, A[i + 1].size() - 1)] << ' ' << A[i][j] << endl;
        }
        
        for (i = 0; i <= a; ++i)A[i].clear();
    }
}

链接： https://ac.nowcoder.com/acm/contest/38630/F
至至子开有 n 家公司，第 iii 家公司有 ci 个员工，并且在该公司内形成了 ci−1对 直接上下级的关系（注意到 BOSS 是没有直接上级的）。

今天他良心发现想让这 n 家公司的所有员工排队买票旅游。
然而这些人的等级观念很重——他们约定一个人在排队的时候不能排在其直接或间接上级的前面（若 a 是 b 的直接上级或间接上级， b 是 c 的直接/间接上级，则 a 是 c 的间接上级）。
于是至至子很好奇，一共有多少种符合条件的排队方案呢？由于这个数可能很大，所以请输出答案对 1000000007 取模的结果。

------------------------------------------------------------------------------------------------------------------------------------------

先用个简单的样例想想：

两条已经确定顺序且长度为a,b的链子合并出来的新链子有（a+b）! /a! /b! 种情况（n！代表阶乘）

同理如果是a,b,c三条链子合并则可以等同为a，b先合并再同c合并为新链子，一共（a+b+c）!/ a! /b! /c! 种情况

那么现在问题就转化为在第t个公司中以i为boss的链子有多少中情况，显然为树形dp？？？

好吧，其实可以直接记录答案ans的...

最后合并n个公司的所有链子即可

------------------------------------------------------------------------------------------------------------------------------------------

以下代码中A[i]代表i的阶乘%1e9+7，C[i]代表以i为boss的链子长度，e代表总人数

关键在于求逆元以及dfs中思想以及数组的清空（其实这个测评的数据量好像不是很大...）

ll i, n, m, j, k, A[N] = { 1 }, ans = 1, e, C[N], y;

inline ll ni(ll a) {
    return pow(a, mod - 2, mod);
}

vector<vector<ll>>biao;

void dfs(ll x) {

    while (!biao[x].empty()) {
        ll y = biao[x].back();

        biao[x].pop_back();

        dfs(y);

        ans = ans * ni(A[C[y]]) % mod;

        C[x] += C[y];
    }

    ans = ans * A[C[x] - 1] % mod;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    for (i = 1; i <= 1e5; ++i)A[i] = A[i - 1] * i % mod;

    n = read();

    for (i = 0; i < n; ++i) {
        m = read(); 
        e += m;
        ans = ans * ni(A[m]) % mod;
        C[1] = 1;

        biao.resize(m + 1);

        for (auto& x : biao)x.clear();

        for (j = 2; j <= m; ++j) {
            k = read();
            
            C[j] = 1;

            biao[k].push_back(j);
        }

        dfs(1);
    }

    ans = ans * A[e] % mod;
    cout<<ans<<endl;
}

------------------------------------------------------------------------------------------------------------------------------------------

注：以上为关键代码，C++中快读以及头文件如下

#include <bits/stdc++.h>
#pragma GCC optimize(2)

using namespace std;
#define ll long long
#define endl '\n'

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

本人也是第一次写题解...码风有待改进，望多多包涵