首页 > 其他分享 >牛客小白月赛106 题解 更新至 F 题

牛客小白月赛106 题解 更新至 F 题

时间：2024-12-18 19:53:48浏览次数：3  
标签：--------------------------------------------------------------------------------

Preface

期末周闲的没事写一场小白月赛

我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.

以下是代码火车头：

#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(const vector<T> &tem) {
    for (const auto &x: tem) cout << x << ' ';
    cout << endl;
}

template<typename T>
void cc(const T &a) { cout << a << endl; }

template<typename T1, typename T2>
void cc(const T1 &a, const T2 &b) { cout << a << ' ' << b << endl; }

template<typename T1, typename T2, typename T3>
void cc(const T1 &a, const T2 &b, const T3 &c) { cout << a << ' ' << b << ' ' << c << endl; }

void cc(const string &s) { cout << s << endl; }

void fileRead() {
#ifdef LOCALL
    freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
    freopen("D:\\AADVISE\\Clioncode\\untitled2\\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 double max(double a, double b) {
    if (a < b) return b;
    return a;
}

inline int min(int a, int b) {
    if (a < b) return a;
    return b;
}

inline double min(double a, double 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; }
void cmin(double &a, const double &b) { if (b < a) a = b; }
void cmax(double &a, const double &b) { if (b > a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;
using vec_int = std::vector<int>;
using vec_char = std::vector<char>;
using vec_double = std::vector<double>;
using vec_int2 = std::vector<std::vector<int> >;
using que_int = std::queue<int>;

Problem A. 最后DISCO

签到题还\(WA\)了一发。。。

明显要根据奇偶性直接判断出来就好了，一个小小的分类讨论。

但是需要注意\(b=1\)的情况。

//--------------------------------------------------------------------------------
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;
        if (b == 0) {
            if ((c+d)%2==1) cc("YES");
            else cc("NO");
            continue;
       
        }
        if (a % 2 == 0 or c % 2 == 0) {
            if (d % 2 == 0) cc("NO");
            else cc("YES");
        }
        else {
            if (d % 2 == 0) cc("YES");
            else cc("NO");
        }
 
    }
    return 0;
}
 
/*
 
 
*/

Problem B. 末日DISCO

题目有一点点的意思，其实会发现我们构造一个

\[1,2,3,4 \\ 2,5,6,7 \\ 3,6,8,9\\ 4,7,9,10\\ \]

这样一个对角线对称的矩阵就好了。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[510][510];
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        int cnt = 0;
        rep(i, 1, n) {
            A[i][i] = ++cnt;
            rep(j, i+1, n) A[i][j] = A[j][i] = ++cnt;
        }
        rep(i, 1, n) {
            rep(j, 1, n) {
                cout << A[i][j] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}
 
/*
 
 
*/

Problem C. 明日DISCO

我们先想一个简单的，如果操作\(1\)的时候：

那么显然我们应该从棋盘的最大值开始，逐渐减少，直到不能减少为止。

所以操作\(2\)对应的就是从最小值开始，逐渐增大，直到不能增大为止。

一个简单的模拟，但是有一点要注意的就是我们在减少的时候可以直接将当前的权值\(val\)变成上下左右四个点中的最值

时间复杂度不会太大，因为可以感性的想到，如果有相邻的情况（正负性一致），那么就一定会不行。

代码写复杂了，刚刚写题解的时候才想到相邻的不行，\(v\)的时候直接暴力模拟去了。。。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[510][510];
//--------------------------------------------------------------------------------
//struct or namespace:
struct node {
    int x;
    int y;
    int val;
};
 
//--------------------------------------------------------------------------------
 
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        // vector<node> tem;
        rep(i, 1, n)
            rep(j, 1, n) {
                int a;
                cin >> a;
                A[i][j] = a;
                // tem.push_back({i, j, a});
            }
        auto cmp1 = [&](const node &q1, const node &q2) {
            return q1.val > q2.val;
        };
        auto cmp2 = [&](const node &q1, const node &q2) {
            return q1.val < q2.val;
        };
        priority_queue<node, vector<node>, decltype(cmp2)> F(cmp2);
        // for (auto &x: tem) F.push(x);
        rep(i, 1, n)
            rep(j, 1, n) F.push({i, j, A[i][j]});
        while (!F.empty()) {
            auto [x,y,val] = F.top();
            F.pop();
 
            if (A[x - 1][y] < val and A[x][y - 1] < val and A[x + 1][y] < val and A[x][y + 1] < val) {
                A[x][y] = max({A[x - 1][y], A[x][y - 1], A[x + 1][y], A[x][y + 1]});
                F.push({x, y, A[x][y]});
            }
            else {
                break;
            }
        }
 
        priority_queue<node, vector<node>, decltype(cmp1)> G(cmp1);
        rep(i, 1, n)
            rep(j, 1, n) G.push({i, j, A[i][j]});
 
        while (!G.empty()) {
            auto [x,y,val] = G.top();
            G.pop();
            // cc(x, y, val);
            if (A[x - 1][y] > val and A[x][y - 1] > val and A[x + 1][y] > val and A[x][y + 1] > val) {
                A[x][y] = min({A[x - 1][y], A[x][y - 1], A[x + 1][y], A[x][y + 1]});
                G.push({x, y, A[x][y]});
            }
            else {
                break;
            }
        }
        bool fl = 1;
        rep(i, 1, n) {
            rep(j, 1, n) {
                if (A[i][j] != 0) fl = 0;
                // cout << A[i][j] << " ";
            }
            // cout << endl;
        }
        if (fl) cc("YES");
        else cc("NO");
    }
    return 0;
}
 
/*
 
 
*/

Problem D. 太阳系DISCO

一眼暴力，但是有一个技能操作。感性的想到，这个技能的操作由于是直接跳到对面，所以应该最多只会执行\(1\)次，那么就直接先不考虑这个暴力走一遍之后判断到达对面点的情况取个\(min\)就好了。代码写起来比\(C\)简单不少\(（bushi\)

//--------------------------------------------------------------------------------
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int dp[N];
bool vis[N];
int st, ed, shun, ni, k;
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n >> k >> st >> ed >> shun >> ni;
        st -= 1, ed -= 1;
        rep(i, 0, n-1) dp[i] = INF;
        queue<PII> F;
        F.push({st, 0});
        while (!F.empty()) {
            auto [x,val] = F.front();
            F.pop();
            if (vis[x]) continue;
            vis[x] = 1;
            dp[x] = val;
            F.push({(x + shun) % n, val + 1});
            F.push({(x - ni + n) % n, val + 1});
        }
 
        int ans = dp[ed];
        if (k > 0) cmin(ans, dp[(ed + n / 2) % n] + 1);
        if (ans >= INF / 2)ans = -1;
        cc(ans);
 
 
    }
    return 0;
}
 
/*
 
 
*/

Problem E. 普通DISCO-1

可以想到我们每次的操作都是在一个\(lca\)的子树里面选择的，然后我们每次选择的时候如果是希望向下深度最大的话，那么肯定是向下深度第二的加到向下深度第一的上面，那么我们只需要枚举\(lca\)，然后将最大值和次大值加起来取\(max\)就好了。、

记得特殊处理一下如果当前的点\(i\)如果只有一个子树的情况。因为这个\(wa\)了两发。。。

//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
// int ans = INF;
//--------------------------------------------------------------------------------
//struct or namespace:
namespace z {
    vector<PII> A[N];
    int son[N], dep[N], dis[N], dis2[N];
 
    void dfs(const int x, const int pa) {
        son[x] = 1;
        dep[x] = dep[pa] + 1;
        for (auto &[y, val]: A[x]) {
            if (y == pa) continue;
            dfs(y, x);
            son[x] += son[y];
            if (dis[y] + 1 > dis[x]) dis2[x] = dis[x], dis[x] = dis[y] + 1;
            else if (dis[y] + 1 > dis2[x]) dis2[x] = dis[y] + 1;
        }
 
    }
 
    void clear(int n) {
        rep(i, 1, n) {
            A[i].clear();
        }
    }
 
    void add(int x, int y, int c = 1) { A[x].push_back({y, c}); }
}
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        z::clear(n);
        rep(i, 1, n-1) {
            int a, b;
            cin >> a >> b;
            z::add(a, b);
            z::add(b, a);
        }
        z::dfs(1, 0);
        int ans = 0;
        using namespace z;
        rep(i, 1, n) {
            cmax(ans, dep[i] + dis[i]);
            if (dis2[i] == 0) {
                continue;
            }
            cmax(ans, dis[i] + dis2[i] + dep[i] - 1);
 
            // cc(i, dis[i], dis2[i]);
        }
        cc(ans);
    }
    return 0;
}
 
/*
 
 
*/

Problem F. 普通DISCO-2

首先一眼二分，求所有点深度的最大值的最小值。

然后考虑怎么处理，首先可以想到要将深度\(mid\)以下的求一个\(lca\)，挪动的时候直接挪动\(lca\)这个点。

然后直接暴力枚举每个点和他交换之后满不满足就好了。

判断满不满足的时候我们就和\(E\)一样求一个向下深度的最大值就好了。

打了两场，感觉小白的\(F\)题貌似是铜--的难度？

//--------------------------------------------------------------------------------
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
namespace z {
    vector<PII> A[N];
    int son[N], dep[N], fa[N], dis[N];
    //重儿子，顶根，时间戳，子树最右端时间戳，时间戳会对应节点x
    int hea[N], up[N], dnf[N], dnff[N], seq[N];
 
    int len[N];
    int tot;
 
    void dfs(int x, int pa) {
        son[x] = 1, dep[x] = dep[pa] + 1, fa[x] = pa;
        int t = 0;
        for (auto [y, val]: A[x]) {
            if (y == pa) continue;
            dis[y] = dis[x] + val;
            dfs(y, x);
            cmax(len[x], len[y] + 1);
            son[x] += son[y];
            if (!t or son[t] < son[y]) t = y;
        }
        hea[x] = t;
    }
 
    void dfs2(int x, int pa, int ding) {
        dnf[x] = ++tot, up[x] = ding, seq[dnf[x]] = x;
        if (hea[x]) dfs2(hea[x], x, ding);
        for (auto [y, val]: A[x]) {
            if (y == pa || y == hea[x]) continue;
            dfs2(y, x, y);
        }
        dnff[x] = tot;
    }
 
    void clear(int n) {
        tot = 0;
        rep(i, 1, n) {
            A[i].clear();
            dis[i] = hea[i] = up[i] = dnf[i] = seq[i] = 0;
        }
    }
 
    void add(int x, int y, int c = 1) {
        A[x].push_back({y, c});
        A[y].push_back({x, c});
    }
 
    int lca(int x, int y) {
        while (up[x] != up[y]) {
            if (dep[up[x]] < dep[up[y]]) swap(x, y);
            x = fa[up[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        return x;
    }
 
    //返回x向上k次的点
    int upup(int x, int k) {
        if (dep[x] <= k) return -1;
        int to = dep[x] - k;
        while (dep[up[x]] > to) x = fa[up[x]];
        return seq[dnf[x] - (dep[x] - to)];
    }
 
    int dist(int x, int y) { return dis[x] + dis[y] - dis[lca(x, y)] * 2; }
 
    void work(int rt = 1) { dfs(rt, 0), dfs2(rt, 0, rt); }
 
    //x的子树里有y就返回1
    bool isFa(int x, int y) { return (dnf[x] <= dnf[y] and dnff[x] > dnf[y]); }
};
 
//--------------------------------------------------------------------------------
 
bool check(int mid) {
    using namespace z;
    int t = 0;
    rep(i, 1, n) {
        if (dep[i] < mid) continue;
        if (len[i] == 0) continue;
        if (t == 0) t = i;
        if (isFa(t, i)) continue;
        t = lca(t, i);
    }
    if (t == 0) return 1;
    if (len[1] + 1 <= mid) return 1;
    rep(i, 1, n) {
        if (isFa(t, i) or isFa(i, t)) continue;
        if (dep[i] >= mid) continue;
        if (dep[t] + len[i] <= mid and dep[i] + len[t] <= mid) return 1;
    }
 
    return 0;
}
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        z::clear(n);
        rep(i, 1, n-1) {
            int a, b;
            cin >> a >> b;
            z::add(a, b);
        }
        z::work();
        int l = 0, r = n + 1;
        while (l + 1 != r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid;
        }
        cc(r);
 
 
    }
    return 0;
}
 
/*
 
 
*/

PostScript

标签：--------------------------------------------------------------------------------
From： https://www.cnblogs.com/advisedy/p/18615750

相关文章

  • tauri2文件资源访问和存储常见问题解决
    上tauri2的github上搜一下，发现问题还是挺多的，如果你是从tauri1迁移过来的话，估计要走的坑更多，因为tauri2的配置很多已经和tauri1不一样了，如果你还是习惯用tauri1的配置思维来搞tauri2的话，肯定会让你很难受。附上tauri2常用的几个链接：官方javascript的api文档：window|Tauri ......
  • [HDU5603] the soldier of love 题解
    考虑到正向求解困难，于是正难则反。那么实际上对于\(a_i\)和\(a_{i+1}\)来说，它们给答案的贡献就是满足\(l_j>a_i,r_j<a_{i+1}\)的区间数量。那么就是经典转化了。直接转换为二维数点问题即可。时间复杂度\(O(tn\logV)\)，离散化可以将\(\logV\)转化为\(\logn\)。#inc......
  • CF1889D Game of Stacks 题解
    很有趣的题目.思路我们考虑如果每一个栈里只有一个数怎么办。这个时候，我们会形成一个基环树森林。我们的操作相当于每走一步就删掉来时的路。那么每个点最终会停在离它最近的环上的点。我们可以发现一个性质，一个环是不会影响结果的，因为它总能走回来。所以我们可以不断的删......
  • P7531 [USACO21OPEN] Routing Schemes P 题解
    best定理居然还有运用范围。思路考虑如何来判断是否有解。由于每一条边都需要用到。但是它是使用很多条路径进行覆盖。我们考虑一个很巧妙的转化。建立一个超级源点，源点向每一条路径的开头连一条边。每一条路径的结尾向源点连一条边，这样一条路径就变成了一个回路。把所有......
  • AT_abc129_f [ABC129F] Takahashi's Basics in Education and Learning 题解
    题目传送门前置知识矩阵加速递推解法设\(f_{i}\)表示将\(s_{1}\sims_{i}\)拼起来后的值，状态转移方程形如\(f_{i}=10^{k}f_{i-1}+s_{i}\)，其中\(k=\left\lfloor\log_{10}s_{i}\right\rfloor+1\)。又因为保证等差数列中的元素\(\le10^{18}\)，对于每个\(k\in[1,......
  • Pinely Round 2 (Div. 1 + Div. 2) / Codeforces contest 1863 题解
    ProblemA.Channelhttps://codeforces.com/contest/1863/problem/A流程看起来很复杂，让我们重述一下题意。两数\(x\),\(y\)。\(opt1\)，你可以选\(x\)和\(y\)当中某个非零的，减少\(1\)。\(opt2\)，让\(x\)增加\(1\)。\(Q1:\)是否可以让\(y\)变成\(0\),$Q2:$......
  • AT_agc032_d [AGC032D] Rotation Sort 题解
    考虑确定哪些点不动，这些点一定构成一个单调递增子序列，那么对于剩下的点：若在它之前存在一个不动点大于它，则需要花费\(b\)的代价向前移动。若在它之后存在一个不动点小于它，则需要花费\(a\)的代价向后移动。如果两个都不存在，则它一定可以加入不动点序列。考虑dp，记\(f_{i,......
  • 鸿蒙Flutter环境相关问题解决方法
    鸿蒙Flutter环境相关问题建议使用的开发工具版本flutter3.7.12-ohos版本python3.8-python3.11java17node18ohpm1.6+HamonyOSSDKapi11Xcode14.3断网环境flutterpubget执行失败解决方案：加上--offline参数，完整命令flutterpubget--offlinemac环境releas......
  • Hongcow Builds A Nation 题解
    HongcowBuildsANation题解洛谷。Codeforces。题目描述给定一张\(n\)个点，\(m\)条边的无向图，有\(k\)个点是特殊点。每个连通块中都得保证无重边、无自环，且最多只有一个特殊点。求最多还能加多少条边，满足以上条件。思路简述首先考虑以下有\(n\)个点的完全图共有多......
  • P6803 [CEOI2020] 星际迷航 题解
    \(\text{P6803[CEOI2020]星际迷航题解}\)观察这个从第\(0\)棵树走向第\(D\)棵树的过程是困难的，我们难以判定走到下一棵树的情况。于是我们不妨从第\(D\)棵树向第\(0\)棵树来倒推。从第\(i\)层走向第\(i+1\)层的边为\(x\toy\)时，事实上此时\(y\)就是第\(i+1\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99