2024牛客寒假D、J题解

发表于 分类于

比赛链接：https://ac.nowcoder.com/acm/contest/67741/D

D. 数组成鸡

可以发现，最后的局面不可能所有数的绝对值都大于 \(\exp{\ln{1e9}/n}\)。直接枚举哪个数在这个范围。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//能确定的事情只有啊，今天感觉有点寂寞啊
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;

int a[N], n, q;

void MAIN() {
    cin >> n >> q;
    set<ll> ans, d;
    ans.insert(0);
    int k = exp(log(1e9) / (double)n) + 3;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = -k; j <= k; j++) d.insert(-a[i] + j);
    }
    for (int di : d) {
        ll r = 1;
        for (int i = 1; i <= n; i++) {
            r *= (di + a[i]);
            if (abs(r) > 1e9 || r == 0) break;
        }
        ans.insert(r);
    }
    while (q--) {
        ll m;
        cin >> m;
        cout << (ans.count(m) ? "Yes" : "No") << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}

J.又鸟之亦心

首先二分将最优化问题变为判定性问题。
首先可以发现当某个任务结束过后一定有一个人在这个位置。
另一个人在更前面的某个位置。考虑下一个任务是继续排这个人还是换人。我们可以发现相当于将任务在时间轴上划分成一些线段。每个任务维护可能的上一个线段右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//能确定的事情只有啊，今天感觉有点寂寞啊
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;

int n, x, y;
int a[N];

bool check(int mid, int x) {
    set<int> st;
    if (abs(a[1] - x) <= mid) st.insert(x);
    for (int i = 2; i <= n; i++) {
        if (st.empty()) return false;
        while (!st.empty() && abs(*st.begin() - a[i]) > mid) st.erase(*st.begin());
        while (!st.empty() && abs(*st.rbegin() - a[i]) > mid) st.erase(*st.rbegin());
        if (abs(a[i] - a[i - 1]) <= mid) st.insert(a[i - 1]);
    }
    return !st.empty();
}

void MAIN() {
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int l = abs(x - y), r = 1e9, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid, x) || check(mid, y)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}