首页 > 其他分享 >CodeforceTon Round 4 div1 + div2 题解

CodeforceTon Round 4 div1 + div2 题解

时间:2024-11-09 15:57:10浏览次数:1  
标签:int 题解 long Round -- while solve using div2

题解 A - E


Dream is so far ~

A. Beautiful Sequence

检查每一位对应的数字是否小于等于位置,如果可以说明这个数字可以移动到对应位置上, 遍历即可

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
	int n;
	cin >> n;

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

	for (int i = 1; i <= n; i++) {
		if (a[i] <= i) {
			cout << "Yes\n";
			return;
		}
	}
	cout << "No\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while(t--) {
		solve();
	}

	return 0;
}

B. Candies

考虑到从一开始往后面变,且每次只能变为 $2 * n - 1$ 或 $2 * n + 1$ , 显然这些数都是奇数, 考虑从末位往前处理, 每次除以二如果是奇数说明这一次选了2来到这一步,否则将除以二结果加一,同时意味着这一步选了1。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
	i64 n;
	cin >> n;

	if (n % 2 == 0) {
		cout << -1 << '\n';
		return;
	}

	vector<int> ans;
	while (n != 1) {
		int now = n / 2;
		if (!(now & 1)) {
			now ++;
			ans.push_back(1);
		}
		else {
			ans.push_back(2);
		}
		n = now;
	}
	cout << ans.size() << '\n';
	for (int i = ans.size() - 1; i >= 0; i--) {
		cout << ans[i] << ' ';
	}
	cout << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while(t--) {
		solve();
	}

	return 0;
}

C. Make It Permutation

首先考虑有一个以上数字,显然需要使用第二步操作去掉(否则将不会形成一排列),
之后对于去重后数组, 将其排序, 从后面往前面dp过去, 考虑把后面全部删掉或者是在这两位之间补齐剩下的数字, 有
$dp[i] = min(dp[i + 1] + (b[i + 1] - b[i] - 1) * d, c * (nn - 1 - i));$
即当前位置最小需要等于上一位到这一位之间需要补齐数字和把后面全部删掉的数字。
注意一开始的1要补上(if no one in this array)

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
	i64 n, c, d;
	cin >> n >> c >> d;

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

	sort(a.begin() + 1, a.end());
	vector<int> b;

	i64 sum = 0;
	if (a[1] != 1) {
		b.push_back(1);
		sum += d;
	}

	b.push_back(a[1]);
	for (int i = 2; i <= n; i++) {
		if (a[i] == a[i - 1]) {
			sum += c;
			continue;
		}
		b.push_back(a[i]);
	}

	int nn = b.size();
	vector<i64> dp(nn);
	for (int i = nn - 2; i >= 0; i--) {
		dp[i] = min<i64>(dp[i + 1] + (b[i + 1] - b[i] - 1) * d, c * (nn - 1 - i));
	}

	cout << dp[0] + sum << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while(t--) {
		solve();
	}

	return 0;
}

D. Climbing The Tree

蜗牛爬树,很好玩的数学题, 直接给代码 : 思路见代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fun (int h, int x, int y) {
	if (h <= x) return 1;
	return ceil ( (h - x) * 1.0 / (x - y) ) + 1;
}
void solve() {
	int q;
	cin >> q;
	bool f = false;
	int l, r;
	while (q --) {
		int op, a, b, n;
		cin >> op >> a >> b;
		if (op == 1) {
			cin >> n;
			if (!f) {
				if (n == 1) {
					l = 1;
					r = a;
				}
				else {
					l = a * n - b * n - a + 2 * b + 1;
					r = a * n - b * n + b;
				}
				f = true;
				cout << 1 << " ";
			}
			else {
				int x, y;
				if (n == 1) {
					x = 1;
					y = a;
				}
				else {
					x = a * n - b * n - a + 2 * b + 1;
					y = a * n - b * n + b;
				}
				if (max (x, l) > min (y, r) ) cout << 0 << " ";
				else {
					l = max (x, l);
					r = min (y, r);
					cout << 1 << " ";
				}
			}
		}
		else {
			if (!f) cout << -1 << " ";
			else {
				if (fun (l, a, b) == fun (r, a, b) ) cout << fun (l, a, b) << " ";
				else cout << -1 << " ";
			}
		}
	}
	cout << "\n";
}
signed main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	
	while (t --) {
		solve();
	}
	
	return 0;
}

E. Monster

给出一张图, 点 u 的遍历需要先经过这一个点所需权值 a[ u ] 个点后才可遍历, 一开始想这道题会想着先选出所有点权为 0 的点, 以这个点作为起点开始bfs 维护一个Krusal树,想着想着不知道怎么写了,换个了思路, 用一个小根堆记录当前能到达的点的相邻所有点, 一开始把所有0的点压入堆中, 用个变量记录当前已经走过的点的数量,之后每次从堆中取出一个点, 检查这个点的权是否小于已经走过的点的数量, 如果大于说明不能到达,直接停止(因为开的是小根堆), 否则对这个点周围的点进行遍历,如果可以到达就让走过的点++ , 否则压入堆中等待处理。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
constexpr int inf = 1e9 + 7;
struct node {
	int u, w;
	bool operator>(const node& a) const { return this->w > a.w; } 
};
void solve() {
	int n, m;
	cin >> n >> m;

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

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

	auto fun = [&](int s) -> bool {
		priority_queue<node, vector<node>, greater<node>> q;
		//queue<int> Q;
		int cnt = 0;
		q.push({s, a[s]});

		while (!q.empty()) {
			auto [u, w] = q.top();
			q.pop();
			if (vis[u] == s) continue;
			vis[u] = s;

			if (cnt >= w) {
				cnt++;
				for (auto v : e[u]) if (vis[v] != s) {
					q.push({v, a[v]});
				}
			}
			else {
				break;
			}
		}
		//cerr << "cnt : " << cnt << '\n';
		return (cnt == n);
	};

	for (int i = 1; i <= n; i++) {
		if (a[i] == 0 && !vis[i]) {
			if (fun(i)) {
				cout << "Yes\n";
				return;
			}
		}
	}
	cout << "No\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while(t--) {
		solve();
	}

	return 0;
}

标签:int,题解,long,Round,--,while,solve,using,div2
From: https://www.cnblogs.com/Dreamstartsblog/p/18536894

相关文章

  • CF607B Zuma 题解
    CF607BZuma不知道为什么你谷会评蓝,这不是很基础的区间DP吗。Problem-607B-Codeforces题意简述消除回文子串的最小次数。思路对于区间\([i,j]\),如果它是回文的,那么消除它所需的次数是\(1\)。如果它不是回文的,但是\(a[i]==a[j]\),那么当区间\([i+1,j-1]\)被消除到只剩下......
  • [ARC158C] All Pair Digit Sums 题解
    C-AllPairDigitSums题意:设\(f(x)\)为\(x\)的数字和。例如\(f(158)=1+5+8=14\)。给定一个长度为\(N\)的正整数序列\(A\),求\(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i+A_j)\)。分析:首先明确\(f(x)\)为\(x\)的数位和。举例情况:若有两个数分别为:\(12,21\)。\[f(......
  • QT中大量数据存储至excel的问题解决
            因为这个问题困扰了我很久,所以在这里记录一下,顺便给可能会遇到类似问题的人提供一点帮助。        在qt中,如果用C++处理数据保存到excel,正常来说在pro文件中添加axcontainer 然后就能够调用到excel,但是这只能适用于数量级没那么大时的需求。  ......
  • Sigrity SPEED2000 Power Ground Noise Simulation模式如何进行电源地噪声分析操作指
    SigritySPEED2000PowerGroundNoiseSimulation模式如何进行电源地噪声分析操作指导-SODIMMSigritySpeed2000是时域仿真分析工具,PowerGroundNoiseSimulation模式可以观测器件的时域电压波形和观测电源地空间电压分布,以下图为例进行分析用Speed2000这个工具打开文件......
  • Sigrity SPEED2000 Power Ground Noise Simulation模式如何进行电源阻抗仿真分析操作
    SigritySPEED2000PowerGroundNoiseSimulation模式如何进行电源阻抗仿真分析操作指导(一)-无电容SigrityPowerGroundNoiseSimulation模式同样可以用来观测电源网络的自阻抗,以下图为例进行说明2D视图3Dview本例要观测的是U17端口处的自阻抗,通过观测电压和电流......
  • ffmpeg问题解决:Unrecognized option 'preset'. Error splitting the argument list: O
    来到这里,十有八九是手动编译安装的ffmpeg,在跑视频流程序或命令时出现这个问题。跟这个报错:ffmpeg:errorwhileloadingsharedlibraries:libx264.so.164:cannotopensharedobjectfile:Nosuchfileordirectory的错误本质是一样的,都是由于ffmpeg时使用到了libx264,而在......
  • 讲座の题解
    讲座配套题单的题解喵每题的文字解释会逐渐补充,如果有疑问直接私信喵目录讲座配套题单的题解喵目录A-看看你会不会用电脑B-求求你不要用内置函数C-GPAD-minE-for循环大神F-居然有人说这个是线性代数G-高三同学秒了H-无穷级数I-不要用内置函数......
  • 【题解】「NOIP2024模拟赛24 T3」钙绿
    【题解】「NOIP2024模拟赛24T3」钙绿https://www.becoder.com.cn/contest/5715/problem/3\(\mathcal{Description}\)给定\(n,p,m\)。对于每个\(k=0,1,\dots,m\),统计满足下面条件的\(n\)位\(10\)进制数:(允许前导零各位数之和不超过\(k\)。\(p\)能整除这个数。数据......
  • [USACO23FEB] Problem Setting P 题解
    [USACO23FEB]ProblemSettingP题目说的很绕,意思就是所有验题人都认为题目难度顺序单增。发现\(m\)很小,很容易想到状压。把H看作\(\tt1\),E看作\(\tt0\),则我们得到\(m\)个长度为\(n\)的\(\tt01\)串,这就是每道题的“状态”。发现状态相同的题没有本质区别,所以我们......
  • P11253 [GDKOI2023 普及组] 小学生数学题 题解
    题目传送门前置知识积性函数|乘法逆元解法观察到\(f(i)=\frac{1}{i^{k}}\bmodp\)是完全积性函数,线性筛预处理即可。需要适当的取模优化。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#definesortstab......