首页 > 其他分享 >2023 ICPC网络赛第一场(A,D,J,L)

2023 ICPC网络赛第一场(A,D,J,L)

时间:2023-09-22 16:12:25浏览次数:45  
标签:int double ++ ans cin ICPC vis 第一场 2023

2023 ICPC网络赛第一场(A,D,J,L)

A Qualifiers Ranking Rules

先把两场比赛的学校排名处理出来,然后两场比赛的同位次进行合并即可

#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<string> str1, str2,ans;
	map<string, bool> vis1, vis2, vis;	
	string s;

	for (int i = 0; i < n; i ++) {
		cin >> s;
		if (vis1[s]) continue;
		str1.emplace_back(s);
		vis1[s] = true;
	}
	for (int i = 0; i < m; i ++) {
		cin >> s;
		if (vis2[s]) continue;
		str2.emplace_back(s);
		vis2[s] = true;
	}

	n = str1.size(), m = str2.size();
	for (int i = 0; i < max(n,m); i ++) {
		if (i < n && !vis[str1[i]]) {
			ans.emplace_back(str1[i]);
			vis[str1[i]] = true;
		}
		if (i < m && !vis[str2[i]]) {
			ans.emplace_back(str2[i]);		
			vis[str2[i]] = true;
		}
	}

	for (auto i : ans)
		cout << i << '\n';

	return 0;
}

D Transitivity

如果题目给的所有的团都是完全图,那么就要合并两个最小的团,答案就是这两个团的点数的乘积,否则就要把所有的团都补成完全图,bfs或者并查集即可

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

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

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

	vector<bool> vis(n + 1);
	vector<i64> ans;

	auto bfs = [&](int i) -> pair<i64, i64> {
		queue<int> Q;
		Q.push(i);
		int edge = 0, node = 0;
		while (Q.size()) {
			auto v = Q.front();
			Q.pop();	

			if(vis[v]) continue;		
			vis[v] = true;
			node ++;

			for (auto i : g[v]) {
				if (vis[i]) continue;
				Q.push(i);
				edge ++;
			}
		}

		return {node, edge};
	};

	bool is_Tuan = true;
	i64 res = 0;
	for (int i = 1; i <= n; i ++) {
		if (vis[i]) continue;
		auto [num, Edge] = bfs(i);		
		if (Edge != num * (num - 1) / 2) {
			is_Tuan = false;
			res += num * (num - 1) / 2 - Edge;
		}		
		ans.push_back(num);
	}

	if (!is_Tuan) {
		cout << res << '\n';
	} else {
		sort(ans.begin(), ans.end());
		cout << ans[0] * ans[1] << '\n';
	}

	return 0;
}

J Minimum Manhattan Distance

题意是求在\(C_2\)上取一点到\(C_1\)任意一点的最小期望曼哈顿距离.

由于题目要求是最小期望曼哈顿距离,所以可以等价于看做就到\(C_1\)圆心,为了方便计算,可以把\(C_2\)的圆心看成坐标轴原点,\(C_1\)的圆心通过对称变换到第一象限,设\(\{x_0,y_0\}\)为答案点,则有\(\begin{cases} x_0 = x_2 + r_2\cos\theta \\ y_0 = y_2+r_2\sin \theta\end{cases}\),答案为\(|x_1-x_0|+|y_1-y_0|\),

且题目规定\(\forall x_i \in C_1 \neq \forall x_j \in C_2,\forall y_i \in C_1 \neq \forall y_j\in C_2,\),所以当\(C_1\)在第一象限时,总有\(x_1>x_0,y_1>y_0\),所以绝对值可拆,然后用三角函数计算一下,可得出当\(\theta = \frac{\pi}{4}\)时有最小值\(x+y-\sqrt{2}\times r_2\).

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

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

    auto get = [&](double x1,double y1,double x2,double y2){
        return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); 
    };

    int T;
    cin >> T;
    while(T--){
        double xa,ya,xb,yb,xc,yc,xd,yd;
        cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
        double r2 = get(xc,yc,xd,yd) / 2;
        double x1 = (xa + xb) / 2, y1 = (ya + yb) / 2;
        double x2 = (xc + xd) / 2, y2 = (yc + yd) / 2;
        double ans = fabs(x1 - x2) + fabs(y1 - y2) - r2 * sqrt(2) ;
        printf("%.10lf\n",ans);
    }

    return 0;
}

L KaChang!

签到题,题目规定了\(k\geq 2\),所以答案为\(\max(2,\lceil\frac{T}{\max\limits_{i=1}^{n}a_i}\rceil)\)

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

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

	i64 n, k;
	cin >> n >> k;
	i64 ma = 0, x;
	for(int i = 0;i < n;i ++){
		cin >> x;
		ma = max(ma, x);
	}

	cout << max(2ll, (k + ma - 1) / k) << '\n';
 
	return 0;
}

标签:int,double,++,ans,cin,ICPC,vis,第一场,2023
From: https://www.cnblogs.com/Kescholar/p/17722627.html

相关文章

  • 2023.9.22 AT practise
    ARC083F显然每个小球必须被\((0,y)\)或\((x,0)\)中的一个收掉,那么把\(i\)的球看成一条边,链接两个机器人。因为\(2n\)个小球对应\(2n\)条边,故建图出来是一个基环树森林。考虑把每条边定向,对应的就是那个球被那个机器人收了。那么每个基环树只有两种情况(环的方向)。现......
  • [IJCAI 2023]Preventing Attacks in Interbank Credit Rating with Selective-aware G
    [IJCAI2023]PreventingAttacksinInterbankCreditRatingwithSelective-awareGraphNeuralNetwork问题文章研究的是对银行间信用评价的攻击的预防。点是银行,边是银行间的借贷关系。攻击方式有特征攻击(改特征)和结构攻击(加边),目标是点预测。模型选择表示层通过伯努利......
  • [JOI 2023 Final] Stone Arranging 2
    洛谷P9349题意一种区间覆盖操作,可以考虑直接无脑线段树,复杂度为\(O(nlog_n)\)。但是观察后发现可以开一个桶,记录这个数在序列中出现的最后一次的下标。循环扫一遍原序列,从小到大对于每一个a[i],使得下标i到m[a[i]]的区间全部覆盖为a[i]。每次覆盖一个小区间后,因为前面的区间已......
  • 2023-09-22 uniapp之canvas调用api【uni.canvasToTempFilePath】报错返回:canvasToTemp
    canvasToTempFilePath:失败-失败画布为空一般的解决方案就是查看uni.canvasToTempFilePath的传参是否正确,一个是canvasId必须正确,另一个就是第二个参数为this;但事情显示没那么简单,这二者我都有填写,却仍旧报这个错,我把canvasid换成别的,最后我想起了一件事情,就是canvas为空是因为......
  • 20230921
    20230921T378733成长grow思路按题目模拟即可。时空复杂度时间:\(O(9)\)空间:\(O(11)\)T378729清洁clean思路首先我们可以将图分为上下两个矩形,以便于我们计算,然后我们会发现圆会和矩形有两个交点,而这两个交点分别会在两条边上,如下图(只有上半部分有):跟据图形,我们......
  • 2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)
    A.AccessDenied先问若干次,问出长度,然后再一位一位的问即可。#include<bits/stdc++.h>usingnamespacestd;intinput(){strings;getline(cin,s);if(s=="ACCESSGRANTED")exit(0);intt=0;for(autoi:s){if(i&g......
  • 2023-09-21 裸k交易法 日内模型 低开
    低开高走  低开低走  ......
  • 【2023-09-21】家庭真相
    20:00凡益之道,与时偕行。对历史能看得多深,对未来就能看得多远。                                                 ——XXX昨天下班,正常6点我就离开公司,直接回家。我晚......
  • 2023.09.21
      今天学习了数据结构栈和队列。采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置。若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判......
  • 2023-9-21 闲话
    鲜花还是在博客园写吧。感觉挺累的,想病个两三天回家睡觉。推歌:竹ノ花原曲之一是《东方求闻史记》的附赠曲,同样改编了本曲的二创还有《现梦-genmu-》都是挺让人伤感的歌曲呢,这首歌是凋叶棕为同名本子做的曲,讲的是稗田三代家主与男主的故事。稗田家的家主30岁必死,然后转生,......