Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) 题解
分类:
IT文章
•
2025-01-15 16:44:31
Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2)
题目链接：https://codeforces.com/contest/1130
A. Be Positive
题意：
给出n个数，看是否正数的个数过半或者负数的个数过半。
题解：
水题，代码如下：
![]()
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n;
double a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
int cnt1 = 0,cnt2=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>0) cnt1++;
else if(a[i]<0) cnt2++;
}
if(cnt1>=(n+1)/2) cout<<1;
else if(cnt2>=(n+1)/2) cout<<-1;
else cout<<0;
return 0;
}
View Code
B. Two Cakes
题意：
给出2*n个商店，每个商店有其序号1,2...n，每个序号两个商店共有。现在有两个人想要买东西，但只能按照序号来买，从1买到n。
他们一开始的位置在最左边，问移动的距离总和最小是多少。
题解：
记录一下序号和位置，然后贪心就行了。
具体见代码吧：
![]()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n;
struct Node{
int val,id;
bool operator < (const Node &A)const{
return val<A.val;
}
}a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
for(int i=1;i<=2*n;i++){
cin>>a[i].val;
a[i].id=i;
}
sort(a+1,a+2*n+1);
ll ans = 0;
ans+=a[1].id+a[2].id-2;
for(int i=3;i<=2*n;i+=2){
ans+=min(abs(a[i].id-a[i-1].id)+abs(a[i+1].id-a[i-2].id),abs(a[i].id-a[i-2].id)+abs(a[i+1].id-a[i-1].id));
}
cout<<ans;
return 0;
}
View Code
给出n*n的矩阵、起点以及终点，每个格子有0或者1，0代表陆地，1代表水。现在有个人想从起点走到终点，但他不能沾水。现在你可以修最多一条管道，连接两块陆地，费用为相应两点间距离的平方。问最终最小的费用为多少。
![]()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int n,cnt;
int r1,c1,r2,c2;
char mp[N][N];
int vis[N][N],bel[N][N];
struct Node{
int x,y;
};
int dx[5]={-1,1,0,0},dy[5]={0,0,-1,1};
bool ok(int x,int y){
return x>=1&&y>=1&&x<=n&&y<=n&&mp[x][y]=='0'&&!vis[x][y];
}
void bfs(int x,int y,int t){
queue <Node> q;
q.push(Node{x,y});
vis[x][y]=1;
while(!q.empty()){
Node now=q.front();q.pop();
int x=now.x,y=now.y;
bel[x][y]=t;
for(int i=0;i<4;i++){
int curx=x+dx[i],cury=y+dy[i];
if(ok(curx,cury)){
vis[curx][cury]=1;
q.push(Node{curx,cury});
}
}
}
}
int dis(int x1,int y1,int x2,int y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main(){
cin>>n>>r1>>c1>>r2>>c2;
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]=='0'&&!vis[i][j]){
bfs(i,j,++cnt);
}
}
}
int block1=bel[r1][c1],block2=bel[r2][c2];
if(block1==block2){
cout<<0;
return 0;
}
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]=='1') continue ;
if(bel[i][j]==block1){
for(int p=1;p<=n;p++){
for(int q=1;q<=n;q++){
if(mp[p][q]=='1') continue ;
if(bel[p][q]==block2){
ans=min(ans,dis(i,j,p,q));
}
}
}
}
}
}
cout<<ans;
return 0;
}
