526互联

Pinely Round 3 (Div. 1 + Div. 2) A~D

发布时间 2023-12-24 02:19:04作者: -37-

A. Distinct Buttons

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
// #include <map>
// #include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

void solve() {
    int n; cin >> n;
    bool px = 0;
    bool nx = 0;
    bool py = 0;
    bool ny = 0;
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        if (a > 0) px = 1;
        if (a < 0) nx = 1;
        if (b > 0) py = 1;
        if (b < 0) ny = 1;
    }
    if (nx && px && ny && py) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
    return;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. Make Almost Equal With Mod

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
#include <map>
#include <unordered_set>
#include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

void solve() {
    LL n; cin >> n;
    vector<LL> V(n);
    for (auto &a : V) cin >> a;

    if (n == 2) {
        cout << (LL)1e18 << '\n';
        return;
    }

    set<LL> S;
    
    LL i;
    for (i = 2; i < 1e17; ) {
        for (int j = 0; j < n; j++) {
            S.insert(V[j] % i);
            if (S.size() > 2) break;
        }
        if (S.size() == 2) break;
        else S.clear();
        i *= 2;
    }

    cout << i << '\n';
    return;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Heavy Intervals

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
// #include <map>
// #include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

// number - graph ？
// 反推？ 用题目思路证正确性？
void solve() {
    int n; cin >> n;
    vector<LL> l(n), r(n), c(n);
    for (auto &a : l) cin >> a;
    for (auto &a : r) cin >> a;
    for (auto &a : c) cin >> a;

    vector<PII> awa; // 0左边 1右边
    for (int i = 0; i < n; i++) {
        awa.push_back({l[i], 0});
        awa.push_back({r[i], 1});
    }

    sort(awa.begin(), awa.end());

    vector<LL> qwq;
    vector<LL> res;
    for (auto a : awa) {
        if (a.second == 0) {
            qwq.push_back(a.first);
        } else {
            res.push_back(a.first - qwq.back());
            qwq.pop_back();
        }
    }
    sort(res.begin(), res.end());
    sort(c.begin(), c.end(), greater<int>());

    LL ans = 0;
    for (int i = 0; i < n; i++) {
        ans += res[i] * c[i];
    }

    cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D. Split Plus K

想复杂了

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
// #include <map>
// #include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

LL gcd(LL a, LL b){
	return b ? gcd(b, a % b) : a;
}

void solve() {
    LL n, k; cin >> n >> k;
    vector<LL> V(n);
    for (auto &a : V) cin >> a;

    sort(V.begin(), V.end());
    if (V[0] == V[n - 1]) {
        cout << 0 << '\n';
        return;
    }
    if (V[0] <= k && k <= V[n - 1]) {
        cout << -1 << '\n';
        return;
    }
    if (V[0] > k) {
        for (int i = 0; i < n; i++) {
            V[i] -= k;
        }
    } else {
        for (int i = 0; i < n; i++) {
            V[i] = k - V[i];
        }
    }
    LL g = V[0];
    for (int i = 0; i < n; i++) {
        g = gcd(g, V[i]);
    }

    LL cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += V[i] / g - 1;
    }

    cout << cnt << '\n';
    return;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}