四道題。一道水題，一道思維+前綴和，一道單調(diào)棧，一道貪心。

1. 給一個(gè)初始，以及一串操作，就，就，就，就，問最后能否走到，輸出或者

Input:

4 2
SDDSDD

Output:

0

#include <bits/stdc++.h>

using namespace std;

int main() {
	int x, y;
  	string s;
  	cin >> x >> y >> s;
  	for (char c : s) {
    	if (c == 'W') ++y;
      	if (c == 'S') --y;
      	if (c == 'A') ++x;
        if (c == 'D') --x;    
    }
  	puts((x | y) ? "NO" : "YES");
	return 0;
}

2. 一個(gè)數(shù)他的子串如果能夠被3整除，那么是一個(gè)好數(shù)。問中好數(shù)的個(gè)數(shù)。如，他的子串有，其中能被3整除。所以是一個(gè)好數(shù)。

• 次詢問，每次給一個(gè)和一個(gè)，其中，

Input:

2
10 20
9 80

Output:

8
57

Code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

LL s[120];

int isgood(int x) {
    if (x % 3 == 0) return 1;
    if (x < 10) return 0;
    int t0 = x % 10, t1 = x / 10;
    return (t0 % 3) != (t1 % 3); 
}

int main() {
    for (int i = 1; i <= 99; ++i) {
        s[i] = s[i - 1] + isgood(i);
    }

    int T;
    scanf("%d", &T);
    while (T -- ) {
        LL l, r;
        scanf("%lld%lld", &l, &r);
        if (r < 100) printf("%lld\n", s[r] - s[l - 1]);
        else if (l >= 100) printf("%lld\n", r - l + 1);
        else printf("%lld\n", s[99] - s[l - 1] + r - 99);
    }
    
    return 0;
}

3. 個(gè)人從前往后站成一排，對(duì)于第個(gè)人，他的身高為，如果且，則說明第個(gè)人可以看到個(gè)人，以此類推。問所有人能看到人的數(shù)量的總和。

• 輸入一個(gè)，以及個(gè)數(shù)表示每個(gè)人的身高。

Input:

5
5 4 3 2 1

Output:

10

Code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 2e5 + 10;

LL h[N];
int st[N], tt;

int main() {
    int n;    
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &h[i]);
    h[n + 1] = 1e9 + 1;
    st[++tt] = n + 1;
    LL ans = 0;
    for (int i = n; i >= 1; --i) {
        while (tt && h[st[tt]] < h[i]) --tt;
        if (st[tt] == n + 1) ans += st[tt] - i - 1;
        else ans += st[tt] - i;
    }
    printf("%lld\n", ans);
    return 0;
}

4. 給兩個(gè)字符串和，以及一個(gè)操作序列X = ，，依次取出操作序列中的整數(shù)，將?？梢噪S意交換操作序列中的任意兩個(gè)元素以及中任意兩個(gè)字符。使得最終操作結(jié)束后的字典序最小。將其輸出。

• 組輸入，每組輸入，以及操作序列，兩個(gè)字符串和

Input:

2
1 2
1 2
c
ab
6 5
2 1 1 2 2
pddedg
abcde

Output:

a
abdedg

Code:

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

char A[N], B[N];
int n, m, X[N];
bool st[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) scanf("%d", X + i);
        getchar();
        scanf("%s", A + 1); 
        getchar();
        scanf("%s", B + 1);
        for (int i = 1; i <= m; ++i) st[X[i]] = 1;
        sort(B + 1, B + 1 + m);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (!st[i]) printf("%c", A[i]);
            else printf("%c", B[++cnt]);
        }
        puts("");
    }
    return 0;
}