A

题解

知识点：模拟。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool solve() {

    string a, b;

    cin >> a >> b;

    if (a.back() != b.back()) {

        if (a.back() > b.back()) cout << '<' << '\n';

        else if (a.back() == b.back()) cout << '=' << '\n';

        else cout << '>' << '\n';

    }

    else if (a.back() == 'S') {

        if (a.size() > b.size()) cout << '<' << '\n';

        else if (a.size() == b.size()) cout << '=' << '\n';

        else cout << '>' << '\n';

    }

    else if (a.back() == 'L') {

        if (a.size() > b.size()) cout << '>' << '\n';

        else if (a.size() == b.size()) cout << '=' << '\n';

        else cout << '<' << '\n';

    }

    else cout << '=' << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

B

题解

知识点：构造。

除了 \(n = 3\) ，其余取末尾两个倒放在前面，然后从 \(1\) 按顺序即可。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool solve() {

    int n;

    cin >> n;

    if (n == 3) return false;

    cout << n << ' ' << n - 1 << ' ';

    for (int i = 1;i <= n - 2;i++) cout << i << ' ';

    cout << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

C

题解

知识点：枚举。

暴力枚举可能的第一段作为基准划分，找到合法划分的中段的最大值，取所有合法的最小值。

时间复杂度 \(O(n^2)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int a[2007];

bool solve() {

    int n;

    cin >> n;

    for (int i = 1;i <= n;i++) cin >> a[i], a[i] += a[i - 1];

    int mi = n;

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

        int tag = a[i] - a[0];

        int l = i + 1, r = i + 1, tmx = i;

        while (l <= n) {

            while (r <= n) {

                if (a[r] - a[l - 1] > tag) break;

                r++;

            }

            if (a[r - 1] - a[l - 1] == tag) tmx = max(tmx, r - l);

            else break;

            l = r;

        }

        if (l > n) mi = min(mi, tmx);

    }

    cout << mi << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

D

题解

知识点：模拟，构造。

模拟这个过程，每次对数组元素分组，组大小从 \(2\) 开始倍增，因为大组交换不会改变组内两边元素相对位置，所以从最小的组开始排序。每组比较先把一组分为两半，因为这两半在上一轮的分组排序一定排序好了，然后把两边第一个元素作为代表元比较大小，每次只交换代表元即可，下一轮比较一定是其中较小的代表元比较。

注意到，无论如何交换，都不能改变原数组两两连续分组后的各个元素的相邻元素（如 12|34|56|78 ，其中两两元素一定相邻）。因此，如果发现某次交换，一组中两半的代表元差值，不是组大小的一半，那一定无解。

时间复杂度 \(O(m)\)

空间复杂度 \(O(m)\)

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int p[300007];

bool solve() {

    int m;

    cin >> m;

    for (int i = 1;i <= m;i++) cin >> p[i];

    int cnt = 0;

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

        for (int j = 1;j <= m;j += 1 << i) {

            if (abs(p[j] - p[j + (1 << i - 1)]) != (1 << i - 1)) return false;

            if (p[j] > p[j + (1 << i - 1)]) swap(p[j], p[j + (1 << i - 1)]), cnt++;

        }

    }

    cout << cnt << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

E

知识点：线性dp。

朴素dp，设 \(dp[i]\) 为 \([1,i]\) 是否合法。考虑 \(b[i]\) 时，可以把其放下一段左侧或者是右侧，因此有转移方程：

if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];

if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

题解

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int b[200007];

bool dp[200007];

bool solve() {

    int n;

    cin >> n;

    for (int i = 1;i <= n;i++) cin >> b[i], dp[i] = 0;

    dp[0] = 1;

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

        if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];

        if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];

    }

    if (dp[n]) cout << "YES" << '\n';

    else cout << "NO" << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

巴特西

Codeforces Round #826 (Div. 3) A-E

A

题解

代码

B

题解

代码

C

题解

代码

D

题解

代码

E

题解

代码

最新文章

热门文章