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

牛客小白月赛88

时间：2024-04-28 16:14:50浏览次数：20  
标签：i32 int auto cin dic 牛客 88 小白月赛 using

A-超级闪光牛可乐

#include <bits/stdc++.h>

using namespace std;

using f64 = double_t;
using i32 = int32_t;
using i64 = int64_t;
using u64 = uint64_t;

#define int long long


i32 main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int x, n;
    cin >> x >> n;
    char c, t;
    int y = -1;
    for (int i = 1, v; i <= n; i++) {
        cin >> c >> v;
        if (v > y) y = v, t = c;

    }
    cerr << y << "\n";
    y = ( x + y - 1  ) / y ;
    cerr << y << "\n";
    if( y > 1000 ){
        cout << "-1\n";
    }else{
        while( y -- ) cout << t;
        cout << "\n";
    }
    return 0;
}

B-人列计算机

#include <bits/stdc++.h>

using namespace std;

using f64 = double_t;
using i32 = int32_t;
using i64 = int64_t;
using u64 = uint64_t;

#define int long long


i32 main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    vector<string> s(5);
    for (auto &it: s)
        getline(cin, it);

    int f = 0;
    for (auto i: s[2]) {
        if (i == '&') f = 1;
        else if (i == 'O') f = 2;
    }
    if (f == 1) {
        int x = s[1].front() == '1';
        int y = s[3].front() == '1';
        cout << (x & y) << "\n";
    } else if (f == 2) {
        int x = s[2].front() == '1';
        cout << (!x) << "\n";
    } else {
        int x = s[1].front() == '1';
        int y = s[3].front() == '1';
        cout << (x | y) << "\n";
    }
    return 0;
}

C-时间管理大师

#include <bits/stdc++.h>

using namespace std;

using f64 = double_t;
using i32 = int32_t;
using i64 = int64_t;
using u64 = uint64_t;

#define int long long


i32 main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    set<int> cnt;
    for (int i = 1, h, m; i <= n; i++) {
        cin >> h >> m;
        m += h * 60;
        cnt.insert(m - 1);
        cnt.insert(m - 3);
        cnt.insert(m - 5);
    }
    cout << cnt.size() << "\n";
    for( auto i : cnt ){
        cout << i / 60 << " " << i % 60 << "\n";
    }
    return 0;
}

D-我不是大富翁

二维 dp,下标为了方便可以直接转换成\([0,n-1]\)

#include <bits/stdc++.h>

using namespace std;

using f64 = double_t;
using i32 = int32_t;
using i64 = int64_t;
using u64 = uint64_t;

#define int long long


i32 main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<i32> f(n);
    f[0] = true;
    for (int i = 1, x; i <= m; i++) {
        cin >> x, x %= n;
        vector<i32> g(n);
        for (int j = 0; j < n; j++) {
            if (f[j] == false) continue;
            g[(j + x) % n] |= f[j];
            g[(j - x + n) % n] |= f[j];
        }
        f.swap(g);
    }
    if (f[0]) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

E-多重映射

反序递推

设\(to_{i,j}\)标准最后\(i\)个操作下\(j\)会被变成\(to_{i,j}\)，显然\(to_{0,j}=j\)

然后我们设倒数第\(i\)次操作是\(x_i\)变为\(y_i\)，则

\[to_{i,j}=\left\{\begin{matrix} to_{i-1,j} & j \neq x_i\\ to_{i-1,y_i}& j = x_i \end{matrix}\right. \]

所以根据这个规律倒过来递推即可，可以优化一维空间。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;

#define int long long

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<i32> a(n);
    for (auto &i: a) cin >> i;
    vector<pair<i32, i32>> op(m);
    for (auto &[x, y]: op) cin >> x >> y;
    reverse(op.begin(), op.end());
    map<i32, i32> to;
    for (auto &[x, y]: op) {
        if (to.count(y)) to[x] = to[y];
        else to[x] = y;
    }
    for (auto i: a) {
        if (to.count(i)) cout << to[i] << " ";
        else cout << i << " ";
    }
    cout << "\n";
    return;
}

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

启发式合并

\(dic[x]\)表示当前被变成\(x\)的集合，则一次操作\(M(x)=y\)等价于把\(dic[x]\)中的数字全部移动到\(dic[y]\)中。

然后，启发式合并就保证每次把较小集合插入到较大的集合中，因为在高版本的c++中\(std::swap\)是\(O(1)\)的。

当然可以通过指针数组来实现。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;

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

const i32 N = 1e6;
vector<vi> dic(N + 1);

void solve() {
    int n, m;
    cin >> n >> m;
    set<int> vis;
    for (int i = 0, x; i < n; i++)
        cin >> x, dic[x].push_back(i), vis.insert(x);
    for (int x, y; m; m--) {
        cin >> x >> y;
        if (x == y) continue;
        if (dic[x].size() > dic[y].size()) swap(dic[x], dic[y]);
        dic[y].insert(dic[y].end(), dic[x].begin(), dic[x].end());
        dic[x].clear();
        vis.insert(y), vis.erase(x);
    }
    vi res(n);
    for (const auto &i: vis) {
        for (const auto &pos: dic[i])
            res[pos] = i;
        dic[i].clear();
    }
    for (const auto &i: res) cout << i << " ";
    cout << "\n";
    return;
}

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

记忆化搜索

我们可以把操作\(M(x_i)=y_i\)，看成一条有向边\((x_i,y_i,i)\)，则转化操作就变成了在图上每次走边权最小的边且所走的边权必须是一个递增的序列。

然后变换的过程就是沿着一条链走，且链上所经过的所有点最终都变成了链上的最后一个点。

所以计划\(ans[i]\)就表示了经过\(i\)边后最终会变成什么，这样可以保证每条边只走一次，复杂度就是\(O(N+M)\)

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;

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

const i32 N = 1e6;

vector<vector<pii>> e(N + 1);
vi ans(N + 1);

int dfs(int x, int time) {
    if (e[x].empty() or e[x].back().second <= time) return x;
    int it = -1;
    for (int l = 0, r = e[x].size() - 1, mid; l <= r;) {
        mid = (l + r) / 2;
        if (e[x][mid].second > time) it = mid, r = mid - 1;
        else l = mid + 1;
    }
    assert(it != -1);
    auto &[y, newTime] = e[x][it];
    if (ans[newTime] != -1) return ans[newTime];
    return ans[newTime] = dfs(y, newTime);
}


void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n);
    for (auto &i: a) cin >> i, e[i].clear();
    vector<pii> op(m);
    for (auto &[x, y]: op)
        cin >> x >> y, e[x].clear(), e[y].clear();
    for (int i = 0; i < m; i++) {
        auto &[x, y] = op[i];
        e[x].emplace_back(y, i + 1);
        ans[i + 1] = -1;
    }
    for (auto i: a)
        cout << dfs(i, 0) << " ";
    cout << "\n";
    return;
}

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

标签：i32,int,auto,cin,dic,牛客,88,小白月赛,using
From： https://www.cnblogs.com/PHarr/p/18157796

相关文章

  • ABC 288 D - Range Add Query
    题目链接：设\(a[i]\)表示下标对\(k\)取模为\(i\)的所有数的和。那每次操作就是将数组\(a\)的所有数都加\(c\)。最终为\(0\)的充分必要条件就是\(a\)的所有数都是一样的。因此，对于每组询问，统计\([l,r]\)中数字下标对\(k\)取模的所有数的和，看看是否为同一个数即可......
  • Debian/Linux安装 Realtek 8811cu无线网卡驱动
    1、下载必备安装包make、gcc（debian中可用build-essential包）、bc、linux-headers-$(uname-r)、dkmssudoaptinstallbuild-essentialbcsudoaptinstalllinux-headers-$(uname-r)dkms2、在github中下载8811cu的驱动(8811cu和8821cu用的同一个驱动)，注意下驱动程序是否能......
  • 基于北京迅为iTOP-RK3588大语言模型部署测试
     人工智能（AI）领域中的大模型（LargeModel）逐渐成为研究的热点。大模型，顾名思义，是指拥有海量参数和高度复杂结构的深度学习模型。它的出现，不仅推动了AI技术的突破，更为各行各业带来了革命性的变化。RK3588是瑞芯微推出的新一代旗舰级高端处理器，采用8nm工艺设计，搭载四核A76+四核A55的......
  • 碎片和水位线回收的验证过程 转发 https://www.modb.pro/db/1780420808865845248
    1、数据库基础内容表空间-数据文件-段-区-块一个表空间由一个或者多个数据文件组成高水位线和表碎片的示意图其中被划掉的字代表delete删除，其中耶就是后续的insert，只会在末尾增加，而不是填充被删除的字段，这样就会导致数据库在搜寻数据时会浪费很多资源。整理碎片后大概是这......
  • P8866 [NOIP2022] 喵了个喵
    P8866[NOIP2022]喵了个喵构造模拟题，思路很简洁，但是代码不好写。首先看到数据范围，发现\(k\)的数据范围很特殊，种类少一种就是部分分，所以\(k\)一定是关键的，先思考\(k=2n-2\)的情况。\(k=2n-2\)观察两种操作，对于即将进入的牌\(x\)，若某个栈顶或栈底有相同的\(x\)，我们都可......
  • P2882 题解
    思想一眼看上去，没什么思路。看一下标签。枚举！于是枚举\(K\)。然后变成了求最少次数。由于枚举放在第一个，我们还是考虑一下枚举。我们枚举反转区间的左端点，我们惊奇地发现，由于从左往右扫，如果左端点是朝后的，那这次不转就没机会了。所以最最简单的暴力：从左往右扫，遇到左端点......
  • 洛谷 P8818 [CSP-S 2022] 策略游戏
    https://www.luogu.com.cn/problem/P8818什么玩意儿。。这种策略题不就是你来我往的，你如果选那个我就选这个，到了最后俩人都做不了决策，一直在博弈吗放个示例跑不过去的代码真不想调，这种题就是恶心啊，你说说怎么调呢针对一方的选择，另一方总能选出更优的策略来。然后这一方针对另......
  • 34.c语言数组练习题(牛客网)
    先打个广告哈哈哈牛客网练编程题不错不错哦冒泡排序必须必须必须会#include<stdio.h>voidsort(intarr[],intn){//外层循环for(inti=0;i<n-1;++i){intflag=1;//假设flag=1就是已经排序好的//内层循环for(intj=0;......
  • 牛客小白月赛91 题解
    A.Bingbong的化学世界签到题意：给你苯环的结构，判断类型。思路：按照区别特判即可。代码：#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#definedebug(x)c......
  • T422088 「LAOI-4」Colors
    /*手玩数据，会发现，你找不出可以进行超过两次操作的字符串，大胆假设，加上题目里怪异的k<=10^18，把k限制在2以内就没了*/#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;typedeflonglongLL;intn,len;LLm;strings;stringmake(......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99