Codeforces Global Round 3

Codeforces Global Round 3

B - Born This Way

首先二分从B到C坐的是哪个航班，然后枚举从A到B坐的是哪个航班即可。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,m,k;
ll a[Maxn],b[Maxn],ta,tb;

bool check(int x) {
    int temp=1;
    if(n<=k||m<=k) return true;
    for(int i=1;i<=n;i++) {
        while(b[temp]<a[i]+ta&&temp<x) temp++;
        if(i-1+x-temp<=k) return true;
    }
    return false;
}

int main() {
//  freopen("test.in","r",stdin);
    read(n,m);
    read(ta,tb,k);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=m;i++) read(b[i]);
    b[m+1]=(ll)inf<<2ll;
    if(check(m+1)) {
        puts("-1");
    }
    else {
        int l=1,r=m,mid=l+r>>1,ans;
        while(l<=r) {
            if(check(mid)) {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
            mid=l+r>>1;
        }
        printf("%I64d\n",b[ans]+tb);
    }
    return 0;
}

C - Crazy Diamond

首先考虑2到n-1中的每一个数，如果这个数应该放在左半边，那么可以考虑把这个数从当前位置移动到n，然后移动到应该放的位置。而移动到n的时候如果这个数是在左半边，就直接移动，否则先移动到1再移动到n。右半边同理。最后特判一下1和n即可。移动的次数为3n。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,p[Maxn],b[Maxn],tot;
pir ans[Maxn];

void work(int x,int y) {
    ans[++tot]=mp(x,y);
    b[p[x]]=y;
    b[p[y]]=x;
    swap(p[x],p[y]);
}

int main() {
//  freopen("test.in","r",stdin);
    read(n);
    for(int i=1;i<=n;i++) read(p[i]),b[p[i]]=i;
    for(int i=2;i<=n/2;i++) {
        if(p[i]==i) continue;
        if(b[i]<=n/2) {
            work(b[i],n);
            work(n,i);
        }
        else {
            work(b[i],1);
            work(1,n);
            work(n,i);
        }
    }
    for(int i=n/2+1;i<n;i++) {
        if(p[i]==i) continue;
        if(b[i]>n/2) {
            work(b[i],1);
            work(1,i);
        }
        else {
            work(b[i],n);
            work(1,n);
            work(1,i);
        }
    }
    if(p[1]!=1) work(1,n);
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++)
        printf("%d %d\n",ans[i].fr,ans[i].sc);
    return 0;
}

D - Dirty Deeds Done Dirt Cheap

有两种类型的数列，第一种是第一个数比第二个数大，而第二种是第一个数比第二个数小。

那么如果\(a_i<b_i\)，这对数一定要放在第二种，否则放在第一种。

考虑第一种数列，要让数列形成波浪形，就要满足\(b_{i-1}<a_i\)，又因为\(b_{i-1}<a_{i-1}\)，所以只要按照a从小到大排序即可。对于第二种数列同理。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,a[Maxn],b[Maxn],tot,cnt;
pir c[Maxn],d[Maxn];

int main() {
//  freopen("test.in","r",stdin);
    read(n);
    for(int i=1;i<=n;i++) {
        read(a[i],b[i]);
        if(a[i]<=b[i]) c[++tot]=mp(a[i],i);
        else d[++cnt]=mp(a[i],i);
    }
    if(tot>cnt) {
        printf("%d\n",tot);
        rsort(c+1,c+tot+1);
        for(int i=1;i<=tot;i++) printf("%d ",c[i].sc);
    }
    else {
        printf("%d\n",cnt);
        sort(d+1,d+cnt+1);
        for(int i=1;i<=cnt;i++) printf("%d ",d[i].sc);
    }
    return 0;
}

E - Earth Wind and Fire

首先石子的相对顺序是不会改变的，因为如果一个石子在移动的过程中跨过了另一个石子，那么只需要把这个石子移动到那个石子上，然后移动那个石子即可。

这样，对于每一个石子，就确定下来最终要移动到哪个位置，记向右走为正，向左走为负，对偏移量做一个类似括号序列的东西即可。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define pir pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fr first
#define sc second
#define rsort(x,y) sort(x,y),reverse(x,y)
#define vic vector<int>
#define vit vic::iterator
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,top,s[Maxn],tot;
ll a[Maxn],b[Maxn];
pair<ll,int> p[Maxn];
pair<pir,ll> ans[Maxn];

void add(int x,int y,int z) {
    ans[++tot]=mp(mp(x,y),z);
}

int main() {
//  freopen("test.in","r",stdin);
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),p[i]=mp(a[i],i);
    for(int i=1;i<=n;i++) read(b[i]);
    sort(p+1,p+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++) a[i]=b[i]-p[i].fr;
    ll temp=0;
    for(int i=1;i<=n;i++) temp+=a[i];
    if(temp) return 0*puts("NO");
    for(int i=1;i<=n;i++) {
        if(a[i]<0) {
            while(top) {
                int temp=min(-a[i],a[s[top]]);
                if(!temp) {
                    top--;
                    continue;
                }
                add(p[s[top]].sc,p[i].sc,min(-a[i],a[s[top]]));
                a[i]+=temp;
                a[s[top]]-=temp;
                if(a[i]==0) break;
            }
            if(a[i]<0) return 0*puts("NO");
        }
        else s[++top]=i;
    }
    puts("YES");
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++) {
        printf("%d %d %I64d\n",ans[i].fr.fr,ans[i].fr.sc,ans[i].sc);
    }
    return 0;
}

Codeforces Global Round 3

原文：https://www.cnblogs.com/shanxieng/p/11084758.html