preface:

This design S T L STL Stack in STL ( A , B ) (A, B) (A,B), priority cohort ( C ) (C) (C) , and b i t s e t bitset bitset ( D ) (D) (D)

A - bottle with only one end open

A - bottle with only one end open

Idea:

If there are two stacks, all sequences can be popped out in order;

1 − > 2 , 2 − > 1 1 - > 2, 2 -> 1 1 − > 2, 2 − > 1 pop up each other, and the number needed until now will pop up to the end of the sequence

In this way, it is only necessary to determine whether two stacks are required:

Each time we insert a number, we judge whether it can be ejected into the sequence. Finally, if there is a number left in the stack, one stack cannot complete the operation, and two stacks are output as the answer.

The code is as follows:

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 4050, M = 16000057 * 2, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

int n, m;
stack<int> stk;

void solve()
{
    cin >> n;
    
    while (stk.size()) stk.pop();
    
    int res = 1;
    int t = 1;
    int x;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x;
        stk.push(x);
        while(stk.size() && stk.top() == t) stk.pop(), t ++;
    }
    
    if(stk.size()) res = 2;
    
    cout << res << endl;
}

signed main()
{
    fast;
    int T;
    cin >> T;
    while (T -- )
        solve();

    return 0;
}

B - train running

B - train running

Idea:

The outbound sequence is the input sequence, and the inbound sequence is 1 1 1 -> n n n

Once in the stack, judge whether the stack can be released according to the stack release sequence. If yes, continue to judge until all the trains are in the stack and judge the stack release sequence. If there are still trains in the stack, the stack release sequence is illegal

The code is as follows:

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 4050, M = 16000057 * 2, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

int n, m;
int a[N];
stack<int> stk;

signed main()
{
    fast;
    while (cin >> n)
    {
        while (stk.size()) stk.pop();
        
        for (int i = 1; i <= n; i ++ )
            cin >> a[i];
        
        int t = 1;
        
        for (int i = 1; i <= n; i ++ )
        {
            stk.push(i);
            while(stk.size() && stk.top() == a[t]) stk.pop(), t ++;
        }
        
        if(stk.size()) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}

C - Prefix K-th Max

C - Prefix K-th Max

Idea:

If inserted once s o r t sort sort a meeting T L E TLE TLE

Available S T L STL Priority queue in STL (small root heap here):

• If held in the priority queue k k k number, then its queue head is the evaluated value
• The time complexity is: O ( l o g k ) O(logk) O(logk)

The total complexity of the algorithm is: O ( ( n − k + 1 ) ∗ ( l o g k ) ) O( (n-k+1) * (logk) ) O((n−k+1)∗(logk)).

When there are k numbers in the queue, how to keep them in the priority queue k k k number?

• Insert a number first
• Pop up the team head and output the team head

Explain step 2:

• Judge the relationship between the number and the original team leader
• If it is larger than the original team head, the team head will pop up (i.e., this number); If the number is less than the original team head, the team head will pop up (the current team head is k + 1 k+1 k+1 is small and worthless); If equal to, pop up
• It is found that no matter whether it is greater than or equal to, the team head is ejected first, and then the team head is output

This is my conclusion!

The code is as follows:

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 5000010, M = 16000057 * 2, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

int n, m;
int a[N];
priority_queue<int, vector<int>, greater<int>> heap;

signed main()
{
    fast;
    
    cin >> n >> m;
    
    int x;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x;
        heap.push(x);
        if(i == m) cout << heap.top() << endl;
        else if(i > m)
        {
            heap.pop();
            cout << heap.top() << endl;
        }
    }
    
    return 0;
}

D - simple nonsense

D - simple nonsense

Idea: b i t s e t bitset bitset + D P DP DP

D P DP DP idea:
f [ i ] [ j ] f[i][j] f[i][j] indicates that the previous i i After i intervals, the answer is: j j Number of j

The state transition equation is: f[i][j] += f[i-1][j - k*k]

D P DP DP T L E TLE TLE code is as follows:

Time complexity: O ( n ∗ n ∗ m ) O(n*n*m) O(n ∗ n ∗ m) where: n = 100 , m = 10 0 3 n = 100, m = 100 ^ 3 n=100,m=1003

signed main()
{
    fast;
    
    cin >> n;
    
    f[0][0] = 1;
    int l, r;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> l >> r;
        for (int j = 1; j <= M; j ++ )
            for (int k = l; k <= r; k ++ )
                if(j >= k * k) f[i][j] += f[i - 1][j - k * k];
    }
    
    int res = 0;
    for (int i = 1; i <= M; i ++ )
        if(f[n][i]) res ++ ;
    
    cout << res << endl;
    
    return 0;
}

Define a b i t s e t bitset bitset d p [ 110 ] dp[110] dp[110]

• d p [ i ] dp[i] A representative of dp[i] f [ i ] [ j ] f[i][j] f[i][j] j j j position is not empty!
• I.e., exist f [ i ] [ j ] f[i][j] f[i][j] this is the case r e s res res ++
• The result is: d p [ n ] dp[n] In dp[n] 1 1 Number of 1

Ready to use b i t s e t bitset bitset array d p [ N ] dp[N] dp[N] equivalent to replace the above code d p [ N ] [ M ] dp[N][M] dp[N][M]

The following code is done with a circular array:

b i t s e t bitset bitset A C AC The AC code is as follows:

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 110, M = 1000010, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

int n, m;
int f[N][M];
bitset<M> dp, t; // 0000001000

signed main()
{
    fast;
    
    cin >> n;
    
    dp = 1;
    int l, r;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> l >> r;
        
        t.reset();
        for (int k = l; k <= r; k ++ )
            t |= (dp << k * k); 
            // All cases where dp[i] + is greater than k * k
            // Equivalent to for (int j = k * k; J < = m; j + +)
            //            dp[i][j] += dp[i-1][j - k * k]
            
        dp = t;
    }
    
    cout << dp.count() << endl;
    
    return 0;
}