#include <iostream>
#include <cstring>

using namespace std;

string a, b;

char turn(char cur) 
{
    switch(cur) {
        case '*':
            return 'o';
        case 'o':
            return '*';
    }
}

int main() 
{
    cin >> a >> b;
    int res = 0;
    int len = a.length();

    for (int i = 0; i < len - 1; i++) {
        if (a[i] != b[i]) {
            a[i + 1] = turn(a[i + 1]);
            res++;
        }
    }
    cout << res << endl;
    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int m;
    cin >> m;

    for (; m --;) {
        string op;
        cin >> op;
        int x;

        if (op == "push") {
            cin >> x;
            stk[++ tt] = x;
        } else if (op == "pop") {
            tt --;
        } else if (op == "empty") {
            cout << (tt ? "NO" : "YES") << endl;
        } else {
            cout << stk[tt] << endl;
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1000010;

int n, k, a[N];
int q[N], hh, tt;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    // min
    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ ) {
        // 窗口移动，队列最左侧超出部分丢掉
        if (hh <= tt && q[hh] < i - k + 1) hh ++;  
        for (; hh <= tt && a[i] < a[q[tt]];) tt --;
        q[++ tt] = i;
        if (i - k + 1 >= 0) cout << a[q[hh]] << ' ';
    }

    cout << endl;
    // max
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++ ) {
        if (hh <= tt && q[hh] < i - k + 1) hh ++;
        for (; hh <= tt && a[i] > a[q[tt]];) tt --;
        q[++ tt] = i;
        if (i - k + 1 >= 0) cout << a[q[hh]] << ' ';
    }

    return 0;
}

题目链接 AcWing
s 为长串, p 为短串，n m 分别为他们的长度。输出所有 p 串在 s 串中的位置。
在暴力解法中：

for(int i = 1; i <= n; i++) {
    bool flag = true;
    for(int j = 1; j <= m；j++) {
        if(s[j - 1 + i] != p[j]) { 
            flag = false;
            break;
        }
    }
    if (flag) cout << i << ' ';
}

为什么下标从1开始也是正确的？不会漏第一位吗？

#include<iostream>

using namespace std;

const int N = 100010;
int n, a[N], tt, stk[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    for (int i = 0; i < n; i ++ ) {
        for (; tt && a[i] <= stk[tt];) tt --;
        if (tt) cout << stk[tt] << " ";
        else cout << -1 << " ";

        stk[++ tt] = a[i];
    }
    return 0;
}

几乎一模一样的题，只是判断条件改成了a[i] > 2 * a[j]。

题目链接 AcWing 785

疑问：
为什么 mid 改成 l + r >> 1 ，然后在比较的地方用 q[mid] 是错的，而
mid 用 q[l + r >> 1] ，然后在比较的地方用 mid 是正确的？

错误的代码：

void qs(int q[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    int i = l - 1, j = r + 1;
    for (;i < j;) {
        for (;q[++ i] < q[mid];);
        for (;q[-- j] > q[mid];);
        if (i < j) swap(q[i], q[j]);
    }
    qs(q, l, j);
    qs(q, j + 1, r);        
}

正确的代码：

void qs(int q[], int l, int r) {
    if (l >= r) return;
    int mid = q[l + r >> 1];
    int i = l - 1, j = r + 1;
    for (;i < j;) {
        for (;q[++ i] < mid;);
        for (;q[-- j] > mid;);
        if (i < j) swap(q[i], q[j]);
    }
    qs(q, l, j);
    qs(q, j + 1, r);        
}

错误的用例：

10
49 59 88 37 98 97 68 54 31 3

#include <iostream>

using namespace std;

const int N = 100010;

int q[N], hh, tt;

int main()
{
    int m;
    cin >> m;
    tt = -1;
    for (; m --;) {
        string op;
        cin >> op;
        int x;
        if (op == "push") {
            cin >> x;
            q[++ tt] = x;
        } else if (op == "pop") {
            hh ++;
        } else if (op == "empty") {
            cout << (tt < hh ? "YES" : "NO") << endl;
        } else {
            cout << q[hh] << endl;
        }
    }
    return 0;
}

1. Q: 为什么要保持栈内元素大小的单调递增特性？
   A: 由于栈内元素是递增的，所以比较次数一定是最少的，这就实现了优化。
2. Q: 如何保持栈内元素大小的递增性？
   A: 在依次出栈比较栈顶元素和当前数组元素大小的时候，如果栈顶元素小，那么找到目标值，将当前数组元素入栈，这样保持了栈内元素大小的递增性；如果栈顶元素大，那么栈顶指针左移，直到找到目标值，再将当前数组元素入栈，这样就保持了栈内元素大小的递增性。我们不必在意这个过程破坏了栈的结构，因为之前的数已经找到之前数组元素对应的目标值了。

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    int i = 0, j = m - 1;
    for (; i < n; i ++ ) {
        for (; j >= 0 && b[j] + a[i] > x;) j --;
        if (b[j] + a[i] == x) break;
    }
    cout << i << " "<<  j << endl;
    return 0;
}