2025.1.26——1400

2025.1.26——1400

A 1400

B 1400

------------------------------------------------

• 2024年最后一篇

A

1. 发现和区间非1之和与1的个数大小有关。前缀维护两个信息即可。

B

1. 找到一种构造方式为：来回摆动构造。

------------------------代码------------------------

A

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                         \
    {                                         \
        for (int I = ST; I < VEC.size(); I++) \
            cout << VEC[I] << ' ';            \
        el;                                   \
    }

void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(10);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, q;
    cin >> n >> q;
    vector<int> prefix(n + 1), pre0(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        pre0[i] = pre0[i - 1] + (x == 1);
        prefix[i] = prefix[i - 1] + x - 1;
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << (r - l && prefix[r] - prefix[l - 1] >= pre0[r] - pre0[l - 1] ? "YES" : "NO");
        el;
    }
}

B

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                         \
    {                                         \
        for (int I = ST; I < VEC.size(); I++) \
            cout << VEC[I] << ' ';            \
        el;                                   \
    }

void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(10);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, k;
    cin >> n >> k;
    vector<int> res(n + 1);
    int st = 1;
    for (int i = 1; i <= k; i++)
    {
        if (i & 1)
            for (int j = i; j <= n; j += k)
                res[j] = st++;
        else
        {
            int j;
            for (j = i; j <= n; j += k)
                ;
            if (j > n)
                j -= k;
            for (; j > 0; j -= k)
                res[j] = st++;
        }
    }
    bugv(res, 1);
}