2022GDUT寒假專題學習-1 B,F,I,J題

• 2022 年 1 月 20 日
• 筆記
• 2022GDUT寒假專題訓練, STL

專題鏈接：專題學習1 – Virtual Judge (vjudge.net)

B – 全排列

題目

思想

這道題可以用DFS進行求解，但是一看到全排列，其實可以立刻想到一個STL函數：next_permutation(x.begin(),x.end()) （頭文件#include ）。

此函數可以按字典序給出當前排列的下一個排列（適用於可遍歷集合：string，數組，vector等）。

代碼

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    string a;
    cin >> a;
    do {
        cout << a << endl;
    } while (next_permutation(a.begin(), a.end()));
    return 0;
}

F – 地毯

題目

思想

二維差分，容斥原理。

根據一維差分，改變當前的數影響的是後面的數可知，二維差分中，改變當前的數影響的是右下角那一塊數。

由題目可知，我們操作的實際上是差分後的數組，操作完利用二維前綴和還原即可（由左上至右下）。

注意

1、n，m的範圍不確定，需使用動態數組，即二維vector。二維vector的初始化格式：

vector<vector > s(n + 1, vector(m + 1))；

初始化後即可當成普通數組使用。

代碼

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int> > s(n + 1, vector<int>(m + 1)), rmb(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> s[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            rmb[i][j] = s[i][j] + rmb[i - 1][j] + rmb[i][j - 1] - rmb[i - 1][j - 1];
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << rmb[c][d] - rmb[c][b - 1] - rmb[a - 1][d] + rmb[a - 1][b - 1] << endl;
    }
    return 0;
}

I – 滑動窗口

題目

思想

用STL中的雙頭隊列deque模擬單調隊列，存當前正在排隊的最值。

先考慮找最小值的情況：

如果當前的數比隊列末尾的數小，就將隊列末尾的數從尾部彈出，並從尾部插入當前數，這樣的話，此單調隊列里的數是從尾至頭逐漸減小的，隊列頭即使當前窗口的最小值。

當窗口離開隊列頭的數所在位置，將隊列頭彈出即可（利用下標判斷）。

注意

1、雙頭隊列deque里存的是pair<int,int> ，first是值，second是下標。

2、普通隊列queue中插入元素是從尾部back插入，彈出元素是從頭部front彈出，所以在操作雙頭隊列deque時最好將back看做尾部，front看做頭部，並優先從尾部back插入元素，以免混淆。

代碼

#include <deque>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
deque<pair<int, int>> minq, maxq;
queue<int> mina, maxa;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    minq.push_back(make_pair(a[1], 1));
    maxq.push_back(make_pair(a[1], 1));  //第一個數一定能入隊列
    for (int i = 2; i <= n; ++i) {
        while (!minq.empty()) {              //如果當前的數比隊列末尾的數小，就將
            if (a[i] < minq.back().first) {  //隊列末尾的數從尾部彈出
                minq.pop_back();
            } else
                break;
        }
        minq.push_back(make_pair(a[i], i));  // 從尾部插入當前數進行排隊
        //以上是最小值操作，下面重複的是最大值操作
        while (!maxq.empty()) {
            if (a[i] > maxq.back().first) {
                maxq.pop_back();
            } else
                break;
        }
        maxq.push_back(make_pair(a[i], i));
        //
        if (i > k) {
            if (minq.front().second == i - k) minq.pop_front();  //如果滑動窗口已經離開了當前隊列頭
            if (maxq.front().second == i - k) maxq.pop_front();  //的位置，那麼彈出隊列頭
        }
        if (i >= k) {
            mina.push(minq.front().first);  //存答案
            maxa.push(maxq.front().first);
        }
    }
    while (!mina.empty()) {
        cout << mina.front() << " ";
        mina.pop();
    }
    cout << endl;
    while (!maxa.empty()) {
        cout << maxa.front() << " ";
        maxa.pop();
    }
    return 0;
}

J – 最大連續和

題目

思想

這也是道狼題，可惡，一開始因為慣性思維一直在想這題怎麼貪，但因為題目對子序列有長度限制，故要用到上題剛寫的滑動窗口（這是朋友@77想到的思路，orz實在是太強了orz，這究竟是什麼級別的天才，什麼神仙智商才想得到）。

因為前綴和公式：單個數a[i] = sum[i] - sum[i-1] 或者某一塊的和如 A[2~5] = sum[5] - sum[1] ，所以我們就可以找每一個窗口的最大子序列和 = 當前窗口的最後一個數 – 當前窗口的最小值。

注意

1、因為前綴和公式中減的時候是減前一個數才能得到當前數，所以為了不漏掉數組中的第一個數，要把前綴和 a[0]也加入到滑動窗口的隊列中，並且滑動窗口的大小要比原來大一格。

即大小為m+1的滑動窗口從i = 0開始向右滑動，且窗口是從i = 0時的一格大逐漸增大到m+1格大。

代碼

#include <deque>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
deque<pair<ll, ll>> minq;
queue<pair<ll, ll>> mina;
ll a[N], b[N], minans[N], minid[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    m++;
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        a[i] = b[i] + a[i - 1];
    }
    minq.push_front(make_pair(a[0], 0));
    mina.push(make_pair(minq.back().first, minq.back().second));
    for (int i = 1; i <= n; ++i) {
        while (!minq.empty()) {
            if (a[i] < minq.front().first) {
                minq.pop_front();
            } else
                break;
        }
        minq.push_front(make_pair(a[i], i));
        if (i > m - 1) {
            if (minq.back().second == i - m) minq.pop_back();
        }
        if (i >= m - 1) {
            mina.push(make_pair(minq.back().first, minq.back().second));
        } else {
            mina.push(make_pair(minq.back().first, minq.back().second));
        }
    }
    int cnt = -1;
    while (!mina.empty()) {
        minans[++cnt] = mina.front().first;
        minid[cnt] = mina.front().second;
        mina.pop();
    }
    ll maxn = -0x7ffffffffff;
    for (int i = 1; i <= n; ++i) {
        if (i == minid[i])
            maxn = max(maxn, b[i]);
        else
            maxn = max(maxn, a[i] - minans[i]);
    }
    cout << maxn << endl;
    return 0;
}