Pinely Round 3 (Div. 1 + Div. 2)

发布时间:2023年12月24日

在这里插入图片描述

Pinely Round 3 (Div. 1 + Div. 2)

Pinely Round 3 (Div. 1 + Div. 2)

A. Distinct Buttons

题意:当前处于(0, 0)原点,给出若干个平面坐标轴上的点,是否可以仅选择三个方向便可以到达所有给出的点。

思路:到达单一坐标点最多需要两个方向,记录到达每个点需要的方向,若四个方向都需要用到则不可能仅选择三个方向。

AC code:

void solve(){
    cin >> n;
    int x = 0, y = 0;
    int l = 0, r = 0, u = 0, d = 0;
    for(int i = 0; i < n; i ++){
        int t, v; cin >> t >> v;
        if(t < 0) l ++;
        if(t > 0) r ++;
        if(v > 0) u ++;
        if(v < 0) d ++;
    }
    if(l && r && u && d){
        cout << "NO" << endl;
        return;
    }cout << "YES" << endl;
}

B. Make Almost Equal With Mod

题意:给出一个长度为n的正整数数组a,现在必须选择一个正整数k,然后对于数组a中的每一个数将 a i a_i ai?替换为 a i a_i ai?mod k,该操作有且只有一次,在操作后,数组a中的元素必须有且仅有两个数不同,找出可能的k值。

思路:从二进制低位开始考虑k值,即从2开始考虑, 2的余数只有0或1两种可能,即二进制最低位是否为1,若2取余后均为同一数,说明二进制最低位要么全是0要么全是1,我们开始考虑次低位,以此类推,题目保证一定存在k值,所以从二进制最低位开始遍历。

k最大可能为1e18,则遍历的不会超过60位。

AC code:

void solve(){
    cin >> n;
    int x = 0, y = 0;
    int mn = 1e18;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 1; i <= 1e18; i *= 2){
        map<int, int> mp;
        for(int j = 1; j <= n; j ++)
            mp[a[j] % i] ++;
        if(mp.size() == 2){
            cout << i << endl;
            return;
        }
    }
}

C. Heavy Intervals

题意:给出左区间数组l和右区间数组r以及每个区间的权值数组c,现在需要将l和r进行任意匹配,保证每个区间的r>l,然后将权值数组c与每个区间进行配对,最终每个区间的权值为( r i r_i ri?- l i l_i li?)* c i c_i ci?,现在需要最小化区间权重的总和。

思路:

首先所有区间的差加起来是恒定的,需要去分配这些差在每个区间的大小,然后在将小区间与大权值进行配对,那么现在问题在于如何找到最佳的区间。

这里需要将大区间尽可能的扩大,从而分配给更小的权值,然后相对的令小区间更小,分配给更大的权值,从而最小化区间权值总和。我们还需要保证每个区间都必须符合r>l的必须条件,所以不能盲目的用最大的r去匹配最小的l来最大化区间。

这里可以以右区间r为基准,因为要保证r>l,可以将左区间l排序后找到第一个小于r的数,然后将该数从l区间中删除,两种操作的最佳选择是set中的*prev(s.lower_bound?)(反转lower_bound函数,从寻找大于等于r的第一个元素变为寻找第一个小于r的元素)。

在匹配到每一对合法区间后,可以用pair进行存取,然后根据区间差进行升序排序(当然可以直接存区间差进行排序),然后对权值数组c进行降序排序,一一对应通过( r i r_i ri?- l i l_i li?)* c i c_i ci?得到最后的最小区间权值和。

AC code:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 3e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n;
int l[N], r[N], c[N];
map<int, int> st;

bool cmp(PII a, PII b){
    return a.second - a.first < b.second - b.first;
}

void solve(){
    vector<PII> cnt;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> l[i];
    for(int i = 1; i <= n; i ++) cin >> r[i];
    for(int i = 1; i <= n; i ++) cin >> c[i];

    sort(l + 1, l + n + 1);
    sort(r + 1, r + n + 1);
    sort(c + 1, c + n + 1, greater<int>());

    set<int> s(l + 1, l + n + 1);
    for(int i = 1; i <= n; i ++){
        auto it = prev(s.lower_bound(r[i]));
        cnt.push_back({*it, r[i]});
        s.erase(it);
    }
    sort(cnt.begin(), cnt.end(), cmp);
    int ans = 0, t = 1;
    for(auto [x, y] : cnt){
        ans += (y - x) * c[t ++];
    }
    cout << ans << endl;
}

signed main(){
    fast();
    
    T = 1;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}
文章来源:https://blog.csdn.net/maisui12138/article/details/135184217
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。