笔试强训week3

day1

Q1 难度⭐

牛牛冲钻五_牛客小白月赛38 (nowcoder.com)

题目：
牛牛最近在玩炉石传说，这是一款一对一对战的卡牌游戏，牛牛打算努力冲上钻五分段，获得丰厚的天梯奖励。
炉石传说的段位可以用星数来表示，具体规则为：若牛牛本场失败，则扣除一星；若牛牛本场获胜，需要看牛牛是否触发了连胜奖励，若牛牛获得了至少三连胜（即本局对局的上一局和上上局都获胜）则获得k星，否则获得一星。
现在给出牛牛游玩的nnn场记录，请你判断牛牛最终的星数和初始星数的差。

思路：

记录是否连胜

#include <iostream>
using namespace std;int main() 
{int t;cin >> t;while(t--){int n, k;int score = 0;int m = 0;cin >> n >> k;while(n--){char ans;cin >> ans;if(ans == 'W') {m += 1;if(m < 3)score += 1;else if(m >= 3)score += k;}else if(ans == 'L'){m = 0;score -= 1;}}cout << score << endl;}return 0;
}

Q2 难度⭐⭐

最长无重复子数组_牛客题霸_牛客网 (nowcoder.com)

题目：
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

思路：

STL的set，双指针

class Solution 
{
public:int maxLength(vector<int>& arr) {set<int> s;int l = 0, r = 0;int ans = 0;while(l < arr.size() && r < arr.size()){if(!s.count(arr[r])){s.insert(arr[r]);r ++;ans = max(ans, r - l);}else{s.insert(arr[r]);s.erase(arr[l]);l ++;}}return ans;}
};

Q3 难度⭐⭐⭐⭐

重排字符串 (nowcoder.com)

题目：
小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排（只改变字母的顺序，不改变数量）
重排后小红想让新字符串不包含任意两个相同的相邻字母。
你能帮帮她吗？

输入描述：第一行一个正整数 n ，代表字符串的长度。
第二行为一个长度为 n 的、只由小写字母组成的字符串。

输出描述：如果可以完成重排，请在第一行输出一个“yes”，第二行输出重排后的字符串。
如果不能重排，则直接输出“no”

思路：

记录每个字母出现的次数
出现最多的次数 > 总数一半，输出no

否则将出现次数最多的字符添加到ans中，然后在剩余的字符中，选择出现次数最多的但不同的字符添加到ans中

#include <iostream>
#include <string>
using namespace std;int n, s[30];
char c;int main() 
{cin >> n;for(int i = 0; i < n; i ++) {cin >> c;s[c - 'a'] ++;}int num = 0, cnt = 0;for(int i = 0; i < 26; i ++){if(s[i] > num){num = s[i];cnt = i;}}if(2 * num > n + 1)cout << "no" << endl;else{cout << "yes" << endl;n -= num;string ans;while(num --){ans += (char)(cnt + 'a');for(int i = 0; i < 26 && n >= num; i ++){if(i != cnt && s[i]){s[i] --;ans += (char)(i + 'a');n --;}}}cout << ans << endl;}return 0;
}

day2

Q1 难度⭐⭐

乒乓球筐__牛客网 (nowcoder.com)

题目：
nowcoder有两盒（A、B）乒乓球，有红双喜的、有亚力亚的……现在他需要判别A盒是否包含了B盒中所有的种类，并且每种球的数量不少于B盒中的数量，该怎么办呢？

输入描述:输入有多组数据。每组数据包含两个字符串A、B，代表A盒与B盒中的乒乓球，每个乒乓球用一个大写字母表示，即相同类型的乒乓球为相同的大写字母。字符串长度不大于10000。

输出描述:每一组输入对应一行输出：如果B盒中所有球的类型在A中都有，并且每种球的数量都不大于A，则输出“Yes”；否则输出“No”。

思路：

map应用

#include <iostream>
#include <string>
#include <map>
using namespace std;int main() 
{string A, B;while(cin >> A >> B){map<char, int> AA, BB;for(int i = 0; i < A.size(); i++)AA[A[i]] ++;for(int j = 0; j < B.size(); j++)BB[B[j]] ++;for(int k = 'A'; k <= 'Z'; k++){if(BB[k] > AA[k]){cout << "No" << endl;break;}if(k == 'Z')cout << "Yes" << endl;}}return 0;
}

Q2 难度⭐

组队竞赛__牛客网 (nowcoder.com)

题目：
牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。
例如:
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。

输入描述：输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值.

输出描述：输出一个整数表示所有队伍的水平值总和最大值.

思路：

排序，求第2，4，6......个较大数的和。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 300000003;
int a[N];int main() 
{int n;cin >> n;for(int i = 0; i < 3*n; i++)cin >> a[i];sort(a, a + 3 * n);long long ans = 0;for(int i = 3 * n - 2; i >= n; i -= 2)ans += a[i];cout << ans;return 0;
}

Q3 难度⭐⭐⭐

删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com)

题目：
给定一个长度为 n 的仅包含正整数的数组，另外有一些操作，每次操作你可以选择数组中的任意一个元素 𝑎𝑖 ，同时数组中所有等于 𝑎𝑖−1 和 𝑎𝑖+1 的元素会被全部移除，同时你可以得到 𝑎𝑖 分，直到所有的元素都被选择或者删除。
请你计算最多能得到多少分。

输入描述：第一行输入一个正整数 n 表示数组的长度

第二行输入 n 个数字表示数组的各个元素值。

输出描述：输出能得到的最大分数。

思路：

dp

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5+4;
int a[N], dp[N];int main() 
{int n;cin >> n;int x = 0;for(int i = 1; i <= n; i ++){int k;cin >> k;a[k] ++;x = max(x, k);}dp[1] = a[1];int ans = 0;for(int i = 2; i <= x; i ++){dp[i] = max(dp[i - 1], dp[i - 2] + a[i] * i);ans = max(ans, dp[i]);}cout << ans;return 0;
}

day3

Q1 难度⭐

平方数 (nowcoder.com)

题目：
牛妹是一个喜欢完全平方数的女孩子。
牛妹每次看到一个数 x，都想求出离 x 最近的完全平方数 y。
每次手算太麻烦，所以牛妹希望你能写个程序帮她解决这个问题。
形式化地讲，你需要求出一个正整数 y，满足 y 可以表示成 a^2（a 是正整数），使得 |x-y| 的值最小。可以证明这样的 y 是唯一的。

思路：

开根号，求数及其+1的平方，判断与原数距离

#include <iostream>
#include <cmath>
using namespace std;int main() 
{long long n;cin >> n;long long m = sqrt(n);long long k = ((m + 1) * (m + 1) - n) > (n - m * m) ? m * m : (m + 1) * (m + 1);cout << k << endl;return 0;
}

Q2 难度⭐⭐⭐⭐

E-分组_牛客小白月赛40 (nowcoder.com)

题目：
dd当上了宣传委员，开始组织迎新晚会，已知班里有nnn个同学，每个同学有且仅有一个擅长的声部，把同学们分成恰好mmm组，为了不搞砸节目，每一组里的同学都必须擅长同一个声部，当然，不同组同学擅长同一个声部的情况是可以出现的，毕竟一个声部也可以分成好几个part进行表演，但是他不希望出现任何一组的人过多，否则可能会导致场地分配不协调，也就是说，她希望人数最多的小组的人尽可能少，除此之外，对组内人员分配没有其他要求，她希望你告诉她，这个值是多少，如果无法顺利安排，请输出-1

输入描述：第一行两个数个数n,m(1≤m≤n≤100000)表示人数
接下来一行n个数,a[i](1≤a[i]≤n)表示第i个学生的擅长声部

输出描述：输出一个数，表示人数最多的小组的人数

思路：

枚举可能的分组数与m比较，并且人数最多的组的人最少
二分查找满足条件的最少的人数

#include <iostream>
#include <unordered_map>
using namespace std;int n, m;
unordered_map<int, int> cnt;// 统计每种声部的人数bool check(int x)
{int g = 0;// 统计能分成多少组for(auto& [a,b] : cnt)g += b / x + (b % x == 0 ? 0 : 1);return g <= m;
}int main()
{cin >> n >> m;int hmax = 0;// 统计声部最多的人数for(int i = 0; i < n; i++){int x;cin >>x;hmax = max(hmax, ++cnt[x]);}int kinds = cnt.size();if(kinds > m)  cout << -1 << endl;else{int l = 1, r = hmax;while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << r << endl;}return 0;
}

Q3

【模板】拓扑排序_牛客题霸_牛客网 (nowcoder.com)

题目：
给定一个包含𝑛n个点𝑚m条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出−1。

输入描述：第一行输入两个整数𝑛,𝑚( 1≤𝑛,𝑚≤2⋅10^5)，表示点的个数和边的条数。
接下来的𝑚行，每行输入两个整数𝑢𝑖,𝑣𝑖 (1≤𝑢,𝑣≤𝑛)，表示𝑢𝑖到𝑣𝑖之间有一条有向边。

输出描述：若图存在拓扑序，输出一行𝑛个整数，表示拓扑序。否则输出−1。

思路：

day4

Q1 难度⭐

字符串替换_牛客题霸_牛客网 (nowcoder.com)

题目：
请你实现一个简单的字符串替换函数。原串中需要替换的占位符为"%s",请按照参数列表的顺序一一替换占位符。若参数列表的字符数大于占位符个数。则将剩下的参数字符添加到字符串的结尾。

给定一个字符串str，参数字符数组arg，请返回替换后的字符串。保证参数个数大于等于占位符个数。保证原串由大小写英文字母组成，同时长度小于等于500。

思路：

遍历str，碰见%s时输出arg

class Solution 
{
public:string formatString(string str, vector<char>& arg) {string ans;reverse(arg.begin(), arg.end());for(int i = 0; i < str.size(); i ++){if(str[i] == '%' && str[i + 1] == 's'){ans += arg.back();arg.pop_back();i ++;}else ans += str[i];}while(!arg.empty()){ans += arg.back();arg.pop_back();}return ans;}
};

Q2 难度⭐⭐

神奇数_牛客笔试题_牛客网 (nowcoder.com)

题目：
给出一个区间[a, b]，计算区间内“神奇数”的个数。
神奇数的定义：存在不同位置的两个数位，组成一个两位数（且不含前导0），且这个两位数为质数。
比如：153，可以使用数字3和数字1组成13，13是质数，满足神奇数。同样153可以找到31和53也为质数，只要找到一个质数即满足神奇数。

输入描述：输入为两个整数a和b，代表[a, b]区间 (1 ≤ a ≤ b ≤ 10000)。

输出描述：输出为一个整数，表示区间内满足条件的整数个数。

思路：

遍历a到b，判断是否为“神奇数”

#include <iostream>
#include <string>
using namespace std;bool yes[100];bool check(int x)
{string s = to_string(x);for(int i = 0; i < s.size(); i ++)for(int j = s.size() - 1; j >= 0; j --){if(s[i] == '0' || i == j) continue;int num = 10*(s[i] - '0') + (s[j] - '0');if(yes[num]) return true;}return false;
}int main() 
{int a, b;cin >> a >> b;yes[11] = yes[13] = yes[17] = yes[19] = yes[23] = yes[29] = yes[31] = yes[37] = yes[41] = yes[43] = yes[47] = yes[53] = yes[59] = yes[61] = yes[67] = yes[71] = yes[73] = yes[79] = yes[83] = yes[89] = yes[97] = true;int ans = 0;for(int i = a; i <= b; i++){if(i < 11) continue;ans += check(i);}cout << ans;return 0;
}

Q3 难度⭐⭐

DNA序列_牛客题霸_牛客网 (nowcoder.com)

题目：
一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。 G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目（也就是序列长度）。在基因工程中，这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。

给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。

DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等

数据范围：字符串长度满足 1≤𝑛≤1000 ，输入的字符串只包含 A/C/G/T 字母

输入描述：输入一个string型基因序列，和int型子串的长度

输出描述：找出GC比例最高的子串,如果有多个则输出第一个的子串

思路：

从前往后计算每一段的GC比例，输出最高的那段

#include <iostream>
#include <string>
using namespace std;int main() 
{string s;int n;cin >> s >> n;string res = "";int ans = -1;for (int i = 0; i < s.size(); ++i) {string tmp = s.substr(i, min(n, (int)s.size() - i));int cnt = 0;for (char c : tmp)if (c == 'G' || c == 'C')cnt++;if (cnt > ans) {res = tmp;ans = cnt;}}cout << res << endl;return 0;
}

day5

Q1 难度⭐

小乐乐改数字_牛客题霸_牛客网 (nowcoder.com)

题目：
小乐乐喜欢数字，尤其喜欢0和1。他现在得到了一个数，想把每位的数变成0或1。如果某一位是奇数，就把它变成1，如果是偶数，那么就把它变成0。请你回答他最后得到的数是多少。

思路：

将int改为string，判断每一位是否为偶数

#include <iostream>
#include <string>
using namespace std;int main() 
{int n, ans = 0;cin >> n;string s = to_string(n);for(int i = 0; i < s.size(); i ++){if((s[i] - '0') % 2 == 0) ans += 0;else ans += 1;if(i != s.size() - 1) ans *= 10;}cout << ans << endl;return 0;
}

Q2 难度⭐⭐

十字爆破_牛客小白月赛25 (nowcoder.com)

题目：
牛牛在玩一个游戏：
一共有n行m列共n*m个方格，每个方格中有一个整数。
牛牛选择一个方格，可以得到和这个方格同行、同列的所有数之和的得分。
例如：对于一个2*2的方格：
1 2
3 4
牛牛选择每个方格的得分如下：
6 7
8 9
因为1+2+3=6，1+2+4=7，1+3+4=8，2+3+4=9。
现在牛牛想知道下一步选择每个格子的得分情况，你可以帮帮他吗？

输入描述：第一行有两个正整数 n m，代表方格的行数和列数。（1≤n∗m≤1000000）
接下来的 n 行，每行有 m 个数 $a_{ij}$ ，代表每个方格中的整数。 $(-10^{9} \leq a_{ij}\leq 10^{9})$

输出描述：输出 n 行 m 列整数，分别代表选择每个位置方格的得分情况。

思路：

两次遍历计算每行和每列的和，最后每个位置结果为horizontal[i] + vertical[j] - nm[i][j]

#include <iostream>
#include <vector>
using namespace std;typedef long long LL;
LL horizontal[1000004], vertical[1000004];// 行  列int main() 
{int n, m;cin >> n >> m;vector<vector<LL> > nm(n + 1, vector<LL> (m + 1));for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++){scanf("%lld", &nm[i][j]);horizontal[i] += nm[i][j];}for(int i = 0; i < m; i ++)for(int j = 0; j < n; j ++)vertical[i] += nm[j][i];for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++)cout << horizontal[i] + vertical[j] - nm[i][j] << ' ';cout << endl;}return 0;
}

Q3 难度⭐⭐⭐

比那名居的桃子_牛客小白月赛37 (nowcoder.com)

题目：
小红有一天看到了一只桃子，由于桃子看上去就很好吃，小红很想把它吃掉。
已知吃下桃子后，每天可以获得 aia_iai 的快乐值，但是每天会获得 bib_ibi 的羞耻度。桃子的持续效果一共为 k 天。

小红想知道，自己在哪一天吃下果实，可以获得尽可能多的快乐值？

如果有多个答案获得的快乐值相等，小红希望获得尽可能少的羞耻度。
如果有多个答案的快乐值和羞耻度都相等，由于小红实在太想吃桃子了，她希望尽可能早的吃下桃子。

输入描述：第一行有两个正整数 n 和 k ，分别代表桃子的有效期总天数，以及桃子效果的持续天
数。

第二行有 n 个正整数 ai，分别代表每天可以获得的快乐值。

第三行有 n 个正整数 bi，分别代表每天可以获得的羞耻度。

$1 \leq k \leq n \leq 10^5$ ， $1 \leq a_i, b_i \leq 10^9$

输出描述：一个正整数，代表小红是第几天吃下桃子的。

思路：

一维前缀和

#include <iostream>
using namespace std;typedef long long LL;
LL a[100004], b[100004], a_sum[100004], b_sum[100004];int main() 
{int n, k;LL s1 = 0, s2 = 0;cin >> n >> k;for(int i = 0; i < n; i ++){cin >> a[i];a_sum[i] = s1 += a[i];}for(int i = 0; i < n; i ++){cin >> b[i];b_sum[i] = s2 += b[i];}LL mxA = 0, mnB = 0x3f3f3f, day = k;for(int i = k - 1; i < n ; i ++){if(mxA < a_sum[i] - a_sum[i - k]){mxA = a_sum[i] - a_sum[i - k];mnB = b_sum[i] - b_sum[i - k];day = i;}if(mxA == a_sum[i] - a_sum[i - k] && mnB > b_sum[i] - b_sum[i - k]){mxA = a_sum[i] - a_sum[i - k];mnB = b_sum[i] - b_sum[i - k];day = i;}}cout << day - k + 2;
}

day6

Q1 难度⭐

压缩字符串(一)_牛客题霸_牛客网 (nowcoder.com)

题目：
利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2bc5a3。
1.如果只有一个字符，1不用写
2.字符串中只包含大小写英文字母（a至z）。

思路：

双指针，从前往后遍历并计数

#include <string>
class Solution 
{
public:string compressString(string param) {string ans;int l = 0, r = 0, num = 0;while(r < param.size()){while(param[l] == param[r]){r ++;num ++;}ans += param[l];if(num > 1) ans += to_string(num);num = 0;l = r;}return ans;}
};

Q2 难度⭐⭐

chika和蜜柑 (nowcoder.com)

题目：
chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。
一共有n个蜜柑，chika吃k个蜜柑，将获得所吃的甜度之和与酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。
她想知道，最终的总酸度和总甜度是多少？

输入描述：第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000)
第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9）第二行有n个正整数
bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）

输出描述：两个正整数，用空格隔开。分别表示总酸度和总甜度。

思路：

贪心，Lambda表达式定义比较函数

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int n, k;cin >> n >> k;vector<pair<int, int>> Or(n + 1);for (int i = 1; i <= n; i++) cin >> Or[i].first;for (int i = 1; i <= n; i++) cin >> Or[i].second;sort(Or.begin() + 1, Or.end(), [](const auto& a, const auto& b) {if (a.second == b.second) return a.first < b.first;return a.second > b.second;});long long ans1 = 0, ans2 = 0;for (int i = 1; i <= k; i++) {ans1 += Or[i].first;ans2 += Or[i].second;}cout << ans1 << " " << ans2 << endl;return 0;
}

Q3 难度⭐⭐⭐

01背包_牛客题霸_牛客网 (nowcoder.com)

题目：
已知一个背包最多能容纳体积之和为v的物品
现有 n 个物品，第 i 个物品的体积为 vi , 重量为 wi
求当前背包最多能装多大重量的物品?

数据范围： 1≤𝑣≤1000， 1≤𝑛≤1000 ， 1≤𝑣𝑖≤1000， 1≤𝑤𝑖≤1000

思路：

01背包动态规划问题-CSDN博客

class Solution 
{
public:int knapsack(int V, int n, vector<vector<int> >& vw) {vector<int> f(V + 1);for(int i = 1; i <= n; i ++){for(int j = V; j >= vw[i - 1][0]; j --){f[j] = max(f[j], f[j - vw[i - 1][0]] + vw[i - 1][1]);}}return f[V];}
};