旺苍网站建设,金乡网站建设哪家便宜,wordpress用户邮件营销插件,中国纪检监察报怎么订阅#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新拼多多近期的春秋招笔试题汇总#xff5e; #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新拼多多近期的春秋招笔试题汇总 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 清隆这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 清隆领取会在飞书进行同步的跟新。 文章目录 ☀️ 01.汉堡王优惠活动问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 02.二进制字符串的十进制值题目描述输入格式输出格式样例输入样例输出数据范围题解参考代码 ⛅️ 03.字符串消消乐问题描述输入格式输出格式样例输入样例输出样例解释数据范围题解参考代码 ☁️ 04.魔法秘境题目描述输入格式输出格式样例输入样例输出数据范围题解参考代码 写在最后 清隆这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 清隆领取会在飞书进行同步的跟新。 ☀️ 01.汉堡王优惠活动
问题描述
K小姐最喜欢到多哆村的金哆炸鸡店吃汉堡每个汉堡原价 10 10 10 元。为了回馈老顾客炸鸡店开展了拼团活动每找到一个朋友一起购买就可以减少 1 1 1 元但价格最低只能降到 5 5 5 元否则就要亏本啦。
现在 K小姐 手上有 N N N 元钱同时有 M M M 个朋友也想吃汉堡。K小姐 想知道自己最多能买多少个汉堡以及在买最多汉堡的情况下最少要花多少钱。
输入格式
第一行包含一个正整数 T T T表示测试用例的数量。
接下来 T T T 行每行包含两个正整数 N N N 和 M M M分别表示 K小姐 的钱数以及一起购买汉堡的朋友数量。
输出格式
对于每组测试用例输出一行包含两个整数分别表示 K小姐 能购买的最多汉堡数量以及购买最多汉堡时最少需要花的钱数。
样例输入
3
100 0
20 18
5 3样例输出
10 100
3 16
0 0数据范围 1 ≤ T ≤ 100 1 \leq T \leq 100 1≤T≤100 1 ≤ N ≤ 100050 1 \leq N \leq 100050 1≤N≤100050 0 ≤ M ≤ 1000 0 \leq M \leq 1000 0≤M≤1000
题解
本题的关键是判断能够凑成多少个优惠价 5 5 5 元的汉堡。
首先我们可以计算出朋友数量可以凑成的 5 5 5 元汉堡个数 t t t以及凑成这些汉堡后剩余的朋友数量 m m m。
如果 t t t 个 5 5 5 元汉堡的总价格超过了 K小姐 的钱数 N N N那么最多只能买 ⌊ N 5 ⌋ \lfloor \frac{N}{5} \rfloor ⌊5N⌋ 个汉堡花费 5 × ⌊ N 5 ⌋ 5 \times \lfloor \frac{N}{5} \rfloor 5×⌊5N⌋ 元。
否则在买完 t t t 个 5 5 5 元汉堡后如果剩下的钱加上剩余的朋友数量可以再凑成一个 10 − m 10-m 10−m 元的汉堡那么就再买一个并将剩下的钱按照 10 10 10 元一个汉堡的价格继续购买。如果不能凑成 10 − m 10-m 10−m 元的汉堡那么最多就只能买 t t t 个汉堡花费 5 × t 5 \times t 5×t 元。
参考代码
Python
T int(input())def solve():n, m map(int, input().split())t m // 5 # 5元汉堡个数m % 5if t * 5 n:print(n // 5, (n // 5) * 5)else:n - t * 5if n 10 - m:n - (10 - m)print(t 1 (n // 10), t * 5 10 - m (n // 10) * 10)else:print(t, t * 5)for _ in range(T):solve()Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int T sc.nextInt();while (T-- 0) {solve(sc);}}private static void solve(Scanner sc) {int n sc.nextInt();int m sc.nextInt();int t m / 5; // 5元汉堡个数m % 5;if (t * 5 n) {System.out.println((n / 5) ((n / 5) * 5));} else {n - t * 5;if (n 10 - m) {n - (10 - m);System.out.println((t 1 (n / 10)) (t * 5 10 - m (n / 10) * 10));} else {System.out.println(t (t * 5));}}}
}Cpp
#include iostreamusing namespace std;void solve() {int n, m;cin n m;int t m / 5; // 5元汉堡个数m % 5;if (t * 5 n) {cout n / 5 (n / 5) * 5 endl;} else {n - t * 5;if (n 10 - m) {n - (10 - m);cout t 1 (n / 10) t * 5 10 - m (n / 10) * 10 endl;} else {cout t t * 5 endl;}}
}int main() {int T;cin T;while (T--) {solve();}return 0;
}02.二进制字符串的十进制值
题目描述
K小姐特别喜欢二进制字符串。有一天博学的 A 先生在迁居时遇到了 K 小姐他准备考考她。
A先生每次会给K小姐一个长度为 n n n 的二进制字符串 s s s。他定义了一种新的子串 d i d_i di作为十进制表示形式为 s [ i : i − 1 ] s[i:i-1] s[i:i−1] 的数字可能有前导零。A 先生定义字符串的十进制值 f ( s ) f(s) f(s) 为所有有效的 d i d_i di 的总和换句话说 f ( s ) ∑ i 1 n − 1 d i f(s) \sum_{i1}^{n-1} d_i f(s)i1∑n−1di
例如对于字符串 s 1101 s1101 s1101 d 1 s [ 0 : 1 ] 11 d_1 s[0:1] 11 d1s[0:1]11 d 2 s [ 1 : 2 ] 10 d_2 s[1:2] 10 d2s[1:2]10 d 3 s [ 2 : 3 ] 01 d_3 s[2:3] 01 d3s[2:3]01
因此 f ( s ) 11 10 1 22 f(s) 11 10 1 22 f(s)1110122。
A 先生允许 K 小姐每次可以交换字符串的任意两个相邻元素最多可以进行 k k k 次操作。他问 K 小姐在进行操作后字符串的十进制值最小是多少。K 小姐喜欢分享于是她邀请你一起解决这个问题。
输入格式
第一行包含一个整数 t t t表示测试用例的数量。 ( 1 ≤ t ≤ 100 ) (1 \le t \le 100) (1≤t≤100)
对于每组测试用例
第一行包含两个整数 n n n 和 k k k分别表示字符串的长度和允许的最大操作数。 ( 2 ≤ n ≤ 1 0 5 , 0 ≤ k 1 0 5 ) (2 \le n \le 10^5, 0 \le k 10^5) (2≤n≤105,0≤k105)第二行包含一个长度为 n n n仅由 0 0 0 和 1 1 1 组成的二进制字符串 s s s。
输出格式
对于每组测试用例分别输出一行每行一个整数表示在最多可以进行 k k k 次操作后字符串的最小十进制值。
样例输入
2
5 0
10100
7 2
0010100样例输出
21
12数据范围 1 ≤ t ≤ 100 1 \le t \le 100 1≤t≤100 2 ≤ n ≤ 1 0 5 2 \le n \le 10^5 2≤n≤105 0 ≤ k 1 0 5 0 \le k 10^5 0≤k105
题解
观察可以发现中间部分的 ‘1’ 对答案的贡献不变只有首尾的 ‘1’ 贡献会不一样主要策略是尽量将 ‘1’ 移动到字符串的尾部从而减少由 ‘1’ 产生的高权重。首先尝试将最后一个 ‘1’ 尽可能右移如果剩余操作数还允许再将第一个 ‘1’ 尽可能左移。这样可以最大程度减少 ‘1’ 的有效出现次数从而降低总和。
参考代码
Python
def solve():n, k map(int, input().split())s input().strip()idx0 s.find(1)idx1 s.rfind(1)# Function to perform operation 0def op0(idx0):nonlocal kif idx0 -1:returnwhile k 0 and idx0 0:s_lst list(s)s_lst[idx0], s_lst[idx0 - 1] s_lst[idx0 - 1], s_lst[idx0]s .join(s_lst)k - 1idx0 - 1# Function to perform operation 1def op1(idx1):nonlocal kif idx1 -1:returnwhile k 0 and idx1 n - 1:s_lst list(s)s_lst[idx1], s_lst[idx1 1] s_lst[idx1 1], s_lst[idx1]s .join(s_lst)k - 1idx1 1if n - idx1 - 1 k:op1(idx1)op0(idx0)res 0for i in range(n - 1):res int(s[i:i 2])print(res)T int(input())
for _ in range(T):solve() Java
import java.util.Scanner;public class Main {static void solve() {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int k scanner.nextInt();String s scanner.next();int idx0 s.indexOf(1);int idx1 s.lastIndexOf(1);// 操作0将1向左移动Runnable op0 () - {if (idx0 -1) return;while (k 0 idx0 0) {char temp s.charAt(idx0);s.setCharAt(idx0, s.charAt(idx0 - 1));s.setCharAt(idx0 - 1, temp);k--;idx0--;}};// 操作1将1向右移动Runnable op1 () - {if (idx1 -1) return;while (k 0 idx1 n - 1) {char temp s.charAt(idx1);s.setCharAt(idx1, s.charAt(idx1 1));s.setCharAt(idx1 1, temp);k--;idx1;}};if (n - idx1 - 1 k)op1.run();op0.run();int res 0;for (int i 0; i n - 1; i)res Integer.parseInt(s.substring(i, i 2));System.out.println(res);}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int T scanner.nextInt();while (T-- 0)solve();}
} Cpp
#include bits/stdc.husing namespace std;void solve() {int n, k;cin n k;string s;cin s;int idx0 s.find(1);int idx1 s.rfind(1);// Function to perform operation 0auto op0 [](int idx0) {if (idx0 -1) return;while (k idx0) {swap(s[idx0], s[idx0 - 1]);k--;idx0--;}};// Function to perform operation 1auto op1 [](int idx1) {if (idx1 -1) return;while (k idx1 n - 1) {swap(s[idx1], s[idx1 1]);idx1;k--;}};if (n - idx1 - 1 k)op1(idx1);op0(idx0);int res 0;for (int i 0; i n - 1; i)res stoi(s.substr(i, 2));cout res \n;
}int main() {int T;cin T;while (T--)solve();return 0;
} ⛅️ 03.字符串消消乐
问题描述
LYA 最近沉迷于一款字符串消除游戏。游戏开始时LYA 会得到一个长度为 N N N 的仅由大小写字母构成的字符串 S S S。
游戏中LYA 可以重复执行以下操作从 S S S 中删除最长且最靠左的连续相同字符构成的子串。
LYA 想知道最少经过多少次操作后能够将整个字符串 S S S 删除完全。
输入格式
第一行包含一个整数 N N N表示字符串的长度 ( 1 ≤ N ≤ 100 , 000 ) (1 \leq N \leq 100,000) (1≤N≤100,000)。
第二行包含一个字符串 S S S表示游戏初始时的字符串。
输出格式
输出一个整数表示将字符串完全删除所需的最少操作次数。
样例输入
4
aBBa样例输出
2样例解释
第一次操作消除 BB剩下的字符串为 aa。 第二次操作消除 aa。
数据范围 1 ≤ N ≤ 100 , 000 1 \leq N \leq 100,000 1≤N≤100,000
题解
可以每次找到最长且最靠左的连续相同字符构成的子串将其删除。重复这一过程直到字符串为空。
具体实现时可以维护一个集合存储当前所有连续相同字符构成的子串的信息子串长度、左右端点位置。每次从集合中取出长度最大的子串删除并更新相邻子串的信息。重复此过程直到集合为空。
时间复杂度为 O ( N log N ) O(N \log N) O(NlogN)其中 N N N 为字符串长度。空间复杂度为 O ( N ) O(N) O(N)。
tips 据说直接暴力replace也能过哦
参考代码
Cpp
#include bits/stdc.h
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin n;string s;cin s;char last s[0];int cnt 1, left 0;mapint, arrayint, 3 mpl, mpr;setarrayint, 3 se;for (int i 1; i n; i) {if (s[i] ! last) {se.insert({-cnt, left, i - 1});mpl[left] {i - 1, last, cnt};mpr[i - 1] {left, last, cnt};left i;cnt 1;last s[i];} else {cnt;}}se.insert({-cnt, left, n - 1});mpl[left] {n - 1, last, cnt};mpr[n - 1] {left, last, cnt};int res 0;while (!se.empty()) {auto fi *se.begin();auto [cnt, l, r] fi;char lc mpr[l - 1][1];char rc mpl[r 1][1];if (lc rc) {int lidx mpr[l - 1][0];int ridx mpl[r 1][0];int lcnt mpr[l - 1][2];int rcnt mpl[r 1][2];se.erase({-lcnt, lidx, l - 1});se.erase({-rcnt, r 1, ridx});se.insert({-(lcnt rcnt), lidx, ridx});mpl.erase(r 1);mpr.erase(l - 1);mpl[lidx] {ridx, lc};mpr[ridx] {lidx, lc};}se.erase(fi);mpr.erase(l);mpl.erase(r);if (se.empty()) break;res;}cout res \n;return 0;
}☁️ 04.魔法秘境
题目描述
LYA 在探索一片神秘的魔法领地时发现了一个蕴含着强大魔法能量的秘境。这个秘境被划分为 n n n 个独特且连续的区域其中第 i i i 个区域的魔法能量值为 x i x_i xi。
为了最大化修炼效果LYA 计划施展一个强大的结界覆盖一系列连续的区域。然而施展结界需要消耗巨大的魔力只有当连续被覆盖的区域数量至少达到 m m m 个时施展结界才是划算的。
请你帮 LYA 计算出在结界覆盖的范围内每个区域的魔法能量的平均值最大可以达到多少。结果四舍五入保留三位小数。
输入格式
第一行包含一个整数 T T T表示测试用例的数量 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10。
对于每组测试用例 第一行为两个整数 n n n 和 m m m分别表示魔法区域的个数和结界至少需要笼罩的连续区域个数 1 ≤ m ≤ n ≤ 1 0 5 1 \leq m \leq n \leq 10^5 1≤m≤n≤105。 接下来的 n n n 行每行一个整数 x i x_i xi表示第 i i i 个区域的魔法能量值 1 ≤ x i ≤ 5000 1 \leq x_i \leq 5000 1≤xi≤5000。
输出格式
对于每组测试用例输出一行为结界覆盖范围内魔法能量的最大平均值结果四舍五入保留三位小数。
样例输入
1
8 3
4
5
6
7
9
9
6
8样例输出
8.333数据范围 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10 1 ≤ m ≤ n ≤ 1 0 5 1 \leq m \leq n \leq 10^5 1≤m≤n≤105 1 ≤ x i ≤ 5000 1 \leq x_i \leq 5000 1≤xi≤5000
题解
本题可以使用二分答案的思路来解决。可以二分枚举平均值判断是否存在一个长度至少为 m m m 的区间使得区间内的平均值大于等于当前二分的值。
具体地我们可以先求出数组的前缀和然后枚举区间右端点利用前缀和数组快速计算出区间和。如果区间长度大于等于 m m m且区间和大于等于二分的值与区间长度的乘积则说明当前二分的值是可行的可以缩小右区间否则需要缩小左区间。
最后二分的结果就是最大的平均值。
参考代码
Python
T int(input())
for _ in range(T):n, m map(int, input().split())arr [int(input()) for _ in range(n)]def check(avg):minv 0sum [0] * (n 1)for i in range(1, n 1):sum[i] sum[i - 1] arr[i - 1] - avgfor i in range(m, n 1):minv min(minv, sum[i - m])if sum[i] minv:return Truereturn Falsel, r 0, max(arr)while r - l 1e-5:mid (l r) / 2if check(mid):l midelse:r midprint(f{r:.3f})Java
import java.util.*;public class Main {static final int MAXN 100005;static int[] arr new int[MAXN];static double[] sum new double[MAXN];static int n, m;public static void main(String[] args) {Scanner sc new Scanner(System.in);int T sc.nextInt();while (T-- 0) {n sc.nextInt();m sc.nextInt();double l 0, r 0;for (int i 1; i n; i) {arr[i] sc.nextInt();r Math.max(r, (double) arr[i]);}while (r - l 1e-5) {double mid (l r) / 2;if (check(mid)) {l mid;} else {r mid;}}System.out.printf(%.3f\n, r);}}static boolean check(double avg) {for (int i 1; i n; i) {sum[i] sum[i - 1] arr[i] - avg;}double minv 0;for (int i m; i n; i) {minv Math.min(minv, sum[i - m]);if (sum[i] minv) {return true;}}return false;}
}Cpp
#include iostream
#include cstdio
#include algorithmusing namespace std;const int MAXN 100005;
int arr[MAXN];
double sum[MAXN];
int n, m;bool check(double avg) {for (int i 1; i n; i) {sum[i] sum[i - 1] arr[i] - avg;}double minv 0;for (int i m; i n; i) {minv min(minv, sum[i - m]);if (sum[i] minv) {return true;}}return false;
}int main() {int T;cin T;while (T--) {cin n m;double l 0, r 0;for (int i 1; i n; i) {cin arr[i];r max(r, (double) arr[i]);}while (r - l 1e-5) {double mid (l r) / 2;if (check(mid)) {l mid;} else {r mid;}}printf(%.3f\n, r);}return 0;
}写在最后 清隆这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 清隆领取会在飞书进行同步的跟新。
