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

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

时间：2024-07-17 20:51:10浏览次数：17  
标签：return ve int 河南 cin st 2024 萌新 ans

A造数

思路：

将n看成二进制，倒着操作将n变为0即可

赛时的想法也是看成二进制，正着从0加到n，乘2就是向前移位，加1就是把0变1，加2就是添一个1...(还是倒着好想些)

 
void solve() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0;
        return ;
    }
    if (n == 1) {
        cout << 1;
        return ;
    }
    string s;
    while (n) {
        if (n % 2) s.push_back('1');
        else s.push_back('0');
        n /= 2;
    }
    int ans = s.size() - 1;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '1') ans ++;
    }
    ans --;
    cout << ans;
}

B爱探险的朵拉

思路：

首先建图，可能会出现多个环，一种是结尾为自环的，一种是没有自环的章鱼图，可以分别来统计

对于结尾为自环的情况，可以统统建立反边，从出现自环的点开始bfs，求出最长路径，答案为最长路径

对于没有自环的章鱼图，首先要找出环，可以用dfs找出，接着求出环上最长的链，可以让环上的点为起点bfs求出最长链，答案为环的个数+最长链长度

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), in(n + 1);
    vector<vector<int> > b(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        //  b建反边
        b[a[i]].push_back(i);
        //  in表示是否被指向
        in[a[i]] = 1;
    }
    vector<int> st(n + 1), vis(n + 1);
    int ans = 0;

    //  求出结尾为自环的路径长度
    for (int i = 1; i <= n; ++i) {
        if (a[i] == i) {
            //  bfs求最长的路径，用反边
            queue<PII> q;
            q.push({i, 1});
            vis[i] = 1;
            while (q.size()) {
                auto [u, cnt] = q.front();
                q.pop();
                ans = max(ans, cnt);
                for (auto v:b[u]) {
                    if (vis[v]) continue;
                    vis[v] = 1;
                    q.push({v, cnt + 1});
                }
            }
        }
    }

    //  章鱼图：求出环，求出环上最长链
    for (int i = 1; i <= n; ++i) {
        if (vis[i] || st[i]) continue;
        //  p记录环上的一点
        int p = 0;
        auto dfs = [&] (int u, auto dfs) -> void {
            if (p != 0) return ;
            if (st[a[u]]) {
                p = a[u];
                return ;
            }
            st[a[u]] = 1;
            dfs(a[u], dfs);
            st[a[u]] = 0;
        };
        st[i] = 1;
        //  dfs求出环上一点
        dfs (i, dfs);
        st[i] = 0;
        
        //  g存环上的点
        vector<int> g;
        g.push_back(p);
        int t = a[p];
        vis[p] = 1;
        while (t != p) {
            g.push_back(t);
            vis[t] = 1;
            t = a[t];
        }
        int m = g.size();
        ans = max(ans, m);
        
        //  bfs求环上最长链，分别从环上每个点出发
        queue<PII> q;
        for (auto v:g) {
            q.push({v, 0});
            vis[v] = 1;
            while (q.size()) {
                auto [u, cnt] = q.front();
                q.pop();
                ans = max(ans, m + cnt);
                for (auto z:b[u]) {
                    if (vis[z] || st[z]) continue;
                    q.push({z, cnt + 1});
                    vis[z] = 1;
                }
            }
        }
    }
    cout << ans;
}

C有大家喜欢的零食吗

思路：

经典的二分图匹配问题，直接用匈牙利求

void solve() {
    int n;
    cin >> n;
    vector<vector<int> > ve( 2 * n + 1);
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int u;
            cin >> u;
            ve[i].push_back(u + n), ve[u + n].push_back(i);
        }
    }
    vector<int> st(2 * n + 1), to(2 * n + 1);
    auto dfs = [&](int u, auto dfs)->bool {
        for (auto v:ve[u]) {
            if (st[v]) continue;
            st[v] = 1;
            if (!to[v] || dfs(to[v], dfs)) {
                to[v] = u;
                return true;
            }
        }
        return false;
    };
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        std::fill(st.begin(), st.end(), 0);
        if (dfs(i, dfs)) ans ++;
    }
    if (ans == n) cout << "Yes";
    else {
        cout << "No\n";
        cout << n - ans;
    }
}

D小蓝的二进制询问

思路：

用前缀和来做，求[1, r]的值，先将数转换为二进制

从最高位开始，假设已经统计了当前位前面的1的个数now，若当前位为1，且前面不变，那区间一定包含了这一位为0，后面为全为1的二进制数，若后面的1的个数为k，则有2k个数，且前面1的个数已经知道了，那么要多加贡献now * 2k。对于全为1的二进制数的贡献：一位一位的求，令某一位为1，则这一位的贡献为2k - 1，所有位的加起来就是k * 2k-1。

所以枚举到这一位带来的贡献为now * 2k + k * 2k-1

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7;


int ksm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    int l, r;
    cin >> l >> r;
    string sl, sr;
    l --;
    auto to2 = [](int x) {
        string t;
        while (x) {
            if (x % 2) t.push_back('1');
            else t.push_back('0');
            x /= 2;
        }
        return t;
    };
    auto P = [=] (string x) {
        int now = 0;
        int ans = 0;
        for (int i = x.size() - 1; i >= 0; --i) {
            if (x[i] == '0') continue;
            if (i > 0) ans = (i * ksm(2, i - 1) % mod + ans) % mod;
            ans = (ans + now * ksm(2, i) % mod) % mod;
            now ++;
        }
        ans = (ans + now) % mod;
        return ans;
    };
    sl = to2(l), sr = to2(r);
    int ans = (P(sr) - P(sl) + mod) % mod;
    cout << ans << '\n';

}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

E奇妙的脑回路

F两难抉择新编

思路：

枚举，类似质数筛的方法，nlogn

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int ans = -1, sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum ^= a[i];
    }
    for (int i = 1; i <= n; ++i) {
        int t = sum ^ a[i];
        for (int j = 1; j <= n / i; ++j) {
            int x = a[i] + j, y = a[i] * j;
            ans = max({ans, t ^ x, t ^ y});
        }
    }
    cout << ans;
}

G旅途的终点

思路：

维护当前畅游国家数需要消耗的最少生命力，标记使用了神力的国家

首先是有一个按消耗生命力排序的国家序列，优先对消耗生命力多的国家使用神力

若当前需要消耗的最少生命力不小于m，说明需要减少畅游国家，畅游国家的顺序已经给出了，那就减去最后一个，要更新需要消耗的生命力，首先看是否使用了神力，若使用了神力，说明需要在将一个原本消耗生命力的国家转变为使用神力，那就从已有的国家序列中选择满足条件的，若没有使用神力，则直接从消耗生命力里减去，知道需要消耗的最少生命力小于m

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e3 + 5, mod = 998244353;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool cmp(PII x, PII y) {
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    multiset<int> se;
    __int128 sum = 0;
    vector<PII> b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
        b[i].first = a[i], b[i].second = i;
    }
    if (k >= n) {
        cout << n;
        return ;
    }
    vector<int> st(n);
    sort(b.begin(), b.end(), cmp);
    for (int i = 0; i < k; ++i) {
        st[b[i].second] = 1;
        sum -= b[i].first;
    }
    if (sum < m) {
        cout << n;
        return ;
    }
    int p = k;
    for (int i = n - 1; i >= 0; --i) {
        if (st[i]) {
            st[i] = 0;
            while (p < n && b[p].second >= i) {
                p ++;
            }
            st[b[p].second] = 1;
            sum -= b[p ++].first;
        } else sum -= a[i];
        if (sum < m) {
            cout << i;
            return ;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

H两难抉择

思路：

肯定是操作最大的数，分别判断哪个操作后大即可

void solve() {
    int n;
    cin >> n;
    vector<int> ve(n);
    for (int i = 0; i < n; ++i) cin >> ve[i];
    sort(ve.begin(), ve.end());
    if (ve.back() + n > ve.back() * n) {
        ve.back() += n;
    } else ve.back() *= n;
    int sum = 0;
    for (auto v:ve) sum += v;
    cout << sum;
}

I除法移位

思路：

分子尽可能大即可

void solve() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n + 1);
    int ma = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ma = max(ma, a[i]);
    }
    if (a[1] == ma) cout << 0;
    else {
        int maa = -1, ans = 0;
        for (int i = n, j = 1; i >= 1 && j <= t; --i, ++j) {
            if (a[i] > maa) {
                maa = a[i], ans = j;
            }
        }
        cout << ans;
    }
}

J最大矩阵匹配

 

K图上计数(Easy)

思路：

任意删边、合并点，当连通块个数去一半是相乘最大

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7;

int fa[N];
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
    }
    if (n == 0) {
        cout << 0;
        return ;
    }
    if (n == 1) {
        cout << 0;
        return ;
    }
    int a = n / 2, b = n - a;
    cout << a * b;

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

L图上计数(Hard)

思路：

首先是直接tarjan求缩边，然后除去缩边外对所有边进行并查集合并，求出每个连通块的个数后，由于n的范围为4e5，那连通块个数的种类数不超过1e3，就可以用多重背包求合并的连通块个数是否存在

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 4e5 + 5, mod = 998244353;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct E {
    int u, v;
};
int dfn[N], low[N], ct, fa[N];
struct EE {
    int fa, cnt;
}t[N];
vector<vector<int> > ve;
map<PII, int> mp;
void tarjan(int u)
{
    t[u].fa = u, t[u].cnt = 1;
    low[u] = dfn[u] = ++ct;
    for (auto v : ve[u])
    {
        if (!dfn[v])
        {
            fa[v] = u;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                mp[{u, v}] = mp[{v, u}] = 1;
        }
        else if (v != fa[u])
            low[u] = min(low[u], dfn[v]);
    }
}
int find(int x) {
    if (x != t[x].fa) t[x].fa = find(t[x].fa);
    return t[x].fa;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<E> g(m);
    ve = vector<vector<int> > (n + 1);
    for (int i = 0; i < m; ++i) {
        cin >> g[i].u >> g[i].v;
        ve[g[i].u].push_back(g[i].v), ve[g[i].v].push_back(g[i].u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 0; i < m; ++i) {
        if (!mp.count({g[i].u, g[i].v})) {
            int u = find(g[i].u), v = find(g[i].v);
            if (u != v) t[u].fa = v, t[v].cnt += t[u].cnt;
        }
    }
    map<int, int> mpp;
    for (int i = 1; i <= n; ++i) {
        int u = find(i);
        if (i == u) mpp[t[u].cnt] ++;
    }

    vector<int> w;
    for (auto [a, b]:mpp) {
        int k = 1;
        while (k <= b) {
            w.push_back(k * a);
            b -= k;
            k *= 2;
        }
        if (b) {
            w.push_back(b * a);
        }
    }
    vector<int> f(n + 1);
    f[0] = 1;
    for (int i = 0; i < w.size(); ++i) {
        for (int j = n; j >= w[i]; --j) {
            f[j] |= f[j - w[i]];
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
        if (f[i]) {
            ans = max(ans, i * (n - i));
        }
    }
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

 

标签：return,ve,int,河南,cin,st,2024,萌新,ans
From： https://www.cnblogs.com/bible-/p/18308274

相关文章

  • 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可用于从人力资源和员工管理到自动......
  • NOI2024游记
    试图性的写一下游记，本来都懒得写了，但是由于太戏剧性了就还是写一下吧Day-？记不太清了，写一部分把由于要提前到重庆熟悉环境，所以我们就都来了来的这段时间是跟着nfls打模拟赛+UNR第一天打的超级好，哈哈，排名12/70+然后就非常高兴第二天和第三天是UNR，打的屁也不是，混了个Cu就滚了......
  • 常用十大加密软件排行榜丨2024好用的加密软件推荐
    2023年7月，中国人民大学的一位硕士毕业生盗取了该校2014级到2022级学生的大量个人隐私信息，包括照片、姓名、学号、籍贯等，并制作成网站，供人搜索浏览甚至颜值打分。该事件引发了对个人隐私保护和数据安全的广泛关注，突显了加密软件在防范数据泄露中的重要性。随着科技的发展，越来......
  • 2024年华为OD机试真题-图像物体的边界-C++-OD统一考试（C卷D卷）
     2024年OD统一考试（D卷）完整题库：华为OD机试2024年最新题库（Python、JAVA、C++合集）题目描述：给定一个二维数组M行N列，二维数组里的数字代表图片的像素，为了简化问题，仅包含像素1和5两种像素，每种像素代表一个物体，2个物体相邻的格子为边界，求像素1代表的物体的边界个数。像素1代表的......
  • 题解：P10723 [GESP202406 七级] 黑白翻转
    背景汗流浃背了。分析容易想到一个显然的思路：以任意节点为根，开始遍历。如果一个节点的子树里面有黑点，那么它必须保留，否则如果它是白点，则可以删去。但这个方法很容易举出反例：在这颗树中，如果以最上面的白点为根，那么手推发现算法显然错误。尝试进行修改，容易发现，对于类似的情况......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99