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

牛客周赛 Round 57

时间：2024-08-28 20:52:50浏览次数：2  
标签：Node cur int 57 back cin 牛客 using Round

A - 小红喜欢1

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

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

const int inf = INT_MAX / 2;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    for(int i = 1 , x ; i <= 5 ; i ++) {
        cin >> x;
        if(x == 1) cout << i;
    }
    return 0;
}

B - 小红的树切割

要切割的边，端点一定同色。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

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

const int inf = INT_MAX / 2;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y, x--, y--;
        if(s[x] == s[y]) cnt ++;
    }
    cout << cnt;
    return 0;
}

C - 小红的双好数（easy）

二进制下，一定只有 \(0\) 和 \(1\)。\(n\)进制下，一定是\(10\)

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

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

const int inf = INT_MAX / 2;

bool check(int x, int y) {
    while (x) {
        if (x % y > 1) return false;
        x /= y;
    }
    return true;
}


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    i64 n;
    cin >> n;
    if (n == 1) cout << "YES\n2 3\n";
    else if (n == 2) cout << "NO\n";
    else cout << "YES\n2 " << n << "\n";
    return 0;
}

D - 小红的线段

点可以分成三种，\(y > kx + b , y = kx + b , y < kx + b\)。然后需要有交点的，最优解是选择一个大于的和一个小于的，其次是选择一个大于（小于）和等于，最后是两个等于，剩余的情况怎么连接都没有交点，所以随便连就好了。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

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

const int inf = INT_MAX / 2;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k, b;
    cin >> n >> k >> b;
    vi A, B, C;
    for (int i = 1, N = n * 2, x, y, yy; i <= N; i++) {
        cin >> x >> y;
        yy = k * x + b;
        if (y == yy) C.push_back(i);
        else if (y > yy) A.push_back(i);
        else B.push_back(i);
    }
    vector<pii> res;
    while (not A.empty() and not B.empty()) {
        res.emplace_back(A.back(), B.back());
        A.pop_back(), B.pop_back();
    }
    while (not A.empty() and not C.empty()) {
        res.emplace_back(A.back(), C.back());
        A.pop_back(), C.pop_back();
    }
    while (not C.empty() and not B.empty()) {
        res.emplace_back(C.back(), B.back());
        C.pop_back(), B.pop_back();
    }
    assert(C.size() % 2 == 0);
    for (int i = 1; i < C.size(); i += 2)
        res.emplace_back(C[i - 1], C[i]);

    cout << res.size() << "\n";
    for (auto &[x, y]: res) cout << x << " " << y << " Y\n";
    for (int i = 1; i < A.size(); i += 2)
        cout << A[i - 1] << " " << A[i] << " N\n";
    for (int i = 1; i < B.size(); i += 2)
        cout << B[i - 1] << " " << B[i] << " N\n";
    return 0;
}

E - 小红的双好数（hard）

枚举\(k2\)进制下只有\(0,1\)的数，然后验证\(k1\)进制下即可。复杂度\(O(2^{18\times\log_{k2} 10})\)

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

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

const int inf = INT_MAX / 2;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int k1, k2;
    cin >> k1 >> k2;
    int N = 1e18;
    vi p(1, 1);
    while (p.back() * k2 <= N)
        p.push_back(p.back() * k2);

    auto check = [k1](int x) {
        if (x < 2) return false;
        while (x) {
            if (x % k1 > 1) return false;
            x /= k1;
        }
        return true;
    };

    auto dfs = [p, check, N](auto &&self, int x, int i) -> void {
        if (x > N) return;
        if (check(x)) {
            cout << "YES\n" << x << "\n";
            exit(0);
        }
        if (i == p.size()) return;
        self(self, x, i + 1);
        self(self, x + p[i], i + 1);
        return;
    };
    dfs(dfs, 0, 0);
    cout << "NO\n";
    return 0;
}

F - 小红的数组操作

每个数组的最小值可以用std::multiset<int>维护。

前缀最小值可以用线段树维护。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

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

const int inf = INT_MAX / 2;


struct Node {
    int l, r, value;
    Node *left, *right;

    Node(int l, int r, int value, Node *left, Node *right) :
            l(l), r(r), value(value), left(left), right(right) {};
};

// 建树
Node *build(int l, int r, const vi &arr) {
    if (l == r) return new Node(l, r, arr[l], nullptr, nullptr);
    int mid = (l + r) >> 1;
    Node *left = build(l, mid, arr), *right = build(mid + 1, r, arr);
    return new Node(l, r, min(left->value, right->value), left, right);
}

// 修改
void modify(int l, int r, int v, Node *cur) {
    if (l > cur->r || r < cur->l) return;
    if (l <= cur->l && r >= cur->r) {
        cur->value = v;
        return;
    }
    int mid = (cur->l + cur->r) >> 1;
    if (l <= mid) modify(l, r, v, cur->left);
    if (r > mid) modify(l, r, v, cur->right);
    cur->value = min(cur->left->value, cur->right->value);
    return;
}
// 查询
int query(int l, int r, Node *cur) {
    if (l <= cur->l && r >= cur->r) return cur->value;
    int mid = (cur->l + cur->r) >> 1, res = inf;
    if (l <= mid) res = min(res, query(l, r, cur->left));
    if (r > mid) res = min(res, query(l, r, cur->right));
    return res;

}

void modify(int x, int v, Node *cur) {
    modify(x, x, v, cur);
}

int query(int x, Node *cur) {
    return query(1, x, cur);
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vi> a(n + 1);
    vector<multiset<int>> calc(n + 1);
    vi arr(n + 1);
    for (int i = 1, m; i <= n; i++) {
        cin >> m;
        a[i] = vi(m + 1);
        for (int j = 1; j <= m; j++)
            cin >> a[i][j], calc[i].insert(a[i][j]);
        arr[i] = *calc[i].begin();
    }
    Node *root = build(1, n, arr);
    int q;
    cin >> q;
    for (int opt, i, j, x; q; q--) {
        cin >> opt;
        if (opt == 1) {
            cin >> i >> j >> x;
            calc[i].erase(calc[i].find(a[i][j]));
            a[i][j] = x, calc[i].insert(x);
            if (*calc[i].begin() != arr[i])
                arr[i] = *calc[i].begin(), modify(i, arr[i], root);
        } else {
            cin >> i;
            cout << query(i, root) << "\n";
        }
    }
    return 0;
}

G - 小红的双排列构造

在大多数情况下是存在无解的情况，大致的构造思路是

\[1,2,3\dots,n,1,2,3,\dots, k - 2 , n , n - 1 , n - 2 , \dots,k - 1 \]

下面说一下几种特例。

  • \(n=1\)时，只有\(1,1\)一种情况
    • \(k = 2\)时，\(1,1\)是唯一解
    • 其他情况均无解
  • \(n=2\)时
    • \(k=1\)时，\(1,1,2,2\)
    • \(k=2\)时，\(1,2,2,1\)
    • \(k=3\)时，\(1,2,1,2\)
    • 其他情况无解
  • 其他情况下，不会出现无解的情况，但依旧有特例
    • \(k=0\)时，\(1,1,2,2,3,3\dots,n,n\)
    • \(k = 1\)时，\(1,1,2,3,\dots,n,2,3,4,\dots,n\)
    • \(k=2\)时，\(1,2,3,\dots,n,n,n-1,n-2,n-3,\dots,1\)
#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

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

const int inf = INT_MAX / 2;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    if (n == 1) {
        if (k == 2) cout << "1 1";
        else cout << "-1";
    } else if (n == 2) {
        if (k == 1)cout << "1 1 2 2";
        else if (k == 3) cout << "1 2 1 2";
        else if (k == 2) cout << "1 2 2 1";
        else cout << "-1";
    } else if (k == 0) {
        for (int i = 1; i <= n; i++)
            cout << i << " " << i << " ";
    } else if (k == 1) {
        cout << 1 << " ";
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        for (int i = 2; i <= n; i++)
            cout << i << " ";
    } else if (k == 2) {
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        for (int i = n; i >= 1; i--)
            cout << i << " ";
    } else {
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        for (int i = 1; i <= k - 2; i++)
            cout << i << " ";
        for (int i = n; i > k - 2; i--)
            cout << i << " ";
    }
    return 0;
}

标签：Node,cur,int,57,back,cin,牛客,using,Round
From： https://www.cnblogs.com/PHarr/p/18385523

相关文章

  • day57-graph theory-part07-8.28
    tasksfortoday:1.prim算法53.寻宝2.kruskal算法53.寻宝----------------------------------------------------------------------------1. prim算法53.寻宝Inthispractice,weseehowprimalgorithmisused.Theessenceofthispractice is:therearen......
  • Educational Codeforces Round 169 (Rated for Div. 2)
    A.ClosestPoint两个数时只要不相邻就有解，超过两个数无解点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#definepiipair<int,int>intread(){intx=0,f=0;charc=getchar();whi......
  • Codeforces Round 968 (Div. 2)
    题目链接：CodeforcesRound968(Div.2)-Codeforces总结：C题想到了，但是写成shi了，出得有点慢。A.TurtleandGoodStringtag：签到Solution：直接判断第一个字符是否与最后一个字符相等即可。voidsolve(){cin>>n;strings;cin>>s;if(s[0]==s[n-1]......
  • Codeforces Round 968 (Div. 2)
    题目链接：CodeforcesRound968(Div.2)-Codeforces总结：C题想到了，但是写成shi了，出得有点慢。A.TurtleandGoodStringtag：签到Solution：直接判断第一个字符是否与最后一个字符相等即可。voidsolve(){cin>>n;strings;cin>>s;if(s[0]==s[......
  • Pinely Round 4 (Div. 1 + Div. 2) VP记录
    PinelyRound4(Div.1+Div.2)VP记录场上打了ABCDF，被E二粉兔创飞了。这场的构造题有：BDEGI，乐死了。A把数列黑白染色，第一个格为黑色，那么每次删除会删除一个黑格子和一个白格子。而黑格子始终比白格子多一个，因此最后选到的是黑格子。答案极为黑格子的最大值，也易证一......
  • Codeforces Round 967 (Div. 2)
    题目链接：CodeforcesRound967(Div.2)-Codeforces总结：B题没测试就交wa一发，C题一直没想到怎么回溯，哎。A.MakeAllEqualtag：签到Solution：找到相同元素的最大值，将其它所有元素删去。voidsolve(){cin>>n;vector<int>a(n);map<int,int>mp;intans......
  • MP157-阻塞IO与非阻塞IO
    linux阻塞IO与非阻塞IO一，简介当应用程序对设备驱动进行操作的时候，如果不能获取到设备资源，那么阻塞式IO就会将应用程序对应的线程挂起，直到设备资源可以获取为止。对于非阻塞IO，应用程序对应的线程不会挂起，它要么一直轮询等待，直到设备资源可以使用，要么就直接放弃。......
  • 牛客周赛 Round 57
     B可以直接统计每条边两个点的情况即可，不用DFS。  F写法和这个差不多。可以用map、set、统计这些方法，计算动态的一个数组的最大数。可以直接用map统计就行，map已经自动给你排好序了（从小到大）。1#include<bits/stdc++.h>2usingnamespacestd;3#defineLLl......
  • Codeforces Round 962 (Div. 3)
    A.Legs若只判断题，根据模4意义下分类即可。B.Scale模拟题，缩小同值矩阵即可。C.Sort对每个字母求前缀数量和，答案就是两端点的差。constintN=2e5+5;intT,n,q;chara[N],b[N];intc[N][26],d[N][26];signedmain(void){ for(read(T);T;T--){ read(......
  • P5776
    耳：若\(G\)种一条简单路径或简单环\(x_1\cdotsx_p\)有\(x_1\inG',x_{p}\inG',x_2\not\inG',x_3\not\inG'\cdotsx_{p-1}\not\inG'\)，则称该路径为关于\(G'\)的耳。简单路径称为开耳。强连通图和存在耳分解充要。边双连通图和存在耳分解充要。构造：无向图，\(G_0\)直......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99