组织选拔赛题解
2024-05-03 13:20:29
发布于:浙江
第一届三体组织ACGO分部组织选拔赛已结束,虽然好像没什么人参加吧,但介于对参加者的尊重,还是把题解交了吧,况且都是版子题,有点参考价值:
T1:橡皮去魔都(Travel)
应该很容易发现是A46.公交换乘改的吧,这里只要把40改60就可以AC了,但数据有误,导致没法AK这个比赛,我对此感到深深抱歉
#include<bits/stdc++.h>
using namespace std;
struct Node {
int t, p;
bool used = 0;
} a[100005];
int n, ans = 0, l = 0;
int main() {
cin>>n;
for (;n--;) {
int g, p, t, k;
cin>>g>>p>>t;
if (!g)ans += p, a[++l].t = t, a[l].p = p;
else {
k = 0;
for (int i = l; i && t - a[i].t <= 60; i--)
if (!a[i].used && a[i].p >= p)k = i;
if (!k)ans += p;
else a[k].used = 1;
}
}
cout<<ans<<endl;
}
T2找橡皮(Where)
一道标准的二分查找,虽然我自己WA了4遍,连排序都排好了,直接上代码:
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[n + 1] = {0};
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
int s;
cin >> s;
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] >= s) r = mid;
if (a[mid] < s) l = mid + 1;
}
if (a[l] == s) cout << l << endl;
else cout << "-1" << endl;
return 0;
}
T3橡皮找徭役(Find)
又是一道版子题,dfs或bfs暴力就行,真没啥好说的,现给出dfs版:
#include<bits/stdc++.h>
using namespace std;
char a[1000][1000];
int minn = INT_MAX;
int sum = 0;
int a1,a2,b1,b2;
int flag = 0;
int nextt[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, s1, s2,dis[50][50];
void f(int i, int j, int sum) {
dis[i][j]=sum;
for (int n = 0; n < 4; n++) {
int dx = i + nextt[n][0], dy = j + nextt[n][1];
if (dx >= 1 && dx <= s1 && dy >= 1 && dy <= s2 &&(a[dx][dy] == '.'||a[dx][dy]=='*') &&sum+1<dis[dx][dy]) {
f(dx, dy, sum + 1);
}
}
}
int main() {
cin >> s1 >> s2;
for (int i = 1; i <= s1; i++) {
for (int j = 1; j <= s2; j++) {
cin >> a[i][j];
dis[i][j]=INT_MAX;
if(a[i][j]=='@'){
a1=i;
a2=j;
}
if(a[i][j]=='*'){
b1=i;
b2=j;
}
}
}
f(a1, a2, 1);
if(dis[b1][b2]!=INT_MAX){
cout << dis[b1][b2]-1 << endl;
}
else{
cout<<"-1"<<endl;
}
return 0;
}
T4 帮派点人(Count)
第3道版子(橡皮4道题3道板子,脸都不要了),标准并查集
#include <iostream>
using namespace std;
int f[999999];
int find(int x){
if(f[x]!=x){
f[x]=find(f[x]);
}
return f[x];
}//查找
void add(int x,int y){
int a=find(x),b=find(y);
f[a]=b;
}//合并
int main(){
int n,m,p,a,b;
cin>>n>>m>>p;
for(int i=0;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++){
cin>>a>>b;
add(a,b);
}
while(p--){
cin>>a>>b;
if(find(a)==find(b))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
四道题题解结束,开始推销时间:
三体组织ACGO分部组织
新一届比赛,邀请码KGPj
这里空空如也
有帮助,赞一个