首页 > 其他分享 >牛客小白月赛100

牛客小白月赛100

时间:2024-09-09 20:03:39浏览次数:10  
标签:fy fx int vi i64 牛客 小白月赛 using 100

A - ACM中的A题

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;

const int N = 10;
char s[N];

i32 main() {
    int a, b, c;
    cin >> a >> b >> c;
    int A = a * 2, B = b * 2, C = c * 2;
    if (A + b > c and A + c > b and b + c > A) {
        cout << "Yes\n";
    } else if (a + B > c and a + c > B and B + c > a) {
        cout << "Yes\n";
    } else if (a + b > C and a + C > b and b + C > a) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

B - ACM中的C题

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;

const int N = 10;
char s[N];

i32 main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << -1;
    } else {
        cout << (n + 1) / 2;
    }

    return 0;
}

C - ACM中的M题

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    map<int, int> cnt;
    for (int i = 1, x; i <= n; i++)
        cin >> x, cnt[x]++;
    int res = 0;
    for (auto [_, b]: cnt) {
        if (b < 2) {
            cout << -1;
            return 0;
        }
        res += (b + 1) / 2;
    }
    cout << res;
    return 0;
}

D - ACM中的AC题

首先我们可以先用一遍 BFS 计算出每个点到最近的传送门的距离。

然后我们从起点开始进行 BFS,另世你和你关于起点对称。因此只维护你的位置就好,当你移动的时候,只要保证另世你的移动也合法即可。当你移动到传送门后,让另世你直接按照最短路移动到传送门即可,把两个距离求和就是答案。但是这里答案就是不满足单调了,所以找到所有的答案取最小值就好。

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const i64 INF = LLONG_MAX / 2;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, sx, sy;
    cin >> n >> m >> sx >> sy, sx--, sy--;
    vector<string> g(n);
    for (auto &i: g) cin >> i;

    vector dis1(n, vi(m, -1));
    queue<pii> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '@') q.emplace(i, j), dis1[i][j] = 0;

    while (not q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0, fx, fy; i < 4; i++) {
            fx = x + dx[i], fy = y + dy[i];
            if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
            if (g[fx][fy] == '#') continue;
            if (dis1[fx][fy] != -1) continue;
            dis1[fx][fy] = dis1[x][y] + 1, q.emplace(fx, fy);
        }
    }

    vector dis(n, vi(m, -1));
    dis[sx][sy] = 0, q.emplace(sx, sy);
    sx = sx * 2, sy = sy * 2;
    int res = INF;

    while (not q.empty()) {
        auto [ax, ay] = q.front();
        q.pop();
        int bx = sx - ax, by = sy - ay;
        if (g[ax][ay] == '@' and dis1[bx][by] != -1)
            res = min(res, dis[ax][ay] + dis1[bx][by]);

        for (int i = 0, fx, fy, gx, gy; i < 4; i++) {
            fx = ax + dx[i], fy = ay + dy[i], gx = sx - fx, gy = sy - fy;
            if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
            if (gx < 0 or gy < 0 or gx >= n or gy >= m) continue;
            if (g[fx][fy] == '#' or g[gx][gy] == '#') continue;
            if (dis[fx][fy] != -1) continue;
            dis[fx][fy] = dis[ax][ay] + 1;
            q.emplace(fx, fy);
        }
    }
    if (res >= INF) cout << -1;
    else cout << res;
    return 0;
}

E - ACM中的CM题

最优解肯定是先把\(m\)变大,然后再贪心覆盖区间就好了。

可以想到的情况是,随\(m\)变化,代价大概是符合三分的性质的。但是通过打表很容易就能找到不符合的情况。因此我们可以考虑通过三分大概先把区间变的小一点,然后再暴力的扫描剩下的区间。

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const i64 INF = LLONG_MAX / 2;

using node = array<int, 4>;
const node T = {-1, -1, -1, -1};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;

    ranges::sort(a);
    auto [ret, lst] = ranges::unique(a);
    a.erase(ret, lst);

    int l = 0, r = a.back() - a.front();

    auto calc = [=](int m) -> int {
        int ans1 = 0, ans2 = 0;
        for (int i = 0, lst = -INF; i < a.size(); i++)
            if (a[i] > lst)
                ans1++, lst = a[i] + m;
        for (int i = a.size() - 1, lst = INF; i >= 0; i--)
            if (a[i] < lst)
                ans2++, lst = a[i] - m;
        return min(ans1, ans2) + m;
    };
    int T = 1e8 / a.size();
    while (r - l > T) {
        int len = (r - l) / 3, lmid = l + len, rmid = r - len;
        if (calc(lmid) < calc(rmid)) r = rmid;
        else l = lmid;
    }
    int res = INF;
    for (int i = l; i <= r; i++)
        res = min(res, calc(i));
    cout << res;
    return 0;
}

但是上述的代码的calc是\(O(n)\)的。但实际上,因为有序,所以但我们知道左端点\(l\)时,是可以直接二分出右端点的。那么此时最多的二分次数也就是$\frac n m $。

这样的话,我们实际可以直接枚举\(m\),总复杂度就是\(O(\sum \frac{n}{m} \log n) = O(n\log ^ 2 n)\)。

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const i64 INF = LLONG_MAX / 2;

using node = array<int, 4>;
const node T = {-1, -1, -1, -1};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;

    ranges::sort(a);
    auto [ret, lst] = ranges::unique(a);
    a.erase(ret, lst);

    auto calc = [=](int m) -> int {
        int ans = m;
        for (int pos, lst = -INF; lst < a.back();) {
            ans++;
            pos = ranges::upper_bound(a, lst) - a.begin();
            lst = a[pos] + m;
        }
        return ans;
    };

    int res = INF;
    for (int i = 0; i <= a.back(); i++)
        res = min(res, calc(i));
    cout << res;
    return 0;
}

F - ACM中的ACM题

一个比较典的三元环问题,我们可以把无向图转换为有向图,规则是边一定从度数小的指向度数大的,如果度数相同从编号小的指向编号大的。这样的话有向图可以满足是一个有向无环图,且每个点的出度不超过\(\sqrt m\)。

我们可以把和\(x\)相邻的所有点染色,然后枚举\(x\)的子节点\(y\),然后看\(y\)的子节点中有没有被染色的点。如果有则说明会形成三元环。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;

#define int i64

const ldb eps = 1e-9;

using vi = vector<int>;
using pii = pair<int, int>;

const i64 mod = 998244353;

class dsu {
private:
    vector<int> fa;
public:
    dsu(int n = 1) {
        fa = vector<int>(n + 1, -1), fa[0] = 0;
    }

    int getfa(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = getfa(fa[x]);
    }

    void merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        if (x == y) return;
        if (fa[x] > fa[y]) swap(x, y);
        fa[x] += fa[y], fa[y] = x;
    }

    bool same(int x, int y) {
        x = getfa(x), y = getfa(y);
        return (x == y);
    }

    int size(int x) {
        x = getfa(x);
        return -fa[x];
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pii> edge(m);
    vi deg(n + 1);
    for (auto &[x, y]: edge)
        cin >> x >> y, deg[x]++, deg[y]++;
    vector<vector<pii>> e(n + 1);
    for (int cnt = 0; auto &[x, y]: edge) {
        if (deg[x] > deg[y]) swap(x, y);
        else if (deg[x] == deg[y] and x > y) swap(x, y);
        e[x].emplace_back(y, ++cnt);
    }
    dsu d(m);
    vi color(n + 1);
    for (int x = 1; x <= n; x++) {
        for (auto [y, i]: e[x]) color[y] = i;
        for (auto [y, i]: e[x])
            for (auto [z, j]: e[y])
                if (color[z])
                    d.merge(i, j), d.merge(color[z], i);
        for (auto [y, i]: e[x]) color[y] = 0;
    }
    if (d.size(1) == m) cout << "Yes\n";
    else cout << "No\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T-- > 0)
        solve();
    return 0;
}

标签:fy,fx,int,vi,i64,牛客,小白月赛,using,100
From: https://www.cnblogs.com/PHarr/p/18405194

相关文章

  • 题单3:基础练习(rating1000)
    题单1A:TheatreSquare数学问题118A:StringTask字符串处理。在体量较小的情况下,用多个cout语句打印可以节省代码时间。倘若体量较大,一般需要用char[]先存储需要打印的内容,最后再一次性打印。本题属于前者。58A:Chatroom字符串处理。可以事先存储需要匹配的序列char[6]......
  • comp10002 Foundations of Algorithms
    SchoolofComputing andInformationSystemscomp10002 Foundations of AlgorithmsSemester 2,2024Assignment 1LearningOutcomesIn this assignment you will demonstrate your understanding of arrays,  strings, functions, and the typedeffac......
  • python知识点100篇系列(13)-几种方法让你的电脑一直在工作
    写在前面:如果只想设置电脑永不息屏,可以在电脑的右下角,电源设置中的电源选项,设置成不熄灭屏幕即可;不需要依靠其他工具,但是这个也只能让电脑不息屏,其他也干不了;这里文章说的电脑一直在工作,是指使用python自动操作鼠标或键盘来使得电脑一直不息屏;第一种,可以使用pyautogui:......
  • AI Toolkit + H100 GPU,一小时内微调最新热门文生图模型 FLUX
    上个月,FLUX席卷了互联网,这并非没有原因。他们声称优于DALLE3、Ideogram和StableDiffusion3等模型,而这一点已被证明是有依据的。随着越来越多的流行图像生成工具(如StableDiffusionWebUIForge和ComyUI)开始支持这些模型,FLUX在StableDiffusion领域的扩展将会持......
  • KernelWarehouse:英特尔开源轻量级涨点神器,动态卷积核突破100+ | ICML 20242A
    动态卷积学习n个静态卷积核的线性混合,加权使用它们输入相关的注意力,表现出比普通卷积更优越的性能。然而,它将卷积参数的数量增加了n倍,因此并不是参数高效的。这导致不能探索n>100的设置(比典型设置n<10大一个数量级),推动动态卷积性能边界提升的同时享受参数的高效性。为此,论文提出......
  • KernelWarehouse:英特尔开源轻量级涨点神器,动态卷积核突破100+ | ICML 2024
    动态卷积学习n个静态卷积核的线性混合,加权使用它们输入相关的注意力,表现出比普通卷积更优越的性能。然而,它将卷积参数的数量增加了n倍,因此并不是参数高效的。这导致不能探索n>100的设置(比典型设置n<10大一个数量级),推动动态卷积性能边界提升的同时享受参数的高效性。为此,论文提出......
  • 《花100块做个摸鱼小网站! 》第六篇—将小网站部署到云服务器上
    ⭐️基础链接导航⭐️服务器→☁️阿里云活动地址看样例→......
  • 牛客周赛 Round 59(下)
    逆序数题目描述登录—专业IT笔试面试备考平台_牛客网运行代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intmain(){lln,k;cin>>n>>k;llsum=(n*(n-1))/2;cout<<sum-k<<endl;return0;}代码思路组合数的计算:在......
  • 使用微信小程序-云开发时报错: Error: errCode: -401003 api parameter type error |
    错误Uncaught(inpromise)thirdScriptErrorerrCode:-401003apiparametertypeerror|errMsg:parameter.datashouldbeobjectinsteadofundefined;Error:errCode:-401003apiparametertypeerror|errMsg:parameter.datashouldbeobjectinsteadofundef......
  • 视野修炼-技术周刊第100期 | CSS observer
    欢迎来到第100期的【视野修炼-技术周刊】,下面是本期的精选内容简介......