牛客周赛 Round 67 A~F题解

Preface

好久没v过牛客周赛了，但估计这场强度不高是特例吧，感觉AK还是不太难的，最后一题也还好，想到了做起来也不太难，还是多v挑战赛吧。

所有代码前面的火车头

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
template<typename T>
void cc(vector<T> tem) { for (auto x : tem) cout << x << ' '; cout << endl; }
void cc(int a) { cout << a << endl; }
void cc(int a, int b) { cout << a << ' ' << b << endl; }
void cc(int a, int b, int c) { cout << a << ' ' << b << ' ' << c << endl; }
void fileRead() {
#ifdef LOCALL
    freopen("D:\\AADVISE\\cppvscode\\CODE\\in.txt", "r", stdin);
    freopen("D:\\AADVISE\\cppvscode\\CODE\\out.txt", "w", stdout);
#endif
}
void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
inline int max(int a, int b) { if (a < b) return b; return a; }
inline int min(int a, int b) { if (a < b) return a; return b; }
void cmax(int& a, const int b) { if (b > a) a = b; }
void cmin(int& a, const int b) { if (b < a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;

Problem A.排序危机

只能说这个签到给我写复杂了，其实只需要先输出小写字母，再输出数字，最后输出大写字母就好了，我却唐成了结构体排序，复杂度还多了一个

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;

//--------------------------------------------------------------------------------
//struct or namespace:
struct node {
    char x;
    int val;
    int id;
};
node A[N];
//--------------------------------------------------------------------------------

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        rep(i, 1, n) {
            char a; int b; cin >> a;
            if (a <= '9' and a >= '0') b = 2;
            if (a <= 'z' and a >= 'a') b = 1;
            if (a <= 'Z' and a >= 'A') b = 3;
            A[i] = { a,b,i };
        }
        sort(A + 1, A + n + 1, [&](const node& q1, const node& q2) {
            if (q1.val == q2.val) return q1.id < q2.id;
            return q1.val < q2.val;
            });
        rep(i, 1, n) {
            cout << A[i].x;
        }

    }
    return 0;
}
/*


*/

Problem B.小歪商店故事：卷

按照题意模拟就好了，直接计算就好了，要注意整除的情况。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;

//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int aa = b * c / d;
        if ((b * c) % d == 0) aa -= 1;
        cout << a - aa << ' ';

    }
    return 0;
}
/*


*/

Problem C.小苯的计算式

的范围比较小，一眼直接暴力枚举即可，也就能直接出来了。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;

//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    // cin >> T;
    while (T--) {
        int c; cin >> n >> c;
        n -= to_string(c).size() + 2;
        int ans = 0;
        rep(i, 0, c) {
            string a = to_string(i), b = to_string(c - i);
            if (a.size() + b.size() == n) ans++;
        }
        cc(ans);

    }
    return 0;
}
/*


*/

Problem D.K

感觉总算有点不是给小白做的题了，区域赛签到题水平？

当的时候直接一直输出就好了。

随便手玩一下，会发现可以直接构造1，2，1，2，这种长度是的序列我们可以造出来的情况来，如果的情况，我们就可以直接让后面一直循环一个数字，变成1，2，1，2，2， 2， 2，这种就能够满足了，代码中间只需要注意是让循环还是循环就好。

顺便要注意会有的情况，要特判，因为这个了一发。TAT

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;

//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        int k; cin >> n >> k;
        if (k > n) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        
        if (n == k) {
            rep(i, 1, n) cout << 1 << " ";
            continue;
        }
        if (n - 1 == k) {
            for (int i = 1; i <= n; i += 2) {
                cout << "1 2 ";
            }
            continue;
        }
        if (k % 2 == 0) {
            for (int i = 1; i <= k / 2; i++) {
                cout << "1 2 ";
            }
            cout << 1 << " ";
            for (int i = 1; i <= n - k - 1; i++) {
                cout << 1 << " ";
            }
        }
        else {
            for (int i = 1; i <= (k + 1) / 2; i++) {
                cout << "1 2 ";
            }
            for (int i = 1; i <= n - k - 1; i++) {
                cout << 2 << " ";
            }
        }

    }
    return 0;
}
/*


*/

Problem E.小苯的区间选数

首先应该一眼反应过来就是要在到之间选择就好了，竟然一开始没看出来。。。

之后还是手玩一下会发现，比如我们只需要找到两个数字第一个不相等的地方，使这一个位置是，后面一直变成就好了。如果和的长度不一样，给补上前导就好了。

但要注意如果r本身就是结尾的情况，我们只需要再计算一下和的情况就可以解决。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        int l1, l2, r1, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int l = l1 + l2, r = r1 + r2;
        int ans1 = 0, ans2 = 0, ans3 = 0;
        string s1 = to_string(l), s2 = to_string(r);
        for (auto& x : s1) {
            ans1 += x - '0';
        }
        for (auto& x : s2) {
            ans2 += x - '0';
        }
        while (s1.size() != s2.size()) s1 = '0' + s1;
        int len = s1.size();
        int num = 0;
        for (int i = 0; i < len; i++) {
            if (s1[i] == s2[i]) {
                ans3 += s1[i] - '0';
                num = (s1[i] - '0') + num * 10;
                continue;
            }
            ans3 += (s2[i] - '0' - 1);
            ans3 += 9 * (len - 1 - i + 1 - 1);
            break;
        }
        ans1 = max({ ans1,ans2,ans3 });
        cc(ans1);
    }
    return 0;
}
/*
 
 
*/

Problem F.小Z的树迁移

只能说写这题脑子有些唐了，竟然默认成这个树会是一个均摊的树，算下来发现不到20，直接写了个暴力，只能说脑子太秀逗了。

之后冷静思考，发现纯纯暴力启发式合并就好了。先离线处理询问。给每一个点开一个并查集，里面开一个，是层数，是存有这个点子树内每一层的最大值就好了，代表点到达根节点之间的距离。计算向下走次的答案时便是。

关于启发式合并的复杂度这里便不再赘述，用的是比较好写的写法，复杂度会因为多一个，可以使用树上启发式合并，复杂度是会少一个的。

时间复杂度是

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
vector<PII> A[N];
vector<PII> qs[N];
int pre[N], dep[N];
int ans[N];
//--------------------------------------------------------------------------------
//struct or namespace:
namespace DSU {
    const int N = 1e5 + 10;
    struct Info {
        int fa;
        int siz;
        map<int, int> mp;
    };
    Info dsu[N];
    void init(int n) {
        //TO DO 记得初始化
        rep(i, 0, n) {
            dsu[i].fa = i, dsu[i].siz = 1;
        }
    }
    int find(int x) { if (x == dsu[x].fa) return x; return dsu[x].fa = find(dsu[x].fa); }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        dsu[y].fa = dsu[x].fa;
        if (dsu[x].siz < dsu[y].siz) swap(x, y);
        dsu[y].fa = dsu[x].fa;

        dsu[x].siz += dsu[y].siz;
        for (auto [a, b] : dsu[y].mp) {
            cmax(dsu[x].mp[a], b);
        }
    }
    bool same(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return 1; return 0;
    }
    int size(int x) { return dsu[find(x)].siz; }
}
using DSU::dsu;
//--------------------------------------------------------------------------------

void dfs(int x, int pa) {
    dep[x] = dep[pa] + 1;

    for (auto [y, val] : A[x]) {
        if (y == pa) continue;
        pre[y] = pre[x] + val;
        dfs(y, x);
    }

    dsu[x].mp[dep[x]] = pre[x];
    for (auto [y, val] : A[x]) {
        if (y == pa) continue;
        DSU::merge(x, y);
    }

    int rt = DSU::find(x);
    for (auto [dis, id] : qs[x]) {
        if (dsu[rt].mp.find(dis + dep[x]) == dsu[rt].mp.end()) ans[id] = -1;
        else ans[id] = dsu[rt].mp[dis + dep[x]] - pre[x];
    }

}

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        rep(i, 1, n - 1) {
            int a, b, c; cin >> a >> b >> c;
            A[a].push_back({ b,c });
            A[b].push_back({ a,c });
        }
        int q; cin >> q;
        rep(i, 1, q) {
            int x, dep; cin >> x >> dep;
            qs[x].push_back({ dep,i });
        }

        DSU::init(n);
        pre[1] = 0;

        dfs(1, 0);
        rep(i, 1, q) {
            cout << ans[i] << endl;
        }

    }
    return 0;
}
/*


*/

PostScript

最近太摆了，感觉EC-Final肯定铁了，也不太有训练的心态了。慢慢康复训练吧。