Codeforces Round #542

Codeforces Round #542

A. Be Positive

题意

给定一个数组$a_1,a_2,…,a_n$,让你到一个数字,是的数组内的所有数字处以这个数字之后,数组内大于0的数字超过$\cfrac{n}{2}$的上界。

题解

由于没有要求整除,所以直接看负数多还是正数多,哪个超过上届,就用$-1或者1$

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 1e3+10;
int a[maxn];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&n);
int cnt1=0,cnt2=0;
rep(i,0,n){
scanf("%d",a+i);
if(a[i]>0) cnt1++;
if(a[i]<0) cnt2++;
}
int ans = 0;
if(n%2) n++;
if(cnt1>=n/2) ans = 1;
if(cnt2>=n/2) ans = -1;
printf("%d",ans);
return 0;
}

B. Two Cakes

题意

两个人要买$n$层蛋糕,他们必须从$1$开始买到$n$,之后给定$2n$个蛋糕店,他们从$1$这个点出发,之后去买蛋糕。其中一旦一个人从一家蛋糕店买了蛋糕,那么另外一个人就不能在那家蛋糕店买蛋糕。问两个人花费的最少步数是多少?

题解

由于每一步只有两种可能,一个人去$x+1$中的一家蛋糕店,另外一个人去另一家。每一步的选择都只有两种,且无后效性。所以我们用贪心来解决。每一步的时候都选择花费步数最少的选择。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
int n;
struct node{
int idx,val;
bool operator<(const node &x){
return val < x.val;
}
}a[maxn<<1];
int vis[maxn*2];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&n);
rep(i,0,2*n){
int x; scanf("%d",&x);
a[i].idx = i+1; a[i].val = x;
}
sort(a,a+2*n);
int cnt = 0;
int now1 = 1, now2 = 1;
ll ans = 0;
for(int i=0;i<2*n;i+=2){
int temp = INF;
int x1 = abs(now1 - a[i].idx) + abs(now2 - a[i+1].idx);
int x2 = abs(now2 - a[i].idx) + abs(now1 - a[i+1].idx);
if(x1>x2){
now2 = a[i].idx;
now1 = a[i+1].idx;
}else{
now1 = a[i].idx;
now2 = a[i+1].idx;
}
ans += 1ll * min(x1,x2);
}
printf("%lld\n",ans);


return 0;
}

C. Connect

题意

Alice要从一个陆地到另外一块陆地,需要建造一座大桥,问桥的花费要最少。

  • 桥的花费是欧几里得距离的平方
  • 只能建造一座桥
  • 可能不需要建造桥

题解

由于只建造一座桥,所以我们可以枚举起始点的陆地和终点的陆地,之后挑选出最近的点。

由于数据小,随便做。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
int stx,sty,edx,edy;
int dir[4][2] = {1,0, -1,0, 0,1, 0,-1};
const int maxn = 100;
int vis[maxn][maxn];
char mx[maxn][maxn];
vector<pII > st;
vector<pII > ed;
void bfs(int x,int y,bool sign){
vis[x][y] = 1;
queue<pair<int,int> >q;
q.push(make_pair(x,y));
while(!q.empty()){
int xx = q.front().first; int yy = q.front().second;
q.pop();
if(sign) st.push_back(make_pair(xx,yy));
else ed.push_back(make_pair(xx,yy));
rep(i,0,4){
int xxx = xx + dir[i][0];
int yyy = yy + dir[i][1];
if(xxx<0 || xxx >=n || yyy<0 || yyy>=n) continue;
if(mx[xxx][yyy] == '1') continue;
if(vis[xxx][yyy]) continue;
vis[xxx][yyy] = 1;
q.push(make_pair(xxx,yyy));
}
}
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%d",&n);
scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
stx--;sty--;edx--;edy--;
rep(i,0,n){
scanf("%s",mx+i);
}
int ans = INF;
bfs(stx,sty,1);
bfs(edx,edy,0);
int len1 = st.size();
int len2 = ed.size();
rep(i,0,len1){
rep(j,0,len2){
int x1 = st[i].first;
int y1 = st[i].second;
int x2 = ed[j].first;
int y2 = ed[j].second;
ans = min(ans,(x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
}
printf("%d\n",ans);
return 0;
}

D2. Toy Train

题意

Alice开火车,他火车的轨道是确定的,之后火车开的方向也是确定的,火车的轨迹是一个圈,轨迹上有很多站点,每个站点上有糖果。

  • 火车在站点上只可以拿起一个糖果
  • 火车在站点上可以放下无限个糖果

目标是将所有站点上的糖果放到指定的站点所花费的时间最小。

题解

由于每一个站点都是独立的。你只需要管他是怎么拿起来的。所以每一个站点如果有$x$个糖果,那么从他开始至少要$x-1$圈加上一个最短的距离。所以我们可以枚举每一个站点所需要的最远距离。

假设从$i$起始点到$j$站点。那么我们开始的距离是$dis(i,j)=(j-i+n)\mod n$。

之后我们需要$x-1$圈。$(x-1)\times n$

之后我们需要从那个点到最近的放置点.$dis(j,z) = (z-j+n)\mod n$

之后两层循环即可。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3+10;
const int maxm = 2e2+10;
int n,m;
vector<int> candys[maxn];
int ans[maxn];
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,0,m){
int x,y;scanf("%d%d",&x,&y);
candys[x-1].push_back(y-1);
}
int mmax = 0;
rep(i,0,n){
mmax = max(mmax,(int)candys[i].size());
}
// ans
rep(i,0,n){
int ans = 0;
rep(j,0,n){
if(candys[j].size()==0)continue;
int temp = (j-i+n)%n;
int tx = INF;
for(auto &x: candys[j]){
tx = min(tx,(x-j+n)%n);
}
ans = max(ans, ((int)candys[j].size()-1)*n + tx + temp);
}
printf("%d ",ans);
}
return 0;
}