Codeforces Global Round 3(A-D)

我凉了。。感觉自己啥都不会做，搞不好起床就绿了啊

代码和反思起床补，今天要反了个大思的

A. Another One Bites The Dust

把所有的ab排在一起然后两边叉a和b

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<stdlib.h>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int main(){

    ll a, b,c;

    scanf("%lld %lld %lld", &a, &b, &c);

    ll ans = c*2ll;

    ll tmp = min(a,b);

    ans+=tmp*;

    a-=tmp;b-=tmp;

    if(a>||b>)ans++;

    printf("%lld",ans);

    return ;

}

B. Born This Way

题意：有n个从A到B的航班，m个从B到C的航班，要你删除k个使得到达C的最晚，求最晚时间

思路：删除的方式一定是前i个从A到B的，和k-i个最早从A到B之后能乘坐的B到C的航班。由于对于每个i，这个方案是惟一的，枚举即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<stdlib.h>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 3e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

ll a[maxn],b[maxn];

ll n,m,ta,tb,k;

ll mi[maxn],mx[maxn];

int main(){

    scanf("%lld %lld %lld %lld %lld",&n, &m,&ta,&tb,&k);

    for(int i = ; i <= n; i++){

        scanf("%lld", &a[i]);a[i]+=ta;

    }

    for(int i = ; i <= m; i++){

        scanf("%lld", &b[i]);

    }ll res = -;

    if(k>=n||k>=m)return printf("-1"),;

    for(int i = ; i <= k; i++){

        int t = k-i;

        int p = lower_bound(b+,b++m,a[i+])-b;

        p+=t;

        if(p>m)return printf("-1"),;

        else res = max(res, b[p]+tb);

    }printf("%lld", res);

    return ;

}

C. Crazy Diamond

题意：给你一个1-n的排列，每次选择两个位置i,j交换位置上的值，且满足2*|i-j|>=n，让你输出具体方案，使得operation不超过5n。

思路：根据限制条件，发现位置1和n合起来可以调动整个数组，而n/2和n/2+1位置只能分别和n和1交换，所以可以从中间开始向两边分别填充，操作不超过3n

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int n;

int a[maxn];

int id[maxn];

vector<PI>v;

void swp(int x, int y){

    if(x==y)return;

    int i = a[x];

    int j = a[y];

    swap(a[x],a[y]);

    swap(id[i],id[j]);

    v.pb({x,y});

}

int main() {

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        scanf("%d", &a[i]);

        id[a[i]]=i;

    }

    for(int i = n/; i >= ; i--){

        int j = n-i+;

        if(id[i]!=i){

            if(id[i]<n/){

                swp(n,id[i]);

            }

            else{

                swp(,id[i]);

                swp(n,);

            }

            swp(id[i],i);

        }

        if(id[j]!=j){

            if(id[j]>n/){

                swp(,id[j]);

            }

            else{

                swp(n,id[j]);

                swp(n,);

            }

            swp(id[j],j);

        }

    }

    //for(int i = 1; i <= n; i++)printf("%d ",a[i]);printf("\n");

    printf("%d\n",v.size());

    for(int i = ; i < (int)v.size(); i++){

        printf("%d %d\n",v[i].fst,v[i].sc);

    }

    return ;

}

D. Dirty Deeds Done Dirt Cheap

题意：给你n个pair，让你取出其中一些排列，使得他们排成一行的数x1>x2<x3>x4<x5...或x1<x2>x3<x4>x5...，问这样排列最长的方案

思路：我好弱智啊。。对于pair内不等号方向相同的分别考虑，比如在每个pair都是x<y的时候，对ans中两个相邻的pair，都有x1<y1>x2<y2。因为y1>x1，所以我们让x1>x2就可以满足y1>x2，所以对该类所有pair排序即可，答案为倒序输出。。。同样地，对x>y的时候只需要排序后正序输出。。把这两种size大的输出即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<stdlib.h>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 3e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

struct Node{

    int x, y;

    int id;

}node[maxn];vector<Node>a,b;

bool cmp(Node a, Node b){

    if(a.x==b.x)return a.y<b.y;

    return a.x<b.x;

}

int main(){

    int n;

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        node[i].id=i;

        scanf("%d %d" ,&node[i].x, &node[i].y);

        if(node[i].x<node[i].y)a.pb(node[i]);

        else b.pb(node[i]);

    }

    printf("%d\n",max(a.size(), b.size()));

    sort(a.begin(),a.end(),cmp);

    sort(b.begin(),b.end(),cmp);

    if(a.size()>b.size()){

        for(int i = a.size()-; i>=; i--){

            printf("%d ",a[i].id);

        }

    }

    else{

        for(int i = ; i < b.size(); i++)printf("%d ",b[i].id);

    }

    return ;

}

巴特西

Codeforces Global Round 3(A-D)

最新文章

热门文章