第一题:排列判断是否相邻
有一个排列,一共有n个数,还有两个数x和y,请你判断x和y在排列中是否相邻,是则输出”Yes”,不是则输出”No”
1 ≤ n ≤ 1e5
输入n,x,y
注意判断x的前后有没有y即可;
第二题:环形公路最短距离
现有一条环形公路,总共有n个站点,a[i]代表第i个站点与第i+1个站点之间的距离,特殊的,a[n]表示第n个站点与第一个站点之间的距离。出发地为x,目的地为y,请你求出x到y的最短距离
1 ≤ n ≤ 1e5
1 ≤ a[i] ≤ 1e9
注意a[i]要用long int,判断正着走与反着走哪个小输出哪个
第三题:切蛋糕
现有一个n*m的蛋糕矩阵a,a[i][j]代表一小块蛋糕的美味度,现在小美要和一个好朋友分享蛋糕,因此需要把这个蛋糕矩阵切成两半,并且要求分成两半后的两块蛋糕的美味度尽可能相等,即求出分成两半后的两块蛋糕的abs(s1 - s2)的最小值,s1代表第一块蛋糕的美味度,s2代表第二块蛋糕的美味度。要求:必须保证每一小块蛋糕的完整性(即不能斜着切,如果把整个大蛋糕正着放)
1 ≤ n , m≤ 1e3
1 ≤ a[i][j] ≤ 1e5
因为只能横切或者竖切,那每次输入数组的时候保存下来每一行 以及 每一列的美味度之和,再遍历每次切的abs最小值判断即可。
#include <iostream> #include <vector> #include <limits.h> using namespace std; int main(){ int n, m, temp; cin>>n>>m; vector<int> row(n,0); vector<int> col(m,0); int sum_all = 0; for(int i = 0; i < n; i++){ int sum = 0; for(int j = 0; j < m; j++){ cin>>temp; sum += temp; col[j] += temp; sum_all += temp; } row[i] = sum; } int half_row = 0, half_col = 0; int min_row = INT_MAX, min_col = INT_MAX; for(int i=0; i<n; i++){ half_row +=row[i]; int minus_row = abs(sum_all - 2*half_row); min_row = min(min_row,minus_row); } for(int i=0; i<m; i++){ half_col += col[i]; int minus_col = abs(sum_all - 2*half_col); min_col = min(min_col,minus_col); } int res = min(min_col,min_row); cout<<res<<endl; return 0; }
第四题:字符串平铺成矩阵
一个长为n的字符串s,将其重组为一个二维矩阵,二维数组长宽x,y,那么x*y = n。
矩阵的权重定义为矩阵连通块的数量。定义上下左右四个方向相邻相同字符是连通的,希望矩阵的权重最小,求最小权重值。
比如 abcbbcbcc,可建立矩阵3*3 abc,bbc,bcc,此时权重为3。
可以遍历出所有x,y的组合,并对每一组x,y分别进行dfs,来计算矩阵的权重
#include <iostream> #include <vector> #include <algorithm> using namespace std; void dfs(const string& s, int width, int height, int row, int col, vector<vector<bool>>& visited) { if (row < 0 || row >= height || col < 0 || col >= width || visited[row][col]) { return; } visited[row][col] = true; char currentChar = s[row * width + col]; if (row > 0 && s[(row - 1) * width + col] == currentChar) { dfs(s, width, height, row - 1, col, visited); } if (row < height - 1 && s[(row + 1) * width + col] == currentChar) { dfs(s, width, height, row + 1, col, visited); } if (col > 0 && s[row * width + col - 1] == currentChar) { dfs(s, width, height, row, col - 1, visited); } if (col < width - 1 && s[row * width + col + 1] == currentChar) { dfs(s, width, height, row, col + 1, visited); } } int computeWeight(const string& s, int width, int height) { int weight = 0; vector<vector<bool>> visited(height, vector<bool>(width, false)); for (int i = 0; i < height; ++i) { for (int j = 0; j < width; ++j) { if (!visited[i][j]) { dfs(s, width, height, i, j, visited); weight++; } } } return weight; } int minWeight(string s, int n) { int minWeight = INT_MAX; // 遍历不同的宽高组合 for (int width = 1; width <= n; ++width) { for (int height = 1; height <= n; ++height) { if (width * height == n) { int weight = computeWeight(s, width, height); minWeight = min(minWeight, weight); } } } return minWeight; } int main() { int n; string s; cin>>n; cin>>s; int result = minWeight(s, n); cout << "Minimum weight: " << result << endl; return 0; }
第五题 染色问题
一个树,每个节点一个值,初始每个节点都是白色,每次操作可以选择一组相邻节点,如果两个节点都是白色并且乘积为完全平方数,可以把这两个节点同时染红,问最多能染红多少个节点
输入第一行n个节点,第二行每个节点权值,后面n-1行每行两个数代表这两个节点中间有边相连
思路:树形dp
#美团信息集散地##美团嵌入式#