首页 > 其他分享 >牛客周赛 Round 52

牛客周赛 Round 52

时间：2024-07-21 22:30:59浏览次数：13  
标签：std return int res 52 牛客 MInt Round define

写在前面

代码需要手动展开！！！
第一次赛时AK牛客周赛

A题

要想分解成两个不同的正整数，这个数至少也得是3
那么一个大于等于3的数可以分解成1和x-1

点击查看代码 
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lowbit(x) (x) & (-x)
using i64 = long long;
using pii = std::pair<int, int>;
void solve()
{
    int z;
    std::cin >> z;
    if (z <= 2) {
    	std::cout << "NO\n";
    }
    else {
    	std::cout << "YES\n";
    	std::cout << 1 << ' ' << z - 1 << '\n';
    }
}
int main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T = 1;
    //std::cin >> T;
    while (T --) solve();
    return 0;
}

B题

对于1x3的方块，只能横着放，那么可以将两个1x3的放在不同列
这样，每两个1x3的方块，贡献是3
对于1x2的方块，可以竖着放，也可以横着放
竖着放的话，一个方块的贡献是1
横着放的话，一次至少放两个方块，贡献是2
所以竖着和横着放，贡献是一样的
所以将1x3的尽可能放进去后，再用1x2的补齐。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lowbit(x) (x) & (-x)
using i64 = long long;
using pii = std::pair<int, int>;
void solve()
{
    int a, b, c;
    std::cin >> a >> b >> c; 
    int x = std::min(c / 3, b / 2);
    int y = c - x * 3;
    if (y <= a) {
        std::cout << "YES\n";
    }
    else {
        std::cout << "NO\n";
    }
}
signed main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    while (T --) solve();
    return 0;
}

C题

分析两种操作
第一种操作ai + aj <= 0
第二种操作ai ^ aj <= 0，这个我们可以发现，只要有一个数是负数，即可满足
对于一个数x, x ^ x = 0
那么贪心的来想
1.一个非负数，如果出现了偶数次，可以自己消除
2.一个负数，可以消除一个非负数
3.两个负数，可以通过操作1来消除
那么先统计经过第一步过后，非负数还剩几个
然后进行第二步，若剩下非负数，直接输出
否则，负数进行两两配对消除

点击查看代码 
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lowbit(x) (x) & (-x)
using i64 = long long;
using pii = std::pair<int, int>;
void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i ++) {
    	std::cin >> a[i];
    }
    int c0 = 0;
    int c1 = 0;
    int c2 = 0;
    std::map<int, int> mp;
    for (int i = 0; i < n; i ++) {
    	if (a[i] >= 0) {
    		c2 ++;
    		mp[a[i]] ++;
    		if (mp[a[i]] == 2) {
    			mp[a[i]] = 0;
    			c2 -= 2;
    		}
    	}
    	else {
    		c1 ++;
    	}
    }
    if (c1 >= c2) {
    	std::cout << (c1 - c2) % 2 << '\n';
    }
    else {
    	std::cout << c2 - c1 << '\n';
    }
}
int main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T = 1;
    //std::cin >> T;
    while (T --) solve();
    return 0;
}

D题

通过贪心的思想，每次选字典序最大的字符串的第一个字符，拼接进答案里面

点击查看代码 
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lowbit(x) (x) & (-x)
using i64 = long long;
using pii = std::pair<int, int>;
void solve()
{
    int n;
    std::cin >> n;
    std::priority_queue<std::string> q;
    std::vector<std::string> s(n + 1);
    for (int i = 1; i <= n; i ++) {
        std::cin >> s[i];
        q.push(s[i]);
    }
    std::string ans;
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        ans += t[0];
        if (t.size() > 1) {
            q.push(t.substr(1));
        }
    }
    std::cout << ans << '\n';
}
int main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T = 1;
    //std::cin >> T;
    while (T --) solve();
    return 0;
}

E题

先用并查集，处理出来每个连通块，并记录每个连通块的最大元素值
然后用类似于哈夫曼树的思想，每次将最大元素值最小的两个连通块合并起来

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lowbit(x) (x) & (-x)
using i64 = long long;
using pii = std::pair<int, int>;
struct DSU
{
    std::vector<int> fa, siz, mx;
    DSU(){}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        fa.resize(n);
        std::iota(fa.begin(), fa.end(), 0);
        siz.assign(n, 1);
        mx.resize(n);
    }
    int find(int x) {
         return fa[x] != x ? fa[x] = find(fa[x]) : fa[x];
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        fa[y] = x;
        mx[x] = std::max(mx[x], mx[y]);
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
    int max(int x) {
    	return mx[find(x)];
    }
};
void solve()
{
    int n, m;
    std::cin >> n >> m;
    DSU dsu(n + 1);
    for (int i = 1; i <= n; i ++) {
    	int x;
    	std::cin >> x;
    	dsu.mx[i] = x;
    }
    for (int i = 0; i < m; i ++) {
    	int u, v;
    	std::cin >> u >> v;
    	if (!dsu.same(u, v)) {
    		dsu.merge(u, v);
    	} 
    }
    // for (int i = 1; i <= n; i ++) {
    //     std::cout << dsu.max(i) << " \n"[i == n];
    // }
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    for (int i = 1; i <= n; i ++) {
    	if (dsu.fa[i] == i) {
    		q.push(dsu.max(i));
    	}
    }
    int cnt = 0;
    while (q.size() != 1) {
    	int a = q.top();
    	q.pop();
    	int b = q.top();
    	q.pop();
        cnt += std::max(a, b);
    	q.push(std::max(a, b));
    }
    std::cout << cnt << '\n';
}
signed main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T = 1;
    //std::cin >> T;
    while (T --) solve();
    return 0;
}

F题

对于'('和')'数量一样的括号序列，一定可以通过循环移位变成合法序列
那么就可以直接通过组合数计算，算出来有多少种合法情况
注意判断是否有合法解

点击查看代码 
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lowbit(x) (x) & (-x)
using i64 = long long;
using pii = std::pair<int, int>;
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 1000000007;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;
struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        m = std::min(m, Z::getMod() - 1);
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;
void solve()
{
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    int c1 = std::count(all(s), '(');
    int c2 = std::count(all(s), ')');
    int c3 = std::count(all(s), '?');
    if (n & 1) {
    	std::cout << 0 << '\n';
    }
    else {
    	if (n / 2 < c1) {
    		std::cout << 0 << '\n';
    	}
    	else if (n / 2 < c2) {
    		std::cout << 0 << '\n';
    	}
    	else {
    		std::cout << comb.binom(c3, n / 2 - c1) << '\n';
    	}
    }
}
int main()
{
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T = 1;
    //std::cin >> T;
    while (T --) solve();
    return 0;
}

标签：std,return,int,res,52,牛客,MInt,Round,define
From： https://www.cnblogs.com/KXDdesu/p/18315040

相关文章

  • 牛客周赛 Round 52 最塘的一场也是看的出平时水平的一场
     A.两数之和题意+思路:你需要找到不同的正整数x和y,使得x+y=z成立->如果<=2输出NO如果>2就输出1z-1即可Code:n=int(input())ifn<=2:print('NO')else:print('YES')print(1,n-1)B.小红装匣子题意: 小红有a块1×2大小的......
  • 牛客FreeRTOS刷题总结
    1.在FreeRTOS中延时函数也相对模式和绝对模式，在FreeRTOS中不同的模式用的函数不同，其中函数vTaskDelay()是相对模式(相对延时函数)，函数vTaskDelayUntil()是绝对模式(绝对延时函数)。两者都会阻塞任务。具体内容可以看博客这一篇：https://www.cnblogs.com/bathwind/p/18139217......
  • Codeforces Round 960 (Div. 2)
    xht真的好强好强，好厉害这场打得有点史，共四发罚时还是抽象了，如果没有xht就真的完了呜呜。不过也说明我是真的菜，还有把做法想出来之后验证不到位。A.SubmissionBait罚时了，15min才过/lh稍微想一下可以知道，对于最大数\(x\)，若其出现次数为奇数，那么A是必胜的，反之则只能从更小......
  • [Codeforces Round 960 (Div. 2)]A-E
    CodeforcesRound960(Div.2)A-EA题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个\(mx\)。每次轮到自己操作的时候就选一个数组里的数，满足\(a[i]>=mx\),然后令\(mx=a[i]\).双方轮流做直到一方无法操作，则另一方取胜。Sol:赛时1min猜了个错解，只看最大值，只看最大值的出......
  • Codeforces Round 958 (Div. 2)
    Preface周末补题计划的最后一场，这场由于是最古早的所以有些题题意都记不太清了赛时经典发病，前四题一题WA一发，然后把时间打没了E题经典没写完（中间还抽空写了个假做法），邮电部诗人了属于是A.SplittheMultiset刚开始还感觉无从下手，写了个记搜交上去还WA了，后面发现每次分......
  • Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
    Preface这场比赛的时候CF一直抽风，快10min的时候才登上去，然后中间交题也一直在人机验证50min左右过了前5题后，F没想到生成树当场趋势了，赛后发现原来是原题大战可海星A.DiverseGame将每个数循环移位变为下一个数即可，注意特判\(n=m=1\)的情形#include<cstdio>#incl......
  • A Bit More Common (2024牛客多校1 B)
    进入博客阅读体验更佳：ABitMoreCommon(2024牛客多校1B)|付诺の小站(funuo0728.github.io)ABitMoreCommon题目大意给定两个整数n和m(1\len,m\le5000)，在所有长度为n且元素取值范围为[0,2^m)的序列中，计算存在两个合法子序列的序列个数。其中，合法子序列是指......
  • Array Craft（Round 960）
    #include<bits/stdc++.h>#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("in.txt","rt",stdin);freopen......
  • Mad MAD Sum（Round 960）
    #include<bits/stdc++.h>#defineintll#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("in.txt","rt",stdin......
  • Codeforces Round 958 (Div. 2)
    A.SplittheMultisetForexample, {2,2,4} isamultiset.Youhaveamultiset ......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99