1.15 360 2024校招笔试真题

1.15.1 ab串

【题目描述】

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

输入描述：

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

输出描述：

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

输入样例1：

输出样例1：

说明1：

ab到bba

输入样例2：

aab

输出样例2：

说明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;

}

1.15.2 神枪手

【题目描述】

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

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

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

现给出小马的得分规则：

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

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

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

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

参加运算的两个数，按二进制位进行或运算，只要两个数中的一个为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个整数为ai，表示每个气球对应的分值。

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

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

输出描述：

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

输入样例：

1 2 3

输出样例：

【解题思路】

暴力解法：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