Original link: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-299/

• https://www.cnblogs.com/Lanly/p/17344724.html

Problem D. Find by Query

Simple dichotomy.

Problem E. Nearest Black Vertex

First of all, the points in the circle must be all white, otherwise the conditions are not met.

Then the optimal state must be that the remaining points are all black. If this does not meet the conditions, then there must be no solution.

So as long as two bfs() are colored and checked separately. .

Problem F. Square Subsequence

The general idea is that substring problems are related to string algorithms, and subsequence problems are related to dynamic programming.

Then first you have to be able to make a string version, that is, given a string, determine how many non-repeating subsequences there are.

This is a classic question. https://leetcode.cn/problems/distinct-subsequences-ii/

The difficulty lies in how not to repeat or omit when counting. The method is to find a representative element for all elements in the same equivalence class. Here we of course find the earliest occurrence time, and then for each character in dp, we only need to start from The latest time can be transferred over (the late appearance has an inclusion relationship with the count of the early appearance).

In this way, the dp process is a simple transfer on the dag.

Consider this question again.

A simple idea is that dp[i][j] represents the number of solutions where the end of the first string is i and the end of the second string is j.

But we can’t complete deduplication as easily as the dp method above (examine aaa).

But in case of indecision, we can enumerate violently. . . The position of the enumeration is of course the initial position of the second string. . .

In this way, after dp, we only need to check that the position of the next closest start character of the second string to the end of the first string is exactly the position we enumerated. .

In this way, this problem is easily solved at the cost of complexity plus one dimension. (Then change backwards to forwards..)

Problem G. Minimum Permutation

Constructing the smallest lexicographic order reminds me of this question .

The first idea is a greedy structure, we look for the smallest number that the current position can take at each step.

  
   
#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;  
   
        }  
   
    }  
   
}  
   

Unfortunately, we have to examine all alternatives one by one at each step, so the complexity is O(n^2logn), which is TLE.

Then there’s a very neat stack-based approach.

My first reaction was to take a deque to record the candidate set, and then use a set to record the latest appearance time of the remaining elements , but after reading the code of kyopro_friends , I found that these are actually unnecessary (囧)

Just scan each position in order and use a stack to maintain the current answer. When the newly added number is better than the top element of the stack and does not affect the existence of the solution, pop the top element of the stack.

The existence of the solution only needs to record the moment when the current stack top element appears the latest, and the complexity is linear.

  
   
#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 xa[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

I freaked out when I saw berlekampMassey(), but it shouldn’t work…

This article is transferred from: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-299/
This site is only for collection, and the copyright belongs to the original author.