Codeforces Round #492 (Div. 2) [Thanks, uDebug!]

这次的题好奇怪哦。。。

思路：先把跟停车位相邻的车停进去，然后开始转圈。。。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = ;

const int M = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

int a[][N], n, k;

vector<int> ans[];

pii getPos(int id) {

    if (id < n) return mk(, id);

    else return mk(,  * n -  - id);

}

void add(int x, int y, int z) {

    ans[].push_back(x);

    ans[].push_back(y);

    ans[].push_back(z);

}

int main() {

    scanf("%d%d", &n, &k);

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

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

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

        }

    }

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

        if(a[][j] == ) continue;

        if(a[][j] == a[][j]) {

            add(a[][j], , j);

            k--;

            a[][j] = ;

        }

    }

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

        if(a[][j] == ) continue;

        if(a[][j] == a[][j]) {

            add(a[][j], , j);

            k--;

            a[][j] = ;

        }

    }

    if(k ==  * n) {

        puts("-1");

        return ;

    }

    while(k > ) {

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

            pii u = getPos(i);

            if(a[u.first][u.second] == ) continue;

            if(a[u.first ^ ][u.second] == a[u.first][u.second]) {

                add(a[u.first][u.second], u.first ^ , u.second);

                k--;

                a[u.first][u.second] = ;

                continue;

            }

            pii v = getPos((i +  * n - ) % ( * n));

            if(a[v.first][v.second] != ) continue;

            add(a[u.first][u.second], v.first, v.second);

            swap(a[u.first][u.second], a[v.first][v.second]);

        }

    }

    printf("%d\n", ans[].size());

    for(int i = ; i < ans[].size(); i++) {

        printf("%d %d %d\n", ans[][i], ans[][i] + , ans[][i] + );

    }

    return ;

}

E：

题目大意：给你n个长度小于1e6的向量，让你把每个向量变成正向或者负向，使得所有向量加起来的长度不超过1.5 * 1e6

思路：正解是每三个向量中都能找到两个向量合起来 <= 1e6，然后不断合并，最后只会剩下一个或者两个向量，

如果一个向量肯定 <= 1e6，如果是两个向量一定 <= 1.5 * 1e6。。。

但是可以用随机洗牌的方法去贪心，因为能卡掉的数据特别不好造。。。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e5 + ;

const int M = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

int n, ans[N], id[N];

LL base = 1500000ll * ;

struct Vector {

    Vector(LL x = , LL y = ) {

        this->x = x;

        this->y = y;

    }

    Vector operator + (const Vector &rhs) const {

        return Vector(x + rhs.x, y + rhs.y);

    }

    Vector operator - (const Vector &rhs) const {

        return Vector(x - rhs.x, y - rhs.y);

    }

    LL len() {

        return x * x + y * y;

    }

    LL x, y, id;

}a[N];

int main(){

    scanf("%d", &n);

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

        scanf("%lld%lld", &a[i].x, &a[i].y);

        id[i] = i;

    }

    while() {

        random_shuffle(id + , id + n);

        Vector now;

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

            int pos = id[i];

            Vector nx1 = now + a[pos];

            Vector nx2 = now - a[pos];

            if(nx1.len() <= nx2.len()) {

                now = nx1;

                ans[pos] = ;

            } else {

                now = nx2;

                ans[pos] = -;

            }

        }

        if(now.len() <= base) {

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

                printf("%d ", ans[i]);

            }

            puts("");

            return ;

        }

    }

    return ;

}

/*

*/

巴特西

Codeforces Round #492 (Div. 2) [Thanks, uDebug!]

最新文章

热门文章