D - Interval Selection

Question

杨启韶年有一个长度为 $n$ 的数组，当且仅当 $a_l,a_{l+1},\dots a_r$ 中的每个元素在当前区间内恰好出现 $k$ 次时，数组中的子数组 $[l,r]$ 才是好数组。

例如，对于$a=[1,1,2,3,2,3,1]$和$k=2$，区间$[1,2]$、$[3,6]$、$[1,6]$等都是好的。但是，$[1,3]$不符合条件，因为元素$2$只出现了一次；$[1,7]$不符合条件，因为元素$1$出现了$3$次。

请帮助杨启绍年找出可以选择的好区间的个数。

• $n \le 2 \times 10^5$

Solution

想不到扫描线是真做不了

从左往右枚举右端点，然后判断左端点可以存在在那些位置，比如： $1,2,1,3,1,2,3$，$k=2$

先考虑 $1$，如果枚举到第三个 $1$，那么 $l$ 的位置可以在第一个 $(1,3]$ 也就是第一个 $1$ 和第二个 $1$ 之间

但是我们不仅仅之考虑 $1$，还需要考虑 $2,3$，所以最后 $l$ 的可行位置位于所有可行位置的交集

那么考虑如果维护这个交集，对于一个位置 $i$, 此时的数为 $a[i]$，对于这个 $a[i]$，那么我们只需要让 $(pos[a[i]][pos.size()-k-1],pos[a[i]][pos.size()-k]]$ 这个区间内为 $0$，其他地方为 $-1$，那么所有为 $0$ 的位置的交集就是 $l$ 所在的位置（其中 $pos[a[i]][j]$ 表示 $a[i]$ 第 $j$ 次出现的位置）

这个很容易用线段树来维护，只需要对每个 $i$，做区间加减就好了，每对一个 $i$ 需要还原上一个 $a[i]$ 的操作，然后进行次次操作

Code

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

typedef long long ll;
typedef pair<ll, ll> pll;

struct Node {
    pll sum;
    ll tag;
};

pll operator + (const pll &a, const pll &b) {
    if (a.first > b.first) return a;
    if (a.first < b.first) return b;
    return {a.first, a.second + b.second};
}
struct Segment_Tree {
    vector<Node> tr;
    int n;
    Segment_Tree(int n) : n(n), tr(n << 4) {}

    void push_up (int u) {
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    }

    void push_down (int u) {
        if (tr[u].tag) {
            tr[u << 1].tag += tr[u].tag;
            tr[u << 1].sum.first += tr[u].tag;
            tr[u << 1 | 1].tag += tr[u].tag;
            tr[u << 1 | 1].sum.first += tr[u].tag;
            tr[u].tag = 0;
        }
    }

    void build (int u, int l, int r) {
        tr[u].tag = tr[u].sum.first = 0; 
        tr[u].sum.second = r - l + 1;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    void update (int x, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            tr[x].tag += val;
            tr[x].sum.first += val;
            return;
        }
        push_down(x);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(x << 1, l, mid, ql, qr, val);
        if (qr > mid) update(x << 1 | 1, mid + 1, r, ql, qr, val);
        push_up(x);
    }

    pll query (int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tr[x].sum;
        push_down(x);
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(x << 1, l, mid, ql, qr);
        if (ql > mid) return query(x << 1 | 1, mid + 1, r, ql, qr);
        return query(x << 1, l, mid, ql, qr) + query(x << 1 | 1, mid + 1, r, ql, qr);
    }

};

int main() {
    freopen ("D.in", "r", stdin);
    ios::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) {
        int n, k; cin >> n >> k;
        ll ans = 0;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];
        auto a_ = a;
        sort(a_.begin() + 1, a_.end());
        a_.erase(unique(a_.begin() + 1, a_.end()), a_.end());
        for (int i = 1; i <= n; i++) a[i] = lower_bound(a_.begin() + 1, a_.end(), a[i]) - a_.begin();
        Segment_Tree T(n + 1);
        T.build(1, 1, n);
    
        int m = a_.size();
        vector<vector<int>> pos(m + 1, vector<int>());

        for (int i = 1; i <= m; i++) pos[i].push_back(0);

        for (int i = 1; i <= n; i++) {
            T.update(1, 1, n, pos[a[i]].back() + 1, i, -1);
            if (pos[a[i]].size() >= k + 1) 
                T.update (1, 1, n, pos[a[i]][pos[a[i]].size() - k - 1] + 1, pos[a[i]][pos[a[i]].size() - k], -1);
            pos[a[i]].push_back(i);
            if (pos[a[i]].size() >= k + 1)
                T.update (1, 1, n, pos[a[i]][pos[a[i]].size() - k - 1] + 1, pos[a[i]][pos[a[i]].size() - k], 1);
            
            auto q = T.query(1, 1, n, 1, i);
            if (q.first == 0) {
                ans += q.second;
                // cout << i << " " << q.second << endl;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

J - Ball

Solution

必然是围绕两个端点扫动扫过的面积最大

Code

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

typedef long long ll;

void solve() {
    ll L, x, y; cin >> L >> x >> y;
    if (x *x + y * y <= L * L) {
        cout << "Yes\n" << 0 << "\n"; 
    }
    else if ((L - x) * (L - x) + y * y <= L * L) {
        cout << "Yes\n" << L << "\n";
    }
    else {
        cout << "No\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

I - Fight Against the Monster

Solution

一个很典的题，肯定是先用 Create 生成机器，然后再 Fight 只需要机器人的数量大于等于 monster 的血量即可

二分答案 $x$

所以增加的 machine 的数量是 $((x-k)/(m-k)+1) \times k$

Code

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

typedef long long ll;

void solve() {
    ll m, k, h; cin >> m >> k >> h;
    
    if (h == 0) {cout << 0 << "\n"; return ;}

    ll L = 0, R = h;

    auto check = [&] (ll x) -> bool {
        if (x < m) return x >= h;
        if (m == k) return true;
        ll add = ((x - m) + (m - k)) / (m - k) * k;
        return add + x >= h;
    };

    while (L + 1 < R) {
        ll mid = (L + R) >> 1;
        if (check(mid)) R = mid;
        else L = mid;
    }

    cout << R << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

K - Strings, Subsequences, Reversed Subsequences, Prefixes

Question

给定两个字符串 $S,T$，求 $S$ 中有多少本质不同的子序列，包含前缀 $T$ 并且要求该子序列的反串也同时包含前缀 $T$

• $1\le N, M\le 10^6$

Solution

我们发现，其实符合条件的子序列只满足两种情况，例如 $T=ab$，第一种是 $ab\cdots ba$ 第二种是 $aba$ 表示前后缀融合在一起

对于第一种情况，我们先把头尾去掉，然后对中间的进行 DP，这是一个经典 DP：区间本质不同子序列

定义 $dp[i]$ 表示 $[1,i]$ 串的区间不同子序列，$lst[x]$ 表示 $x$ 上一次出现的位置

如果 $a[i]$ 在之前没有出现过，那么 $dp[i]=2dp[i-1]+1$，$1$ 表示不选前面的 $i-1$ 个字母，$2dp[i-1]$ 表示选或者不选 $a[i]$

如果 $a[i]$ 在之前出现过，那么就会有一部分算重复：

• 对于选 $a[i]$，那么 $dp[i-1]-dp[lst[a[i]]-1]$
• 对于不选 $a[i]$，那么 $dp[i-1]$

所以 $dp[i]=2dp[i-1]-dp[lst[a[i]]-1]$

考虑第二种情况，先从后往前找对称轴，例如：$abcada$ 中 $d$ 就是一个对称轴，然后考虑对称之后的串是否存在

我们可以提前预处理出正反串中每个字母匹配的位置，然后 $O(1)$ 判断即可

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int p = 7;

int n, m, l, r, dp[maxn], lst[30], ans;
string s, t;

void f1 () {
    for (int i = l + 1; i < r; i++) {
        if (lst[s[i]]) dp[i] = (dp[i - 1] * 2 - dp[lst[s[i]] - 1]) % MOD;
        else dp[i] = (dp[i - 1] * 2 + 1) % MOD;
        lst[s[i]] = i;
    }
    ans = (ans + dp[r - 1] + 1) % MOD;
}

void f2 (int x) {
    int tx, ty, k;
    tx = ty = 0; k = 1;
    for (int i = 0; i < m; i++) {
        tx = (tx * p + t[m - i - 1]) % MOD;
        ty = (t[m - i - 1] * k + ty) % MOD;
        k = k * p % MOD;
        if (tx == ty && i >= x - 1) ans += 1;
    }
}

signed main() {
    cin >> n >> m >> s >> t;
    int num = 0;
    for (l = 0; l < n; l++) {
        if (s[l] == t[num]) num += 1;
        if (num == m) break;
    }
    if (num < m) {
        cout << 0 << endl;
        return 0;
    }
    num = 0;
    for (r = n - 1; r > l; r--) {
        if (s[r] == t[num]) num += 1;
        if (num == m) break;
    }
    if (l < r) f1();
    f2(m - num);
    cout << (ans + MOD) % MOD << endl;
    return 0;
}