XCPC wiki - 贪心 | 小明の雜貨鋪

用于解决多阶段的优化问题。在总体最优策略无法给出的情况下，每一步的选择都是求局部最优解：当求目标函数值最大时，选择当前最大值；当求目标函数值最小时，选择当前最小值。

CF1930D. Sum over all Substrings

题意对于一个长度为 $L$ 的 01 串 $p$ ，定义一个长度为 $L$ 的 01 串 $q$ 关于 $p$ 是好的，当且仅当 $\forall i\in[1,n]$ 满足： $\exists1\leq l\leq i\leq r\leq L$ ，满足 $p_i$ 为 $q[l,r]$ 的区间众数。定义 $g(p)$ 为所有关于 $p$ 是好的串 $q$ 中 $1$ 的个数的最小值。

给定一个长度为 $n$ 的 $01$ 串 $s$ ，求 $s$ 所有子串的 $g$ 的和。

思路贪心地，每个 $p_{i}=1$ 只需要在左中右三个位置之一选择一个填 $1$ 。

从前向后遍历，如果 $p_{i}=1$ ，可以填 $q_{i-1}=1$ ，只需要看前 $i-3$ 个位置有几个 $1$ ，于是有转移 $f_{i}=f_{i-3}+1$ 。

本题问所有子串的答案，如果 $p_{i}=1$ ，考虑以 $i$ 结尾的 $i$ 个子串，有转移 $f_{i}=f_{i-3}+i$ ，答案为 $\sum f_{*}$ 。

CF1992D. Test of Love

有一个长 $n$ 米的河流，你站在 $0$ 号点上，想要去 $n+1$ 号点，不能走回头路。 $1$ 号点到 $n$ 号点有 $3$ 种情况：

W 表示水，允许经过，但不能经过超过 $k$ 个点。
L 表示木头，允许经过。
C 表示鳄鱼，不允许经过。

运动的方式有 $2$ 种：

站在木点 $i$ 上，你可以跳到 $i+j\ (0 \leqslant j \leqslant m)$ 上，可以跳入水中或者另一个木头，但是不能跳到鳄鱼上。
在水 $i$ 上，你能且仅能到达 $i+1$ 号点。如果 $i+1$ 是鳄鱼，不可以走。

如果这两种运动方式都无法到达 $n+1$ 号点，或是经过了超过 $k$ 个水点，则失败，反之成功。判断能不能成功。

数据范围： $n,m,k \leqslant 2\times 10^{5}$ （原数据 $m \leqslant 10$ ）

线性解 $\Theta(n)$ ：站在木点 $i$ 上，记录 能跳到的最右端 $i+m$ ；否则如果是水或鳄鱼，首先判断是否在最右端的左边，如果不是，在鳄鱼上直接死，在水中则减小体力。

这个「能跳到的最右端」即是用贪心优化 DP，并不需要转移 $1\sim m$ 的所有情形。

int n, m, k;
cin >> n >> m >> k;
// k: swim in total
// m: jump forward one time

string s;
cin >> s;
s = 'L' + s + 'L';

bool ok = true;
int mx = 0;  // 能跳到的最远距离
for (int i = 0; i < s.length(); i++) {
	char c = s[i];
	if (c == 'L') {  // log
		mx = max(mx, i + m);
	} else if (mx <= i && (c == 'W' && k-- == 0 || c == 'C')) {
		ok = false;
	}
}
cout << (ok ? "YES" : "NO") << "\n";

2024 CCPC 哈尔滨 J. 新能源汽车

Problem - J - Codeforces

[[…/contests/VP/2024-10-30-Autumn13-2024CCPC哈尔滨#J. 新能源汽车|2024-10-30-Autumn13-2024CCPC哈尔滨]]

Description

有一辆新能源汽车，这辆车有 $n$ 个电瓶，第 i 个电瓶容量为 $a_{i}$ 单位，每消耗 $1$ 单位电力能恰好前进 $1$ 公里。车只能前进，不能反向行驶。你可以选择汽车行驶的每一公里所使用的电力来自哪个电瓶。

汽车在出发前每个电瓶都是充满电的。行驶中途会经过 $m$ 个充电站，第 $j$ 个充电站距离起点 $x_j$ 公里，并且只能给第 $t_j$ 个电瓶充电，每个充电站能提供的电力是无限的。

请计算这辆新能源汽车最远可以行驶多少公里。

Notes

考虑一个 $n^2$ 的贪心，我们从一个加油站 $j$ 走向 $j+1$ 的时候，一定是先用能先加到的油，这样模拟就是 $O(n^{2})$ 。

考虑加速这个过程，我们的贪心需要支持不断删去前缀的数，修改第一个数，插入一个数，用堆即可维护。

复杂度 $O(nlogn)$ 。

以上为官方题解。。。

首先开一个邻接表 $adj$ 用于存放一个电瓶的充电桩的所有位置。这些位置需要是倒序的。
我们可以开一个 $set$ ，用于维护对于目前的位置来说，每一个电瓶的最近的充电桩， $set$ 用于对这些充电桩进行自动的排序，使最近的充电桩在最前面。

PS ：对于最后一个点，直接将其设置为无穷远即可 ( 警钟敲烂 )

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void eachT()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    vector<ll> X(m + 2), T(m + 3);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> X[i] >> T[i];
    }
    X[m + 1] = 2e18;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= n; i++)
    {
        adj[i].push_back(m + 1);
    }
    for (int i = m; i >= 1; i--)
    {
        adj[T[i]].push_back(i);
    }

    vector<ll> b = a;
    set<array<int, 2>> alive;
    auto upd = [&](int i)
    {
        if (b[i] > 0)
        {
            alive.insert({adj[i].back(), i});
        }
    };

    for (int i = 1; i <= n; i++)
    {
        upd(i);
    }
    int x = 0;
    int tx = 1;
    while (!alive.empty())
    {
        auto [pos, i] = *alive.begin();
        ll now = min<ll>(b[i], X[tx] - x);
        if (b[i] < X[tx] - x)
        {
            alive.erase({pos, i});
            b[i] = 0;
        }
        else
        {
            b[i] -= now;
            int j = T[tx];
            alive.erase({adj[j].back(), j});
            adj[j].pop_back();
            alive.insert({adj[j].back(), j});
            b[j] = a[j];
            tx++;
        }
        x += now;
    }
    cout << x << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        eachT();
    }
}

以上为野羊题解。。

一个电瓶没电后所有和这个电瓶相关的信息 都同时消失，充电后 都同时出现，说明每个电瓶的信息具有 强相关性，因此将其存为链表，再用 set 存储每个链表的头。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 2e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

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

        vector<vector<int>> vec(n + 1);  // 每个电瓶有哪些充电桩
        vector<array<int, 2>> b(m + 1);
        for (int i = 0; i < m; i++) {
            int x, t;
            cin >> x >> t;
            t--;
            vec[t].push_back(i);
            b[i] = { x, t };
        }
        b[m] = { inf, n };

        set<array<int, 2>> Q;
        vector<vector<int>::iterator> head(n + 1);
        for (int i = 0; i <= n; i++) {
            vec[i].push_back(m);      // 所有的电瓶最后都要连到一个无穷远的充电桩
            head[i] = vec[i].begin();
            Q.insert({ *head[i], i });
        }

        auto now = a;
        int res = 0;
        for (auto [x, t] : b) {   // 枚举每个充电桩
            int i;  // 当前正在消耗的电瓶编号
            while (!Q.empty() && res + now[i = (*Q.begin())[1]] < x) {  // 跑不到充电桩
                res += now[i];
                now[i] = 0;  // 把所有电用完
                Q.erase(Q.begin());
            }
            if (Q.empty()) break;

            ll dis = x - res;
            now[i] -= dis;
            res += dis;

            Q.erase({ *head[t], t });
            head[t]++;
            Q.insert({ *head[t], t });

            now[t] = a[t];  // 充电
        }

        cout << res << '\n';
    }
}

2024 ICPC 南京 K. Strips

Problem - K - Codeforces

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 10;
const ll inf = 1e18;

void eachT()
{
    int n, m, k, w;
    cin >> n >> m >> k >> w;
    vector<int> a(n), b(m + 2);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }
    b[0] = 0;
    b[m + 1] = w + 1;
    sort(b.begin(), b.end());

    bool ok = 1;
    vector<int> res;

    auto solve = [&](vector<ll>& a, int& l, int& r) -> void
    {
        vector<int> pos;
        int len = a.size();
        for (int i = 0; i < len; )
        {
            pos.push_back(a[i] + k - 1);
            int p = upper_bound(a.begin(), a.end(), a[i] + k - 1) - a.begin();
            if (a[p] == r)
            {
                for (auto x : pos)
                {
                    res.push_back(x - k + 1);
                }
                return;
            }
            else if (a[p] == inf)
            {
                pos[pos.size() - 1] = r - 1;
                for (int j = pos.size() - 1; j >= 0; j--)
                {
                    if (pos[j] - k + 1 <= l)
                    {
                        ok = 0;
                        return;
                    }
                    if (j >= 1 && pos[j] - k + 1 <= pos[j - 1])
                    {
                        pos[j - 1] = pos[j] - k;
                    }   
                    else
                    {
                        for (auto x : pos)
                        {
                            res.push_back(x - k + 1);
                        }
                        return;
                    }
                }
            }
            else
            {
                i = p;
            }
        }
    };

    int now = 1;
    vector<ll> aa;
    for (int i = 0; i < n;)
    {
        if (!ok)
        {
            break;
        }
        while (a[i] > b[now])
        {
            now++;
        }
        while (a[i] <= b[now])
        {
            aa.push_back(a[i]);
            i++;
            if (i >= n)
            {
                break;
            }
        }
        aa.push_back(b[now]);
        aa.push_back(inf);
        solve(aa, b[now - 1], b[now]);
        aa.clear();
        now++;
        
    }
    if (!ok)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << res.size() << endl;
        for (auto x : res)
        {
            cout << x << " ";
        }
        cout << endl;
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        eachT();
    }
}