首页 > 其他分享 >河南萌新联赛2024第（一）场：河南农业大学

河南萌新联赛2024第（一）场：河南农业大学

时间：2024-07-17 21:51:10浏览次数：14  
标签：i64 int 河南 cin long 2024 vector 萌新 using

河南萌新联赛2024第（一）场：河南农业大学

A-造数_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

2 的二进制为 10，对于任意一个数，如 13，其二进制为 1101，可由 10 \(\rightarrow\) 100 \(\rightarrow\) 110 \(\rightarrow\) 1100 \(\rightarrow\) 1101，即 +2，×2，+2，×2，+1，即按照二进制来判断需要用多少次加 2 乘 2 ，最后判断需不需要加 1 即可。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n;
    cin >> n;

    int ans = 0;
    for (i64 i = 31; i > 0; i --) {
        if (ans) ans ++;
        if ((n >> i) & 1) {
            ans ++;
        }
    }

    cout << ans + (n & 1) << '\n';

    return 0;
}

B-爱探险的朵拉_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

前置知识： tarjan缩点+拓扑序。

根据题意可以抽象出就是给你一个有向有环图，然后就是用 tarjan 将环缩成点，用拓扑序跑最长路即可。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 15;
int n, m, sum, tim, top, s;
int p[maxn], head[maxn], sd[maxn];
int dfn[maxn], low[maxn];
//DFN(u)为节点u搜索被搜索到时的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
int stac[maxn], vis[maxn]; //栈只为了表示此时是否有父子关系
int h[maxn], in[maxn], dist[maxn];

vector<int> g[maxn], ng[maxn];

void tarjan(int x) {
    low[x] = dfn[x] = ++tim;
    stac[++top] = x; vis[x] = 1;
    for (auto v : g[x]) {
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (vis[v]) {
            low[x] = min(low[x], low[v]);
        }
    }
    if (dfn[x] == low[x]) {
        int y;
        while (y = stac[top--]) {
            sd[y] = x;
            vis[y] = 0;
            if (x == y) break;
            p[x] += p[y];
        }
    }
}
int topo() {
    queue <int> q;
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (sd[i] == i && !in[i]) {
            q.push(i);
            dist[i] = p[i];
        }
    while (!q.empty())
    {
        int k = q.front(); q.pop();
        for (auto v : ng[k]) {
            dist[v] = max(dist[v], dist[k] + p[v]);
            in[v]--;
            if (in[v] == 0) q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dist[i]);
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i ++)
        p[i] = 1;

    vector<int> a(n + 1);
    vector<pair<int, int>> edge;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        edge.push_back({i, a[i]});
        g[i].push_back(a[i]);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    for (auto &[from, to] : edge) {
        int x = sd[from], y = sd[to];
        if (x != y) {
            ng[x].push_back(y);
            in[y]++;
        }
    }

    cout << topo() << '\n';

    return 0;
}

C-有大家喜欢的零食吗_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

前置知识：二分图最大匹配，匈牙利算法。

将第 i 个小朋友喜欢的第 j 份零食大礼包看成由 i 向 j 连一条边，问左边的 n 个点能最大匹配右边的多少个点，那么这题就是求二分图的最大匹配数，上板子即可。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

struct augment_path {
    vector<vector<int> > g;
    vector<int> pa;  // 匹配
    vector<int> pb;
    vector<int> vis;  // 访问
    int n, m;         // 两个点集中的顶点数量
    int dfn;          // 时间戳记
    int res;          // 匹配数

    augment_path(int _n, int _m) : n(_n), m(_m) {
        assert(0 <= n && 0 <= m);
        pa = vector<int>(n, -1);
        pb = vector<int>(m, -1);
        vis = vector<int>(n);
        g.resize(n);
        res = 0;
        dfn = 0;
    }

    void add(int from, int to) {
        assert(0 <= from && from < n && 0 <= to && to < m);
        g[from].push_back(to);
    }

    bool dfs(int v) {
        vis[v] = dfn;
        for (int u : g[v]) {
            if (pb[u] == -1) {
                pb[u] = v;
                pa[v] = u;
                return true;
            }
        }
        for (int u : g[v]) {
            if (vis[pb[u]] != dfn && dfs(pb[u])) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        return false;
    }

    int solve() {
        while (true) {
            dfn++;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    augment_path ad(n,n);
    for(int i = 0;i < n;i ++){
        int k;
        cin >> k;
        for(int j = 0;j < k;j ++){
            int x;
            cin >> x;
            ad.add(i,--x);
        }
    }

    int res = ad.solve();
    if(res == n){
        cout << "Yes\n";
    }else{
        cout << "No\n" << n - res << '\n';
    }

    return 0;
}

D-小蓝的二进制询问_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

对于这种给一个区间求种类数的题目，不难想到前缀和的思想。

现考虑求一个数 x 从 1 到 x 的整数的二进制中的 1 的个数之和。

以 25 为例:

image

可以看出，对于每一位，画红框的地方是每一位的循环节，第 k 位的循环节长度为 \(2^{k+1}\) ，其中有 \(2^k\) 个 1，所以我们可以按位枚举，计算每一位上总共有多少个循环节和剩下非循环节中 1 的个数，因为这里是从 0 开始计算每一行的长度，所以实际计算时 x 需要加 1，具体计算就是，对于第 i 位：

\[\sum_{i=0}^{60}\frac{x+1}{2^{i+1}}\times2^i+\max((x+1)\%2^{i+1}-2^i,0) \]

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 mod = 998244353;

void solve() {

    i64 l, r;
    cin >> l >> r;

    auto calc = [&](i64 x)->i64{
        i64 res = 0;

        x ++;
        for (int i = 60; i >= 0; i --) {
            i64 y = x / (1ll << (i + 1));
            res = (res + y * (1ll << i) % mod) % mod;
            res = (res + max(x % (1ll << (i + 1)) - (1ll << i), 0ll)) % mod;
        }

        return res % mod;
    };

    cout << (calc(r) - calc(l - 1) + mod) % mod << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E-奇妙的脑回路_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

代码

F-两难抉择新编_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

对于第 i 个数，直接按 \([1,\frac{n}{i}]\) 的范围枚举两种操作，更新最大值即可。

复杂度 \(O(nlogn)\)

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    i64 ans = 0;
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        ans ^= a[i];
    }

    i64 t = ans;
    for (int i = 1; i <= n; i ++) {
        i64 res = t;
        res ^= a[i];
        for (int j = 1; j <= n / i; j ++) {
            ans = max(ans, res ^ (a[i] + j));
        }
        for (int j = 1; j <= n / i; j ++) {
            ans = max(ans, res ^ (a[i] * j));
        }
    }

    cout << ans << '\n';

    return 0;
}

G-旅途的终点_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

遍历 1 到 n ，用最小堆去维护当前最大的 k 个需要消耗的生命力，当枚举到当前所有消耗的生命力之和减去 k 个最大的也大于了 m 就说明无法继续再往下旅游了，注意会爆longlong，开 int128 即可。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, m, k;
    cin >> n >> m >> k;

    using pii = pair<i64, i64>;
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    __int128 Hp = 0, qhp = 0;
    priority_queue<i64, vector<i64>, greater<>> q;

    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        Hp += a[i];
        q.push(a[i]);
        qhp += a[i];
        if (q.size() > k) {
            qhp -= q.top();
            q.pop();
        }
        if (Hp - qhp >= m) break;
        ans = i;
    }

    cout << ans << '\n';

    return 0;
}

H-两难抉择_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

两种操作都是保证会让原数增大的，所以只要判断下最大值怎么操作即可。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    i64 sum = 0,ma = 0;;
    vector<i64> a(n);
    for(auto &i : a){
        cin >> i;
        sum += i;
        ma = max(ma,i);
    }

    sum += max(ma + n,ma * n) - ma;

    cout << sum << '\n';

    return 0;
}

I-除法移位_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

按定义化成分数形式可得：\(\frac{a_1}{a_2a_3\dots a_n}\)，要使该式最大化，即分子越大或者让分母越小，所以只要找到右移（倒序）后小于等于 t 的最大值下标即可。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

struct node {
    int v, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, t;
    cin >> n >> t;

    vector<node> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].v;
        a[i].id = n - i + 1;
    }

    a[1].id = 0;
    sort(a.begin() + 1, a.end(), [](node x, node y) {
        if (x.v == y.v) return x.id < y.id;
        return x.v > y.v;
    });

    for (int i = 1; i <= n; i ++) {
        auto [v, id] = a[i];
        if (id <= t) {
            cout << id << '\n';
            return 0;
        }
    }

    return 0;
}

J-最大矩阵匹配_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector a(n + 1, vector<bool>(m + 1));
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            char c;
            cin >> c;
            a[n + 1 - i][j] = c - '0';
        }

    vector s(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    auto get = [&](int x1, int y1, int x2, int y2)->int{
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    };

    int ans = 0;
    vector dp(n + 1, vector<int>(m + 1));

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            int k = dp[i - 1][j - 1];
            if (k > 0 && a[i][j] && a[i - k + 1][j] && a[i][j - k + 1] && get(i - k + 1, j - k + 1, i, j) == 3 * k - 2)
                dp[i][j] = dp[i - 1][j - 1];
            if (a[i][j] && a[i - k][j] && a[i][j - k] && get(i - k, j - k, i, j) == 3 * k + 1)
                dp[i][j] = dp[i - 1][j - 1] + 1;
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << '\n';

    return 0;
}

K-图上计数(Easy)_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

因为可以删掉任意边又合并任意联通块，所以直接就想象成给你一堆点，合并成两堆使得其乘积最大，即就是两堆点数接近 \(\frac{n}{2}\) 时最大。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, m;
    cin >> n >> m;

    vector g(n + 1, vector<int>());
    for (int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cout << (n / 2)*(n - n / 2) << '\n';

    return 0;
}

L-图上计数(Hard)_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路

代码

标签：i64,int,河南,cin,long,2024,vector,萌新,using
From： https://www.cnblogs.com/Kescholar/p/18308368

相关文章

  • 2024 (ICPC) Jiangxi Provincial Contest -- Official Contest
    2024(ICPC)JiangxiProvincialContest--OfficialContestA.MaliangLearningPainting题意：a+b+cvoidsolve(){lla,b,c;cin>>a>>b>>c;llans=a+b+c;cout<<ans<<'\n';}C.Lia......
  • 河南萌新联赛2024第（一）场：河南农业大学
    造数\(25-24-12-6-3-2-0\)\(11-10-5-4-2-0\)1.观察上面的例子可以发现，每个数如果是偶数直接除二，如果是奇数就减一，这样得到的次数最少#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefpair<int,int>pii;#definexfirst#de......
  • 2024.7.17
    2024.7.17【我们必须知道，我们必将知道】Wednesday六月十二P5999[CEOI2016]kangaroo//2024.7.17//bywhite_ice//P5999[CEOI2016]kangaroo#include<bits/stdc++.h>usingnamespacestd;#defineitnlonglong#defineintlonglongconstexprintoo=4003;co......
  • 河南萌新联赛2024第（一）场：河南农业大学
    A造数思路：将n看成二进制，倒着操作将n变为0即可赛时的想法也是看成二进制，正着从0加到n，乘2就是向前移位，加1就是把0变1，加2就是添一个1...(还是倒着好想些)voidsolve(){intn;cin>>n;if(n==0){cout<<0;return;}if(n==1......
  • 2024.7.17 鲜花
    極私的極彩色アンサー-TOGENASHITOGEARI——fromK*(K8)我怎么每天早上补昨天没写完的鲜花。算了，放到今天吧。书接上回发现2开了，和幂次没关系了。发现有\(b-a+1\)个数，猜到是区间。考虑\(p\)和分布位置，可知是质数。线性筛即可。910.值域偏大，可以用Miller_......
  • SMU Summer 2024 Contest Round 4
    1.HandV原题链接：http://162.14.124.219/contest/1008/problem/B二进制枚举行列即可查看代码#include<bits/stdc++.h>#defineintlonglong#definePIIpair<int,int>usingnamespacestd;intn,m,k;chara[10][10];signedmain(){ios::sync_with_stdio(fals......
  • 2024-07-17 如何在vscode部署你的代码块，从而在新建页面时能快速搭建模板（windows环境）
    步骤一：打开vscode，按住ctrl+shif+p唤出命令窗口 步骤二：在窗口中输入命令，并回车Preferences:OpenUserSnippets 对，就是这个代码片段，接着输入你想添加代码的某某语言or脚本，比如我要添加vue的代码片段输入vue，回车，会显示vue.json文件出来给你更改，我的是这样 注意：如果你......
  • 2024-07-17 搭建一个node+express服务器，并把静态资源部署到该服务器（本地开发）
    前言：请确保你已安装了node，没有你得先装这个。步骤一：//创建文件夹mkdirexpress-node//创建完了进入该文件夹cdexpress-node//初始化npminit-y//安装expressnpmiexpress前提工作都准备好后，在express-node文件夹里新建文件server.js，作为启动服务器的入口文件......
  • 2024.7.15 近期练习
    P3488[POI2009]LYZ-IceSkates我们对于鞋码为\(x\)的人，贪心地，显然先把鞋小的给他穿。所以就有了一个暴力的检验方法：从左往右扫，并对应修改。但是这样太慢。这是一个二分图匹配问题，考虑Hall定理。对于任意\(1\lel\ler\len\)，当\(sum(a_l\sima_r)\le(r-l+1+d)k\)时合......
  • Goby漏洞发布 | CVE-2024-4879 ServiceNowUI /login.do Jelly模板注入漏洞【已复现】
    漏洞名称：ServiceNowUI/login.doJelly模板注入漏洞（CVE-2024-4879）EnglishName：ServiceNowUI/login.doInputValidationVulnerability（CVE-2024-4879）CVSScore:9.3漏洞描述：ServiceNow是一个业务转型平台。通过平台上的各个模块，ServiceNow可用于从人力资源和员工管理到自动......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99