当前位置：首页 > web >正文

AtCoder Beginner Contest 409（ABCDEF）

web 2025/6/23 19:04:43

A - Conflict

翻译：

        共有 N 个物品。你被给定长度为 N 的字符串 T 和 A，分别表示 Takahashi 和 Aoki 想要的物品。设 T_i 和 A_i 分别表示 T 和 A 的第 i 个（1≤i≤N）字符。

        当 T_i 为 o 时，Takahashi 想要第 i 个物品；当 T_i 为 x 时，Takahashi 不想要第 i 个物品。同样地，当 A_i 为 o 时，Aoki 想要第 i 个物品；当 A_i 为 x 时，Aoki 不想要第 i 个物品。

        判断是否存在一个物品是他们都想要的。

思路：

一一对比字符串TA即可。(模拟)

时间复杂度：O(N)

空间复杂度：O(1)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;cin>>n;string a,b;cin>>a>>b;for (int i=0;i<n;i++){if (a[i]=='o' && b[i]=='o'){cout<<"Yes"<<endl;return;}}cout<<"No"<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;
//    cin>>t;while (t--) solve();return 0;
}

B - Citation

翻译：

给定一个长度为 N 的非负整数序列 $A=(A_1,A_2,...,A_N)$ 。求满足以下条件的最大非负整数 x：

在序列 A 中，大于或等于 x 的元素至少出现 x 次（包括重复项）。

思路：

二分答案，遍历答案，通过二分遍历答案是否正确。（二分答案）

时间复杂度：O(NlogN)

空间复杂度：O(1)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;cin>>n;vector<int> a(n);for (int &i:a)cin>>i;sort(a.begin(),a.end());int l=-1,r=1e9+1;while (l+1!=r){int mid = (l+r)/2;int now = lower_bound(a.begin(),a.end(),mid)-a.begin();if (n-now>=mid) l = mid;else r = mid;}cout<<l<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;
//    cin>>t;while (t--) solve();return 0;
}

C - Equilateral Triangle

翻译：

有一个周长为 L 的圆，圆上分布着 1, 2, …, N 个点。对于 i = 1, 2, …, N − 1，点 i+1 位于圆上距离点 i 顺时针方向 d 位的位置。

求满足以下两个条件的整数三元组 (a,b,c) (1≤a<b<c≤N) 的个数：

三个点 a, b 和 c 均位于不同位置。
以三个点 a, b 和 c 为顶点的三角形为等边三角形。

思路：

等边三角形，两两顶点间的距离相同，对应在圆上也一样。(组合，模拟)

时间复杂度：O(N)

空间复杂度：O(1)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll n,l;cin>>n>>l;vector<ll> cnt(l+1,0);cnt[0] = 1;for (ll now=0,d,i=1;i<n;i++){cin>>d;now = (now+d)%l;cnt[now]++;}if (l%3){cout<<0<<endl;return;}ll ans = 0;for (ll i=0;i<l/3;i++){ans+=cnt[i]*cnt[(i+l/3)%l]*cnt[(l+i-l/3)%l];}cout<<ans<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();ll t=1;
//    cin>>t;while (t--) solve();return 0;
}

D - String Rotation

翻译：

        你被给定一个长度为 N 的字符串 $S=S_1S_2...S_N$ ，其中包含小写英文字母。你将对 S 执行以下操作，且仅执行一次：

选择S中长度不小于1的连续子串，并将其向左循环移动1位。即，选择1≤ℓ≤r≤N的整数，将S ℓ插入到S的第r个字符右侧，然后删除S的第ℓ个字符。

        在所有可能的操作结果中，找出字典序最小的字符串。

        你将得到 T 个测试案例，请分别解决它们。

思路：

找到右边比当前大的，同时考虑到换过去后是否比其后面的小，如果其后面的不大于换过去的，则应该继续向后推。（贪心）

时间复杂度：O(N)

空间复杂度：O(1)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;cin>>n;string s;cin>>s;for (int i=0;i<n-1;i++){// 递减,可相同if (s[i]>s[i+1]){int r = i+1;while (r+1<n && s[r+1]<=s[i]) r++;// 旋转for (int j=0;j<i;j++) cout<<s[j];for (int j=i+1;j<=r;j++) cout<<s[j];cout<<s[i];for (int j=r+1;j<n;j++) cout<<s[j];cout<<"\n";return;}}cout<<s<<"\n";
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();ll t=1;cin>>t;while (t--) solve();return 0;
}

E - Pair Annihilation

翻译：

        你被给定一棵具有 N 个顶点的树。顶点编号为 1, 2, …, N，边编号为 1, 2, …, N−1。边 j 双向连接顶点 u j 和 v j，并具有权重 w j。此外，每个顶点i被赋予一个整数x_i。若x_i > 0，则在顶点i放置x_i个正电子；若x_i < 0，则在顶点i放置−x_i个电子；若x_i = 0，则顶点i不放置任何粒子。这里保证 $\sum\limits^N_{i=1}x_i=0$ 。

        沿边j移动一个正电子或电子需要消耗能量w_j。此外，当正电子和电子位于同一顶点时，它们会以相等数量相互湮灭。

        求湮灭所有正电子和电子所需的最小能量。

思路：

令点1为根节点，从叶节点开始所有电子向根节点移动即可。（贪心，dfs）

时间复杂度：O(N)

空间复杂度：O(1)

实现：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll MAXN = 1e5 + 5;
vector<pair<ll, ll>> tree[MAXN]; 
ll x[MAXN];
ll ans = 0;ll dfs(ll u, ll parent) {ll charge = x[u]; // 当前节点的净电荷for (auto& [v, w] : tree[u]) {if (v == parent) continue;ll child_charge = dfs(v, u);ans += abs(child_charge) * w;charge += child_charge;}return charge;
}int main() {// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();ll n;cin >> n;for (ll i = 1; i <= n; ++i) cin >> x[i];for (ll i = 0; i < n - 1; ++i) {ll u, v, w;cin >> u >> v >> w;tree[u].emplace_back(v, w);tree[v].emplace_back(u, w);}dfs(1, 0); cout << ans << "\n";return 0;
}

F - Connecting Points

翻译：

        存在一个图G，其包含N个顶点和0条边，位于二维平面上。顶点从1到N依次编号，顶点i位于坐标 $(x_i,y_i)$ 处。

        对于图G中的顶点u和v，顶点u和v之间的距离d(u,v)定义为曼哈顿距离，即 $d(u,v)=|x_u-x_v|+|y_u-y_v|$ 。

        此外，对于图 G 的两个连通分量 A 和 B，令 V(A) 和 V(B) 分别表示 A 和 B 的顶点集。顶点 A 和 B 之间的距离 d(A,B) 定义为 d(A,B)=min{d(u,v)∣u∈V(A),v∈V(B)}。

        处理 Q 个查询，具体如下。每个查询属于以下三种类型之一：

1 a b ：设 n 为 G 中顶点的数量。将顶点 n+1 添加到 G 中，其坐标为 (x n+1,y n+1 )=(a,b)。
2：设 n 为图 G 中顶点的数量，m 为连通分量数量。
若 m=1，输出 -1。
若 m≥2，合并所有连通分量中距离最小的分量，并输出该最小距离的值。具体而言，设图 G 的连通分量为 $A_1,A_2,...,A_m$ ，且 $k=\min\limits_{1\leq i< j\leq m}d(A_i,A_j)$ 。对于所有不属于同一连通分量的顶点对 (u,v) (1≤u<v≤n) 且满足 d(u,v)=k，在顶点 u 和 v 之间添加一条边。然后输出 k。

3 u v：如果顶点 u 和 v 属于同一连通分量，输出 Yes；否则输出 No。

思路：

要实现查询3，可使用并查集，实现查询1，2，使用小根堆存储每个点之间的距离，即可。（并查集，最小生成树，优先队列）

时间复杂度： $O((n+q)^2log(n+q))$

空间复杂度： $O((n+q)^2)$

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// fa:所属集合，trees: 集合的大小
vector<int> fa,trees;
// 记录每个点
vector<array<int,2>> graph;
// 点x到y的距离,距离小的在前
struct cmp{bool operator()(array<int,3>x,array<int,3>y){return x[0]>y[0];}
};
priority_queue<array<int,3>,vector<array<int,3>>,cmp> pq;
int find(int k){return fa[k]==k ? k :fa[k]=find(fa[k]);}
void merge(int a, int b) {a = find(a);b = find(b);if (a == b) return;if (trees[a] < trees[b]) swap(a, b);fa[b] = a;trees[a] += trees[b];
}
void solve(){int n,q,cnt=0;cin>>n>>q;for (int u,v;cnt<n;cnt++){cin>>u>>v;// 加入优先队列for (int i=0;i<graph.size();i++){pq.push({abs(graph[i][0]-u)+abs(graph[i][1]-v),cnt,i});}graph.push_back({u,v});trees.push_back(1);fa.push_back(cnt);}int f,a,b;while (q--){cin>>f;// 加点if (f==1){cin>>a>>b;// 加入优先队列for (int i=0;i<graph.size();i++){pq.push({abs(graph[i][0]-a)+abs(graph[i][1]-b),cnt,i});}graph.push_back({a,b});trees.push_back(1);fa.push_back(cnt++);// 合并}else if (f==2){// 最小距离int mx = -1;while (!pq.empty()){// 是否同一集合auto [w,u,v] = pq.top();if (find(u)==find(v)) pq.pop();else {// 合并最小的if (mx==-1 || w==mx){mx = w;merge(u,v);pq.pop();}else break;}}cout<<((mx!=-1) ? mx : -1)<<endl;// 判断是否同一集合}else if (f == 3) {cin>>a>>b;a--,b--;cout<<((find(a)==find(b)) ? "Yes" : "No")<<endl;}}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;
//    cin>>t;while (t--) solve();return 0;
}