牛客小白月赛42题解

A题 冰狱寒岚

仔细观察一下，会发现

当$x\le 1023x\backslash leq1023$时，直接输出这个数；

当$x>1023x\backslash gt1023$时，输出$-1024+(n-1)-1024+\backslash left(n-1\backslash right)$%2048

我们解释一下第二部分吧，可以发现就是将当数$x>=1024x>=1024$时，从-1024开始计数，那么也就是说将一个数减去1024后映射到-1024~1023，我们考虑将x映射到0到2047，也就是(x-1024)%2047，最后再减去1024就是-1024到1023了

#include <bits/stdc++.h>

using namespace std;

#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

void solve() {
    ll n;
    cin >> n;
    if (n <= 1023) {
        cout << n << " ";
        return;
    }
    cout << -1024 + (n - 1024) % 2048 << " ";
}

signed main(void) {
    IO;
	int t;
	cin >> t;
	while (t -- ) {
		solve();
    }
    return 0;
}

B题 光之屏障

显然由$2^{30}>1e92^\{30\}\backslash gt1e9$

那么我们对每一个最多暴力30次就可以了

或者我们将每个$2^i\le 1e92^i\backslash leq1e9$的数放入容器中，每次二分就可以了

#include <bits/stdc++.h>

using namespace std;

#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

void solve() {
    int a, b;
    cin >> a >> b;
    int cnt = 1;
    while (cnt <= b) {
        if (cnt >= a && cnt <= b) {
            cout << cnt << endl;
            return;
        }
        cnt *= 2;
    }
    cout << "-1\n";
}

signed main(void) {
    IO;
	int t;
	cin >> t;
	while (t -- ) {
		solve();
	}
    return 0;
}

c题 寒潭烟光

$ans=\frac{F\left(x\right)\times n+x_0\times (n+1)}{(n+1)}ans\; =\; \backslash frac\{F\backslash left(x\backslash right)\; \backslash times\; n\; +\; x\_0\backslash times(n+1)\}\; \{(n\; +\; 1)\}$

$F(x)\times nF(x)\; \backslash times\; n$即可得到数列s的和，那么$x_{0}x\_0$对数列s的贡献为$x_0\times (n+1)x\_0\; \backslash times\; \backslash left(n+1\backslash right)$，最后就可以求解平均值了

#include <bits/stdc++.h>

using namespace std;

#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    cout << (a * n + b * (n + 1)) / (n + 1) << endl;
}

signed main(void) {
    IO;
	int t;
	cin >> t;
	while (t -- ) {
		solve();
	}
    return 0;
}

D题 金蛇狂舞

这题即使是小白也应该能够一眼bfs吧，那么就直接bfs就行了 每次bfs由3中选择，就最多会有$3^7=2187\mathrm{个}\mathrm{状}\mathrm{态}3^\{7\}\; =\; 2187个状态$

上取整$ceil\left(x\right)ceil\backslash left(x\backslash right)$

下取整$floor\left(x\right)floor\backslash left(x\backslash right)$

比较难处理的就是阶乘这个东西了，我们不知道他的范围会有多大，可以肯定的是用到的状态不会太多，20！是在longlong范围内，那么我们需要2次阶乘可以得到一个大于20!的数，那么通过对其5次开根号，其值仍大于7，故当要对一个大于20的数做阶乘操作时，我们直接continue掉，我们开一个map记录到达一个点的最短距离就可以了

#include <bits/stdc++.h>

using namespace std;

#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

int x, y;
map<ll, int> dist;

ll get(int n) {
    ll ans = 1;
    rep(i, 1, n) {
        ans *= i;
    }
    return ans;
}

void solve() {
    dist.clear();
    cin >> x >> y;
    dist[x] = 0;
    queue<int > q;
    q.push(x);
    while (!q.empty()) {
        ll u = q.front(); q.pop();
        if (dist[u] >= 7 || u == y) break;
        if (u <= 20) {
            ll v = get(u);
            if (!dist.count(v)) dist[v] = dist[u] + 1, q.push(v);
        }
        ll w1 = floor(sqrt((double) u)), w2 = ceil(sqrt((double) u));
        if (!dist.count(w1)) dist[w1] = dist[u] + 1, q.push(w1);
        if (!dist.count(w2)) dist[w2] = dist[u] + 1, q.push(w2);
    }
    if (dist.count(y)) {
        cout << dist[y] << endl;
    }
    else cout << "-1\n";
}

signed main(void) {
    IO;
	int t;
	cin >> t;
	while (t -- ) {
		solve();
	}
    return 0;
}

E题 暗灭侵烛

直接让最小点以最大点为中心条约就可以了， 我们考虑、证明这个结论.

设最小点，次小点，最大点依次为a,b,c

动最小点得到$2\times c-a2\; \backslash times\; c\; -\; a$

动次小点得到$2\times c-b2\; \backslash times\; c\; -\; b$

由此可以得到每次动最小点比较优

#include <bits/stdc++.h>

using namespace std;

#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

void solve() {
    int a[4] = {}, n;
    cin >> a[0] >> a[1] >> a[2] >> n;
    int x = max({a[0], a[1], a[2]});
    int cnt = 0;
    while (x < n) {
        sort(a, a + 3);
        x = 2 * a[2] - a[0];
        a[0] = x;
        cnt++;
    }
    cout << cnt << endl;
}

signed main(void) {
    IO;
	int t;
	cin >> t;
	while (t -- ) {
		solve();
	}
    return 0;
}

F题 火凤燎原

怎么说呢，f题看起来是一个比较难的题目，但是其实仔细分析一下也是一个简单题吧 我们考虑以节点u作为中心点

如果，直接continue就好了

如果$d_u\ge 3d\_\{u\}\; \backslash geq\; 3$那么我们假设u为根节点 接着考虑以u点的一个儿子v作为一条链的起点，那么就会有$si{z}_v-1siz\_\{v\}\; -\; 1$中不同的链($si{z}_{v}siz\_\{v\}$代表以v为根的子树大小，减去的1代表链只有儿子节点，那么就不满足情况），那么以每个u的每个儿子节点为链的情况总数为每个儿子的子树大小和-儿子个数，也就是$n-1-d_{u}n-1-d\_\{u\}$

#include <bits/stdc++.h>

using namespace std;

#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

constexpr int N = 1e5 + 10;
int n, d[N], siz[N];

void solve() {
    cin >> n;
    rep(i, 1, n) {
        d[i] = siz[i] = 0;
    }
    rep(i, 1, n - 1) {
        int a, b;
        cin >> a >> b;
        d[a]++, d[b]++;
    }
    ll ans = 0;
    rep(i, 1, n) {
        if (d[i] >= 3) {
            ans += (n - 1 - d[i]);
        }
    }
    cout << ans << endl;
}

signed main(void) {
    IO;
	int t;
    cin >> t;
	while (t -- ) {
		solve();
	}
    return 0;
}