526互联

Codeforces Round 887 (Div. 2)

发布时间 2023-10-22 00:41:06作者: value0

Codeforces Round 887 (Div. 2)

A. Desorting

解题思路:

每次操作能使相邻数之差减\(2\)，设最小相邻数之差为\(mind\),答案为\(ans = (mind + 1) / 2\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    int mind = 1e9 + 10;
    for (int i = 2; i <= n; i++)
    {
        mind = min(mind, v[i] - v[i - 1] + 1);
        if (v[i] < v[i - 1])
        {
            cout << 0 << endl;
            return;
        }
    }
    cout << (mind + 1) / 2 << endl;
}

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

B. Fibonaccharsis

解题思路:

斐波那契数列递增速度是\(logn\)级别。

\(c + b = a\)，\(c = a - b\)。

不难发现，若\(a = n\)，只要确定了\(b\)，那么根据性质递推，整个序列就确定了。

所以第一层枚举\(n\)，即枚举\(b = 1\sim n\)。第二层就直接回推，上面说了，最多回推\(logn\)次。递推过程只要最多\(logn\)次，就一定能递推到负数、推到非法或者推完跳出。

时间复杂度:\(O(nlogn)\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    ll n, k;
    cin >> n >> k;
    // c + b = a;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int a = n;
        int b = i;
        bool f = true;
        for (int j = 1; j <= k - 2; j++)
        {
            int c = a - b;
            if (c < 0 || c > b)
            {
                f = false;
                break;
            }
            a = b;
            b = c;
        }
        if (f)
        {
            ans++;
        }
    }
    cout << ans << endl;
}

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

C. Ntarsis' Set

解题思路:

最终答案具有单调性。

我们按第\(k\)小来看，最终答案是第\(1\)小。凡是比答案小的全部都被删完了。凡是比他大的还活着的一定是第\(i > 1\)小。

如果我们当前是第\(10\)小，删完第\(1,3,11\)小之后，这个数就是当前第\(8\)小了，因为比他小的数删了两个。

如果进行\(3\)轮，那么这个数就是第\(4\)小了。以此类推。

我们二分\(mid\),在\(check\)内对其进行\(k\)轮减去升序小于\(mid\)的个数。其中每轮寻找有\(cnt\)个要删的数的升序小于\(mid\)这一步用二分。

时间复杂度:\(O(log(1e18)\times k\times log(k))\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    ll l = 0;
    ll r = 1e18 + 10;
    auto check = [&](ll mid)
    {
        for (int i = 1; i <= k; i++)
        {
            // 找到第一个大于当前位置的位置，那么前面的位置就是前进的步数
            int idx = upper_bound(v.begin() + 1, v.end(), mid) - v.begin() - 1;
            mid -= idx;
            if (mid <= 0)
            {
                return false;
            }
        }
        return true;
    };
    while (l + 1 < r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    cout << r << endl;
}

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

D. Imbalanced Arrays

解题思路:

本题思路有点复杂，建议去看洛谷题解。

为了方便构造，满足\(b_i + b_j \neq 0\),我们\(n\)个位置数的绝对值分别为\(1\sim n\).

性质一：

若\(a_i > a_j\),则\(b_i > b_j\)。

假设$b_j + b_k > 0 \(，那么因为\)b_i > b_j\(，所以一定有\)b_i + b_k >0$。

所以我们根据\(a\)进行升序排序。

此时有\(a_1 \leq a_2 \leq ...\leq a_n\),所以有\(b_1 \leq b_2 \leq ...\leq b_n\)。

对于序列\(b\)中，设绝对值最大为\(w_i\)。此时，若对应\(b_i\)为正数，那么他加上所有数都是正数。若对应\(b_i\)为负数，那么他加上任何数都是负数。

根据以上性质,我们用双指针从左右两边开始判断,即从最大最小值开始构造。我们按绝对值从大往小进行构造。

如果\(b_n + b_1 > 0\)，那么\(a_n = n\)是一定的，且\(a_1 \geq 1\)也是一定的。如果我们对左边的数都进行的是负数构造，那么\(abs(b_1) < abs(b_n)\)。我们可以使\(b_n = n\)。

同理，\(a_1 = 0\)那么\(a_n = n\)是不可能的。\(a_1= 1\)，那么\(a_n < n\)是不可能的。

当有一边确定当前最大绝对值符合\(a_i\)构造，那么我们就直接构造并将指针向中间移动。

当不存在左右指针的合法构造时，说明无解。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    vector<pii> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i].fi;
        v[i].se = i;
    }
    int l = 1;
    int r = n;
    sort(v.begin() + 1, v.end());
    vector<int> ans(n + 1);
    int tot = n;
    while (l <= r)
    {
        // 绝对值最大的如果是负数，那么此处a[i] = 0;
        // b[v[l].se] + {b[n - r + 1 ~ n]} > 0
        // 因为 abs(b[n-r+1 ~ n]) > b[v[l].se]
        // 所以如果v[l].fi == n - r,意味着当前的b[r] + b[l] 需要小于0
        // 即，此时在b[l ~ r]这个区间中，b[l]的绝对值应当最大。所以赋值。
        if (v[l].fi == n - r)
        {
            ans[v[l].se] = -tot;
            l++;
            tot--;
        }
        // 绝对值最大的如果是正数,那么此处a[i] = n;
        // 此时b[1 ~ (l)]的绝对值大于b[v[r].se]。
        // 所以，如果要求b[v[r].se] + b[l ~ n] > 0
        // 即,v[r].fi == n - l + 1,此时在b[l ~ r]这个区间中，b[r]的绝对值应当最大。所以赋值
        else if (v[r].fi == n - l + 1)
        {
            ans[v[r].se] = tot;
            r--;
            tot--;
        }
        else
        {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << ' ';
    }
    cout << "\n";
}

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