Codeforces Round #542

A. Be Positive

题意

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

题解

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

ac代码

#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代码

#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代码

#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代码

#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;
}