Topic links: Project Study 1 - Virtual Judge (vjudge.net)

B - Full Permutation

subject

thought

This problem can be solved by DFS, but when you see the full arrangement, you can immediately think of an STL function: next_permutation(x.begin(),x.end()) (header file #include).

This function can give the next permutation of the current permutation in dictionary order (applicable to traversable sets: string, array, vector, etc.).

code

#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 - carpet

subject

thought

Two dimensional difference, inclusion exclusion principle.

According to one-dimensional difference, changing the current number affects the following number. It can be seen that in two-dimensional difference, changing the current number affects the number in the lower right corner.

It can be seen from the title that what we operate is actually the differential array. After the operation, we can use the two-dimensional prefix and restore (from top left to bottom right).

be careful

1. The range of n and m is uncertain, so it is necessary to use dynamic array, that is, two-dimensional vector. Initialization format of 2D vector:

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

After initialization, it can be used as an ordinary array.

code

#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 - sliding window

subject

thought

The deque of the double headed queue in STL is used to simulate the monotonic queue and store the latest value of the queue currently being queued.

Consider finding the minimum value first:

If the current number is smaller than the number at the end of the queue, pop up the number at the end of the queue from the tail and insert the current number from the tail. In this way, the number in the monotonic queue gradually decreases from tail to head, even if the queue head is the minimum value of the current window.

When the window leaves the position of the number of queue headers, the queue header can be popped out (judged by subscript).

be careful

1. Pair < int, int > is stored in deque, where first is the value and second is the subscript.

2. The inserted elements in the ordinary queue are inserted from the tail back, and the ejected elements are ejected from the head front. Therefore, when operating the double headed queue deque, it is best to regard the back as the tail and the front as the head, and give priority to inserting elements from the tail back to avoid confusion.

code

#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));  //The first number must be in the queue
    for (int i = 2; i <= n; ++i) {
        while (!minq.empty()) {              //If the current number is smaller than the number at the end of the queue, the
            if (a[i] < minq.back().first) {  //The number at the end of the queue is popped from the end
                minq.pop_back();
            } else
                break;
        }
        minq.push_back(make_pair(a[i], i));  // Insert the current number from the tail to queue
        //The above is the minimum operation, and the following is the maximum operation
        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 the sliding window has left the current queue header
            if (maxq.front().second == i - k) maxq.pop_front();  //Then pop up the queue header
        }
        if (i >= k) {
            mina.push(minq.front().first);  //Save answer
            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 - maximum continuous sum

subject

thought

This is also a wolf problem. Damn it. At the beginning, I always thought about how greedy this problem is because of inertial thinking, but because the problem has a length limit on the sub sequence, I need to use the sliding window just written in the previous problem (this is a friend) @77 The thought of orz is really too strong (orz, what level of genius is it and What immortal IQ can you think of).

Because the prefix and formula: single number a[i] = sum[i] - sum[i-1] or the sum of a block, such as A[2~5] = sum[5] - sum[1], we can find the sum of the maximum subsequence of each window = the last number of the current window - the minimum value of the current window.

be careful

1. Because the current number can be obtained by subtracting the previous number in the prefix and formula, in order not to miss the first number in the array, the prefix and a[0] should also be added to the queue of the sliding window, and the size of the sliding window should be one grid larger than the original.

That is, the sliding window with the size of m+1 slides to the right from i = 0, and the window gradually increases from one grid size when i = 0 to m+1 grid size.

code

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