首页 > 其他分享 >河南萌新联赛2024第（二）场：南阳理工学院

河南萌新联赛2024第（二）场：南阳理工学院

时间：2024-07-25 20:39:30浏览次数：17  
标签：int vi cin 理工学院 2024 vector 萌新 auto using

A - 国际旅行Ⅰ

因为保证联通，所以直接排序就好了

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;

using vi = vector<int>;

i32 main() {
	int n, m, q;
	cin >> n >> m >> q;

	vi a(n);
	for(int &i : a) cin >> i;

	sort(a.begin(), a.end());

	for(int x, y; m; m --)
		cin >> x >> y;
	
	for(int x; q; q--){
		cin >> x, x--;
		cout << a[x] << "\n";
	}
	return 0;
}

D - A*BBBB

直接用高精度是不可以的，但是我们可以用先成一个\(b\)然后再乘法\(11111\)就可以，这样的话就可以使用前缀和模拟高精度就好了。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using vi = vector<int>;

void solve() {
    string a, b;
    cin >> a >> b;
    reverse(a.begin(), a.end());
    int n = a.size(), m = b.size(), t = b[0] - '0';
    a = " " + a;
    vector<int> ans;
    int sum = 0, now = 0, carry = 0;
    for (int i = 1; i < n + m; i++) {
        if (i <= n) sum += a[i] - '0';
        if (i > m) sum -= a[i - m] - '0';
        now = (sum * t + carry) % 10;
        carry = (sum * t + carry) / 10;
        ans.push_back(now);
    }
    if (carry > 0) cout << carry;
    else {
        while (ans.size() > 1 and ans.back() == 0)
            ans.pop_back();
    }
    ranges::reverse(ans);
    for (auto i: ans) cout << i;
    cout << "\n";
}

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

E - “好”字符

把\(b\)串存两边，题目就变成在\(b\)串查询\(a\)串出现的次数。但是这里要剔除其他字母的影响，所以可以用*表示一个通配符就好了。剩下用kmp就好了。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;

using vi = vector<int>;

vi prefix_function(const string &s){
	int n = s.size();
	vi pi(n);
	for(int i = 1, j; i < n; i ++) {
		j = pi[i - 1];
		while(j > 0 and s[i] != s[j]) j = pi[j - 1];
		if(s[i] == s[j]) j ++;
		pi[i] = j;
	}
	return pi;
}


bool kmp(const string &text, const string &pattern) {
	string cur = pattern + "#" + text;
	int n = text.size(), m = pattern.size();
	vi lps = prefix_function(cur);
	for(int i = m + 1; i <= n + m; i ++) {
		if(lps[i] == m) return true;
	}
	return false;
}

i32 main() {
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t, t = t + t;
	vector<i.nt> cntS('z' + 1), cntT('z' + 1);
	for(auto i : s)
		cntS[i] = 1;
	for(auto i : t)
		cntT[i] = 1;

	int res = 0;
	for(char c = 'a'; c <= 'z'; c ++) {
		if( cntS[c] == 0 or cntT[c] == 0) continue;
		string ss = s, tt = t;
		for(auto &i : ss)
			if(i != c) i = '*';
		for(auto &i : tt)
			if(i != c) i = '*';
		if(kmp(tt, ss)) res ++;
	}
	cout << res;
	return 0;
}

F - 水灵灵的小学弟

两个人都是DHY

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;

using vi = vector<int>;

i32 main() {
	int n;
	cin >> n;
	while(n --) cout << "DHY\n";
	return 0;
}

G - 小w和大W的决斗。

在二维网格中如果要想将军队合并，就需要知道每个军队之间的距离，我们可以跑bfs来实现，当知道每个点之 间的距离之后我们跑一下最小生成树就可以知道最少多少天可以将军队合并了，如果军队与军队之间被阻挡无法到 达，则输出No。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

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

const int inf = INT_MAX / 2;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

class dsu {
private:
    vector<int> fa;
public:
    dsu(int n = 1) {
        fa = vector<int>(n + 1, -1), fa[0] = 0;
    }

    int getfa(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = getfa(fa[x]);
    }

    void merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        if (x == y) return;
        if (fa[x] > fa[y]) swap(x, y);
        fa[x] += fa[y], fa[y] = x;
    }

    bool same(int x, int y) {
        x = getfa(x), y = getfa(y);
        return (x == y);
    }
};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pii> pos;

    vector<string> g(n);
    for (auto &gi: g) cin >> gi;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '*')
                pos.emplace_back(i, j), cerr << i << " , " << j << "\n";

    auto bfs = [=](int sx, int sy) {
        vector dis(n, vi(m, inf));
        queue<pii> q;
        q.emplace(sx, sy);
        dis[sx][sy] = 0;
        while (not q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0, fx, fy; i < 4; i++) {
                fx = x + dx[i], fy = y + dy[i];
                if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
                if (g[fx][fy] == '#') continue;
                if (dis[fx][fy] <= dis[x][y] + 1) continue;
                dis[fx][fy] = dis[x][y] + 1;
                q.emplace(fx, fy);
            }
        }
        return dis;
    };

    vector<array<int, 3>> edge;
    for (int i = 0; i < pos.size(); i++) {
        auto [xi, yi] = pos[i];
        auto dis = bfs(xi, yi);
        for (int j = 0; j < i; j++) {
            auto [xj, yj] = pos[j];
            if (dis[xj][yj] == inf) {
                cout << "No\n";
                return 0;
            }
            edge.push_back({dis[xj][yj], i + 1, j + 1});
        }
    }

    sort(edge.begin(), edge.end());
    int res = 0;
    int t = pos.size();
    dsu d(t);
    for (auto &[w, x, y]: edge) {
        if (d.same(x, y)) continue;
        res += w, d.merge(x, y);
    }
    cout << res;
    return 0;
}

H - 狼狼的备忘录

小模拟，善用 STL 就好

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;

using vi = vector<int>;


i32 main() {
	map<string, vector<string>> info;
	int T;
	for(cin >> T; T; T--) {
		string name;
		cin >> name;
		int k;
		for(cin >> k; k; k --){
			string s;
			cin >> s;
			info[name].push_back(s);
		}
	}
	for(auto &[name, it] : info){
		sort(it.begin(), it.end());
		it.resize(unique(it.begin(), it.end()) - it.begin());

		for(auto &s : it)
			reverse(s.begin(), s.end());

		vector<string> newIt;

		for(const auto &s: it){
			bool flag = false;
			for(const auto &t : it){
				if(t.size() < s.size() or s == t) continue;
				if(t.substr(0, s.size()) != s) continue;
				flag = true;
				break;
			}
			if(flag) continue;
			newIt.push_back(s);
		}
		for(auto &s: newIt)
			reverse(s.begin(), s.end());
		sort(newIt.begin(), newIt.end());
		it = move(newIt);
	}
	cout << info.size() << "\n";
	for(auto &[name, it]: info){
		cout << name << " " << it.size();
		for(auto s : it) cout << " " << s;
		cout << "\n";
	}
	return 0;
}

I - 重生之zbk要拿回属于他的一切

暴力匹配

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;

using vi = vector<int>;

i32 main() {
	int n;
	cin >> n;
	string s;
	cin >> s;

	int cnt = 0;
	for(int i = 0; i + 4 < n; i ++)
		cnt += s.substr(i, 5) == "chuan";
	cout << cnt;
	return 0;
}

J - 这是签到

拉普拉斯展开

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;

using vi = vector<int>;

int calc(vector<vector<int>> a){
	int n = a.size(), sum = 0;
	if(n == 1) return a[0][0];


	for(int i = 0; i < n; i ++){
		vector<vi> b;
		for(int j = 1; j < n; j ++ ){
			b.push_back(vi());
			for(int k = 0; k < n; k ++) {
				if(k == i) continue;
				b.back().push_back(a[j][k]);
			}
		}

		sum += a[0][i] * pow(-1, i) * calc(b);
	}
	return sum;
}

i32 main() {
	int n, m, N;
	cin >> n >> m, N = max(n, m);

	vector<vi> a(N, vi(N));
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++)
			cin >> a[i][j];
	
	int res = INT_MAX;
	while(not a.empty()){
		res = min(res, calc(a));
		a.pop_back();
		for(auto &ai : a)
			ai.pop_back();
	}
	cout << res;
	return 0;
}

标签：int,vi,cin,理工学院,2024,vector,萌新,auto,using
From： https://www.cnblogs.com/PHarr/p/18324112

相关文章

  • 【专题】2024年云计算白皮书报告合集PDF分享（附原数据表）
    原文链接：https://tecdat.cn/?p=371122023年全球云计算市场显著增长，预计将持续繁荣至2027年突破万亿美元，中国市场同样保持强劲势头，预计也将大幅跃升。国内云计算经过十余年发展，虽取得显著进展，但在资源布局、服务质量和技术融合等方面仍需深化提升。阅读原文，获取专题报告合集全文，解......
  • 平邑2024高算（补题）
    Day1risk题目描述解法考虑最后的集结，不妨考虑找出所有集结过程中可能经过的边，不难发现是一棵树，所以答案就是最小生成树。代码点击查看代码structnode{ intu,v,w;}e[3000001];intn,m;intfa[3000001];intfind(intx){ returnx==fa[x]?fa[x]:fa[x]=find(......
  • 2024 暑假友谊赛-热身2
    TreeDestruction-洛谷|计算机科学教育新生态(luogu.com.cn)思路:树的直径。定理：在一棵树上，从任意节点y开始进行一次DFS，到达的距离其最远的节点z必为直径的一端。第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。再从找到的端点开始dfs1(),......
  • NOIP2024/7/25模拟赛
    T4题意：答案对\(2^{16}\)取模。分析：根节点\(1\)选到\(1\)的概率为\(\frac{1}{n}\)，然后随便把剩下的\(n-1\)分配给它的所有子树，记\(1\)的其中一个儿子为\(y\)，那么\(y\)选到它所被分配到的数中最小值的概率为\(\frac{1}{siz_{y}}\)，然后\(y\)再继续分配给它的子......
  • 河南萌新联赛2024第（二）场：南阳理工学院
    1.D-A*BBBB原题链接：https://ac.nowcoder.com/acm/contest/87255/D根据乘法的原理，且b的每一位都相同，最终答案则是错位相加得出的结果，于是我们将a翻转，从个位开始计算，如果当前位置小于a.size就往前累加，但如果大于或等于b.size就从头开始一个一个的减（这个过程可以通过纸上手写乘法计......
  • 2024.7.25（Git、gitlab以及分支管理）
    分布式版本控制系统一、Git概述Git是一种分布式版本控制系统,用于跟踪和管理代码的变更。它是由LinusTorvalds创建的,最初被设计用于Linux内核的开发。Git允许开发人员跟踪和管理代码的版本,并且可以在不同的开发人员之间进行协作。Github用的就是Git系统来管理它们的网......
  • Metasploit Pro 4.22.2-2024071901 (Linux, Windows) - 专业渗透测试框架
    MetasploitPro4.22.2-2024071901(Linux,Windows)-专业渗透测试框架Rapid7Penetrationtesting,releaseJul19,2024请访问原文链接：https://sysin.org/blog/metasploit-pro-4/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org世界上最广泛使用的渗透测试框架......
  • 2024年CRM系统选型：9款最强推荐
    文章介绍的工具有：纷享销客、ZohoCRM、八百客、红圈通、简道云、简信CRM、Salesforce、HubSpotCRM、Apptivo。在选择合适的CRM系统时，许多企业面临着功能繁多、选择困难的痛点。对于中小企业来说，找到一个既能提高客户关系管理效率，又能适应业务扩展的CRM系统尤为重要。本文将介......
  • 2024企业网站源码|网站后台管理系统 带搭建教程
    在网站搭建前需要考虑的问题了解完网站的搭建基本流程后，我们需要知道，网站该怎么设计，怎么搭建？在建站的时候需要从哪些方面考虑？网站的需求，是用来干什么的，比如：展示产品、品牌宣传、营销推广等；打算用什么方式建站，外包公司还是SaaS产品甚至是自己开发；网站内容，标准的企业网站需要包......
  • 2024 山东省夏令营高算班【讲课】
    Day1数论数论入门欧几里得算法若\(a\perpb\)，则\(\gcd(a^m-b^m,a_n-b^n)=a^{\gcd(n,m)}-b^{\gcd(n,m)}\)，证明用辗转相减做到指数上。若\(n^a\equiv1(\modm)\)且\(n^b\equiv1(\modm)\)，则\(n^{\gcd(a,b)}\equiv1(\modm)\)，同理可证。[CF1656H]EQUALLCMSUBSETS......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99