A

题意

给一个字符串每个物品对应的灯的照明方向，L/R 能照亮它左侧/右侧的所有物品（不包括自己对应的物品），现在能交换相邻两个灯一次（不改变照明方向），问能否找亮所有物品。

题解

知识点：贪心。

显然，如果存在 LR 或 RL 就可以照亮全部，否则全是 L 或 R 就不可行。

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

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

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool solve() {

    int n;

    cin >> n;

    string s;

    cin >> s;

    s = "?" + s;

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

        if (s[i] != s[i + 1]) {

            if (s[i] == 'L') cout << i << '\n';

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

            return true;

        }

    }

    return false;

}

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\) 为偶数时，构造 \(1,-1,1,-1,\cdots\) 即可。

\(n\) 为奇数时，显然奇数项和偶数项要各自相等，随后由 \(a_1+\cdots+a_n = a_{n-1}+a_{n}\) 可以得到 \((n-1)a_1+(n-3)a_2 = 0\) ，取 \(a_1 = n-3,a_2 = 1-n\) 即可，只有 \(n=3\) 时无解（因为 \(a_1 = 0\)）。

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

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

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool solve() {

    int n;

    cin >> n;

    if (n & 1) {

        if (n == 3) return false;

        cout << "YES" << '\n';

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

            if (i & 1) cout << n - 3 << ' ';

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

        }

        cout << '\n';

    }

    else {

        cout << "YES" << '\n';

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

            if (i & 1) cout << 1 << ' ';

            else cout << -1 << ' ';

        }

        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 << "NO" << '\n';

    }

    return 0;

}

C

题意

给一组数，可以修改元素变成其相反数。问最少修改几次，可以使得第 \(m\) 个前缀和 \(a_1+\cdots+a_m\) 是所有前缀和里最小的。

题解

知识点：前缀和，数学，贪心。

定义 \(a[l,r] = a_l+\cdots+a_r\) 。

当 \(k\in [1,m-1]\) 时

\[\begin{aligned}
a[1,k] &\geq a[1,m]\\
a[1,k] &\geq a[1,k] + a[k+1,m]\\
0 &\geq a[k+1,m]
\end{aligned}
\]

当 \(k\in [m+1,n]\) 时

\[\begin{aligned}
a[1,k] &\geq a[1,m]\\
a[1,m] + a[m+1,k] &\geq a[1,m]\\
a[m+1,k] &\geq 0
\end{aligned}
\]

所以只要保证任意 \(i\in[2,m]\) ，满足 \(a[i,m]\leq 0\) ；任意 \(i\in[m+1,n]\) ，满足 \(a[m+1,i] \geq 0\) 即可。

每次操作时，贪心地取最优的即可。

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

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

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int a[200007];

bool solve() {

    int n, m;

    cin >> n >> m;

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

    int cnt = 0;

    multiset<int> ms;

    ll sum = 0;

    for (int i = m;i >= 2;i--) {

        sum += a[i];

        ms.insert(a[i]);

        if (sum > 0) {

            sum -= 2 * (*prev(ms.end()));

            ms.erase(prev(ms.end()));

            cnt++;

        }

    }

    ms.clear();

    sum = 0;

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

        sum += a[i];

        ms.insert(a[i]);

        if (sum < 0) {

            sum -= 2 * (*ms.begin());

            ms.erase(ms.begin());

            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;

}

D

题意

给定一组头发长度 \(a_i\) ，以及理想头发长度 \(b_i\) 。

理发师有刀片 \(x_i\) ，每个刀片只能用一次，每次可以修减一段连续区间的头发，满足 \(a'_i = \min(a_i,x),i\in[L,R]\)。

问理发师能不能通过这些刀片将 \(a\) 修剪至 \(b\) 。

题解

知识点：单调栈。

显然 \(a_i<b_i\) 无解。

利用最大值单调栈维护刀片的值。以下按顺序满足：

\(b_i\) 大于栈顶刀片，则栈顶刀片因为太小不能再用了，刀片需要出栈直至 \(b_i\) 小于等于栈顶刀片或栈空。
\(b_i = a_i\) ，说明 \(b_i\) 不需要修剪，什么都不用干。
\(b_i \neq a_i\) ，说明 \(b_i\) 需要修剪，此时如果 \(b_i\) 小于栈顶刀片或栈空，则需要使用新的刀片，满足 \(x = b[i]\) ，如果不存在这个刀片则无解。

全部满足后，即 YES 。

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int a[200007];

int b[200007];

bool solve() {

    int n;

    cin >> n;

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

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

    int m;

    cin >> m;

    map<int, int> mp;

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

        int x;

        cin >> x;

        mp[x]++;

    }

    stack<int> st;

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

        if (a[i] < b[i]) return false;

        while (!st.empty() && b[i] > st.top()) st.pop();

        if (a[i] != b[i]) {

            if (st.empty() || b[i] < st.top()) {

                if (mp[b[i]]) {

                    mp[b[i]]--;

                    st.push(b[i]);

                }

                else return false;

            }

        }

    }

    cout << "YES" << '\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 << "NO" << '\n';

    }

    return 0;

}

巴特西

Hello 2023 A-D

A

题意

题解

代码

B

题意

题解

代码

C

题意

题解

代码

D

题意

题解

代码

最新文章

热门文章