Problem D. Find by Query

简单二分。

Problem E. Nearest Black Vertex

首先圈内的点必须全部染白，否则不满足条件。
然后最优状态一定是剩下点全是黑，如果这也不满足条件那么一定无解了。
所以只要两个 bfs() 分别染色和检查即可。。

Problem F. Square Subsequence

一般的 idea 是子串问题和字符串算法有关，子序列问题和动态规划有关。
然后首先得会做一个串版本的，既给定一个字符串，判断有多少不重复的子序列。

这是一个经典问题。https://leetcode.cn/problems/distinct-subsequences-ii/

难点在于计数的时候如何不重不漏，方法就是对于同一个等价类中的所有元素，我们找到一个代表元，在这里我们当然找出现时刻最早的，然后 dp 的时候对于每个字符只要从最晚时刻转移过来即可（晚出现对于早出现的计数存在包含关系）。
这样这个 dp 过程就是一个简单的在 dag 上的转移。

再来考虑这个问题。
一个简单的想法是 dp[i][j] 表示第一个串的末尾是 i，第二个串的末尾是 j 的方案数。
但我们没法向上面的 dp 方法一样简单完成去重（考察 aaa）。

但是遇事不决我们可以暴力枚举。。。枚举的位置当然是第二个串的初始位置。。。
这样在 dp 之后，我们只需要检查第一个串的结尾的下一个最接近的第二个串的开始字符的位置恰好是我们枚举的位置即可。。
这样就以复杂度加一维的代价轻松的解决了这个问题。（然后把倒推改成顺推。。）

Problem G. Minimum Permutation

构造字典序最小，让人想起 这个题。
第一想法是贪心构造，我们每一步寻找当前位置所能取的最小的数。

#include <lastweapon/io>
using namespace lastweapon;
const int N = int(2e5) + 9;
SI t, c; VI a[N];
int n, m, p;

bool ok(int x) {
    int p = *lower_bound(ALL(a[x]), ::p);
    return *c.begin() >= p;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, m); REP(i, n) a[RD()].PB(i);
    REP_1(i, m) t.insert(i), c.insert(a[i].back()); p = 0;

    while (!t.empty()) {
        for (auto x: t) if (ok(x)) {
            p = *lower_bound(ALL(a[x]), p);
            printf("%d ", x); t.erase(x); c.erase(a[x].back());
            break;
        }
    }
}

遗憾的是，每一步我们都要一个一个考察所有备选情况，所以复杂度是 O(n^2logn)，会 TLE。
然后有一个非常巧妙的基于栈的方法。

我第一反应是 拿一个 deque 记录备选集合，再用一个 set 记录剩下元素最晚出现时刻，但是读了 kyopro_friends 的代码 之后发现这些其实都是不需要的（囧）
只需按顺序扫描每一个位置，并用一个栈维护当前的答案，当新加入的数字比栈顶元素更优，且不影响解的存在性时，弹出栈顶元素即可。
而解的存在性只需要记录当前栈顶元素最晚出现的时刻即可，复杂度线性。

#include <lastweapon/io>
using namespace lastweapon;
const int N = int(2e5) + 9;
int a[N], r[N]; stack<int> s; bool used[N];
int n, m;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, m); REP(i, n) r[RD(a[i])] = i;
#define x a[i]
#define y s.top()
    REP(i, n) if (!used[x]) {
        used[x] = 1;
        while (!s.empty() && x < y && r[y] > i) {
            used[y] = 0;
            s.pop();
        }
        s.push(x);
    }
    DWN(i, m, 0) {
        a[i] = y;
        s.pop();
    }
    REP(i, m) printf("%d ", x);
}

Problem Ex.

https://atcoder.jp/contests/abc299/submissions/40868354
看到 berlekampMassey() 我就吓傻了，但是应该没用吧…

Posted by xiaodao
Category: 日常