360 2021校招笔试真题

1、ab串

【题目描述】

小明得到一个只包含a,b两个字符的字符串，但是小明不希望在这个字符串里a出现在b左边。现在他可以将“ab”这样的子串替换成“bba”，在原串中的相对位置不变。输出小明最少需要操作多少次才能让一个给定字符串所有a都在b的右边。

输入描述：

一个只包含a,b字符的字符串，长度不超过100000。

输出描述：

最小的操作次数。结果对1000000007取模。

输入样例1：

ab

输出样例1：

1

说明1：

ab到bba

输入样例2：

aab

输出样例2：

3

说明2：

aab到abba到bbaba到bbbbaa

【解题思路】
从右往左做操作，每次操作后，操作位置左边所有的a其右边的b的数量相当于增加了。那么就从右往左遍历字符串，维护一下每次操作右边有多少个b即可，然后统计答案。

【参考代码】
#include <bits/stdc++.h>
using namespace std;
#define modo 1000000007
int main() {
    char s[1000005];
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    long long ans = 0;
    long long b = 0;
    for (int i = n; i >= 1; i--) {
        if (s[i] == 'b')
            b++;
        else if (s[i] == 'a') {
            ans += b;
            b *= 2;
            ans %= modo;
            b %= modo;
        }
    }
    cout << ans << endl;
}

2、神枪手

【题目描述】

小马最近找到了一款打气球的游戏。

每一回合都会有n个气球，每个气球都有对应的分值，第i个气球的分值为a_i。

这一回合内，会给小马两发子弹，但是由于小马的枪法不准，一发子弹最多只能打破一个气球，甚至小马可能一个气球都打不中。

现给出小马的得分规则：

1)        若小马一只气球都没打中，记小马得0分。

2)        若小马打中了第i只气球，记小马得a_i分。

3)        若小马打中了第i只气球和第j只气球（i<j），记小马得a_i|a_j分。

（其中 | 代表按位或，按位或的规则如下：

参加运算的两个数，按二进制位进行或运算，只要两个数中的一个为1，结果就为1。

即0|0-0，1|0=1，0|1=1，1|1=1.

例：2|4即00000010 | 00000100 = 00000110，所以2|4=6 ）

现在请你计算所有情况下小马的得分之和。

输入描述：

第一行，一个整数n，表示此回合的气球数量。

第二行，用空格分开的n个整数，第i个整数为a_i，表示每个气球对应的分值。

对于其中60%的数据，1≤n≤1000，1≤a_i≤100000

对于另外40%的数据，1≤n≤50000，1≤a_i≤100000

输出描述：

一行一个整数，代表所有情况下小马的得分之和。

输入样例：

3

1 2 3

输出样例：

15

【解题思路】
暴力解法：O(n^2)
所有情况有三种，
一个气球没打破，0分。
打破一个气球，枚举打破了哪个气球，O(n)。
打破两个气球，枚举打破了哪两个气球，O(n^2)。
因此总时间复杂度为 O(n^2)。

优化解法：O(n log |最大值| )
在二进制上考虑，按位计算。
我们求二进制下，得分的每一位，在【分数和】中共出现了多少次，计算出至少含有一次的次数，再乘以对应的二进制数，即为对答案的总贡献。
枚举二进制下的每一位，O(logn)。
枚举每个气球，O(n)。
因此总时间复杂度为 O(n logn)。
【参考代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int a[N], cnt[40];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 30; j++) {
            if ((1 << j) & a[i]) {
                cnt[j]++;
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i <= 30; i++)