2023秋招笔试题记录-自用_任意输出两个3*3矩阵a和b,同时将数字矩阵转换成字符矩阵,并统计两个字符-程序员宅基地
小美的01串翻转（美团0819）
小美定义一个 01 串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。
例如，"10001"的权值是 1，因为只需要修改一次：对第三个字符取反即可。
现在小美拿到了一个 01 串，她希望你求出所有非空连续子串的权值之和，你能帮帮她吗？
输入描述
一个仅包含’0’和’1’的字符串，长度不超过 2000。
输出描述
所有非空子串的权值和。
示例1
输入
10001
输出
8
说明
长度为 2 的子串中，有 2 个"00"的权值是 1。
长度为 3 的 3 个子串权值都是 1。
长度为 4 的 2 个子串权值都是 1。
长度为 5 的 1 个子串权值是 1。
总权值之和为 2+3+2+1=8
思路与代码
前缀和模拟。
不难发现，最后的序列必然是 10101…或者是 010101…，因此对于长度为n的序列，最后的结果只有2种可能。枚举其中的最小值即可。
pres1和pres2分别表示两种可能的修改次数的前缀和。
枚举所有可能的子串，使用前缀和快速求得区间的修改次数（权值），叠加即可。
s = [int(c) for c in input()]
n = len(s)
# 枚举第一位就好了
s1 = list(s)
s2 = list(s)
s2[0] ^= 1
for i in range(1,n):
s1[i] = s1[i-1] ^ 1
s2[i] = s2[i-1] ^ 1
pres1, pres2 = [0]*(n+1),[0]*(n+1)
for i in range(1, n+1):
pres1[i], pres2[i] = pres1[i-1], pres2[i-1]
//需要改动，则次数+1
if s[i-1] != s1[i-1]: pres1[i] += 1
if s[i-1] != s2[i-1]: pres2[i] += 1
res = 0
//将不同情况字串的结果相加
for i in range(n):
for j in range(i+1,n):
res += min(pres1[j+1]-pres1[i], pres2[j+1]-pres2[i])
print(res)
小红的皇后(JD 0819)
来自 https://mp.weixin.qq.com/s/E9vgnAASzcuojHq8DDGasw
有一个n行m列的棋盘，有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发，每次移动她可以控制皇后进行以下三种方式中的一种:
1.向右移动若干个格子
2.向下移动若干个格子
3.向右下移动若干个格子。
用数学语言描述，当前的坐标在(x,y)时，每次移动可以到(x+k,y)或(x,y+k)或(x+k,y+k)其中k为任意正整数。移动的前提是，路径上没有障碍物。
小红想知道，皇后从左上角移动到右下角，最少要移动多少步?
输入描述
第一行输入两个正整数n和n，代表行数和列数。
接下来的n行，每行输入一个长度m的字符串，用来表示棋盘。
其中’.‘代表可以通过的位置，'*'代表障碍物。
保证左上角和右下角都不是障碍物。
1<=n,m<=2000。
输出描述
如果无法到达，请输出-1。
否则输出一个整数，代表最少的移动次数。
思路与代码：
记录到达每个点的步数，向三个方向走的时候每次尽可能走到最远；在遍历三个方向的过程中，首先需要判断一下当前节点和对应方向的上一个节点是否步数相同，如果相同，则说明可以一步到达，则没必要再遍历这个方向上的点，跳过此方向；否则则说明改变了前进方向，在当前节点的步数基础上+1才可到达下一个节点。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<char>> grid(n,vector<char>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
int dx[3]={
1,0,1};
int dy[3]={
0,1,1};
vector<vector<int>> distance(n,vector<int>(m,INT_MAX));
distance[0][0]=0;
queue<pair<int,int>> q;
q.push({
0,0});
while(!q.empty()){
auto current = q.front();
q.pop();
int x = current.first;
int y = current.second;
for(int i=0;i<3;i++){
//三种方向的试探
int oldX = x-dx[i];
int oldY = y-dy[i];
if(oldX>=0&&oldX<n&&oldY>=0&&oldY<m){
if(distance[oldX][oldY]==distance[x][y]){
continue;
}
}
int index=1;
do{
int newX = x+dx[i]*index;
int newY = y+dy[i]*index;
index++;
if(newX<0||newY<0||newX>=n||newY>=m||grid[newX][newY]=='*'){
break;
}
if(distance[newX][newY]>distance[x][y]+1){
//如果原先这个格子已经走过了，那么就将他更新为最近的最小值
distance[newX][newY] = distance[x][y]+1;
q.push({
newX,newY});
}
}while(true);
}
}
if(distance[n-1][m-1]==INT_MAX){
cout<<-1<<endl;
}
else{
cout<<distance[n-1][m-1]<<endl;
}
return 0;
}
小红吃药(JD 0819)
参考京东秋招0819-https://ujimatsu-chiya.github.io
小红准备买药治病。已知共有n种症状和m种药，第i种药可以治疗一些症状，但可能会导致一些副作用，添加一些新的症状。小红依次服用了一些药，请你告诉小红，当她每次服用一副药时，当前还有多少症状？
输入描述
第一行输入一个正整数n，代表症状的数量
第二行输入一个长应为n的01串，第i位是‘1’代表小红目前有第i个症状，第i位是‘0’代表没有该症状。
第三行输入一个正整数m，代表药的数量
接下来的2 * m行，每2行描述一副药:
第一行输入一个长度为n的01串，代表该药能治疗的症状。’1‘代表可以治疗，‘0’代表不能治疗。
第二行输入一个长度为n的01串，代表该药会产生的副作用。’1‘代表会产生该症状，’0‘代表不会产生。
接下来的一行，输入一个正整数q，代表小红服用的药数量。
接下来的q行，每行输入一个正整数u，代表小红服用了第u副药。
1<=n<=20
1<=m,q<=10^4
1<=ai,u<=m
保证每副药的副作用产生的症状和该药治疗的症状是不会重复的，即不会存在同一个位置的两个01串都是‘1’。
输出描述
输出q行，每行输入一个正整数，代表当前小红服用药后，身体有多少症状。
示例1
4
0101
3
1100
0010
0101
1000
1001
0000
3
2
3
1
输出
1
0
1
# include <bits/stdc++.h>
using namespace std;
const int N=10004;
int m1[N],m2[N],n,q,m;
int parse(string &s){
int x=0;
for(int i=0;i<n;i++)
x|=int(s[i]-'0')<<i;
return x;
}
int main(){
string s,t;
cin>>n>>s>>m;
int st=parse(s);
for(int i=1;i<=m;i++){
cin>>s>>t;
m1[i]=parse(s);
m2[i]=parse(t);
}
cin>>q;
int id;
while(q--){
cin>>id;
//((1<<n)-1)^m1[id]先将每一位都置反，st&= 然后再求与
//m1[i]是第i种药的治疗效果，与全1序列异或的结果是取反。最终将关键位置原本为1，先取反就变为了0，但非关键位全为1
//将((1<<n)-1)^m1[id]与st相与，导致关键位（此时为0）对应的下标的病症消失了，因为非关键位是全1，其他与病症无关的位还是原状。
st &= ((1<<n)-1)^m1[id];
//st |= m2[id];就是添加副作用病症
st |= m2[id];
cout<<__builtin_popcount(st)<<"\n";
}
}
分割序列（联想 0809）
来自：https://mp.weixin.qq.com/s/5-A_-HcahKScXnMopcVKyg
题目描述:
定义f(A)表示将序列A进行unique操作之后的序列的元素个数。unique 操作是指将相邻且相同的元素合成一个元素，再按照原序列的相对顺序进行排列之后得到的序列。例如，[1,1,1,2,2,3,3,1] 进行 unique 操作之后的序列为[1,2,3,1]; [1,2,3,3,2,1] 进行unique操作之后的序列为[1,2,3,2,1]; [1,1,1,1,1] 进行unique操作之后得到的序列为 [1]。
现在，输入一个长度为n的序列S，你需要将其划分为k段，使得每一段都不为空，且你需要最大化所有段的f函数的值之和。你只需要输出这个最大值就行。
输入描述
第一行两个正整数n,k(1<=k<=n<=10^5);
第二行n个由空格隔开的正整数a1,a2,…,an(1<=ai<=10000)，表示输入的序列S.
输出描述
输出一个整数，表示所求的最大值。
样例输入
8 3
1 1 1 2 2 3 3 1
样例输出
6
思路与代码
观察得出以下规律:
- 分割一次，肯定会让最后的结果变大。
- 如果切割一次，应该选择相邻且不同的位置切割，这操作可以使得f函数的值增大1。
因此，可以先算出在不切割的时候的f函数的值之和 res，最多可以切割k-1次，也就是最多可以使得res增大k-1次，只要有k-1个切割点满足相邻且不同。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
/**
* 1 1 1 2 2 3 3 1
*
* */
int[] a = new int[n];
int samecnt = 0;
int res = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
if (i > 0 && a[i] == a[i-1]) samecnt++;
if (i == 0 || a[i] != a[i-1]) res++;
}
//两种情况，取较小值
//可以来切分的相同序列长度 为较小值，就把他全切完
//可以来切分的相同序列长度 为较大值，那就把k-1次切割机会用完
System.out.println(res + Math.min(samecnt, k-1));
}
}
平均数为k的最长连续子数组(美团 0828)
给定n个正整数组成的数组，求平均数正好等于k 的最长连续子数组的长度。
输入描述
第一行输入两个正整数n和k，用空格隔开。
第二行输入n个正整数ai，用来表示数组。
1<=n<=200000
1<=k,ai<=10^9
输出描述
如果不存在任何一个连续子数组的平均数等于k，则输出-1。
否则输出平均数正好等于k的最长连续子数组的长度。
示例1
输入
5 2
1 3 2 4 1
输出
3
说明
取前三个数即可，平均数为2。
思路与代码
思维题+哈希表模拟。
平均数比较难处理，我们不妨将原数组中每个元素都-k，这样问题转换成找到和为0的最长子数组。
n,k = map(int, input().split())
a = [int(c) - k for c in input().split()]
res = 0
occ = {
}
occ[0] = -1
tmp = 0
for i in range(n):
tmp += a[i]
if tmp in occ:
//如果有某个键值与当前前缀和相等，那么这段连续子数组和为0
res = max(res, i - occ[tmp])
if tmp not in occ: occ[tmp] = i
print(res)
这段代码使用Python实现了一种计算数组中最长连续子串和为0的长度的方法。以下是代码的功能和步骤解释：
- 输入n和k，其中n表示数组的长度，k是一个整数。
- 输入数组a，其中包含n个整数，并将每个元素减去k。
- 初始化变量res为0，occ为一个字典。
- 将occ的初始键值对设置为{0: -1}，表示当和为0时的索引为-1。
- 初始化变量tmp为0。
- 遍历数组a的索引i从0到n-1：
- 将当前元素a[i]添加到tmp中。
- 如果tmp已经存在于occ中：
- 更新res为当前i与occ[tmp]之差的最大值。
- 如果tmp不存在于occ中：
- 将tmp作为键，将i作为值添加到occ中。
- 输出res，即连续子串和为0的最大长度。
这段代码通过维护一个累加和tmp，并利用字典occ来记录每个累加和第一次出现的索引。当出现重复的累加和时，通过计算当前索引与该累加和第一次出现的索引之间的差值来更新res。最后输出res作为结果。
请注意，代码的执行过程按照给定的步骤进行，并输出最终的res值。
求符合要求子串数量（oppo 0826）
一个字符串的权值定义为字符串中“oppo”子串的数量，例如，“oppoppo"的权值为 2，"opop"的权值为 0。
小欧有一个仅由’o’和’p’组成的字符串，他想知道这个字符串的所有子串的权值之和。
输入描述：
第一行输入一个仅由和‘o’和‘p’组成的字符串。
字符申长度不超过2x10^5。
输出描述
输出一个整数代表答案。
示例一：
输入
oppoppo
输出：
8
解释：
oppo权值为1，有2个oppo子串
oppop权值为1
oppopp权值为1
poppo权值为1
ppoppo权值为1
oppoppo权值为2
思路与代码：
长度为4枚举起点终点，如果是由oppo组成，其前面和后面的随便什么字符权值都可以为1，所以res加上前面和后面的字符组合个数就行，前面的字符个数可选择的为i+1,后面可选择的为len – j(包含oppo自身)，所以res+（I + 1）*(len - j).
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 2e5+10;
string s;
bool check(int l, int r) {
if (s[l] == 'o' && s[l+1] == 'p' && s[l+2] == 'p' && s[l+3] == 'o') return true;
return false;
}
int main() {
cin >> s;
int len = s.length();
ll res = 0;
for (int i = 0, j = i+3; j < len; i++, j++) {
if (check(i, j)) {
//中间结果注意转成long long 类型
res += 1ll*(i+1)*(len-j);
}
}
cout << res << "\n";
}
信号传递的最短时间（HW 0823）
在给定的 mxn 网格地图grid中，分布看一些信号塔，用来各区域间通信，每个单元格可以有以下三个状态:
值0代表空地，无法传递信号;
值1代表信号塔A，在收到消息后，信号塔A在1ms后可以将信号发送给上下左右四个方向的信号塔;
值2代表信号塔B，在收到消息后，信号塔B在2ms后可以将信号发送给上下左右四个方向的信号塔，
先给定一个坐标(j,k)输入保证坐标 (j,k)位置一定有信号塔，在坐标(,k)位置的信号塔触发一个信号
返回 网格地图中所有信号塔收到信号的最小时间，单位为ms。如果不可能，返回-1。
解答要求时间限制:C/C++100ms,其他语言: 200ms 内存限制:C/C++32MB,其他语言: 64MB
输入
网格的列数n
网格的行数m
触发信号的信号塔坐标(j,k)
第0行网格n个位置的信号塔安装信息(通过空格间隔每个状态值)
第m-1行网格n个位置的信号塔安装信息
输出返回 网格地图中所有信号塔收到信号的最小时间，单位为ms。如果不可能，返回-1。
样例1
输入
3
3
1 0
0 1 2
1 2 1
0 1 2
输出
4
解释:
在给定3x3的网格中，坐标(1,0)位置信号塔产生的信号经过4ms就可以传播给所有信号塔
思路与代码
迪杰斯特拉。
public class Main {
public static void main(String[] args) {
new Main().solve();
}
int m, n;
int[][] matrix;
void solve() {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
matrix = new int[m][n];
int sx = in.nextInt();
int sy = in.nextInt();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = in.nextInt();
}
}
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0] - b[0]);
int[][] DIS = new int[m][n];
for (int i = 0; i < m; i++) Arrays.fill(DIS[i], 1000001);
boolean[][] vst = new boolean[m][n];
q.add(new int[]{
0, sx, sy});
DIS[sx][sy] = 0;
int[][] dirs = {
{
0,1},{
1,0},{
0,-1},{
-1,0}};
while (!q.isEmpty()) {
int[] arr = q.poll();
int i = arr[1], j = arr[2];
if (vst[i][j])continue;
vst[i][j] = true;
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n || matrix[ni][nj] == 0) continue;
if (DIS[ni][nj] > DIS[i][j] + matrix[i][j]) {
DIS[ni][nj] = DIS[i][j] + matrix[i][j];
q.add(new int[]{
DIS[ni][nj], ni, nj});
}
}
}
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != 0)res = Math.max(res, DIS[i][j]);
}
}
if (res != Integer.MAX_VALUE)System.out.println(res);
else System.out.println(-1);
}
}
字符串处理模拟（HW 0823）
字符串处理器
产品代码需要设计一个带游标的字符串处理器，它需要实现以下功能:
插入:在游标所在处添加文本，其对应操作为insert str,insert表示插入操作命令关键字 (区分大小写)，str表示待操作的字符串，insert操作执行后将str拼接到游标当前位置，同时游标移动到str的右边;
删除:在游标所在处删除文本，其对应操作为delete len，delete表示删除操作命令关键字(区分大小写)，len为整数，表示删除游标左边字符串的长度，此时len要求大于等于0，如果len小于或len大于字符串长度，认为输入命名非法，不做任何处理;
移动:将游标往左或者往右移动，其对应操move cnt，move表示游标移动操作命令关键字(区分大小写)，cnt为整数，表示游标移动次数，cnt如果为负数时表示向左移动cnt次，如果为正数表示向右移动cnt次数，如果cnt等于0，则表示游标不移动，如果移动次数cnt超过字符串左右边界则认为输入命名非法，不做任何处理:
复制:将游标左边字符串复制并插入到游标的右边，游标位置不变(如果游标右边有字符，复制插入到游标和原有字符中间)，其对应操作为copy，copy表示复制操作命令关键字(区分大小写):
解答要求
时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++256MB,其他语言: 512MB
输入
支持输入多行，每个仅支持输入一个操作命令，当输入end结束操作命令关键字（区分大小写)时则代表操作停止。
首次执行时字符串处理器内部字符串为空，游标位置索引为0，此时字 符串处理器序列化结果为1。
1 <= str.length<= 40
1 <= len<= 40
-40 <= cnt<= 40
调用insert，delete，move和oopy的总次数不超过200次。
输出
当前字符串处理器的序列化结果，游标使用“i”来表示。
样例2
输入
insert test
insert hellohuawei
move -6
delete 5
insert practice
copy
end
输出
testpractice|testpracticehuawei
思路与代码
字符串模拟即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
String res = "";
int pos = 0; //游标
Scanner scanner = new Scanner(System.in);
while (true) {
String str = scanner.nextLine();
if (str.equals("end")) break;
String[] strs = str.split(" ");
if (strs[0].equals("insert")) {
res = res.substring(0, pos) + strs[1] + res.substring(pos);
pos += strs[1].length();
} else if (strs[0].equals("delete")) {
int _len = Integer.parseInt(strs[1]);
if (_len < 0 || _len > pos) continue;
res = res.substring(0, pos - _len) + res.substring(pos);
pos = pos - _len;
} else if (strs[0].equals("move")) {
int cnt = Integer.parseInt(strs[1]);
if ((cnt < 0 && pos + cnt < 0) || (cnt > 0 && pos + cnt > res.length())) continue;
pos += cnt;
} else if (strs[0].equals("copy")) {
res = res.substring(0, pos) + res.substring(0, pos) + res.substring(pos);
}
}
System.out.println(res.substring(0, pos) + "|" + res.substring(pos));
}
}
树中的最长路径（Bilibili 0829）
给定一个二叉树的 root ，返回 最长的路径的长度，这个路径中的每节点具有相同值。这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
树的节点数的范围是[0,10^4]
-1000 <= Node.val <= 1000
树的深度将不超过1000
示例1
输入
[5,4,5,1,1,5]
输出
2
示例2
输入[1,4,5,4,4,5]
输出
2
思路与代码
深度优先搜索，按照左、右、中进行遍历。对于每个节点，计算以当前节点为根的最长路径。对所有的最长路径取max即可。当前结点的左孩子的最长路径为left 当前结点的左孩子的最长路径为right 如果结点值等于左右孩子则加上对应的left和right。最后对于返回单侧最长路径，即max(left + 1, right + 1);
class Solution {
private:
int res;
public:
int longestUnivaluePath(TreeNode* root) {
res = 0;
dfs(root);
return res;
}
int dfs(TreeNode *root) {
if (root == nullptr) {
return 0;
}
int left = dfs(root->left), right = dfs(root->right);
int left1 = 0, right1 = 0;
if (root->left && root->left->val == root->val) {
left1 = left + 1;
}
if (root->right && root->right->val == root->val) {
right1 = right + 1;
}
res = max(res, left1 + right1);
return max(left1, right1);
}
};
代码使用了res“全局变量”，dfs函数返回的是单侧的最长路径，全局最长路径则是用res更新
寻找字典序最小的数（淘天 0824）
题目描述：
小红有一个01字符串，她可以进行最多。次提作，每次提作司以交换相邻的两个字符，问可以得到的字典序最小的字符串是什么
输入描述：
一行两个整数n和人，表示字符串的长度和可以进行的操作次数接下来一行一个长度为n的01字符串。1<n<1051<k<109
输出描述：
输出一个长度为n的字符串，表示字典序最小的字符串。
示例1：
输入
5 2
01010
输出
00101
思路与代码：
双指针模拟，将第一个出现在1后面的0与最前面的1交换，若需要交换次数大于k,则后移指向1的指针，满足交换次数小
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();;
int k = sc.nextInt();
sc.nextLine();
char[] input= sc.nextLine().toCharArray();
int indexOne = -1, indexZero = -1;
for (int i = 0; i < input.length; i++) {
if(input[i] == '1'){
indexOne = i;
break;
}
}
for (int i = input.length - 1; i >= indexOne ; i--) {
if(input[i] == '0'){
indexZero = i;
}
}
if(indexZero == -1 || indexOne == -1){
print(input);
return;
}
while(k > 0){
if(indexZero - indexOne <= k) {
k -= (indexZero - indexOne);
swap(input, indexOne, indexZero);
}else{
while(indexZero - indexOne > k){
//找到连续的1序列
while(input[indexOne] != '1') indexOne++;
}
indexOne++;
swap(input, indexOne, indexZero);
k -= (indexZero - indexOne);
}
int[] next = nextPos(input, indexOne, indexZero);
indexOne = next[0];
indexZero = next[1];
}
print(input);
}
public static void print(char[] input){
for (char c : input) {
System.out.print(c);
}
}
public static void swap(char[] input, int i, int j){
char temp = input[i];
input[i] = input[j];
input[j] = temp;
}
public static int[] nextPos(char[] input, int indexOne, int indexZero){
for(int i = indexOne; i < input.length; i++){
if(input[i] == '1'){
indexOne = i;
break;
}
}
for (int i = indexZero; i < input.length; i++) {
if(input[i] == '0'){
indexZero = i;
break;
}
}
return new int[]{
indexOne, indexZero};
}
}
小红的数字匹配(科大讯飞0715)
定义一个“模板串”为一个由数字字符和′?"组成的字符串。我们可以通过将问号替换成数字字符来得到正整数。显然，一个模板串可能会和多个正整数匹配。例如: “1?2"可以和102或者132等正整数匹配。请注意，匹配的正整数不能包含前导零，例如”??1"可以匹配101，但不能匹配001。小红拿到了一个模板串，她想知道，和这个模板串匹配的正整数中，第k小的是多少?
输入描述
第一行输入一个正整数t，代表询问次数。接下来的2* t行，每两行为一次询问: 第一行输入一个字符串，仅由数字字符和?'组成。第二行输入一个正整数k，代表询问的是第k小。
1≤t ≤ 10^4 1≤k≤10 ^9
字符串长度不超过30。
输出描述
输出t行，每行输出一个答案。如果一共都没有k个匹配的正整数，则输出-1。否则输出第小的匹配的正整数。
示例1
输入
4
??1
1
22?
100000000
2??
3
000???
1
输出
101
-1
202
-1
思路与代码
第k个元素等价于将k的十进制数的每一个数位，依次替换原字符串中的"?"即可。注意处理前导”?“的情况，由于答案不能出现前导0，因此，如果第一个数位为”0“，则+1。
#include <iostream>
#include <string>
using namespace std;
void solve() {
string input;
getline(cin, input);
//使用 const_cast 将 const char* 类型的指针 input.c_str() 转换为 char* 类型的指针 s
char* s = const_cast<char*>(input.c_str());
int k;
cin >> k;
cin.ignore();
int wh = 0;
for (char c : input) {
if (c == '?') {
wh++;
}
}
if ((s[0] == '?' && pow(10, wh - 1) * 9 < k) || (s[0] != '?' && pow(10, wh) < k) || (s[0] == '0')) {
cout << -1 << endl;
return;
}
string strk = to_string(k - 1);
reverse(strk.begin(), strk.end());
bool flag = false;
if (s[0] == '?') flag = true;
int n = input.length();
int j = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '?') {
if (j < strk.length()) {
s[i] = strk[j];
j++;
} else {
s[i] = '0';
}
}
}
if (flag) s[0] += 1;
cout << s << endl;
}
int main() {
int t;
cin >> t;
cin.ignore();
for (int i = 0; i < t; i++) {
solve();
}
return 0;
}
数字迷宫（蔚来0830）
题目描述：
牛牛困在了数字迷宫里面，该数字迷宫是一个nxn的字符矩阵，它由字符’#’，’.’，’*’组成。
其中：
‘#’代表该位置存在障碍，牛牛不能经过他，但是牛牛可以花费a代价消除该障碍。
‘.‘代表该位置牛牛可以随意移动，无需代价。
‘’代表传送门，牛牛可以使用它并花费b代价传送到迷宫中另外一个‘’的位置。注意传送门是非强制性的，牛牛可以经过它但不使用它。
牛牛每次可以从位置(x, y):
要么向上移动一格，到(x, y+1)；
要么向下移动一格，到(x, y-1)；
要么向左移动一格，到(x-1, y)；
要么向右移动一格，到(x+1, y)；
当然，牛牛不能走到迷宫外面去。
牛牛的起点在(1, 1)，他想知道走到迷宫出口(n, n)所需的最小代价是多少？
输入描述：
第一行输入三个正整数n, a, b，其意义如题意所述。
1≤a, b≤1000
2≤n≤1000
接下来n行，每一行一个长度为n的字符串，以次来表示数字迷宫 注意：
起点和终点位置不能是’#‘，但可以是’*’和’.’。
迷宫中’*’的数量要么为0，要么为2。
输出描述：
输出一行一个整数，表示牛牛走出迷宫所花费的最小代价
示例：
// 输入1
2 5 10
*#
#*
// 输出1
5
// 输入2
5 2 3
.....
.###.
.###.
.###.
.....
// 输出2
0
思路：
单源最短路问题，dijkstra算法。注意处理障碍物和传送门，要加上a或b
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, a, b;
cin >> n >> a >> b;
vector<string> matrix(n);
for(int i = 0; i < n; i++) {
cin >> matrix[i];
}
vector<vector<int>> portals;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '*') {
portals.push_back(vector<int>{
i,j});
}
}
}
//优先队列比较器，使用Lamda函数实现
//比较vector的最后一个元素大小，大的放在后边，小的放在前边，实现一个小顶堆的结构
auto cmp = [](const vector<int>& v1, const vector<int>& v2) {
return v1.back() > v2.back();
};
priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pQue(cmp);
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
vector<vector<int>> isVisit(n, vector<int>(n, 0));
vector<vector<int>> dirs{
{
0, 1}, {
0, -1}, {
1, 0}, {
-1, 0}};
dist[0][0] = 0;
isVisit[0][0] = 1;
pQue.push(vector<int>{
0, 0, 0});
while(!pQue.empty()) {
vector<int> vecCur = pQue.top();
pQue.pop();
int curX = vecCur[0]; int curY = vecCur[1];
if(curX == portals[0][0] && curY == portals[0][1]) {
int x = portals[1][0]; int y = portals[1][1];
if(!isVisit[x][y]) {
if(dist[x][y] > dist[curX][curY] + b) {
dist[x][y] = dist[curX][curY] + b;
isVisit[x][y] = 1;
pQue.push(vector<int>{
x, y, dist[x][y]});
}
}
}
else if(curX == portals[1][0] && curY == portals[1][1]) {
int x = portals[0][0]; int y = portals[0][1];
if(!isVisit[x][y]) {
if(dist[x][y] > dist[curX][curY] + b) {
dist[x][y] = dist[curX][curY] + b;
isVisit[x][y] = 1;
pQue.push(vector<int>{
x, y, dist[x][y]});
}
}
}
for(auto d: dirs) {
int x = curX + d[0];
int y = curY + d[1];
if(x < 0 || y < 0 || x >= n || y >= n || isVisit[x][y]) {
continue;
}
if(matrix[x][y] =='#') {
if(dist[x][y] > dist[curX][curY] + a) {
dist[x][y] = dist[curX][curY] + a;
isVisit[x][y] = 1;
pQue.push(vector<int>{
x, y, dist[x][y]});
}
}
else {
if(dist[x][y] > dist[curX][curY]) {
dist[x][y] = dist[curX][curY];
isVisit[x][y] = 1;
pQue.push(vector<int>{
x, y, dist[x][y]});
}
}
}
}
cout << dist[n-1][n-1] << endl;
return 0;
}
手机流畅运行的秘密（小米0902）
时间限制: 1000MS内存限制: 65536KB
题目描述:
8月份发布会一结束，米小兔就在公司领到了一台最新发布的Xiaomi MIX Fold 3手机，这是一款小米旗舰折叠屏手机，并搭载了全新升级架构的MIU114系统。其先进的应用引擎不仅让系统更流畅，应用体验也大幅提升。
在一个优化项中，为了尽可能提升用户白天使用手机的体验和续航，某些已经在系统中注册过的任务会被设置为空闲任务，仅在手机空闲时运行 (比如数据备份或AI相册整理)。现在系统中注册了若干组空闲任务，每个任务有各自的耗电量以及允许任务运行的最低初始电量，我们需要计算手机能够串行完成全部任务的最低初始电量。
注意点1: 所有电量以mAh(毫安时)计，Xiaomi MIX Fold 3的大电池容量是4800mAh。
注意点2:本题目假设手机在运行空闲任务期间，不处于充电状态，也没有额外耗电行为。
注意点3:智能应用引擎会以最合适的顺序串行运行任务。
输入描述
一个描述了所有任务的长字符串。任务与任务之间用逗号阳开，每组任务由耗电量及最低初始电量组成，用冒号限开。
输出描述
一个数字，代表依次完成全部任务的最低初始电量，如果最低初始电量超过手机电池容量，则返回-1。
样例输入
1:10,2:12,3:10
样例输出
13
提示
在样例中，手机至少需要有13mah的初始电量，在运行任务2后剩余电量11mAh、运行任务1后剩余电量10mah、运行任务3后剩余7mah。
思路与代码
基本是leetcode的一道原题（哪道原题？），核心思想是 贪心+排序，思考一下任务a和任务b谁排在前面？一种思路是：计算先a需要的电量 和 先b需要的电量，两者中最小的那个对应的任务排在前面；
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;
int main () {
string s; cin >> s;
int n = s.size();
vector<vector<ll>> a;
//提取出所需的信息
for (int i = 0; i < n; ++i) {
int j = i;
while (j < n && s[j] != ',') ++j;
string ss = s.substr(i, j - i);
int p = ss.find(':');
a.push_back({
stoll(ss.substr(0, p)), stoll(ss.substr(p + 1))});
i = j;
}
//排序原则，看b和c哪个放在前边启动需要的电量更小
//如果b先启动，为了满足b和c都能运行，
//那么需要的最低电量为b的门槛电量，加上执行c比b的门槛高多少（差值），然后加上执行b所需耗费的电量
//这样就能满足先执行b，耗费了b[0]电量之后还能高于执行c的门槛,
sort(a.begin(), a.end(), [](vector<ll>& b, vector<ll>& c){
// 先b
int f1 = b[1] + max(0LL, c[1] - b[1] + b[0]);
// 先c
int f2 = c[1] + max(0LL, b[1] - c[1] + c[0]);
return f1 < f2;
});
int m = a.size();
ll sum = a[0][1], r = a[0][1] - a[0][0], MAX = 4800;
for (int i = 1; i < m; ++i) {
if (r >= a[i][1]) r -= a[i][0];
else {
//如果剩余的电量r不够完成第i项任务的门槛,那么就提高结果的标准
//结果的标准在试错中逐步提升
sum += a[i][1] - r;
//确立新的"剩余电量"，中间如果"剩余变量"不够，需要向上调整sum
r = a[i][1] - a[i][0];
}
}
if (sum > MAX) cout << -1;
else cout << sum;
}
不同高度的士兵（微众银行0902）
酷酷的小明准备和小伙伴们展示他捏出来的超酷的橡皮泥士兵。在展示之前，小明发现有些橡皮泥士兵大小十分相似甚至相同，这让小明感觉不是很酷，因为小明想要他的橡皮泥作品都有自己的风格，即使是大小也要有区别。小明的n个橡皮泥士兵的大小分别为a1,a2…an，小明可以通过给某个士兵加一单位皮泥来使得其大小增加一单位。小明想知道如果他想要让所有的橡皮泥士兵大小都不相同，至少需要一共加多少单位橡皮泥。
输入描述
第一行1个整数n，表示小明的橡皮泥士兵数量.
第二行n个整数a1a2…an，分别表示小明的橡皮泥士兵的大小。
对于100%的数据，1<=n<=50000,1<=ai<=100000
输出描述
输出一行一个整数表示总共至少加多少单位的橡皮泥.
样例输入
5
1 1 2 3 3
样例输出
5
思路
将数组排序，进行遍历，根据泥士兵大小是否相等分别处理
要让所有的橡皮泥士兵大小都不相同，我们需要对大小相同的士兵进行调整。我们可以采取以下方法：
- 将士兵的大小进行排序，从小到大。
- 遍历排序后的士兵大小，检查当前士兵和前一个士兵的大小是否相同。
- 如果相同，需要将当前士兵的大小增加至少1单位，使其与前一个士兵的大小不同。
- 累加所有的调整单位数，即为答案。
具体的算法实现如下：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n;
std::cin >> n;
std::vector<int> soldierSizes(n);
for (int i = 0; i < n; ++i) {
std::cin >> soldierSizes[i];
}
std::sort(soldierSizes.begin(), soldierSizes.end());
int minUnits = 0;
for (int i = 1; i < n; ++i) {
if (soldierSizes[i] <= soldierSizes[i - 1]) {
minUnits += soldierSizes[i - 1] - soldierSizes[i] + 1;
soldierSizes[i] = soldierSizes[i - 1] + 1;
}
}
std::cout << minUnits << std::endl;
return 0;
}
这段代码首先读取士兵数量 n 和每个士兵的大小，然后对大小进行排序。接下来，通过遍历排序后的士兵大小，如果相邻两个士兵的大小相同，就调整当前士兵的大小，并累加调整的单位数。最后输出累加的单位数，即为至少需要加多少单位橡皮泥。
购买理财产品（多重背包）（奇安信0903）
养鹅计划
小可在读了《小狗钱钱》以后，决定利用自己的压岁钱来一个养鹅计划。可是她不确定什么时候要花这些压岁钱(比如来一场迪士尼梦幻之旅)，也不确定该怎么组合理财产品才能获取到更多的收益。
因此小可列举了市面上稳健型理财产品，并计算出每种理财产品需要投入月份数以及总收益。请你帮助小可计算下，如果她投入n个月，怎么选择理财产品组合才能获取最大收益?
1.小可计算出来的理财产品列表已经是一个有序数组按照投入月份数从小到大排序:例如[(3,902),(6,1873)(9,3654)]
2.单个理财产品数据表示投入月份和总收益:例如(3,902)，其中3代表投入月份数，902代表总收益;
3.每种理财产品只能按照投入月份的整数倍进行购买:比如上述列表中有3，6，9三种月份产品，如果购买11个月，只有3+3和3+6两种组合。
示例1
输入
[(1,235),(3,902),(6,1873),(9,3654)],7
输出
[(1,235),(6,1873)]
说明
总共预计投入7个月，计算出最佳收益组合为:1+6，最大总收益为:235+1873;
示例2
输入
[(2,602),(4,1275)1,7
输出
[(2,602),(4,1275)]
说明
总共预计投入7个月，计算出最佳收益组合为:2+4，最大总收益为:602+1275;
思路
本题比较明显，是一个多重背包问题，但是题目没有说清楚数据范围，但是在笔试的时候可以大胆尝试一下；多重背包问题和01问题的解法差不多，如果出现超时，可以尝试一下多重背包的优化解法；计算出最大值并不难，另一个关键的点是 构造出所选答案；一个可行的方案是：在更新dp数组的时候，同时记录是从哪个状态转移过来的，以本题为例，path[i][j]=k 的含义是，选取k个第i元素转移到dp[i][j]；最后再反序递归可以得到路径。
代码理解：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
struct Point {
int x, y;
Point(int xx, int yy) : x(xx), y(yy) {
}
};
class Solution {
public:
using ll = long long;
vector<Point> maxIncomeProducts(vector<Point>& products, int months) {
int n = products.size();
vector<vector<ll>> dp(n + 1, vector<ll>(months + 1, 0));
vector<vector<int>> path(n + 1, vector<int>(months + 1, 0));
for (int i = 1; i <= n; ++i) {
auto& p = products[i - 1];
for (int j = 1; j <= months; ++j) {
int cnt = j / p.x;
for (ll k = 0; k <= cnt; ++k) {
if (j >= k * p.x) {
ll cur = dp[i - 1][j - k * p.x] + p.y;
if (cur > dp[i][j]) {
dp[i][j] = cur;
path[i][j] = k;
}
}
}
}
}
int m = months, i = n;
vector<Point> ans;
while (i > 0) {
int cnt = path[i][m];
for (int k = 0; k < cnt; ++k) ans.push_back(products[i - 1]);
m -= cnt * products[i - 1].x;
i--;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
for (int i = 1; i <= n; ++i) {
auto& p = products[i - 1];
for (int j = 1; j <= months; ++j) {
int cnt = j / p.x;
for (ll k = 0; k <= cnt; ++k) {
if (j >= k * p.x) {
ll cur = dp[i - 1][j - k * p.x] + p.y;
if (cur > dp[i][j]) {
dp[i][j] = cur;
path[i][j] = k;
}
}
}
}
}
这段代码是多重背包问题求解的核心循环部分。下面我会逐行解释这段代码的作用：
-
for (int i = 1; i <= n; ++i) { ... }：外层循环遍历理财产品列表，n是理财产品的个数。 -
auto& p = products[i - 1];：根据索引i-1获取当前的理财产品，p是对应的Point结构体引用。 -
for (int j = 1; j <= months; ++j) { ... }：内层循环遍历投入的月份数，months是投入的总月份数。 -
int cnt = j / p.x;：计算当前月份可以购买该理财产品的最大数量，p.x是该理财产品的投入月份数。 -
for (ll k = 0; k <= cnt; ++k) { ... }：遍历购买数量从 0 到最大可购买数量。 -
if (j >= k * p.x) { ... }：判断当前购买数量是否合法，即判断当前月份数是否能够购买k个该理财产品。 -
ll cur = dp[i - 1][j - k * p.x] + p.y;：计算购买k个该理财产品后的总收益，dp[i - 1][j - k * p.x]表示前i-1种理财产品在剩余月份j-k*p.x的最大收益，p.y表示当前理财产品的总收益。 -
if (cur > dp[i][j]) { ... }：如果当前计算的总收益cur大于存储在dp[i][j]的已知最大收益，则更新当前最大收益和购买数量信息。 -
dp[i][j] = cur;：更新当前月份购买p后的最大收益。 -
path[i][j] = k;：记录购买p的数量k。
int m = months, i = n;
vector<Point> ans;
while (i > 0) {
int cnt = path[i][m];
for (int k = 0; k < cnt; ++k) ans.push_back(products[i - 1]);
m -= cnt * products[i - 1].x;
i--;
}
这段代码是使用之前计算出的 path 数组来回溯，得到最佳的购买方案。
-
int m = months, i = n;：初始化变量m为投入的总月份数，i为理财产品的个数。 -
vector<Point> ans;：创建一个空的vector来存储最佳购买方案。 -
while (i > 0) { ... }：循环遍历理财产品，直到遍历完所有的产品。 -
int cnt = path[i][m];：根据path数组中存储的购买数量信息，获取当前选择的理财产品i的购买数量。 -
for (int k = 0; k < cnt; ++k) ans.push_back(products[i - 1]);：将购买数量为cnt的理财产品products[i - 1]添加到最佳购买方案列表ans中。 -
m -= cnt * products[i - 1].x;：更新剩余的月份，减去购买数量乘以当前理财产品的投入月份数。 -
i--;：递减理财产品索引，继续回溯下一个产品。 -
reverse(ans.begin(), ans.end());：翻转最佳购买方案列表，以保证按照投入月份数的从小到大的顺序排列。
通过这段代码，可以得到最佳的购买方案，即购买哪些理财产品以获得最大的收益。最后的结果存储在 ans 中，按照投入月份数的从小到大的顺序排列。
通过这个循环，动态规划算法将填充 dp 数组和 path 数组，得到了每种组合下的最大收益和对应的购买数量信息。最后，根据 path 数组的记录，通过倒推的方式得到最佳的购买方案。
时间字符串输出和排序（荣耀0905）
来源：
https://mp.weixin.qq.com/s/NePhJ3c7VU3IkdCR7ljQbQ 吴师兄学算法公众号
题目描述
解析输入的字符串数组，提取出字符串中的时间戳信息，并且将字符串按照时间戳排序后，输出到控制台。
输入描述
第1行指定数组的size;
第2行到第n行，每行为一个独立的字符串，n为size的值。
每行的字符串由"-:"和字母、数字组成，时间戳在字符串中的位置不确定，时间戳格式为2019-01-01T07:30:20表示2019年1月1日，7点30分20秒。时间为24小时制。
输出描述
将输入的字符串按照时间戳进行从小到大排序后，输出。符合如下规则:
如果时间戳信息相同，按照字符串长度从小到大进行排序;
如果长度相同，则按照从首字符开始的ASCII码值比较从小到大进行排序;
如果两个字符串完全一样，则只需要输出一个。
示例一
输入
5
my/2019-01-01T09:00:01
my/2019-01-01T09:00:01
abc/2018-12-24T08:00:00/test/you
1/2018-12-24T08:00:00/test/Test1
123/2018-12-24T08:00:09/test/me
输出
1/2018-12-24T08:00:00/test/Test1
abc/2018-12-24T08:00:00/test/you
123/2018-12-24T08:00:09/test/me
my/2019-01-01T09:00:01
思路
时间戳模拟，时间戳长度为19
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
// 根据年、月、日、小时、分钟、秒，判断是否是一个有效的时间戳
bool checkAvailable(int YYYY, int MM, int DD, int hh, int mm, int ss) {
// hh、mm、ss超出限度，返回false
if (hh >= 24 || mm >= 60 || ss >= 60) {
return false;
}
// MM超出限度，返回false
if (MM >= 13) {
return false;
}
// MM和DD不能是0，否则返回false
if (MM == 0 || DD == 0) {
return false;
}
// 31天的月数，DD超出限度，返回false
if ((MM == 1 || MM == 3 || MM == 5 || MM == 7 || MM == 8 || MM == 10 || MM == 12) && DD > 31) {
return false;
}
// 30天的月数，DD超出限度，返回false
if ((MM == 4 || MM == 6 || MM == 9 || MM == 11) && DD > 30) {
return false;
}
// 闰年，2月，DD天数超过29天，返回false
if ((YYYY % 400 == 0 || (YYYY % 4 == 0 && YYYY % 100 != 0)) && MM == 2 && DD > 29) {
return false;
}
// 平年，2月，DD天数超过28天，返回false
if (MM == 2 && DD > 28) {
return false;
}
return true;
}
// 获取s中时间戳的函数
vector<int> getTimeStamp(const string& s) {
//一直循环到最后一个可能的时间戳起始位置下标
for (int i = 0; i < s.length() - 18; i++) {
// 获得长度为19的切片
string sub_s = s.substr(i, 19);
// 判断"-"是否在正确的位置
if (sub_s[4] != '-' || sub_s[7] != '-') {
continue;
}
// 判断"T"是否在正确的位置
if (sub_s[10] != 'T') {
continue;
}
// 判断":"是否在正确的位置
if (sub_s[13] != ':' || sub_s[16] != ':') {
continue;
}
try {
// 根据切片获取时间戳信息
int YYYY, MM, DD, hh, mm, ss;
YYYY = stoi(sub_s.substr(0, 4));
MM = stoi(sub_s.substr(5, 2));
DD = stoi(sub_s.substr(8, 2));
hh = stoi(sub_s.substr(11, 2));
mm = stoi(sub_s.substr(14, 2));
ss = stoi(sub_s.substr(17));
// 若时间戳信息通过了检查，则直接返回一个六元整数数组
if (checkAvailable(YYYY, MM, DD, hh, mm, ss)) {
return {
YYYY, MM, DD, hh, mm, ss};
}
} catch (...) {
continue;
}
}
return {
};
}
int main() {
int n;
cin >> n;
// 哈希集合，用于去重
set<string> hash_set;
vector<pair<vector<int>, string>> ans;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
// 只有没出现过的s，才需要进行计算
if (hash_set.find(s) == hash_set.end()) {
hash_set.insert(s);
// ans中储存时间戳和字符串s本身
ans.push_back({
getTimeStamp(s), s});
}
}
// 对ans进行排序，
// 先根据时间戳即x.first排序
// 再根据原字符串s的长度即x.second.size()排序
// 再根据原字符串s的字典序即x.second进行排序
sort(ans.begin(), ans.end(), [](const pair<vector<int>, string>& a, const pair<vector<int>, string>& b) {
if (a.first != b.first) {
return a.first < b.first;
} else if (a.second.size() != b.second.size()) {
return a.second.size() < b.second.size();
} else {
return a.second < b.second;
}
});
// 输出排序结果
for (const auto& item : ans) {
cout << item.second << endl;
}
return 0;
}
找出升序数组中和为给定值的两个数字（荣耀0905）
注意输入的处理
题目描述
输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
如果有多对数字的和等于输入的数字，输出找到的第一对即可。
输入描述
第一行输入一个按升序排序过的整数数组，数组元素不可重复，数组最大不超过1000个元素，起始和结束用中括号。
第二行输入一个整数，表示要在第一行数组中要查找的两个数字的和。
输出描述
输出一行三个整数，第一个表示结果是否正常(0表示异常或未找到，1表示正常)，第二个对应找到的数组索引小的数字，第三个对应找到的数组索引大的数字。
三个整数用单个空格隔开。
如果结果异常或未找到，后两个数字返回均为0。
示例一
输入
[1 2 4 7 11 15]
6
输出
1 2 4
解题思路
注意，本题和LeetCode167. 两数之和 II - 输入有序数组基本完全一致，属于贪心类的相向双指针题目，唯一的区别在于输出上有些区别。
另外，由于数据范围较小，本题用暴力解也可以通过，但还是建议使用双指针解法。
#include <iostream>
#include <vector>
using namespace std;
int main() {
string line;
getline(cin, line);
vector<int> nums;
// 解析输入的数组
int startPos = line.find('[');
int endPos = line.find(']');
string numStr = line.substr(startPos + 1, endPos - startPos - 1);
size_t pos = 0;
while ((pos = numStr.find(',')) != string::npos) {
string token = numStr.substr(0, pos);
nums.push_back(stoi(token));
numStr.erase(0, pos + 1);
}
nums.push_back(stoi(numStr));
// 解析目标和
int target;
cin >> target;
// 初始化双指针
int left = 0, right = nums.size() - 1;
bool findFlag = false;
// 进行循环
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
findFlag = true;
break;
} else if (sum > target) {
right--;
} else if (sum < target) {
left++;
}
}
// 输出结果
if (findFlag) {
cout << "1 " << nums[left] << " " << nums[right] << endl;
} else {
cout << "0 0 0" << endl;
}
return 0;
}
欧几里得法-同余方程求解（快手0908）
求关于x的同余方程ax1≡(mod b)的最小正整数解
输入描述
输入只有一行，包含两个正整数 a,b，用一个空格隔开。
对于40%的数据，2<=b<=1,000;
对于60%的数据，2<=b<=50,000,000;
对于100%的数据，2<=a,b<=2,000,000,000。
输出描述
输出只有一行，包含一个正整数x，即最小正整数解。输入数据保证一定有解。
示例1
输入
3 10
输出
7
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
void exgcd(int a, int b, ll& x, ll& y) {
if (!b) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
}
int main() {
ll a, b; cin >> a >> b;
ll x, y;
exgcd(a, b, x, y);
cout << (x+b)%b;
}
上述代码是一个计算两个数的逆元的程序。逆元是指对于整数 a、b，如果存在整数 x、y，使得 ax + by = 1，那么 x 称为 a 对于模 b 的逆元。
这段代码中，函数 exgcd 实现了扩展欧几里德算法来计算逆元。exgcd 函数的输入是两个整数 a 和 b，输出是使得 ax + by = gcd(a, b) 的整数解 x 和 y。在函数内部，使用递归方式调用 exgcd 函数来求解。
在主函数中，首先读入两个长整数 a 和 b。然后声明两个长整数 x 和 y，用于保存计算得到的逆元。接着调用 exgcd 函数来计算逆元，并将结果存储在 x 和 y 中。最后输出 (x + b) % b，即 a 对于模 b 的逆元。
在 exgcd 函数中，x 和 y 是通过引用传递的参数。在每一次递归调用中，它们的值都会发生变化。
首先，在递归的起始阶段，当 b 为 0 时，递归结束。此时，函数将 x 设置为 1，y 设置为 0。
然后，在每一次递归调用中，计算下一层的 x 和 y 的值。具体过程如下：
将 b 和 (a % b) 的值作为参数，继续递归调用 exgcd 函数。
在递归结束后，得到上一层递归调用中的 x 和 y 值，记为 x1 和 y1。
更新当前递归层中的 x 和 y 的值：
将 x1 的值赋给 x。
将 y1 的值赋给 y。
计算 t = x，然后将 y1 - a / b * t 的值赋给 y。
通过不断递归调用和更新 x 和 y 的值，最终得到的 x 和 y 就是满足条件 ax + by = gcd(a, b) 的整数解。
在主函数中，x 和 y 是用于存储计算得到的逆元的变量。最后通过 (x + b) % b 的操作，确保 x 为正数，获得 a 对于模 b 的逆元。
大数相乘（快手0908）
输入两个大数字符串(超过int64范围的数)，计算大数的乘法，并输出结果。
输入格式:
两个字符串，表示要相乘的两个数，长度均不超过1000。
输出格式:
一个字符串，表示两个数的乘积。
注意事项:
输入保证两个字符串均为非负整数。
不允许使用任何高精度库函数或类库。
输入描述输入两个非空纯数字字符串
输出描述
输出乘积结果
示例1
输入
15869523698 854789632596
输出
13565104331286935260008
思路与代码
本题也是经典的大数相乘问题，主要注意的是 不能有前导0，所以可以判断两个乘数是否为0；可以自己掌握几个模板，不需要每次都整一个写法。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string add(string& a, string& b) {
string ans = "";
int carry = 0;
for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0 || carry; --i, --j) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
//如果 x 等于 0，表示当前位置 i 已经没有数字字符了。这段代码在循环遍历时，处理完了所有 a 字符串中的数字字符，但 b 字符串仍然有剩余时会用到这个判断。
int z = x + y + carry;
ans.push_back('0' + (z % 10));
carry = z / 10;
}
reverse(ans.begin(), ans.end());
return ans;
}
string mul(string& a, int b) {
string ans = "";
int carry = 0;
for (int i = a.size() - 1; i >= 0 || carry; --i) {
int x = i >= 0 ? a[i] - '0' : 0;
int z = x * b + carry;
ans.push_back('0' + (z % 10));
carry = z / 10;
}
reverse(ans.begin(), ans.end());
return ans;
}
int main() {
string a, b;
cin >> a >> b;
if (a == "0" || b == "0") {
cout << "0";
return 0;
}
string ans = "";
for (int i = b.size() - 1, j = 0; i >= 0; --i, ++j) {
string s = mul(a, b[i] - '0');
s += string(j, '0');
ans = add(ans, s);
}
cout << ans;
}
注意：
- 如果 x 等于 0，表示当前位置 i 已经没有数字字符了。这段代码在循环遍历时，处理完了所有 a 字符串中的数字字符，但 b 字符串仍然有剩余时会用到这个判断。
- s += string(j, ‘0’);表示s加上j个0，表示将中间结果乘以10,模拟乘法操作
点的移动(快手0908)
给定二维平面上有一组点PO,P1，…PN，用直接把它们依次连接起来形成一条折线段，玩家从P0点开始沿折线段往PN移动，每移动长度s，就做一个标记点。请给出所有标记点的坐标。
输入描述
输入N，表示接下来会有多少个点数据。
输入N行数据，每一行包含两个数据x和y。
输入每移动长度s
输出描述
多行数据，每行输出标记点的x和y，中间用逗号区分
示例
输入
5
0.0 0.0
1.0 2.0
3.0 1.0
5.0 4.0
6.0 2.0
2.0
输出
0,0
0.894427，1.78885
2.57771，1.21115
3.84751，2.27126
4.95691，3.93536
5.85968，2.28063
思路与代码
题目没有明确说明精度，C++使用cout可以过，printf不可以；整体的思路就是遍历每一个点，累加距离，如果超过s，那么就截断，截断的方式也比较显然，按比例截断，即need/dist
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int N; cin >> N;
vector<vector<double>> arr;
for (int i = 0; i < N; ++i) {
double x, y; cin >> x >> y;
arr.push_back({
x, y});
}
double s; cin >> s;
double px = arr[0][0], py = arr[0][1], sum = 0;
cout << px << ", " << py << endl;
for (int i = 1; i < arr.size(); ++i) {
double x = arr[i][0], y = arr[i][1];
double dist = sqrt((x - arr[i - 1][0]) * (x - arr[i - 1][0]) +
(y - arr[i - 1][1]) * (y - arr[i - 1][1]));
if (dist + sum < s) {
sum += dist;
} else {
double need = s - sum;
sum = dist - (s - sum);
px = arr[i - 1][0], py = arr[i - 1][1];
while (true) {
double t = need / dist;
px += t * (x - arr[i - 1][0]);
py += t * (y - arr[i - 1][1]);
cout << px << ", " << py << endl;
if (sum < s) {
break;
} else sum -= s;
need = s;
}
}
}
}
将石头分散到网格图的最少移动次数(恒生力扣周赛0910)
给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。
每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。
请你返回每个格子恰好有一个石头的 最少移动次数 。
输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。
grid.length == grid[i].length == 3
0 <= grid[i][j] <= 9
grid 中元素之和为 9 。
最小费用最大流
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int src = m * n; // 超级源点
int dst = src + 1; // 超级汇点
struct edge {
int to, rid, cap, cost;
};
vector<vector<edge>> g(m * n + 2);
auto addEdge = [&](int from, int to, int cap, int cost) {
g[from].push_back({
to, static_cast<int>(g[to].size()), cap, cost });
g[to].push_back({
from, static_cast<int>(g[from].size() - 1), 0, -cost });
};
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
int v = grid[x][y];
if (v > 1) {
addEdge(src, x * n + y, v - 1, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
addEdge(x * n + y, i * n + j, 1, abs(x - i) + abs(y - j));
}
}
}
}
else if (v == 0) {
addEdge(x * n + y, dst, 1, 0);
}
}
}
const int inf = numeric_limits<int>::max();
vector<int> dist(m * n + 2);
vector<pair<int, int>> fa(m * n + 2);
auto spfa = [&]() -> bool {
fill(dist.begin(), dist.end(), inf);
dist[src] = 0;
vector<bool> inQ(m * n + 2, false);
inQ[src] = true;
queue<int> q;
q.push(src);
while (!q.empty()) {
int v = q.front();
q.pop();
inQ[v] = false;
for (int i = 0; i < g[v].size(); i++) {
auto& e = g[v][i];
if (e.cap == 0) {
continue;
}
int w = e.to;
int newD = dist[v] + e.cost;
if (newD < dist[w]) {
dist[w] = newD;
fa[w] = {
v, i };
if (!inQ[w]) {
q.push(w);
inQ[w] = true;
}
}
}
}
return dist[dst] < inf;
};
auto ek = [&]() -> pair<int, int> {
int maxFlow = 0;
int minCost = 0;
while (spfa()) {
int minF = inf;
for (int v = dst; v != src; ) {
auto p = fa[v];
int c = g[p.first][p.second].cap;
minF = min(minF, c);
v = p.first;
}
for (int v = dst; v != src; ) {
auto p = fa[v];
auto& e = g[p.first][p.second];
e.cap -= minF;
g[v][e.rid].cap += minF;
v = p.first;
}
maxFlow += minF;
minCost += dist[dst] * minF;
}
return {
maxFlow, minCost };
};
auto result = ek();
return result.second;
}
};
代码解释：
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
int v = grid[x][y];
if (v > 1) {
addEdge(src, x * n + y, v - 1, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
addEdge(x * n + y, i * n + j, 1, abs(x - i) + abs(y - j));
}
}
}
}
else if (v == 0) {
addEdge(x * n + y, dst, 1, 0);
}
}
}
构建有向图。它遍历二维网格中的每个格子，并根据格子中的值进行判断和添加边。
对于每个格子 (x, y)，获取该格子的值 v = grid[x][y]。
如果 v 大于 1，表示该格子上有石子，需要进行处理。首先，将超级源点 src 连接到当前格子的节点编号 x * n + y，边的容量为 v - 1，代表可以将 v - 1 个石子移动出该格子，费用为 0。
接下来，通过两层循环遍历整个网格，找到所有空白格子 (i, j)。如果当前格子的值 grid[i][j] 为 0，表示该格子为空白，可以将一个石子移动到该格子。这时，将当前格子的节点编号 x * n + y 连接到目标格子的节点编号 i * n + j，边的容量为 1，代表可以移动一个石子，费用为 abs(x - i) + abs(y - j)，即从当前格子到目标格子的曼哈顿距离。
如果当前格子的值 v 等于 0，表示是空白格子，需要将该格子连接到超级汇点 dst。将当前格子的节点编号 x * n + y 连接到超级汇点 dst，边的容量为 1，代表可以将一个石子移动到目标格子，费用为 0。
这样，通过遍历整个网格并根据需求添加边，就得到了构建有向图的过程。最后，该有向图可以用于最小费用最大流算法来求解问题。
const int inf = numeric_limits<int>::max();
vector<int> dist(m * n + 2);
vector<pair<int, int>> fa(m * n + 2);
auto spfa = [&]() -> bool {
fill(dist.begin(), dist.end(), inf);
dist[src] = 0;
vector<bool> inQ(m * n + 2, false);
inQ[src] = true;
queue<int> q;
q.push(src);
while (!q.empty()) {
int v = q.front();
q.pop();
inQ[v] = false;
for (int i = 0; i < g[v].size(); i++) {
auto& e = g[v][i];
if (e.cap == 0) {
continue;
}
int w = e.to;
int newD = dist[v] + e.cost;
if (newD < dist[w]) {
dist[w] = newD;
fa[w] = {
v, i };
if (!inQ[w]) {
q.push(w);
inQ[w] = true;
}
}
}
}
return dist[dst] < inf;
};
这段代码是SPFA（最短路径快速算法）的实现，用于寻找从超级源点 src 到超级汇点 dst 的最短路径。
代码逻辑如下：
- 定义一个常量 inf，表示一个很大的数值，用于初始化距离数组 dist 的初始值。
- 创建一个大小为 m * n + 2 的的距离数组 dist，表示从源点到每个节点的最短距离。
- 创建一个大小为 m * n + 2 的父节点数组 fa，用于记录最短路径中的节点和边。
- 定义一个名为 spfa 的 Lambda 函数，用于执行 SPFA 算法。
- 在 spfa 函数中，首先将 dist 数组初始化为 inf，然后将源点的距离 dist[src] 设置为 0，表示源点到自身的距离为 0。
- 创建一个大小为 m * n + 2 的布尔型数组 inQ，用于标记节点是否在队列中，初始时将超级源点 src 标记为 true。
- 创建一个队列 q，并将超级源点 src 入队。
- 在一个循环中，不断从队列中取出节点 v 进行操作：
- 将节点 v 设置为不在队列中（inQ[v] = false）。
- 遍历节点 v 的邻接边 e，并检查边 e 的容量（e.cap）是否为 0，如果为 0，则说明该边不能再通过，继续下一条边的遍历。
- 计算经过节点 v 到达节点 w 的新距离 newD，即 dist[v] + e.cost。
- 如果新距离 newD 小于 dist[w]，说明找到了一条更短的路径，更新 dist[w] 和父节点 fa[w]。
- 如果节点 w 不在队列中，将节点 w 入队，并将 inQ[w] 设置为 true。
- 最后，如果目标节点 dst 的最短距离 dist[dst] 小于 inf，则表示存在一条从超级源点 src 到超级汇点 dst 的最短路径，函数返回 true，否则返回 false。
这样，通过 SPFA 算法可以求解从超级源点到超级汇点的最短路径，并得到 dist 数组和父节点数组 fa 以供之后的最小费用最大流算法使用。
auto ek = [&]() -> pair<int, int> {
int maxFlow = 0;
int minCost = 0;
while (spfa()) {
int minF = inf;
for (int v = dst; v != src; ) {
auto p = fa[v];
int c = g[p.first][p.second].cap;
minF = min(minF, c);
v = p.first;
}
for (int v = dst; v != src; ) {
auto p = fa[v];
auto& e = g[p.first][p.second];
e.cap -= minF;
g[v][e.rid].cap += minF;
v = p.first;
}
maxFlow += minF;
minCost += dist[dst] * minF;
}
return {
maxFlow, minCost };
};
这段代码是最小费用最大流（EK 算法）的实现，用于求解最大流的同时得到最小费用。
代码逻辑如下：
- 定义一个变量 maxFlow，用于记录最大流的值，初始值为 0。
- 定义一个变量 minCost，用于记录最小费用的值，初始值为 0。
- 创建一个名为 ek 的 Lambda 函数，用于执行最小费用最大流算法。
- 在 ek 函数中，通过调用 spfa 函数来寻找从超级源点 src 到超级汇点 dst 的最短路径，如果找到最短路径则进入下一步，否则算法结束。
- 初始化一个变量 minF 为一个较大的值（inf）。
- 通过循环遍历，从超级汇点 dst 开始，依次获取父节点和对应边的信息。对于每个节点，获取该节点的父节点 p，然后通过父节点找到对应的边 e，获取该边的容量 c。
- 更新 minF 为 minF 和 c 的较小值，即取最小的容量值。
- 通过循环遍历，从超级汇点 dst 开始，依次获取父节点和对应边的信息。对于每个节点，获取该节点的父节点 p，然后通过父节点找到对应的边 e。将边 e 的容量减去 minF，即表示该边上的流量减少了 minF；同时将反向边（即 g[v][e.rid]）的容量增加 minF，即表示反向边上的流量增加了 minF。
- 更新 maxFlow，将 maxFlow 累加上 minF，表示当前的最大流增加了 minF。
- 更新 minCost，将 minCost 累加上 dist[dst] 乘以 minF，表示当前的最小费用增加了 dist[dst] 乘以 minF。
- 循环回到第3步，继续寻找下一条最短路径，并重复上述步骤，直到无法找到最短路径为止。
- 最后，返回一个 pair<int, int> 类型的值，其中第一个元素是 maxFlow，表示最大流的值，第二个元素是 minCost，表示最小费用的值。
照明灯安装（滴滴0915）
题目描述:
你负责在一条笔直的道路上安装一些照明灯。但是道路上并不是任意位置都适合安装照明灯，具体地，假设将道路看作一条起点坐标为0，终点坐标为M的线段，那么只有在x1,x2,…,xn这n个坐标可以安装照明灯，且每个坐标上最多只能安装一个照明灯。现在你要在道路上安装k个照明灯，为了使照明灯能够尽量覆盖道路，你需要使距离最近的两个照明灯尽量远。请问这个最近距离最大可以是多少?
输入描述
第一行是两个整数n、k，分别表示可以安装照明灯的位置数和需要安装的照明灯数量。
接下来一行n个整数x1,x2,…,xn表示可以安装照明灯的坐标。保证x1<x2<…<xn。
1<=k<=n<=100000,1<xi<1000000
输出描述
一行，一个整数，表示最近距离的最大值.
样例输入
5 3
1 3 4 7 9
样例输出
3
提示
分别放在1、4、7的位置(放在1、4、9也可以)
能够证明3是最小的最大距离。
思路与代码
二分最近距离，然后用这个距离去进行判断是否能够达到条件，如果可以，则令l = mid + 1,ans记录距离，继续二分。
用二分法逼近这个最优距离，初始为（l+r)/ 2
#include<algorithm>
#include<iostream>
#include<thread>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
bool check(int n, int k, int dis) {
int cnt = 1, last = a[1];
for (int i = 2; i <= n && cnt < k; i++) {
if (a[i] >= last + dis) {
cnt++;
last = a[i];
}
}
return cnt >= k;
}
int main() {
std :: ios :: sync_with_stdio(false);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
int l = 0, r = 1e9, ans = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if (check(n, k, mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans << "\n";
}
这段代码是一个二分查找的应用，用于找到一个最大的间距（dis），使得在数组a中存在至少k个数，它们之间的间距都大于等于dis。
首先，代码读取输入的值n和k，表示数组a的长度和需要找到的数的个数。
然后，代码通过循环读取数组a的元素。
接下来，代码初始化二分查找的范围，l为最小值0，r为最大值1e9（10^9）。
在while循环中，代码计算出中间值mid，然后调用check函数判断在数组a中是否存在至少k个间距大于等于mid的数。
如果存在，说明间距可以更大，因此更新ans为mid，并向右半部分查找，即将l更新为mid + 1。
如果不存在，说明间距需要更小，因此将r更新为mid - 1，继续向左半部分查找。
最后，在while循环结束后，输出ans即为所求的最大间距。
优秀数组问题（aliyun 0910第一题？）
题目描述：
小红有一个长度为n的排列p，其中1到n的每个数都恰好出现一次，pos[i]表示排列中元素i的下标。例如p=[3,2,4,5,1],则pos =[5,2,1,3,4]。还有一个长度为m的数组a，数组的元素互不相同，即ai!=aj,。如果满足pos[ai]<pos[ai+1]<=pos[ai]+d,则认为a是一个优秀的数组。
现在给定长度为n的排列p，以及长度为m的数组a1,a2…am，小红想知道最少需要多少次操作可以将数组变的不优秀，每次操作可以交换排列p的相邻元素，对应的pos数组也会发生变化。
输入描述
一行三个整数n,m,d，表示排列的长度，数组的长度以及d的值。
一行n个整数p1，p2，…,pn，表示排列p。
一行m个整数a1,a2,…am,表示数组a。
2≤m≤n≤10^5
输出描述
输出一个整数表示最少需要多少次操作。
示例1
输入：
5 2 2
3 2 4 5 1
3 4
输出：
1
说明
只需要交换4，5得到p=[3,2,5,4,1],这样a=[3,4]就不是优秀数组了。
思路与代码
题目有点绕，其实只需要记录数组p中每个数的下标，然后遍历a数组，查出来a数组连续两个数在p数组中的下标，然后计算破坏他们的优秀关系需要的次数即可。
破坏优秀关系有两种方案，一种是互相远离，值是 (p1 + d + 1-p2),需要判断移动后的坐标是否越界，越界的话这种方案就不成立了；第二种方案是互相接近，直到位置交换，值是(p2-p1).遍历结束后取最小值就是答案。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int d = sc.nextInt();
int [] a = new int[m + 1];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i <= n; i++) {
int p = sc.nextInt();
map.put(p, i);
}
for (int i = 1; i <= m; i++) {
a[i] = sc.nextInt();
}
int ans = Integer.MAX_VALUE;
for (int i = 1; i < m; i++) {
int num = a[i];
int p1 = map.get(num);
int num2 = a[i + 1];
int p2 = map.get(num2);
int c1 = Integer.MAX_VALUE;
if (p1 + d <= n || p2 - d >= 1) {
c1 = p1 + d + 1 - p2;
}
int c2 = p2 - p1;
ans = Math.min(Math.min(c1, c2), ans);
}
System.out.println(ans);
}
不超过k个相同字母的字符串（aliyun 0910）
小红有x个字母a，y个字母b，小红不喜欢在串中出现连续超过k个相同的字符。如果存在用完所有字母组成的字符串，找出其中字典序最大的串，否则输出-1。
输入描述
一行三个整数x，y，k，表示小红有x个字母a，y个字母b，小红不喜欢在串中出现连续超过k个相同的字符。
1<=x,y<=10^5
1<=k<=100
输出描述
如果存在，输出字典序最大的串，否则输出-1.
示例1
输入
3 5 2
输出
bbabbaba
思路与代码
贪心。可以算出来x和y不满足条件时的关系，假设x>y, 如果x%k==0的话，至少需要x/k-1个b才能构建字符串，否则就需要x/k个b。每一步都优先使用b去填，检查b的连续出现次数和放置b后x和y的数量关系能否满足构建条件，如果可以放置b就放置b，否则放置a。
#include <iostream>
#include <string>
bool check(int x, int y, int k);
std::string findLargestString(int x, int y, int k, char firstChar, char secondChar);
std::string fun(int x, int y, int k);
int main() {
int x, y, k;
std::cin >> x >> y >> k;
if (!check(x, y, k)) {
std::cout << "-1" << std::endl;
return 0;
}
std::cout << fun(x, y, k) << std::endl;
return 0;
}
bool check(int x, int y, int k) {
if (x % k == 0) {
int c = x / k;
if (y < c - 1) return false;
} else {
int c = x / k;
if (y < c) return false;
}
if (y % k == 0) {
int c = y / k;
if (x < c - 1) return false;
} else {
int c = y / k;
if (x < c) return false;
}
return true;
}
std::string findLargestString(int x, int y, int k, char firstChar, char secondChar) {
std::string result = "";
int curB = 0;
int curA = 0;
int a = x;
int b = y;
while (result.length() < x + y) {
if (curB < k && check(a, b - 1, k)) {
result += secondChar;
b--;
curB++;
curA = 0;
} else if (curA < k) {
result += firstChar;
a--;
curA++;
curB = 0;
} else {
return "-1";
}
}
return result;
}
std::string fun(int x, int y, int k) {
return findLargestString(x, y, k, 'a', 'b');
}
小明的传送门
小明的传送门
时间限制: 4000MS 内存限制:589824KB
题目描述:
某航空公司开发了无人岛移居计划，小明和他的很多朋友都参与了这项计划，搬到了不同的无人岛上生活。
一些无人岛之间具有稳定的双向来回的航班路线，所以小明可以通过航班路线来往到其他岛。
但是，显然存在一些岛屿小明无法前往。例现在存在三座小岛分别为:小岛A，小岛B，小岛C，A和B之间有航班路线，那么小明就无法从A岛前往C岛(此时没有路线)。
现在小明收到了朋友的邀请，要从小明居住的岛屿前往朋友居住的岛屿。小明有一项超能力，小明可以在两座不同的岛屿之间架设传送门这两座岛屿就可以直接通过传送门来往。
你的任务是求出现在小明有多少种架设传送门的方法，使得从小明的岛屿出发能够抵达朋友所居住的鸟屿。
请注意: 由于传送门是双向可达的，因此A岛与B岛之间架设传送门和B岛与A岛之间架设传送门是同一种架设方法。不能计为两种方法。
输入描述
第一行四个正整数n,m,s,t，n表示有n个无人岛，编号从1到n，m表示有m种已经存在的航班路线。小明生活在无人岛s上，将要前往的是无人岛t。保证s和t不相等。
接下来有m行，每行两个正整数x,y，表示无人岛x和无人岛y之间存在一个航班路线。
对于100%的数据，保证1<=n<=10000,1<=m<=10000.1<=s<=t<=n
输出描述
输出一个整数表示传送门的架设方法
样例输入
3 1 1 3
1 2
样例输出
2
解释
1和2之间有航班相连，小明想从1去3，则此时可以在1到3之间或2到3之间架设传送门，因此有两种方案。
思路与代码
并查集的思路。
最后判断起点所在的生成树和终点所在的生成树之间，一共有多少个点，分别为num1，num2，两边的生成树的点的个数乘积即为方案的总数。
package weizhong;
import java.util.Scanner;
public class Main3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int s = sc.nextInt();
int t = sc.nextInt();
int num1 = 0, num2 = 0;
int[] pa = new int[n + 1];
for(int i = 1; i <= n; i++){
pa[i] = i;
}
for(int i = 0; i < m; i++){
int from = sc.nextInt();
int to = sc.nextInt();
int paFrom = findParent(from, pa);
int paTo = findParent(to, pa);
if(paFrom != paTo){
pa[paFrom] = paTo;
}
}
for(int i = 1; i <= n; i++){
if(findParent(i, pa) == findParent(s, pa))
num1++;
if(findParent(i, pa) == findParent(t, pa))
num2++;
}
if(findParent(s, pa) == findParent(t, pa))
System.out.println(n * (n - 1) / 2);
else
System.out.println(num1 * num2);
}
public static int findParent(int a , int[]pa){
if(a != pa[a]){
pa[a] = findParent(pa[a], pa);
}
return pa[a];
}
}
这段代码是一个使用并查集（Union Find）算法解决的问题。下面是对代码的解释：
- 在
main函数中，首先通过Scanner获取输入的整数n，m，s，t，分别表示节点数量、边数量、起始节点和目标节点。 - 创建一个长度为
n+1的整型数组pa，用于保存每个节点的父节点，初始化每个节点的父节点为自身。 - 接下来进行
m次循环，通过Scanner依次获取每条边的起始节点和结束节点。然后使用findParent函数找到起始节点和结束节点的父节点，如果它们的父节点不同，说明它们属于不同的连通分量，将它们合并在一起。 - 使用
findParent函数遍历每个节点，统计和起始节点s具有相同父节点的节点个数，保存到num1中。同样地，统计和目标节点t具有相同父节点的节点个数，保存到num2中。 - 如果起始节点和目标节点具有相同的父节点，说明它们在同一个连通分量中，此时输出
n * (n-1) / 2，表示任意选取两个节点的组合数量。 - 如果起始节点和目标节点不在同一个连通分量中，输出
num1 * num2，表示选择一个属于起始节点所在连通分量的节点，再选择一个属于目标节点所在连通分量的节点，共有num1 * num2种组合方式。
这段代码使用了并查集算法来判断节点间的连通性，并进行相应的计算。
二叉树拼接（腾讯音乐 0922，费马小定理）
小红拿到了n个二叉树，她准备把这些二又树拼接起来。
拼接的方式是:选择一个二叉树a的一个叶子，将二叉树b的根作为该叶子的左儿子或者右儿子。这样就把a和b拼接起来了。
小红希望最终将这n个二叉树拼接成一个二叉树，需要满足最终二又树的高度尽可能大。小红想知道，有多少种不同的拼接方式?由于答案可能过大，请对10^9+7取模。
数据范围:
所有二叉树的节点数量之和不超过200000。
每个二叉树至少有一个节点
每个节点的权值随机。
1<=n<=200000
示例1
输入
[{1,#,2},{3.4.5}]
输出
6
说明
将第二个二叉树接到第一个的权值为2的叶子上面，共有2种方式。
将第一个二叉树接到第二个的权值为4的叶子或者权值为5的叶子上面，共有4种方式。
思路
重点是最大深度叶子节点的递归搜索算法和求逆元算法
显然应该把根节点接在另外一棵树最深的节点上。
假设一棵树有x个这样的节点，另一颗有y个。
那么把第二棵树接在第一棵树的下面有2* x种方案。现在有n棵树，第i棵树有ai个这样的节点。考虑第一棵树在最底下的情形，此时剩下的n-1棵树的上下排列共有n-1 ！种，对于任意一种上下排列，通过改变每棵树的根节点对接的叶结点，共有（2* a2）* （2* a3）… (2* an)种。令total = 2* a1* 2* a2* … * 2* an。 ans = total * （n-1）！（1/（2 a1）+…+ 1/(2* an))
但是求（1/（2 a1）+…+ 1/(2* an))需要会逆元操作
求逆元的方法
算法学习笔记(9)：逆元 - Pecco的文章 - 知乎
https://zhuanlan.zhihu.com/p/100587745
所谓逆元就是模大质数意义下的1/a
方法之一是快速幂运算，理论依据是费马小定理
int mod = 1000000007;
public long call(long c){
long res=1;
int modj=mod-2;
while(modj>0){
if((modj&1)>0)res=res*c%mod;
c=c*c%mod;
modj>>=1;
}
return res;
}
private int findML(TreeNode tree) {
if (tree == null) return 0;
if (tree.left == null && tree.right == null) {
return 1;
}
return Math.max(findML(tree.left),
findML(tree.right)) + 1;
}
public int findMN(TreeNode tree, int maxLength, int length) {
if (tree == null) return 0;
if (tree.left == null && tree.right == null && length == maxLength) {
return 1;
}
return findMN(tree.left, maxLength, length + 1) + findMN(tree.right,
maxLength, length + 1);
}
int mod = 1000000007;
public long call(long c){
long res=1;
int modj=mod-2;
while(modj>0){
if((modj&1)>0)res=res*c%mod;
c=c*c%mod;
modj>>=1;
}
return res;
}
public int cntOfMethods (TreeNode[] trees) {
int[] nums=new int[trees.length];
for (int i = 0; i < trees.length; i++) {
int x = findMN(trees[i], findML(trees[i]), 1);
nums[i]=x;
}
long sum=1,res=0;;
for(int i=1;i<trees.length;i++){
sum=sum*i%mod;
}
for(int i=0;i<trees.length;i++){
sum=sum*2*nums[i]%mod;
}
for(int i=0;i<trees.length;i++){
res=(res+sum*call(2*nums[i])%mod)%mod;
}
return (int) res;
}
findML函数是为了找到树的最大深度
findMN是为了找到树的最大深度对应的叶子节点数目
生成字符串的不同方式（腾讯音乐 0922）
小红拿到了一个空字符串s。她有以下两种操作:
1.将任意一个字母添加在s的末尾。
2.选择s的一个长度不小于2的连续子串，复制下来添加到s的末尾
小红希望用空串s生成一个给定的字符串t，她想知道有多少种不同的生成方式？由于答案可能过大，请对10^9+ 7取模。
数据范围:
字符串t仅包含小写字母，且长度不超过300.
示例1
输入
“ababa”
输出
3
第一种方式:
""->"a"->"ab"->"aba"->"abab"->"ababa"
第二种方式:
""->"a"->"ab"->"aba"->"ababa"
第三种方式:
""->"a"->"ab"->"abab"->"ababa"
参考2023.9.22腾讯音乐秋招笔试题解 - 机智yhy的文章 - 知乎
https://zhuanlan.zhihu.com/p/657898729
f[i]表示长度为i的字符串的所有可能生成方式
看t[k:k+len] 和t[j+1:j+len+1]是否相等，k小于j，j小于i
k j i，看k-j段的字符是否能移到j-i段
如果可以，那么f[i]就可以加上f[j]的结果，更新
class Solution {
public:
const int mod=1e9+7;
int cntOfMethod(string t) {
int n=t.size();t=' '+t;
vector<int>f(n+1,0); //与前i个字符匹配的方案数
f[0]=1;
for(int i=1;i<=n;i++){
f[i]=f[i-1];
for(int j=0;j<=i-2;j++){
//[j+1,i]
int len=i-j; //字符串长度
for(int k=1;k+len-1<=j;k++){
if(t.substr(k,len)==t.substr(j+1,len)){
f[i]=(f[i]+f[j])%mod;
}
}
}
}
return f[n];
}
};
PCB印刷电路板布线（huawei 0921）
在PCB印剧电路板设计中，器件之间的连线需要避免线路的用抗值增大，而且器件之间还有别的器件和别的干扰源，在布线时我们希望爱到的干扰尽量小。
现将电路板简化成一个M*N的矩阵，每个位置(单元格) 的值表示其源干扰度。
如果单元格的值为0，表示此位置没有干扰源;如果单元格的值为非0，则表示此位置是干扰源，其值为源干扰度。
连线经过干扰源或千扰源附近会增加连线的总干扰度。
位置A[x,y]的干扰源的源干扰度为d(d>0)，则连线的干扰度计算如下
1、若连线经过位置A[x,y]，则其总干扰度会增加d;
2、若连线经过离位置A[x,y]距离小于d的位置时，设其距离为k，则总干扰度会增加(d-k);
3、若连线经过离位置A[x,y]距离大于或等于d的位置时，总干扰度不会增加；
注:位置[x1,y1]和位置[x2,y2]之间距离的定义为:|x1-x2| + |y1-y2|。
如下3x3矩阵，位置[1,1]的源干扰度是2，连线的位置序列为:[0,0]->[0,1]->[0,2]->[1,2]>[2.2]。
其中[0,1]和[1,0]到干扰源的距离为1，会叠加1的干扰度;其他位置到[1,1]的距离均大于等于2，所以不会叠加干扰度。
因此这条连线的总干扰度为2。
现在我们需要将左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的[0,0]和右下角的[M-1,N-1]。由于我们希望连线尽量地短，从位置[0,0]到[M-1,N-1]的连线途中，我们规定连线只能向下或向右。
请根据输入 (MxN的矩阵)，计算出连线的最小干扰度。
动态规划+BFS
首先计算出所有节点的干扰值,使用广度优先遍历
动态规划计算走到终点的最小干扰值。 f[i,j] = min(f[i-1,j], f[i,j-1]) + dis[i,j]
from collections import deque
from math import inf
m,n = map(int, input().split())
matrix = []
for _ in range(m):
matrix.append([int(c) for c in input().split()])
dis = [[0]*n for _ in range(m)]
def ranse(i,j):
vst = [[False]*n for _ in range(m)]
q = deque()
q.append((i,j,matrix[i][j]))
vst[i][j] = True
while q:
i,j,g = q.popleft()
if g == 0: continue
dis[i][j] += g
for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
if ni<0 or nj<0 or ni>=m or nj>=n or vst[ni][nj]: continue
vst[ni][nj] = True
q.append((ni,nj,g-1))
q = deque()
for i in range(m):
for j in range(n):
if matrix[i][j] != 0:
ranse(i,j)
dp = {
}
def dfs(i,j):
if i >= m or j >= n: return inf
if i == m-1 and j == n-1: return dis[-1][-1]
if (i,j) in dp:
return dp[(i, j)]
dp[(i,j)] = min(dfs(i+1,j),dfs(i,j+1)) + dis[i][j]
return dp[(i,j)]
print(dfs(0,0))
开电动汽车回家过年（huawei 0921）
题目描述
新年即将来临，小明计划开新买的电动汽车回老家过年。
已知小明的工作地在上海，老家在中部某城市A。上海到城市A的距离是L公里(1<=L≤100000)。
小明的电动汽车的电池航程是P，电池最大电量也是P(假设电动汽车行使一公里需要消耗1度电。(1<=P<=100))。如果电动车在中途电量耗尽了，将无法继续强行，也就无法到达目的地了。
已知小明出发前已经把电池充满了。途中依次经过N(1<=N<10000)个充电站。第i个充电站距离城市A有 Ai公里，最大可充电 Bi度。
请问，小明能不能顺利地回老家过年?如果可以，请输出最少需要充电多少次;如果不可以，请输出-1。
解答要求
时间限制: C/C++ 1000ms, 其他语言: 2000ms内存限制: C/C++ 256MB,其他语言: 512MB
输入
输入的第一行为数字N。
接下来的N行，每行包含2个数并用空格隔开: Ai Bi
最后一行包括两个数LP，并用空格隔开。
输出
按照题目要求输出最少次数或者-1。
样例1
输入:4
4 4
5 5
11 6
15 8
25 10
输出:3
解释:小明出发时电池电量是10，距离城市A 25公里。
行驶10公里后，到达距离城市A 15公里的充电站，充点前电池电量为0，充电8度之后，再出发。
行驶4公里后，到达距离城市A11公里的充电站，充电前电池电量为4。充电6度之后，再出发。
行驶6公里后，到达距离城市A 5公里的充电站，充电前电池电量为4，充电1度之后，再出发。
之后，可以直接开到城市A
一共需要充电3次才能到达城市A。
思路与代码
动态规划。
此处使用记忆化搜索来进行实现。f[i, j]表示从第i个充电桩，剩余电量为j的时候，走到终点的最小充电次数。
f[i, j] = min(f[i+1,j-diff], f[i+1, j+B[i] - diff] + 1) //充电和不充电
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
unordered_map<string, int> cache;
int dfs(vector<vector<int>>& stations, int i, int j, int L, int P) {
string hash = to_string(i) + "-" + to_string(j);
if (cache.count(hash)) {
return cache[hash];
}
if (i == stations.size() - 1) {
int diff = L - stations.back()[0];
if (j >= diff) return 0;
if (j + stations.back()[1] >= diff) return 1;
return INT_MAX;
}
int diff = stations[i + 1][0] - stations[i][0];
int ans = INT_MAX;
if (j >= diff) {
ans = min(ans, dfs(stations, i + 1, j - diff, L, P));
}
if (j + stations[i][1] >= diff) {
int curP = min(j + stations[i][1], P);
ans = min(ans, dfs(stations, i + 1, curP - diff, L, P) + 1);
}
cache[hash] = ans;
return ans;
}
int solve(vector<vector<int>>& stations, int L, int P) {
for (int i = 1; i < stations.size(); i++) {
if (stations[i][0] - stations[i - 1][0] > P) {
return -1;
}
}
return dfs(stations, 0, P, L, P);
}
int main() {
int N;
cin >> N;
vector<vector<int>> stations(N, vector<int>(2));
for (int i = 0; i < N; i++) {
cin >> stations[i][0] >> stations[i][1];
}
sort(stations.begin(), stations.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
stations.insert(stations.begin(), {
0, 0});
int L, P;
cin >> L >> P;
int ans = solve(stations, L, P);
cout << ans << endl;
return 0;
}
以上代码是一个解决题目要求的代码实现。让我来解释一下其主要部分：
-
首先，通过输入获取充电站的数量N，然后读取N行输入数据，每行包含两个整数Ai和Bi，表示第i个充电站距离目的地的距离和最大可充电量。最后一行是两个整数L和P，表示目的地距离和电动汽车的电池航程。
-
接下来，对充电站列表按照距离进行排序，并在列表的开头插入一个表示起点的站点[0, 0]。
-
定义一个
solve函数来解决问题。首先，遍历充电站列表，检查是否有相邻充电站之间的距离超过了电池航程P，如果超过了则无法到达目的地，直接返回-1。 -
定义一个嵌套的
dfs函数来进行深度优先搜索。该函数的参数i表示当前所在的充电站索引，j表示当前电池的电量。首先检查是否已经到达目的地（i == N），如果是，则计算到达目的地所需的剩余距离diff，判断如果当前电量j足够到达目的地，则返回0，如果可以通过充电到达目的地，则返回1，否则返回一个很大的值inf表示无法到达目的地。 -
如果未到达目的地，则计算下一个充电站与当前充电站的距离diff。定义一个变量ans来保存最小的充电次数，初始化为inf。
-
如果当前电量j足够到达下一个充电站，则递归调用dfs函数继续向下一个充电站前进，此时电量减少diff，即
dfs(i+1, j-diff)，并更新ans为不充电情况下的充电次数。 -
如果当前电量通过充电和上一个充电站的剩余电量足够到达下一个充电站，则递归调用dfs函数继续向下一个充电站前进，此时电量更新为充电后的剩余电量curP（curP为当前电量j与充电站的最大可充电量stations[i][1]的较小值），即
dfs(i+1, curP - diff)，并更新ans为充电情况下的充电次数。 -
返回ans作为dfs函数的结果。
-
在solve函数的末尾，判断如果ans值为inf，则说明无法到达目的地，返回-1，否则返回ans作为最少充电次数。
-
调用solve函数并打印结果。
门打开的顺序（小米 0924）
小X在一片大陆上探险，有一天他发现了一个洞穴，洞穴里面有n道门，打开每道门都需要对应的钥匙，编号为的钥匙能用于打开第i道门，而且只有在打开了第i道门之后，才能打开第i+1道门，一开始只能打开第1道门。幸运的是，小X在外面探索的途中，每天都能发现一把能打开这n道门中其中一道门的钥匙，每天找完钥匙后他都会去打开所有能打开的门。现在给出他每天找到的钥匙编号，请问每道门分别在哪一天被打开。
输入描述
第一行包合一个正整数n，表示门的数量。接下来一行包含n个正整数a1，a2，.，an，其中ai表示第i天他找到的钥匙的编号，能够打开第ai道门，数据保证a1-an为1-n的一个排列。输出描述 输出一行n个数s1，s2，…，sn , 其中si表示第 i 道门在第si天被打开
样例输入
5
5 3 1 2 4
样例输出
3 4 4 5 5
数据范围和说明
1<n<100000
样例说明
到第三天时获得的钥匙为1、3、5，能够打开第1道门，到第四天时为1、2、3、5能继续打开第2和3道门，到第五天时获得了全部钥匙，能打开所有剩下的门。
思路与代码
双指针模拟，当能开第 i 扇门的时候继续往后开，当天开的门就记录上是哪一天
用一个哈希表表示当前已经收集到了哪扇门的钥匙
now表示打开门的时间点
i从0到n-1按收集钥匙的顺序遍历钥匙。i表示当前是第i天
#include<bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
gg n; cin >> n;
vector<gg> arr(n);
for(int i = 0; i < n; i++) cin >> arr[i];
vector<gg> have(n+1, 0), ans(n + 1);
gg now = 1;
for(int i = 0; i < n; i++) {
have[arr[i]]++;
while(now <= n && have[now]) {
ans[now] = i + 1;
now++;
}
}
cout << ans[1];
for(int i = 2; i <= n; i++) cout << ' ' << ans[i];
cout << '\n';
return 0;
}
快速传球（huawei 0920）
班级组织传球活动，男女同学随机排成m行n列队伍，第一列中的任意一个男同学都可以作为传球的起点，要求最终将球传到最后一列的任意一个男同学手里，求所有能够完成任务的传球路线中的最优路线(传球次数最少的路线)的传球次数。
传球规则:
1.男同学只能将球传给男同学，不能传给女同学。
2.球只能传给身边前后左右相邻的同学。
3.如果游戏不能完成，返回-1。
说明
1.传球次数最少的路线为最优路线。
2最优路线可能不唯一，不同最优路线都为最少传球次数。
解答要求
时间限制:C/C++100ms其他语言: 200ms内存限制: C/C++256MB,其他语言: 512MB
输入
班级同学随机排成的m行n列队伍，1代表男同学，0代表女同学。
输入第一行包含两个用空格分开的整数m[1,30]和n [1,30]，表示m行n列的队伍;
接下来是m行每行包含n个用空格分开的整数1或0。
输出
最优路线的传球次数（最少传球次数）
样例1
输入
4 4
1 1 1 0
1 1 1 0
0 0 1 0
0 1 1 1
输出
5
思路与代码
最短路BFS。
枚举第一列的所有的点，做一次BFS，判断走到最后一列的最短距离即可。
import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
//注意不让输入超时
private static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream stream){
br = new BufferedReader(new InputStreamReader(stream), 32768);
st = null;
}
String next() {
while (st == null || !st.hasMoreTokens())
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
public static void main(String[] args) {
new Main().solve();
}
int m,n;
int[][] grid;
void solve() {
PrintWriter pwin = new PrintWriter(new OutputStreamWriter(System.out));
FastScanner fsc = new FastScanner(System.in);
m = fsc.nextInt();;
n = fsc.nextInt();
grid = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = fsc.nextInt();
}
}
int[][] dirs = {
{
0,1},{
1,0},{
0,-1},{
-1,0}};
int res = 10000001;
for (int i = 0; i < m; i++) {
//从是第一列中的男同学开始
if (grid[i][0] == 1) {
Deque<int[]> dq = new LinkedList<>();
dq.add(new int[]{
0,i,0});
boolean[][] used = new boolean[m][n];
used[i][0] = true;
while (!dq.isEmpty()) {
int[] a = dq.poll();
int d = a[0], x = a[1], y = a[2];
if (y == n-1) {
res = Math.min(res, d);
}
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || ny < 0 || nx >= m || ny >= n || used[nx][ny] || grid[nx][ny] != 1) continue;
used[nx][ny] = true;
dq.add(new int[]{
d+1, nx,ny});
}
}
}
}
if (res != 10000001) pwin.println(res);
else pwin.println(-1);
pwin.flush();
}
}
#I 加减 （牛客小白月赛37）
题目描述
题解：https://www.nowcoder.com/discuss/353149614410899456
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100010],k,n;
ll sum[100010];
int main(){
ll i,j,temp;
cin>>n>>k;
ll s=0;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)sum[i+1]=s+=a[i];
i=j=temp=0;
ll res=0;
for(i=0;i<n;i++)res+=abs(a[i]-a[n/2]);
if(res<=k){
cout<<n;
return 0;
}
ll ma=0;
for(i=0;i<n;i++){
j--;
do {
j++;
temp=(i+j)/2;
res=(temp-i)*a[temp]-(sum[temp]-sum[i]);
res+=sum[j+1]-sum[temp+1]-(j-temp)*a[temp];
} while (j<n&&res<=k);
ma=max(ma,j-i);
}
cout<<ma;
}
作者：神崎兰子
链接：https://www.nowcoder.com/discuss/353149614410899456
来源：牛客网
这段代码的功能是求解一个数组中，将其中一些元素替换成中位数，使得替换后的数组中任意相邻两个元素的差值的绝对值不超过给定的值 k。代码的主要内容如下：
首先，读入输入的数组长度 n 和限制值 k。
接着，读入数组元素，并对数组进行排序。
然后，计算前缀和数组 sum，其中 sum[i] 存储数组前 i 个元素的和。
然后，初始化变量 i、j 和 temp 为0，变量 res 为0。变量 ma 用于记录最大的替换后的数组长度。
接下来，通过一个循环来遍历数组。在每一次循环中，计算将数组的某个位置 i 到 j 之间的元素替换成中位数后的数组长度，以及替换后的数组元素之和。具体计算方法如下：
- 将
j减小1。 - 使用二分查找来寻找一个位置
temp，使得替换位置在i到temp之间时，替换后的数组元素之和与给定的限制k之间的差值最小。具体来说，根据中位数的性质，res的计算包括三部分：(temp-i) * a[temp] - (sum[temp] - sum[i])表示将位置i到temp之间的元素替换为中位数后，替换后的数组元素之和减去替换前的数组元素之和。sum[j+1] - sum[temp+1] - (j-temp) * a[temp]表示将位置temp+1到j之间的元素替换为中位数后，替换后的数组元素之和减去替换前的数组元素之和。
- 判断是否满足替换后的数组元素之和与给定的限制
k之间的差值小于等于0。如果满足，则直接输出数组长度n，表示整个数组都被替换成中位数。然后结束程序。 - 利用二分查找逐渐调整替换的范围，直到找到最大的替换后的数组长度。
最后，输出最大的替换后的数组长度。
总而言之，这段代码通过遍历数组，并使用二分查找找到最大的替换后的数组长度，使得替换后的数组满足相邻元素差值的绝对值不超过给定的值 k。
有效IP地址（bilibili 0926）
力扣原题
import java.util.ArrayList;
import java.util.List;
class C {
List<String> res = new ArrayList<>();
List<String> ip = new ArrayList<>(7);
public String[] getList(String s) {
List<String> strings = restoreIpAddresses(s);
strings.removeIf(item -> item == null);
String[] ss= new String[strings.size()];
for (int i = 0;i<strings.size();i++){
ss[i] = strings.get(i);
}
return ss;
}
public List<String> restoreIpAddresses(String s) {
if (s.length() < 4 || s.length() > 12) {
return res;
}
backtrack(s, 0);
return res;
}
private void backtrack(String s, int idx) {
if (idx == s.length()) {
if (ip.size() == 4) {
//将 ip 中的元素以.作为分隔符拼接成一个字符串，并将该字符串添加到 res 中。
res.add(String.join(".", ip));
}
return;
}
for (int i = idx; i < s.length(); ++i) {
//从字符串 s 中取出从索引 idx 开始到索引 i（包括索引 i）之间的子字符串，并将其赋值给临时变量 tmp
String tmp = s.substring(idx, i + 1);
if ((tmp.length() > 1 && tmp.startsWith("0")) || Integer.parseInt(tmp) > 255 || ip.size() >= 4) {
return;
}
ip.add(tmp);
backtrack(s, i + 1);
ip.remove(ip.size() - 1);
}
}
}
木棍组成的有效三角形个数（滴滴 0928）
一家木材厂需要加工三根圆木。这三根圆木长度分别为 a,b,c，一共需要进行不超过n次加工程序。第i道加工程序需要选择其中一根长度严格大于i的圆木，将其切割，使其长度减少i。被切下的部分不再进入后续的加工流程。如果这三根圆木的长度能够组成一个面积大于0的三角形，那么就称此时的圆木长度三元组(ab,c)是好的 现在的问题是:一共可能形成多少种好的三元组?
输入描述
输入仅一行四个正整数n,a,b,c。对于100%的数据，1<=n,a,b,c<=100
输出描述
输出一行，一个整数，表示好的三元组的个数
样例输入
5 3 4 5
样例输出
10
提示
有如下10种三元组 (1,4,4),(2,2,2),(2,4,3),(2,4,5),(3,2,4),(3,3,3),(3,3,5),(3,4,2),(3,4,4),(3,4,5)
n为5即可加工不超过5次，原始3根圆木的长度为3，4，5
以(1,4,4)为例，可以第1道加工长度为5的圆木，使其长度变为4，第2道加工长度为3的圆木，使其长度变为1。此时不再进行加工，3根圆木的长度为1，4，4可以构成面积不为0的三角形
以(2,2,2)为例，可以第1道加工长度为3的圆木，使其长度变为2，第2道加工长度为4的圆木，使其长度变为2;第3道加工长度为5的圆木，使其长度变为2。此时不再进行加工，3根圆木的长度为2,2,2可以构成面积不为0的三角形
其他组合以此类推
思路与代码：
动态规划（偏暴力） 或 记忆化dfs
给出动态规划的思路和代码
定义dp[i] [j] [k] [l] 表示，第i次加工，三根木棍分别长j k l是否存在;
同时定义vis[j] [k] [l] 表示，三元组j k l是否已访问;
判断能否构成三角形可以通过两条短边之和是否大于最大边来判断；
在过程中判断能构成三角形的三元组在第一次访问时累加答案；
初始情况为dp[0] [a] [b] [c] = 1;
接下来就是循环中分别尝试对三条边做减操作；
定义dp[i] [j] [k] [l] 表示，第i次加工，三根木棍分别长j k l是否存在;
dp[i][j - i][k][l] = dp[i - 1][j][k][l];是因为dp[i][j - i][k][l]表示j切去i之后，这种长度的情况是存在的，可以由dp[i - 1][j][k][l]推算得到
#include<bits/stdc++.h>
using namespace std;
int dp[105][105][105][105];
int vis[105][105][105];
int judge(int a, int b, int c) {
int ma = max({
a, b, c});
if(a + b + c - ma > ma) {
return 1;
}
return 0;
}
int main() {
int n, a, b, c;
long long ans = 0;
cin >> n >> a >> b >> c;
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
dp[0][a][b][c] = 1;
if(judge(a, b, c) == 1) {
ans++;
}
vis[a][b][c] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= a; j++) {
for (int k = 1; k <= b; k++) {
for (int l = 1; l <= c; l++) {
if(j - i > 0 && dp[i - 1][j][k][l] != 0) {
//定义dp[i] [j] [k] [l] 表示，第i次加工，三根木棍分别长j k l是否存在;
dp[i][j - i][k][l] = dp[i - 1][j][k][l];
if(vis[j - i][k][l] == 0 && judge(j - i, k, l) == 1) {
ans++;
vis[j - i][k][l] = 1;
}
}
if(k - i > 0 && dp[i - 1][j][k][l] != 0) {
dp[i][j][k - i][l] = dp[i - 1][j][k][l];
if(vis[j][k - i][l] == 0 && judge(j, k - i, l) == 1) {
ans++;
vis[j][k - i][l] = 1;
}
}
if(l - i > 0 && dp[i - 1][j][k][l] != 0) {
dp[i][j][k][l - i] = dp[i - 1][j][k][l];
if(vis[j][k][l - i] == 0 && judge(j, k, l - i) == 1) {
ans++;
vis[j][k][l - i] = 1;
}
}
}
}
}
}
cout << ans << endl;
return 0;
}
树形动态规划（滴滴 0928）
类似leetcode 837题
官方题解讲的不错
https://leetcode.cn/problems/sum-of-distances-in-tree/solutions/437205/shu-zhong-ju-chi-zhi-he-by-leetcode-solution/
首先计算根节点到其他节点的距离和
**dp[u]表示以u为根的子树，其所有子节点到它的距离，
nodes[u] 表示以u为根的子树的节点数量，**可以得到树形dp递推式
nodes[u] = nodesv
由此dfs可得到dp[root]。
为了避免每个根都重复计算，接下来要进行换根操作
让 v 换到根u的位置，u 变为其孩子节点，同时维护原有的dp 信息，该过程中只会改变dp[u]和dp[v]，只更新这两者即可
回顾之前计算dp[]的过程，改动后，dp[u]要减去原来节点v的部分，即dp[u] -= dp[v] + nodes[v];
同时nodes也要相应减少，nodes[u] -= nodes[v];
与此同时，dp[v] 和nodes[v]也有相应的加操作
dp[v] += dp[u] + nodes[u]; nodes[v] += nodes[u];
此时就完成了换根，在O(1)时间内得到以v为根的dp值，之后就是dfs和相应的回溯操作；
本题的改动点就在于树的边的输入，以及查询，另外节点是从1开始的，代码上统一调整从0开始；
#include<bits/stdc++.h>
using namespace std;
using gg = long long;
vector<vector<gg>> map1;
vector<gg> dp, nodes, ans;
void dfs(gg u, gg fa) {
dp[u] = 0;
nodes[u] = 1;
for(auto& ch : map1[u]) {
if(ch == fa) continue;
dfs(ch, u);
dp[u] += dp[ch] + nodes[ch];
nodes[u] += nodes[ch];
}
}
void dfs2(gg u, gg fa) {
ans[u] = dp[u];
for(auto& ch : map1[u]) {
if(ch == fa) continue;
gg su = dp[u], sc = nodes[u];
gg cu = dp[ch], cc = nodes[ch];
dp[u] -= dp[ch] + nodes[ch];
nodes[u] -= nodes[ch];
dp[ch] += dp[u] + nodes[u];
nodes[ch] += nodes[u];
dfs2(ch, u);
// 回溯
dp[u] = su; nodes[u] = sc;
dp[ch] = cu; nodes[ch] = cc;
}
}
int main() {
gg n, m; cin >> n >> m;
dp.resize(n); ans.resize(n); nodes.resize(n);
map1.resize(n, {
});
for(int i = 2; i <= n; i++) {
gg x; cin >> x;
gg u = i - 1, v = x - 1;
map1[u].push_back(v);
map1[v].push_back(u);
}
dfs(0, -1);
dfs2(0, -1);
vector<gg> pans(m);
for(int i = 0; i < m; i++) {
gg ask; cin >> ask;
pans[i] = ans[ask-1];
}
cout << pans[0];
for(int i = 1; i < m; i++) cout << ' ' << pans[i];
cout << '\n';
return 0;
}
去掉1个1（小米 1014）
时间限制：1000MS内存限制：65536KB
题目描述
刷掉一个元素以后全为1的最长子数组。
给定一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包合 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0。
输入描述
一个二进制数组
限制; 1length(二进制数组)<10^4
输出描述
删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
样例输入
[1,1,0,1]
样例输出
3
提示
删掉位置 2 的数后，[1,1,1] 包含 3 个 1。
思路与代码
删掉一个数，返回最长的全是1的子数组。
遍历一遍，记录连续1的起点和终点。
然后再遍历一遍刚才记录的起点和终点，前面的终点和后面的起点要是只差1的话就可以合并，这个过程中记录下最长的就行了。
复杂度O(n)。
要注意是一定要删掉一个元素，如果全是1的话，结果是要少1的。
std::vector<int> split(std::string s, const char c)
{
// 输入是[1,1,0,1]这种形式的，所以要写split函数
std::istringstream iss(s);
std::string token;
std::vector<int> result;
while (std::getline(iss, token, c))
{
result.push_back(token[0] - '0');
}
return result;
}
// std::getline 函数是一个库函数，用于从输入流中读取一行字符串。它的原型如下：
// std::istream &
// getline(std::istream &is, std::string &str, char delim);
// 其中的第三个参数 delim 表示分隔符，指定了在何处将字符串分割成多个子字符串。
// 这里的 c 就是作为 delim 参数传递给 std::getline 函数的。在这段代码中，
// 使用指定的字符 c 对 std::istringstream 对象 iss 中的字符串进行分割操作。
// 每次遇到字符 c，std::getline 就将字符串分割成一个子字符串，并将该子字符串存储在 token 变量中。
int main()
{
std::string s;
std::cin >> s;
std::vector<int> nums = split(s.substr(1, s.size() - 2), ',');
// 记录连续1的起点终点
// 如果不是1，start也是-1，continue，否则push
// 如果是连续的第一个1，也就是start = -1，那就两个都变
// 如果不是第一个1，只有end++
int n = nums.size();
std::vector<std::vector<int>> sande;
int start = -1;
int end = -1;
for (int i = 0; i < n; i++)
{
if (nums[i] != 1)
{
if (start == -1)
continue;
else
{
sande.push_back({
start, end});
start = -1;
end = -1;
}
}
else
{
if (start == -1)
{
start = i;
end = i;
}
else
{
end = i;
}
}
}
if (start != -1)
sande.push_back({
start, end});
if (sande.size() == 1)
{
std::cout << sande[0][1] - sande[0][0] << std::endl;
return 1;
} // 全是1的情况
int result = 0;
for (int i = 0; i < sande.size() - 1; i++)
{
int len1 = sande[i][1] - sande[i][0] + 1;
if (result < len1)
result = len1;
int len2 = sande[i + 1][1] - sande[i + 1][0] + 1;
if (result < len2)
result = len2;
int len3 = 0;
if (sande[i + 1][0] - sande[i][1] == 2)
{
len3 = len1 + len2;
}
if (result < len3)
result = len3;
}
std::cout << result << std::endl;
}
比较版本号（小米 1014）
时间限制：1000MS内存限制：65530KB
假设你是一个安卓app的开发者，在App的版本升级时经常需要比较两个版本号。给你两个版本号version1和version2，请你比较它们。版本号由一个或多个修订号组成，各修订号由一个.链接。每个修订号由多位数字组成，可能包含前导零。例如，2.5.33和0.1都是有效的版本号。
比较版本号时，请注意如下规则：
1.按从左到右的顺序依次比较它们的修订号。
2.从左到右比较两个版本号时，如果其中一个版本号没有修订号，可以用0补齐，也就是说，版本号1.1和1.1.0相等。
3.只离比较忽略任何前导零后的整数值，也就是说，修订号1和修订号 001相等。
输入描述
2个版本号之间用逗号分隔，例如: 1.01,1.001
输出描述
1.如果 version1 > version2 返回 1,
2.如果 version1 < version2 返回-1
3.除此之外返回 0。
样例输入
1.01,1.001
样例输出
0
思路与代码
比较两个版本号，每个版本号由多个修订号用“.”连接(可能有前导0)
从左到右比较，位数可能不相等，需要用0补，前导0是需要被忽略的
如果长度不一样就把短的补补0
然后遍历
先处理前导0，转成int，比较
split函数可以用作日后的模板
std::vector<std::string> split(std::string s, const char c)
{
// 输入要想用","分再用"."分
std::istringstream iss(s);
std::string token;
std::vector<std::string> result;
while (std::getline(iss, token, c))
{
result.push_back(token);
}
return result;
}
int string2int(std::string s)
{
// 处理前导0和string转int
int index = 0;
int n = s.size();
for (int i = 0; i < n; i++)
{
if (s[i] == 0)
index++;
}
if (index >= n)
return 0;
else
return std::stoi(s.substr(index, n - index));
}
int main()
{
std::string s;
std::cin >> s;
std::vector<std::string> s_ = split(s, ',');
std::vector<std::string> s1 = split(s_[0], '.');
std::vector<std::string> s2 = split(s_[1], '.');
if (s1.size() > s2.size())
{
// 补齐长度
for (int i = 0; i < s1.size() - s2.size(); i++)
{
s2.push_back("0");
}
}
if (s2.size() > s1.size())
{
for (int i = 0; i < s2.size() - s1.size(); i++)
{
s1.push_back("0");
}
}
int n = s1.size();
for (int i = 0; i < n; i++)
{
int ver1 = string2int(s1[i]);
int ver2 = string2int(s2[i]);
if (ver1 > ver2)
{
std::cout << 1 << std::endl;
return 1;
}
if (ver1 < ver2)
{
std::cout << -1 << std::endl;
return 1;
}
}
std::cout << 0 << std::endl;
return 1;
}
优质瓜（字节 1015）
小红准备卖n个西瓜,已知每个西瓜的品质为ai。小红可以设置一个品质标准品质x，不小于x的西瓜为优质品。小红希望设置完品质标准x后,当顾客从左到右依次买瓜时，每个人买到优质品的概率都不小于P(顾客不知道哪个瓜是优质品,只知道剩下的瓜数量以及剩下的优质品数量)。小红想知道,x的最大值是多少?
输入描述：
第一行输入一个正整数n和一个正实数p,含义如题意所述。
第二行输入n个正整数ai,分别代表每个瓜的品质。
输出描述：
一个正整数,代表x的最大值。
示例1：
// 输入
4 0.5
5 3 9 6
// 输出：
6
// 说明：
当优质品标准设置为6时,第三个和第四个瓜是优质品：
第一个顾客买瓜时,买到优质品的概率是0.5。
第二个顾客买瓜时,买到优质品的概率是0.6666666。
第三个顾客买瓜时,买到优质品的概率是1。
第四个顾客买瓜时,买到优质品的概率是1。
可以证明,6为品质标准设置的最大值。
思路：
二分：其实只看题目并没有清楚具体含义，通过示例可以看出，顾客从左往右买瓜时，是按照次序买的，即第一个人只能买第一个瓜，那么就比较直观了；可以使用二分，枚举品质标准的设置值mid，再计算当品质标准为x时，是否满足买到优质品的概率不低于p；
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;
int main()
{
{
int n;
double p;
cin >> n >> p;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
int l = 1, r = 1e9;
// 不断更新mid值，试探合乎要求的最大值
while (l <= r)
{
int mid = (l + r) / 2;
bool ok = true;
int good = 0;
for (int i = n - 1; i >= 0 && ok; --i)
{
// 注意要从后向前遍历，记录符合条件的good值，不符合条件就直接退出
good += a[i] >= mid;
double cur = good * 1.0 / (n - i);
if (cur < p)
ok = false;
}
// 如果各种情况下都能符合条件
if (ok)
l = mid + l;
else
r = mid - l;
}
// 二分查找的过程中，每次更新左边界或右边界时，都将当前中间值 mid 加或减给左/右边界，
// 所以当结束循环时，左边界 l 的值肯定比右边界 r 的值大 1。所以最终返回 l - 1 就得到了符合要求的最大值。
// 实际上就是返回迭代中最后一个mid值
cout << l - 1;
}
return 0;
}
字符串中出现次数不同的字符（建信金科 1016）
给定一个字符串s，现在想让你删除掉一些字符，使得这个字符串每个字符出现的次数均不相同，想知道最少需要删除多少个字符?
示例1
输入
“aab”
输出
0
说明
我们不需要删除任何字符，a出现了2次，b出现了1次
思路与代码
给定一个字符串s，现在想让你删除掉一些字符，使得这个字符串每个字符出现的次数均不相同，想知道最少需要删除多少个字符?
首先采用长度为26的int数组来统计字符串s中不同字符出现的次数，然后利用HashSet元素不重复的特性进行删除操作：遍历int数组，当a[i]不为0且set中不存在a[i]，直接添加到set中；当a[i]不为0，a[i]在set中已存在的情况下，对a[i]–，操作数res++，直到a[i]在set中不存在，此时判断a[i]是否大于0，大于0才加入set集合中。
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;
int main()
{
{
int n;
double p;
cin >> n >> p;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
int l = 1, r = 1e9;
// 不断更新mid值，试探合乎要求的最大值
while (l <= r)
{
int mid = (l + r) / 2;
bool ok = true;
int good = 0;
for (int i = n - 1; i >= 0 && ok; --i)
{
// 注意要从后向前遍历，记录符合条件的good值，不符合条件就直接退出
good += a[i] >= mid;
double cur = good * 1.0 / (n - i);
if (cur < p)
ok = false;
}
// 如果各种情况下都能符合条件
if (ok)
l = mid + l;
else
r = mid - l;
}
// 二分查找的过程中，每次更新左边界或右边界时，都将当前中间值 mid 加或减给左/右边界，
// 所以当结束循环时，左边界 l 的值肯定比右边界 r 的值大 1。所以最终返回 l - 1 就得到了符合要求的最大值。
// 实际上就是返回迭代中最后一个mid值
cout << l - 1;
}
return 0;
}
小红一家人（阿里文娱 1015）
小红拿到了一棵二叉树。小红定义，如果一个节点既有左孩子又有右孩子，那么这三个节点被称为 “一家人”。
小红想知道，在这个二叉树中，一共能找到多少 “一家人”？ (每个节点最多被计算一次)，任意两点权值互不相同。
样例
输入：
{1,2,3,4,5,6,7}
输出：
2
提示：
若选择了[1,2,3]这一家人，那么2,3节点就无法选取为父亲，最终就只有一组“一家人”。
上面样例对应的树为：
解答
有点类似力扣-打家劫舍问题
来源：https://ujimatsu-chiya.github.io/EXAM/Alidawenyu-20231015/
class Solution {
public:
vector<int> dfs(TreeNode *r){
if(r->left==nullptr&&r->right==nullptr) return {
0,0};
if(r->left==nullptr){
vector<int>v=dfs(r->right);
return {
max(v[0],v[1]),0};
}
else if(r->right==nullptr){
vector<int>v=dfs(r->left);
return {
max(v[0],v[1]),0};
}
else{
vector<int> vl=dfs(r->left),vr=dfs(r->right);
return {
max(vl[0],vl[1])+max(vr[0],vr[1]),vl[0]+vr[0]+1};
}
}
int maxDepth(TreeNode* root) {
vector<int>v=dfs(root);
return max(v[0],v[1]);
}
};
最小的区间（度小满 1009？）
样例
输入：
8 5
2 3 3 1 2 4 2 5
1 2 0 0 0
输出：
4
提示：
样例中，区间[4,7]是长度最小的满足条件的区间，其区间长度为7-4+1=4。
样例中需要满足的条件是“1至少出现1次”，“2至少出现2次”，“3、4、5至少出现0次”。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],b[N],n,m;
int cnt[N];
unordered_set<int>st;
void add(int x,int op){
if(x>m) return;
if(op==1){
if(++cnt[x]>=b[x])
st.erase(x);
}
else{
if(--cnt[x]<b[x])
st.insert(x);
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
if(b[i]) st.insert(i);
}
int ans=1e9;
for(int l=1,r=1;l<=n;l++){
for(;r<=n&&!st.empty();r++){
add(a[r],1);
}
if(st.empty()){
ans=min(ans,r-l);
}
add(a[l],-1);
}
if(ans>n) ans=-1;
printf("%d\n",ans);
}
accept（度小满 1009）
输出
对于每组数据，如果存在则输出 “YES” 否则输出 “NO”。
样例
输入：
2
10
dc
ac
ca
ec
cc
qe
gp
ht
ee
pd
2 10
dscacceptd
pqoxaccepw
输出：
YES
YES
提示：
第一组数据中，第二列中包舍了"accept"子串。
第二组数据中，第一行中包含了“accept"子串。
首先枚举 “accept” 或者是其逆序 “tpecca” 是否在字符矩阵的每一行存在即可，可以使用内置的库完成。
至于纵向的处理，只需要将这个字符矩阵进行转置，再进行和刚刚相同的操作即可。
p1 = "accept"
p2 = p1[::-1]
def solve(ls):
for s in ls:
if p1 in s or p2 in s:
return True
n, m = len(ls), len(ls[0])
lt = ["" for _ in range(m)]
//矩阵倒置
for i in range(n):
for j in range(m):
lt[j] += ls[i][j]
for s in lt:
if p1 in s or p2 in s:
return True
return False
T = int(input())
for _ in range(T):
n, m = map(int, input().split())
ls = []
for i in range(n):
ls.append(input())
print("YES" if solve(ls) else "NO")
37进制乘法（广发银行 1021）
37进制的规则为:“0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ$”输入两个37进制数字请输出二者相乘的结果。输入的数字位数，不超过999位。
输入
“Z”,“1”
输出
“Z”
输入
“A”,“B”
输出
“2$”
思路与代码：
把两个字符串的每一位拆开，模拟乘法的操作，注意进位即可。
#include<string>
#include<iostream>
using namespace std;
class Solution {
public:
int get(char ch) {
return ch >= 'A' ? ch - 'A' + 10 : (ch == '$' ? 36 : ch - '0');
}
string mul37(string x, string y) {
int n = x.size(), m = y.size();
int len = n + m;
//先预留分配一个全0数组，大了没关系，可以减
int a[len+10] = {
0};
//a数组低位存放高位计算结果
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int ai = get(x[n - 1 - i]);
int aj = get(y[m - 1 - j]);
a[i + j] += ai * aj;
a[i + j + 1] += a[i + j] / 37;
a[i + j] %= 37;
}
}
//用不到的剪掉
while (len > 1 && a[len - 1] == 0) len--;
string ans;
//重新恢复顺序，倒过来
for (int i = len - 1; i >= 0; i--) {
char c;
if (a[i] >= 10 && a[i] <= 35) c = a[i] - 10 + 'A';
else if (a[i] == 36) c = '$';
else c = a[i] + '0';
ans += c;
}
return ans;
}
};
到两个源点距离的最小值（字节 1022）
小红和朋友被困在了迷宫里，迷宫有n 个传送阵，每个传送阵都有一个编号i(编号从1到n)，编号为i的传送阵会将小红传送到编号为ai的传送阵。小红最初在编号为s的传送阵，朋友最初在编号为t的传送阵，小红和朋友都可以通过传送阵传送，每次传送都会花费一分钟(两人可以同时传送)。现在小红想知道，小红和朋友最少需要多少分钟才能在同一个传送阵里见面，如果不能见面，输出 -1。
输入描述
第一行输入三个整数n，s，t，表示传送阵的数量，小红最初所在的传送阵编号，朋友最初所在的传送阵编号。
第二行输入n个整数ai，表示编号为i的传送阵会将小红传送到编号为ai的传送阵。
1<=n<=10^5
1<=s,t<=n
1<=ai<=n
保证 a 数组中的元素互不相同。
输出描述
输出一个整数，表示小红和朋友最少需要多少分钟才能在同一个传送阵里见面，如果不能见面，输出-1。
示例1
输入
5 1 2
5 1 2 3 4
输出
1
思路与代码
该程序的核心思想是通过使用广度优先搜索（BFS）算法，计算从给定起点 s 和终点 t 到图中所有其他节点的最短距离。首先，将输入的节点信息存储在向量中，并初始化两个向量 S 和 T，用于分别记录从 s 和 t 到各个节点的距离，初始值为无穷大（INT_MAX）。然后，通过两次BFS遍历计算出从 s 和 t 到每个节点的最短距离，并将结果存储在 S 和 T 向量中。接下来，程序找到从 s 和 t 到每个节点的最短距离之间的最大值，找到最小值，这将是从 s 和 t 到达某个节点的最短路径。最后，程序输出这个最小值作为答案，如果无法从 s 和 t 到达任何节点，则输出 -1。这个核心思想允许解决一种特定问题，即从起点 s 和终点 t 出发，寻找最短路径，并输出其长度。
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n,s,t;
cin >> n >> s >> t;
s--,t--;
vector<int> next(n);
for(int i = 0;i < n;i++) {
int a;
cin >> a;
a--;
next[i] = a;
}
vector<int> S(n,INT_MAX);
S[s] = 0;
vector<int> T(n,INT_MAX);
T[t] = 0;
queue<int> q;
q.push(s);
int d = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
S[cur] = d;
if(S[next[cur]] == INT_MAX) {
q.push(next[cur]);
}
d++;
}
q.push(t);
d = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
T[cur] = d;
if(T[next[cur]] == INT_MAX) {
q.push(next[cur]);
}
d++;
}
int ans = INT_MAX;
for(int i = 0;i < n;i++) {
if(S[i] != INT_MAX && T[i] != INT_MAX) {
//迭代求最小值的最大值
ans = min(ans,max(S[i],T[i]));
}
}
if(ans == INT_MAX) {
cout << -1 << endl;
}else {
cout << ans << endl;
}
}
int main() {
solve();
}
贪心-赛车队组队（字节 1022）
样例
输入：
1
4
1 2 3 4
输出：
3
提示：
前两个车队一组，第三个车队一组，第四个车队一组即可。
代码：
# include <bits/stdc++.h>
using namespace std;
int c[7];
int solve(){
memset(c,0,sizeof(c));
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);++c[x];
}
int ans=c[4]+c[3];
c[1]=max(0,c[1]-c[3]);
ans+=c[2]>>1;
if(c[2]&1){
++ans;
c[1]=max(0,c[1]-2);
}
ans+=(c[1]+3)/4;
return ans;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
printf("%d\n",solve());
}
}
不相交区间-动态规划（字节 1022）
题解来自https://ujimatsu-chiya.github.io/EXAM/Zijietiaodong-20231022/
输出
输出一个整数，表示可以获得的最大分数。
样例
输入：
5 3
1 2 3 4 9
1 4
2 3
4 5
输出：
18
输入：
5 3
9 2 3 4 1
1 4
2 3
4 5
输出：
18
解答
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll f[N],s[N];
int a[N];
vector<int>g[N];
int main(){
int n,m,l,r;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
for(int i=1;i<=m;i++){
scanf("%d %d",&l,&r);
//以l为终点的起点
if(r<=n) g[r].push_back(l);
}
for(int r=1;r<=n;r++){
f[r]=f[r-1];
for(int l:g[r]){
f[r]=max(f[r],f[l-1]+s[r]-s[l-1]);
}
}
printf("%lld\n",f[n]);
}
字符子串是oppo的最小修改次数？（oppo 1027）
小欧有一个仅由小写字母组成的字符串，小欧每次可以修改一个字母，求使得字符串中至少有k个子串是“oppo”的最小修改次数。
输入描述
第一行输入两个整数 n,k(1<=n<=10^4,1<=k<=200)
第二行输入一个长度为 n 的仅由小写字母组成的字符串。
输出描述
输出一个整数表示答案。
若是无解则输出 -1。
示例1
输入
4 1
opop
输出
2
说明
可以将字符串 后两个字母改成”po”，此时字符串变成了"oppo"，有1个子串是"oppo”
思路与代码
使用动态规划的方法，计算了在给定操作次数下，通过替换字符’o’为’p’，使得字符串中的字符’p’连续出现的最小次数。如果无法进行足够的替换操作，则输出-1。
public class Solution {
static int kk = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
String s = in.next();
if (n < k * 3 + 1){
System.out.println(-1);
return;
}
int[][] dp = new int[n + 1][k + 1];
int[][] min = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], kk);
Arrays.fill(min[i], kk);
}
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
min[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (i < 3 * j + 1){
dp[i][j] = kk;
continue;
}
int tt = 0;
if (j == 1){
if (s.charAt(i - 1) != 'o') tt++;
if (s.charAt(i - 2) != 'p') tt++;
if (s.charAt(i - 3) != 'p') tt++;
if (s.charAt(i - 4) != 'o') tt++;
dp[i][j] = dp[i-4][j-1] + tt;
min[i][j] = Math.min(min[i-1][j], dp[i][j]);
}else{
if (s.charAt(i - 1) != 'o') tt++;
if (s.charAt(i - 2) != 'p') tt++;
if (s.charAt(i - 3) != 'p') tt++;
dp[i][j] = dp[i-3][j-1] + tt;
if (s.charAt(i - 4) != 'o') tt++;
dp[i][j] = Math.min(min[i-4][j-1] + tt, dp[i][j]);
min[i][j] = Math.min(min[i-1][j], dp[i][j]);
}
}
}
int res = kk;
for (int i = 3 * k + 1; i <= n; i++) {
res = Math.min(res, dp[i][k]);
}
System.out.println(res);
}
}
切分字符串使得3的倍数最多（吉比特 1025）
小红喜欢 3 的倍数的数字，现在小红有一个长度为 n 的数字串，小红想通过分隔字符串的方式，获得一些子串，每个子串代表一个数字，那么小红最多能获得多少个数字是 3 的倍数呢？
比如，小红有数字 1123，那么可以分隔为[1,12,3]，这样获得了两个数字是 3 的倍数。
请注意，分隔后的数字串，不能包含前导零，比如 012 不能视为 12。可以分割出 0，0 也是 3 的倍数。怎么用C++和动态规划写这道题？
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int getMaxMultiples(string s) {
int n = s.size();
vector<int> dp(n+1, 0); // dp[i]表示前i个字符中能获得的最多的数字是3的倍数的个数
for (int i = 1; i <= n; i++) {
dp[i] = dp[i-1]; // 不将当前字符作为单独的数字分隔出来
int num = 0;
for (int j = i; j > 0; j--) {
num = (num * 10 + (s[j-1] - '0')) % 3;
if (num == 0) {
dp[i] = max(dp[i], dp[j-1] + 1); // 将前j-1个字符与第j个字符一起分隔出来作为一个数字
}
}
}
return dp[n];
}
int main() {
string s;
cout << "请输入数字串: ";
cin >> s;
int result = getMaxMultiples(s);
cout << "小红最多能获得 " << result << " 个数字是3的倍数" << endl;
return 0;
}
字典序最小的回文串（阿里飞猪 1028）
小红拿到了一个仅由小写字母组成的字符串s,她希望你构造一个字符串t，满足以下条件：
1.也是仅由小写字母组成，长度和s相同。
2.t是回文串。
3.的字典序小于s，且在满足以上条件时字典序尽可能大。
输入描述：
一个字符串s,字符串长度不超过100000。
输出描述：
如果无解，则输出-1。否则输出一个字符串t。
输入
abc
输出
aba
输入
cba
输出
cac
思路与代码
根据题意，先去除len(s)/2个字符，用他来构造回文串t，看t和s的大小关系，如果不满足则在前len(s)/2字符内贪心的找到最后一个不为’a’的字符（假设位置idx），将它的字符值-1，并且让(idx,len(s)/2]位置的值都置为z即可。
对于s中字符全为a的情况，输出-1.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string s, t;
int main()
{
cin >> s;
for (int i = 0; i <= (s.size() - 1) / 2; i++)
{
t += s[i];
}
int up = (s.size() - 1) / 2;
if (s.size() % 2 == 1)
up--;
for (int i = up; i >= 0; i--)
t += s[i];
if (t >= s)
{
//从中轴线开始
int idx = (s.size() - 1) / 2;
//相当于借位，'0'-1 == '9'
while (idx >= 0 && s[idx] == 'a')
{
t[idx] = 'z';
idx--;
}
if (idx < 0)
t = "-1";
//如果借位有效
//就把能借到的一个有效位-1
//t后边的东西就按对称的来（回文字串）
else
{
t[idx]--;
for (int i = (s.size() - 1) / 2 + 1; i < s.size(); i++)
{
t[i] = t[s.size() - i - 1];
}
}
}
cout << t << endl;
return 0;
}
三个子节点的树（阿里飞猪 1028）
小红希望你构造一棵树，满足共有n个节点，且恰好有k个节点的度数为3。你能帮帮她吗？
输入描述：
输入两个整数n,k，用空格隔开。
1≤k≤n≤10^5
输出描述：
如果无解，请输出1。否则输出n-1行，每行输出两个正整数u,v,用空格隔开，代表节点u和节点v连一条边。
请务必保正最终构造的为一棵树，且恰好有k个节点的度数为3。有解时输出任意即可。
1≤u,v≤n
输入
4 1
输出
1 2
1 3
1 4
输入
4 2
输出
-1
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> vv[100005];
int n, k;
int main()
{
cin >> n >> k;
// mx是当前遍历子节点的序号指向
// cur 是遍历中父节点的序号指向
int cur = 1, mx = 2;
bool ok = true;
for (int i = 1; i <= k; i++)
{
// 节点已经指向了最后一个，超出了范围
// 此处可以改为mx > n吗？
if (mx + 1 > n)
{
ok = false;
break;
}
// 其他所有非叶子节点都有两个孩子”即可
int num = 2;
if (i == 1)
// 只要构造出一棵“根节点有三个孩子
num = 3;
for (int j = 0; j < num; j++)
// 用Vector存节点和孩子的关系
vv[cur].push_back(mx++);
cur++;
}
// 剩下的节点成一条链状，接在最后一个节点上即可
while (mx <= n)
{
vv[mx - 1].push_back(mx);
mx++;
}
if (ok == false)
cout << -1 << endl;
else
{
for (int i = 1; i <= n; i++)
{
for (auto x : vv[i])
{
cout << i << " " << x << endl;
}
}
}
return 0;
}
链表节点合并（建信金科 1104）
小红拿到了一个链表，她需要把所有偶数节点合并到该节点前面和它相邻的奇数节点上(新节点权值为两个节点权值之和)，直到剩余的节点无法合并为止。你能帮帮她吗?
示例1
输入
{2,3,4,1,2,2,3}
输出
{2,7,5,3}
说明
对于链表2->3->4->1->2->2->3，先将4合并到3上面，形成2->7->1->2->2->3，然后将2合并到1上面，形成2->7->3->2->3，最后将2合并到3上面，形成2->7->5->3。此时无法合并，合并结束。
思路与代码
在循环中，首先跳过当前节点和后续的所有偶数值节点，直到找到一个奇数值节点或到达链表末尾。
ListNode mergNode(ListNode head) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur = head;
while(cur != null) {
//跳过偶数节点，找到最前边的奇树节点并停下
while(cur != null && cur.val % 2 == 0) {
cur = cur.next;
}
if(cur == null) break;
ListNode next = cur.next;
//后边第二个奇数节点前的偶数节点都加到这个节点上
//
while(next != null && next.val % 2 == 0) {
cur.val += next.val;
next = next.next;
}
//进到下一个奇数节点
//进行下一轮循环
cur.next = next;
cur = next;
}
return dummy.next;
}
删除节点清空链表的次数期望值（建信金科 1104）
小红拿到了一个链表。她每次操作会随机选择一个节点，将该节点、该节点下一个节点和该节点上一个节点同时删除。请注意，如果选择的节点是头节点，则不存在上一个节点，若是尾节点，则不存在下一个节点。
小红希望你计算将链表删成空链表的操作次数的期望 1<=n<=10^5
如果你返回的答案和正确答案的相对误差不超过10^-3，则认为你的答案正确。
示例1
输入
3
输出
1.66666667
说明
如果第一次击打最左边或者最右边的弹珠，则还需要一次击打。
如果第一次击打中间的弹珠，则直接打出全部弹珠。答案是1/3* 1+2/3*2=5/3
思路与代码
直接使用动态规划的方式计算了一个级数的期望值，并在最后将结果以8位小数的形式打印出来。
static double get_expect(int n) {
if(n == 1 || n == 2) {
return (double)1;
}
double[] f = new double[n + 1];
f[1] = 1;
f[2] = 1;
for(int i = 3;i <= n;i++) {
//分情况讨论
//删除开头结尾或者中间的，分别减去2和3
//动态规划
f[i] += (double)(i - 2) / i * (1 + f[i - 3]);
f[i] += (double)2 / i * (1 + f[i - 2]);
}
double ans = f[n];
String str = String.format("%.8f", ans);
ans = Double.parseDouble(str);
return ans;
}
public static void main(String[] args) {
int n = 3;
System.out.println(get_expect(n));
}
}
数组质因子转移（aliyun 1029）
样例
输入：
2
4
1 2 3 4
2
10 12
输出：
Yes
No
提示：
第一组询问，不需要任何操作，因为每个元素本身只含一种素因子。
第二组询问，显然是无解的。
解答
题目中提到的操作意味着可以将每一个数的质因子转移到另一个数中。因此，一种贪心的思想是：同一个下标的数汇聚所有同一个质因子。
因此，我们只需要分别对 a 中的每个数进行质因数分解，然后判断这些不同的质因子数量是否超过 n 即可，因为同一个质因子可以汇聚到不同的下标。
import sympy
def solve(a):
n = len(a)
st = set()
for x in a:
// 分解为质因子相乘的形式，并求并集
st |= set(sympy.factorint(x).keys())
if len(st) > n:
return False
return True
T = int(input())
for _ in range(T):
input()
a = list(map(int, input().split()))
print("Yes" if solve(a) else "No")
智能推荐
js-选项卡原理_选项卡js原理-程序员宅基地
文章浏览阅读90次。【代码】js-选项卡原理。_选项卡js原理
设计模式-原型模式（Prototype）-程序员宅基地
文章浏览阅读67次。原型模式是一种对象创建型模式，它采用复制原型对象的方法来创建对象的实例。它创建的实例，具有与原型一样的数据结构和值分为深度克隆和浅度克隆。浅度克隆：克隆对象的值类型（基本数据类型），克隆引用类型的地址；深度克隆：克隆对象的值类型，引用类型的对象也复制一份副本。UML图：具体代码：浅度复制：import java.util.List;/*..._prototype 设计模式
个性化政府云的探索-程序员宅基地
文章浏览阅读59次。入选国内首批云计算服务创新发展试点城市的北京、上海、深圳、杭州和无锡起到了很好的示范作用，不仅促进了当地产业的升级换代，而且为国内其他城市发展云计算产业提供了很好的借鉴。据了解，目前国内至少有20个城市确定将云计算作为重点发展的产业。这势必会形成新一轮的云计算基础设施建设的**。由于云计算基础设施建设具有投资规模大，运维成本高，投资回收周期长，地域辐射性强等诸多特点，各地在建...
STM32问题集之BOOT0和BOOT1的作用_stm32boot0和boot1作用-程序员宅基地
文章浏览阅读9.4k次，点赞2次，收藏20次。一、功能及目的 在每个STM32的芯片上都有两个管脚BOOT0和BOOT1，这两个管脚在芯片复位时的电平状态决定了芯片复位后从哪个区域开始执行程序。BOOT1=x BOOT0=0 // 从用户闪存启动，这是正常的工作模式。BOOT1=0 BOOT0=1 // 从系统存储器启动，这种模式启动的程序_stm32boot0和boot1作用
C语言函数递归调用-程序员宅基地
文章浏览阅读3.4k次，点赞2次，收藏22次。C语言函数递归调用_c语言函数递归调用
明日方舟抽卡模拟器wiki_明日方舟bilibili服-明日方舟bilibili服下载-程序员宅基地
文章浏览阅读410次。明日方舟bilibili服是一款天灾驾到战斗热血的创新二次元废土风塔防手游，精妙的二次元纸片人设计，为宅友们源源不断更新超多的纸片人老婆老公们，玩家将扮演废土正义一方“罗德岛”中的指挥官，与你身边的感染者们并肩作战。与同类塔防手游与众不同的几点，首先你可以在这抽卡轻松获得稀有，同时也可以在战斗体系和敌军走位机制看到不同。明日方舟bilibili服设定：1、起因不明并四处肆虐的天灾，席卷过的土地上出..._明日方舟抽卡模拟器
随便推点
Maven上传Jar到私服报错：ReasonPhrase: Repository version policy: SNAPSHOT does not allow version: xxx_repository version policy snapshot does not all-程序员宅基地
文章浏览阅读437次。Maven上传Jar到私服报错：ReasonPhrase: Repository version policy: SNAPSHOT does not allow version: xxx_repository version policy snapshot does not all
斐波那契数列、素数、质数和猴子吃桃问题_斐波那契日-程序员宅基地
文章浏览阅读1.2k次。斐波那契数列（Fibonacci Sequence）是由如下形式的一系列数字组成的：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …上述数字序列中反映出来的规律，就是下一个数字是该数字前面两个紧邻数字的和，具体如下所示：示例：比如上述斐波那契数列中的最后两个数，可以推导出34后面的数为21+34=55下面是一个更长一些的斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,_斐波那契日
PHP必会面试题_//该层循环用来控制每轮 冒出一个数 需要比较的次数-程序员宅基地
文章浏览阅读363次。PHP必会面试题1. 基础篇1. 用 PHP 打印出前一天的时间格式是 2017-12-28 22:21:21？ //>>1.当前时间减去一天的时间，然后再格式化echo date('Y-m-d H:i:s',time()-3600*24);//>>2.使用strtotime，可以将任何字符串时间转换成时间戳，仅针对英文echo date('Y-m-d H:i:s',str..._//该层循环用来控制每轮 冒出一个数 需要比较的次数
windows用mingw(g++)编译opencv，opencv_contrib，并install安装_opencv mingw contrib-程序员宅基地
文章浏览阅读1.3k次，点赞26次，收藏26次。windows下用mingw编译opencv貌似不支持cuda，选cuda会报错，我无法解决，所以没选cuda，下面两种编译方式支持。打开cmake gui程序，在下面两个框中分别输入opencv的源文件和编译目录，build-mingw为你创建的目录，可自定义命名。1、如果已经安装Qt，则Qt自带mingw编译器，从Qt安装目录找到编译器所在目录即可。1、如果已经安装Qt，则Qt自带cmake，从Qt安装目录找到cmake所在目录即可。2、若未安装Qt，则安装Mingw即可，参考我的另外一篇文章。_opencv mingw contrib
5个高质量简历模板网站，免费、免费、免费_hoso模板官网-程序员宅基地
文章浏览阅读10w+次，点赞42次，收藏309次。今天给大家推荐5个好用且免费的简历模板网站，简洁美观，非常值得收藏！1、菜鸟图库https://www.sucai999.com/search/word/0_242_0.html?v=NTYxMjky网站主要以设计类素材为主，办公类素材也很多，简历模板大部个偏简约风，各种版式都有，而且经常会更新。最重要的是全部都能免费下载。2、个人简历网https://www.gerenjianli.com/moban/这是一个专门提供简历模板的网站，里面有超多模板个类，找起来非常方便，风格也很多样，无须注册就能免费下载，_hoso模板官网
通过 TikTok 联盟提高销售额的 6 个步骤_tiktok联盟-程序员宅基地
文章浏览阅读142次。你听说过吗？该计划可让您以推广您的产品并在成功销售时支付佣金。它提供了新的营销渠道，使您的产品呈现在更广泛的受众面前并提高品牌知名度。此外，TikTok Shop联盟可以是一种经济高效的产品或服务营销方式。您只需在有人购买时付费，因此不存在在无效广告上浪费金钱的风险。这些诱人的好处是否足以让您想要开始您的TikTok Shop联盟活动？如果是这样，本指南适合您。_tiktok联盟