---

前言：

本篇设计 $STL$ 中的 栈 $(A,B)$ ，优先队列 $(C)$ ，以及 $bitset$ $(D)$

---

A - 只有一端开口的瓶子

A - 只有一端开口的瓶子

思路：

若两个栈，则可以将所有序列按照顺序弹出；

$1->2,2->1$ 互相弹出，直到现在需要的数则弹出到序列末端

如此只需判断是否需要两个栈即可：

我们每插入一个数时判断能否弹出到序列中，最后如果栈中剩下数，则一个栈无法完成该操作，输出两个栈为答案。

代码如下：

#include 

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

---

B - 火车快跑

B - 火车快跑

思路：

出栈序列为输入的序列，入栈序列为 $1$ -> $n$

每入栈一次，判断能否按照出栈序列出栈，若可以则接着判断，直到所有火车都入栈，且判断玩出栈顺序，若栈中仍有火车，则该出栈顺序不合法

代码如下：

#include 

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

---

C - Prefix K-th Max

C - Prefix K-th Max

思路：

如果插入一次 $sort$ 一次会 $TLE$

可以利用 $STL$ 中的优先队列（此处指小根堆）：

• 如果优先队列中保持 $k$ 个数，则其队头即为所求值
• 时间复杂度为 $O(logk)$

则算法总复杂度为 $O((n-k+1)\ast (logk))$。

当队列中已经有 k 个数时，如何使优先队列中保持 $k$ 个数 ？

• 先插入一个数
• 弹出队头，输出队头

解释 步骤 2 ：

• 判断该数与原队头的关系
• 若大于 原队头 则弹出现队头（即、此数）；若该数小于 原队头 则弹出现队头（现队头为 $k+1$小的数，无价值）；若 等于 则弹出
• 发现无论大于小于等于都是先弹出队头，再输出队头

如此得出结论！

代码如下：

#include 

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

D - 简单瞎搞题

D - 简单瞎搞题

思路： $bitset$ + $DP$

$DP$ 思路：
$f[i][j]$ 表示：已经取了前 $i$ 个区间后答案为 $j$ 的个数

状态转移方程为：f[i][j] += f[i-1][j - k*k]

---

$DP$ 的 $TLE$ 代码如下：

时间复杂度： $O(n\ast n\ast m)$ 其中：$n=100,m=100^3$

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

定义一个 $bitset$ $dp[110]$

• $dp[i]$ 的一位代表 $f[i][j]$ 的 $j$ 位置不为空！
• 即、存在 $f[i][j]$ 这种情况 $res$ ++
• 如此结果即为 $dp[n]$ 中 $1$ 的个数

即用 $bitset$ 数组 $dp[N]$ 等效替换 上述代码的 $dp[N][M]$

下面代码采用循环数组做的:

$bitset$ 的 $AC$ 代码如下：

#include 

#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); 
            // dp[i] + 比 k * k 大的所有情况
            // 等效于 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46