拼多多暑期实习笔试

四道题。一道水题，一道思维+前缀和，一道单调栈，一道贪心。

1. 给一个初始，以及一串操作，就，就，就，就，问最后能否走到，输出或者

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. 一个数他的子串如果能够被3整除，那么是一个好数。问中好数的个数。如，他的子串有，其中能被3整除。所以是一个好数。

• 次询问，每次给一个和一个，其中，

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. 个人从前往后站成一排，对于第个人，他的身高为，如果且，则说明第个人可以看到个人，以此类推。问所有人能看到人的数量的总和。

• 输入一个，以及个数表示每个人的身高。

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. 给两个字符串和，以及一个操作序列X = ，，依次取出操作序列中的整数，将。可以随意交换操作序列中的任意两个元素以及中任意两个字符。使得最终操作结束后的字典序最小。将其输出。

• 组输入，每组输入，以及操作序列，两个字符串和

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