竞赛讨论区 > 2024/05/19 简短的题解记录
头像
Levi_yxc
编辑于 05-24 23:34
+ 关注

2024/05/19 简短的题解记录

CSDN 版本

A. 广告位招租中

Solution

首先数组内一定只要留下 的 ，然后开一个数组 记录一下 每个位置有多少数。

考虑枚举最大公约数 ，接着我们只要枚举 的倍数即可。对于 ， 是数组 中出现过的，我们要把这些 取 ，看最终是否是 ，如果是说明这些数的 为 ，否则是 的倍数。

这样的总时间复杂度是 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n, m;
    std::cin >> n >> m;
    
    int max = 0;
    std::vector<int> a;
    for (int i = 0; i < n; i += 1) {
        int x;
        std::cin >> x;
        if (x >= m) {
            a.push_back(x);
            max = std::max(max, x);
        }
    }
    if (a.empty()) {
        std::cout << "0 0\n";
        return 0;
    }
    std::vector<int> vis(max + 1);
    for (int x: a) {
        vis[x] += 1;
    }
    int k = 0, ans = 0;
    for (int g = m; g <= max; g += 1) {
        int cnt = 0;
        int d = 0;
        for (int x = g, y = 1; x <= max; x += g, y += 1) {
            if (vis[x]) {
                cnt += vis[x];
                d = std::gcd(d, y);
            }
        }
        if (d == 1 and k < cnt) {
            k = cnt;
            ans = g;
        }
    }
    std::cout << k << " " << ans << "\n";
    
    return 0;
}

B. MEX of MEXes

Solution

首先，特判长度为 的排列，此时子数组只有 ，所以 中只有 ，答案为 。

对 的排列 ，我们考虑 中是否可能出现 。对于一个确定的 ，如果 的数都在 的一侧，说明可以选择 ，而不选到 ，这样就产生了一个 的子数组；否则，只要想选全 ，就一定会选到 ，导致没有任何一个子数组的 为 。

因此我们只要用树状数组计算每个数左右各有多少数小于它，然后从 开始枚举到 ，看是否存在一个 无法成为 。

但是特别注意，如果枚举完了 个数都满足条件，说明此时整个数组 的 ，所以答案应该是 。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

template<class T>
struct BIT {
    int n, down;
    std::vector<T> a;
    BIT(int _n = 0): down(0) {
        init(_n);
    }
    BIT(std::vector<int> _a, int op): down(0) {
    	init(_a, op);
    }
    void init(int _n) {
        n = _n;
        a.assign(n, T{});
    }
    void init(std::vector<int> _a, int op) {
    	assert(op == 0 or op == 1);
    	if (op == 0) {
    		init(_a.size());
    		for (int i = 0; i < _a.size(); i += 1) {
    			add(i, _a[i]);
    		}
    	} else {
    		int max = *std::max_element(_a.begin(), _a.end());
	    	int min = *std::min_element(_a.begin(), _a.end());
	    	init(max - min + 1);
	    	for (int x: _a) {
	    		add(x - min, 1);
	    	}
	    	down = min;
    	}
    }
    int lowbit(int x) {
    	return x & -x;
    }
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += lowbit(i)) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    void clear() {
    	a.assign(n, T{});
    }
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
    int kth(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n and cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n;
    std::cin >> n;
    
    if (n == 1) {
        std::cout << 1 << "\n";
        return 0;
    }
    std::vector<int> a(n), pos(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> a[i];
        pos[--a[i]] = i;
    }
    BIT<int> bit(n);
    std::vector<int> pre(n);
    for (int i = 0; i < n; i += 1) {
        pre[a[i]] = bit.sum(a[i]);
        bit.add(a[i], 1);
    }
    bit.clear();
    std::vector<int> suf(n);
    for (int i = n - 1; i >= 0; i -= 1) {
        suf[a[i]] = bit.sum(a[i]);
        bit.add(a[i], 1);
    }
    for (int v = 0; v < n; v += 1) {
        if (pre[v] > 0 and pre[v] < v or suf[v] > 0 and suf[v] < v) {
            std::cout << v + 1 << "\n";
            return 0;
        }
    }
    std::cout << n + 2 << "\n";
    
    return 0;
}

C. 战斗时回复

Solution

把时间拉长到两个时间最小公倍数，然后比较二者的大小即可。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int T, H, t, n;
    std::cin >> T >> H >> t >> n;
    
    i64 lcm = std::lcm(1LL * T, 1LL * t);
    i64 H1 = lcm / T * H;
    i64 n1 = lcm / t * n;
    
    std::cout << (H1 >= n1 ? "kirito": "hangeki");
    
    return 0;
}

D. 小太阳的帕鲁世界1

Solution

我们直接从终点 逆向搜索即可，只是要特别注意，它对方向的要求是进来的，而我们是回去的，所以要反一下，比如说 ，正着走是 ，所以反着就是 。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

constexpr int dx[] = {
	-1, 0, 1, 0, -1, 1, 1, -1, -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2
};
constexpr int dy[] = {
	0, 1, 0, -1, 1, 1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::string> g(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> g[i];
    }
    
    std::vector dis(n, std::vector(m, -1));
    dis[n - 1][m - 1] = 0;
    
    std::queue<std::pair<int, int>> q;
    q.emplace(n - 1, m - 1);
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        int a = x, b = y;
        if (g[x][y] == 'D') {
            x -= 1;
        } else if (g[x][y] == 'U') {
            x += 1;
        } else if (g[x][y] == 'L') {
            y += 1;
        } else {
            y -= 1;
        }
        if (x >= 0 and x < n and y >= 0 and y < m) {
            dis[x][y] = dis[a][b] + 1;
            q.emplace(x, y);
        }
    }
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < m; j += 1) {
            std::cout << dis[i][j] << " \n"[j == m - 1];
        }
    }
    
    return 0;
}

E. 小太阳的帕鲁世界2

Solution

这个我记得是 上近期一场 的单调队列优化 。

设 表示考虑前 个位置的最小代价，显然转移是 ，这可以用单调队列优化到 。

不过本题有个额外要求，就是要求 这个点必须搞点石头，那我们可以把 划分为 和 ，前半段我们已经做完，后半段只要对 逆序做一次上述 即可，设为 。这样答案即为 。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n, k, Q;
    std::cin >> n >> k >> Q;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> a[i];
    }
    std::vector<i64> f(n), g(n);
    f[0] = a[0];
    std::vector<int> q(n);
    int hh = 0, tt = -1;
    q[++tt] = 0;
    for (int i = 1; i < n; i += 1) {
        while (hh <= tt and i - q[hh] > k) {
            hh += 1;
        }
        f[i] = f[q[hh]] + a[i];
        while (hh <= tt and f[q[tt]] >= f[i]) {
            tt -= 1;
        }
        q[++tt] = i;
    }
    g[n - 1] = a[n - 1];
    hh = 0, tt = -1;
    q[++tt] = n - 1;
    for (int i = n - 2; i >= 0; i -= 1) {
        while (hh <= tt and q[hh] - i > k) {
            hh += 1;
        }
        g[i] = g[q[hh]] + a[i];
        while (hh <= tt and g[q[tt]] >= g[i]) {
            tt -= 1;
        }
        q[++tt] = i;
    }
    
    while (Q--) {
        int x;
        std::cin >> x;
        x -= 1;
        std::cout << f[x] + g[x] - a[x] << "\n";
    }
    
    return 0;
}

F. 又掉分了

Solution

这个可以看成很简单的 或者就单纯是模拟。

设 表示考虑前 场比赛，小 能获得的最高 ，那转移方程就是

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int x, n;
    std::cin >> x >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> a[i];
    }
    
    std::vector<int> f(n + 1);
    f[0] = x;
    
    for (int i = 0; i < n; i += 1) {
        f[i + 1] = std::max(f[i], (f[i] + a[i]) / 2);
    }
    std::cout << f[n] << "\n";
    
    return 0;
}

F. Birusu的公园

Solution

考虑两点 （），题目意思其实就是求 或 。

那我们可以化简一下，分为两大种情况

  • ，

  • ，

因此我们只要维护 和 的前缀最大最小，以及后缀最大最小，按照上述方式转移即可。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
	int n;
	std::cin >> n;
	
	std::vector<int> h(n);
	for (int i = 0; i < n; i += 1) {
	    std::cin >> h[i];
	}
	
    std::vector<int> add(n), sub(n);
    for (int i = 0; i < n; i += 1) {
        add[i] = h[i] + i;
        sub[i] = h[i] - i;
    }
	std::vector<int> preadd(n + 1, -n), presub(n + 1, -n);
    for (int i = 0; i < n; i += 1) {
        preadd[i + 1] = std::max(preadd[i], add[i]);
        presub[i + 1] = std::max(presub[i], sub[i]);
    }
    std::vector<int> sufadd(n + 1, -n), sufsub(n + 1, -n);
    for (int i = n - 1; i >= 0; i -= 1) {
        sufadd[i] = std::max(sufadd[i + 1], add[i]);
        sufsub[i] = std::max(sufsub[i + 1], sub[i]);
    }
    
    int ans = 0;
    for (int i = 0; i < n; i += 1) {
        if (i + 2 <= n) {
            ans = std::max(ans, sub[i] + sufadd[i + 2] - 1);
        }
        ans = std::max(ans, add[i] + sufsub[i + 1] + (n - 1));
        if (i > 0) {
            ans = std::max(ans, add[i] + presub[i - 1] - 1);
        }
        ans = std::max(ans, sub[i] + preadd[i] + (n - 1));
    }
    std::cout << ans << "\n";
    
    return 0;
}

H. 被诅咒的宝藏

Solution

显然，如果想要拿走的越多，每个物品价值就越大，这样真正拿走的就可能越少（拿得越多，拿得越少）。因此可以观察到这个 是具有二段性的， 越小，越可能真正拿走 个物品。

所以我们只要二分这个 即可。对于确定的 ，我们直接开一个新的数组记录 ，然后排序，从小到大选择最小的 个，看是否超过 ，如果没超过就成功。

时间复杂度 ，我这个做法还是有点紧的。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
	int n, s;
	std::cin >> n >> s;
	
	std::vector<int> a(n);
	for (int i = 0; i < n; i += 1) {
	    std::cin >> a[i];
	}
	
	std::vector<i64> b(n);
	auto calc = [&](int k) -> std::array<i64, 2> {
	    for (int i = 0; i < n; i += 1) {
	        b[i] = a[i] + (i + 1LL) * k;
	    }
	    std::sort(b.begin(), b.end());
	    int cnt = 0;
	    i64 sum = 0;
	    for (int i = 0; i < n and cnt < k; i += 1) {
	        if (sum + b[i] <= s) {
	            sum += b[i];
	            cnt += 1;
	        } else {
	            break;
	        }
	    }
	    return {cnt == k, sum};
	};
	
	int lo = 0, hi = n;
	while (lo < hi) {
	    int mid = lo + hi + 1 >> 1;
	    if (calc(mid)[0]) {
	        lo = mid;
	    } else {
	        hi = mid - 1;
	    }
	}
	std::cout << hi << " " << calc(hi)[1] << "\n";
    
    return 0;
}

I. 决定命运的博弈

Solution

当 与 互质时， 与 也是互质的，所以后手必胜。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    i64 n;
    std::cin >> n;
    
    std::cout << "Tpdjbmjtn\n";
    
    return 0;
}

J. 52Hz的minmax区间（easy）

Solution

首先把求和式从减号处拆开，变成求 。

这样就变成了一道板子题，即求每个数左右第一个大于/小于自己的数的位置，这可以用单调栈优化到 。

设第 个数左边第一个大于自己的为 ，右边第一个大于自己的为 ，这样就会有 个子区间是下标 的正贡献。对两边第一个小于的同理，只不过是负贡献。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
     
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
template<>
int MInt<0>::Mod = 998244353;
 
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
 
constexpr int P = 998244353;
using Z = MInt<P>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n;
    std::cin >> n;
    
    std::vector<int> p(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> p[i];
        p[i] -= 1;
    }
    
    std::stack<int> stk;
    std::vector<int> lmax(n, -1), rmax(n, n);
    for (int i = 0; i < n; i += 1) {
        while (!stk.empty() and p[stk.top()] < p[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            lmax[i] = stk.top();
        }
        stk.push(i);
    }
    stk = std::stack<int>();
    for (int i = n - 1; i >= 0; i -= 1) {
        while (!stk.empty() and p[stk.top()] < p[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            rmax[i] = stk.top();
        }
        stk.push(i);
    }
    stk = std::stack<int>();
    std::vector<int> lmin(n, -1), rmin(n, n);
    for (int i = 0; i < n; i += 1) {
        while (!stk.empty() and p[stk.top()] > p[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            lmin[i] = stk.top();
        }
        stk.push(i);
    }
    stk = std::stack<int>();
    for (int i = n - 1; i >= 0; i -= 1) {
        while (!stk.empty() and p[stk.top()] > p[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            rmin[i] = stk.top();
        }
        stk.push(i);
    }
    Z ans = 0;
    for (int i = 0; i < n; i += 1) {
        ans += Z(i) * (rmax[i] - i) * (i - lmax[i]);
        ans -= Z(i) * (rmin[i] - i) * (i - lmin[i]);
    }
    std::cout << ans << "\n";
    
    return 0;
}

K. 52Hz的minmax区间（hard）

Solution

考虑每个左端点为 的区间 |最大值下标与最小值下标差值| 的和。

我们需要维护一段区间的三个信息，最大值下标、最小值下标以及它们差值的绝对值，这可以用线段树来实现，即拓展到维护一段区间 的最大值下标和 ，最小值下标和 ，以及以 为左端点，右端点 的所有子区间的 |最大值下标与最小值下标差值| 之和 。

而要做到修改一段区间的最大值/最小值下标，就需要用到单调栈，因为我们需要找到 右侧第一个大于/小于 的值 的下标 。

我们从右到左逆序遍历这个排列，维护两个单调栈，分别是递减栈 和递增栈 。

  • 通过 ，找到 右侧第一个大于 的值 的下标 ，这样一来，右端点在 内的区间最大值下标都可以改为 。

  • 通过 ，找到 右侧第一个小于 的值 的下标 ，这样一来，右端点在 内的区间最小值下标都可以改为 。

由于我们是从右到左遍历，因此每次修改一定会把最大值/最小值下标 变小，也就是说每次修改可以直接改变整段区间的 或 ，然后 。

这里特别注意，对于一段区间内下标差值绝对值的维护，如果 一个都没被修改过，那就不应该修改 ，其实就是没有懒标记就别下传。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

template<class Info, class Tag>
struct LSGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LSGT() {}
    LSGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LSGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
    #undef l(p)
    #undef r(p)
};

struct Tag {
    std::array<int, 2> tag{-1, -1};
    void apply(const Tag &t) {
        for (int i = 0; i < 2; i += 1) {
            if (t.tag[i] != -1) {
                tag[i] = t.tag[i];
            }
        }
    }
};
struct Info {
    std::array<i64, 3> sum{};
    void apply(const Tag &t, int len) {
        bool mod = false;
        for (int i = 0; i < 2; i += 1) {
            if (t.tag[i] != -1) {
                sum[i] = 1LL * t.tag[i] * len;
                mod = true;
            }
        }
        if (mod) {
            sum[2] = std::abs(sum[0] - sum[1]);
        }
    }
};
Info operator+(const Info &a, const Info &b) {
    Info c;
    for (int i = 0; i < 3; i += 1) {
        c.sum[i] = a.sum[i] + b.sum[i];
    }
    return c;
}

constexpr int P = 998244353;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n;
    std::cin >> n;
    
    std::vector<int> p(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> p[i];
        p[i] -= 1;
    }
    LSGT<Info, Tag> sgt(n);
    for (int i = 0; i < n; i += 1) {
        sgt.modify(i, {i, i, 0});
    }
    std::stack<int> stk0, stk1;
    stk0.push(n - 1);
    stk1.push(n - 1);

    i64 ans = 0;
    for (int i = n - 2; i >= 0; i -= 1) {
        while (!stk0.empty() and p[i] > p[stk0.top()]) {
            stk0.pop();
        }
        while (!stk1.empty() and p[i] < p[stk1.top()]) {
            stk1.pop();
        }
        if (p[i] > p[i + 1]) {
            sgt.Apply(i, stk0.empty() ? n: stk0.top(), {i, -1});
        } else {
            sgt.Apply(i, stk1.empty() ? n: stk1.top(), {-1, i});
        }
        ans = (ans + sgt.query(i, n).sum[2]) % P;
        stk0.push(i);
        stk1.push(i);
    }
    std::cout << ans << "\n";
    
    return 0;
}

L. Kaiou的笑话

Solution

设 表示考虑 的前 个字符，已经有连续子数组组成目标串 的前 个字符的最少字符删除数。

这里目标串为 或者 ，所以跑两次一样的 就 。

首先，考虑 可以被删除的情况，那只有 或 ，这种情况下 。如果啥都没开始和已经凑成了所有字符，那么不删除一定更优。

接着，考虑凑字符。若 ，则 ，表示 不删，拿来凑 用了。

初始状态 ，其余均为正无穷，表示非法状态。最终答案 。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

constexpr int inf = 1E9;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n;
    std::cin >> n;
    
    std::string s;
    std::cin >> s;
    
    auto work = [&](const std::string &t) {
        std::array<int, 4> f{0, inf, inf, inf};
        for (int i = 0; i < n; i += 1) {
            auto g = f;
            for (int j = 1; j < 3; j += 1) {
                g[j] += 1;
            }
            for (int j = 0; j < 3; j += 1) {
                if (s[i] == t[j]) {
                    g[j + 1] = std::min(g[j + 1], f[j]);
                }
            }
            f.swap(g);
        }
        return f[3];
    };
    int ans = std::min(work("ten"), work("han"));
    if (ans == inf) {
        ans = -1;
    }
    std::cout << ans << "\n";
    
    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
东土科技校招硬件-控制岗
中国系统2021校园招聘-前端笔试
完美世界校招游戏剧情策划
全部 >
面经
面试常考问题整理
硬件/IC/嵌入式高薪--你应该看看这些公司和岗位
2022考研失败春招选手的群面攻略（适用于菜鸡互啄型）
0928携程笔试题解
全部 >
内推
员工内推码获取
字节电商｜预测算法｜社招/校招/实习内推
【TP-LINK北理工内推】2025届提前批启动，戳我内推！
【美团】校招社招内推，所有岗位，进度可查
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”