专栏文章

【M Contect-Div.3】#5 题解

mmengnn
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minipanr
此快照首次捕获于
2025/12/02 03:03
3 个月前
此快照最后确认于
2025/12/02 03:03
3 个月前
查看原文
本帖由 mengnn 编写，若有疏漏感谢指出。
本帖 2025.10.24 完工。

A. Wind-Money 题解

题面及思路

太简单了，这题没做对的不应该。
按照题面读入 a,b,c,da,b,c,d，然后直接计算即可（注意 a / b的格式），公式：
ab+cd=a×d+b×cb×d\frac{a}{b}+\frac{c}{d}=\frac{a\times d+b\times c}{b\times d}
最后化简，需要保分子和分母互质：
a×d+b×cb×d=g×pg×q=pq\frac{a\times d+b\times c}{b\times d}=\frac{g\times p}{g\times q}=\frac{p}{q}
我们用 gg 表示原分子与原分母的最大公约数，pp 和 qq 表示最终最简分数的分子和分母。易知，此时 pp 与 qq 互质。
注意：十年 OI 一场空，不开____见祖宗。
观察到 1≤a,b,c,d≤1091\le a,b,c,d\le10^9，所以我们在计算分子/母，的时候会爆 int，开 long long 可以解决此问题。

时间复杂度

因为我们要求 gcd，所以最终复杂度 O(log⁡2n)O(\log_2 n)。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d;
char ch;
int main(){
	cin>>a>>ch>>b>>c>>ch>>d;
	long long x=a*d+b*c;
	long long y=b*d;
	cout<<(x/__gcd(x,y))<<" / "<<(y/__gcd(x,y));//直接使用 C++ 内置 gcd 函数
	return 0;
}
代码来自 mengnn。

B. Wind-Baptism 题解

题面及思路

思路可太好想了，我们可以通过计算来直接求解。
首先，求 11 到 nn 的和直接用等差数列求和公式：
∑i=1ni=n×(n+1)2\sum_{i=1}^{n}i=\frac{n\times(n+1)}{2}
接下来，我们再统计次幂和，根据次幂求和公式：
∑i=1n2i=2n+1−1\sum_{i=1}^{n}2^i=2^{n+1}-1
变形得：
∑i=1⌊log⁡2n⌋2i=2⌊log⁡2n⌋+1−1\sum_{i=1}^{\lfloor \log_2 n\rfloor}2^i=2^{\lfloor \log_2 n\rfloor+1}-1
所求的原式为：
∑i=1ni−2∑i=1⌊log⁡2n⌋2i\sum_{i=1}^{n}i-2\sum_{i=1}^{\lfloor \log_2 n\rfloor}2^i
将公式代入：
∑i=1ni−2∑i=1⌊log⁡2n⌋2i=n×(n+1)2−2×(2⌊log⁡2n⌋+1−1)\sum_{i=1}^{n}i-2\sum_{i=1}^{\lfloor \log_2 n\rfloor}2^i=\frac{n\times(n+1)}{2}-2\times(2^{\lfloor \log_2 n\rfloor+1}-1)
其中的 log⁡2n\log_2 n 需要用 log2(n) 函数来求解
注意：十年 OI 一场空，不开____见祖宗。
观察到 1≤n≤1091\le n\le10^9，所以我们在计算时会爆 int，开 long long 可以解决此问题。

时间复杂度

由于我们直接取的公式，单次计算复杂度均为 O(1)O(1)。
数据组数为 TT，则总复杂度为 O(T)O(T)。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
int main(){
	cin>>T;
	while (T--){
		cin>>n;
		cout<<(n*(n+1)>>1)-(((1<<((long long)log2(n)+1))-1)<<1)<<'\n';
        //代码中我们用 <<1 和 >>1 作为 *2 和 /2
	}
	return 0;
}
代码来自 mengnn。

C. Wind-Trader 题解

题面及思路

题面写的很丑，zxz 改了之后也很难看。
第一眼看题，很像图论算法，但实则不然。
知道了我们只能将点 00 与其余两个点连接后，不难想到枚举这两个点。
首先对于 mm 次寄存，我们可以统计一下每个点的贡献，分为 44 种情况（设寄存关系的两点为 aa 与 bb，其中 a≤ba\le b）。
  1. 旅行者 aa 和 bb 都认识，那答案加 11，贡献为 00；
  2. 旅行者只认识 aa，则对于连接 bb 的贡献加 11；
  3. 旅行者只认识 bb，则对于连接 aa 的贡献加 11；
  4. 旅行者对于 aa 和 bb 都不认识，则连接 aa 和 bb 的共同贡献加 11。
注意：aa 与 bb 可能相等，若 a>ba>b 则直接交换即可。
部分代码：
CPP
if (a>b) swap(a,b);
if (f[a]&&f[b]) ++ans1,++ans2;
else if (f[a]) ++t[b];
else if (f[b]) ++t[a];
else if (a==b) ++t[a];
else ++mp[{a,b}];
最后统计答案也分类讨论：
  1. 连接的是两个有关联的点，直接计算两个单点贡献加上连边贡献：
CPP
for (auto i:mp){
    int x=i.first.first,y=i.first.second,z=i.second;
    ans2=max(ans2,ans1+t[x]+t[y]+z);
}
  1. 连接的是两个无关的点，直接计算两个单点的贡献（直接取最大值与次大值，贡献最大）：
CPP
sort(t+1,t+k+1,greater<int>());
ans2=max(ans2,ans1+t[1]+t[2]);
于是你就轻松通过了本题（简单）！

时间复杂度

我们需要进行 map<pair<int,int>,int> 来存储边，且统计时我们还需进行排序，所以单次复杂度 O(log⁡2n)O(\log_2 n)。
因为我们的算法基底复杂度为 O(n)O(n)，故总时间复杂度为 O(nlog⁡2n)O(n\log_2n)。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,m,k,t[N];
bool f[N];
template<typename T>inline void rd(T &x){
	x=0;char ch;
	bool f=false;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
		if (ch=='-')
			f=true;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
	if (f) x=-x;
}
template<typename T>inline void wr(T x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) wr(x/10);
	putchar(x%10+'0');
	return ;
}
int main(){
	rd(T);
	while (T--){
		rd(n),rd(m),rd(k);
		for (int i=1;i<=k;i++) t[i]=f[i]=0;
		for (int i=1,x;i<=n;i++) cin>>x,f[x]=true;
		int ans1=0,ans2=0;
		map<pair<int,int>,int> mp;
		for (int a,b,i=1;i<=m;i++){
			rd(a),rd(b);
			if (a>b) swap(a,b);
			if (f[a]&&f[b]) ++ans1,++ans2;
			else if (f[a]) ++t[b];
			else if (f[b]) ++t[a];
			else if (a==b) ++t[a];
			else ++mp[{a,b}];
		}
		for (auto i:mp){
			int x=i.first.first,y=i.first.second,z=i.second;
			ans2=max(ans2,ans1+t[x]+t[y]+z);
		}
		sort(t+1,t+k+1,greater<int>());
		ans2=max(ans2,ans1+t[1]+t[2]);
		wr(ans2),putchar('\n');
	}
	return 0;
}
代码来自 mengnn。

D. Wind-Ball 题解

题面及思路

我们设 kk 为小球跳跃能力。若 kk 无法完成任务则 k−1k - 1 亦无法完成；若 kk 可以完成任务则 k+1k + 1 亦可以完成。故答案具有单调性，考虑二分答案。
小球做 xx 组折返，所以一个点要经过 2x2x 次。而当跳跃能力为 kk 时，我们一次最多跳 kk 长度，所以可以发现每个长度为 kk 的区间，浮冰承受力总和不得小于 2x2x。我们依据这点来写 check() 函数。
我们在读入之后，将能力进行排序，在排序后的数组中查找能满足条件的最小值，若能查到输出编号；当 l=n+1l=n+1 时，则无解。
若仍不懂见 P8775 青蛙过河。

时间复杂度

二分答案和排序时间复杂度均为 O(nlog⁡2n)O(n\log_2n)，很好理解，不做解释。

AC Code:

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 20;
int n,k,a[N],s[N],m;
struct node{
	int w,id;
}p[N];
inline bool cmp(node a,node b){
	return a.w != b.w ? a.w < b.w : a.id < b.id;
}
inline bool check(int mid){
	for ( int i = mid; i <= m; i ++){
		if (s[i] - s[i - mid] < 2 * k) return false;
	}
	
	return true;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for ( int i = 1; i <= n; i ++){
		cin >> p[i].w;
		p[i].id = i;
	}
	for ( int i = 1; i <= m; i ++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	int l = 1,r = 1e9,mid;
	while (l <= r){
		mid = (l + r) >> 1;
		if (check(mid)){
			r = mid - 1;
		} 
		else l = mid + 1;
	} 
	int ans = r + 1;
	sort(p + 1,p + n + 1,cmp);
	l = 1,r = n;
	while (l <= r){
		mid = l + r >> 1;
		if (p[mid].w >= ans){
			r = mid - 1;
		}else l = mid + 1;
	}
	if (l == n + 1) cout << "Sorry";
	else cout << p[r + 1].id;
	return 0;
}
代码来自 Realize_Goal。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...