先注册域名后建设网站可以吗,青岛城阳网站开发,wordpress 插件使用,注销备案号 网站前言:
1.第一题#xff08;模拟#xff09;
2.第二题#xff08;模拟#xff09;
3.第三题#xff08;二维前缀和#xff09;
4.第四题的思维#xff08;双指针#xff09;
5.第五题难度比较大#xff08;并查集删边离散化#xff09;
一.小美的MT
MT 是美团的…
前言:
1.第一题模拟
2.第二题模拟
3.第三题二维前缀和
4.第四题的思维双指针
5.第五题难度比较大并查集删边离散化
一.小美的MT
MT 是美团的缩写因此小美很喜欢这两个字母。
现在小美拿到了一个仅由大写字母组成字符串她可以最多操作k次每次可以修改任意一个字符。小美想知道操作结束后最多共有多少个M和T字符
输入描述
第一行输入两个正整数n,k代表字符串长度和操作次数。第二行输入一个长度为n的、仅由大写字母组成的字符串。1kn10^5
输出描述
输出操作结束后最多共有多少个M和T字符。
示例 1
输入
5 2
MTUAN
输出
4
说明
修改第三个和第五个字符形成的字符串为 MTTAM这样共有 4 个M和T。
思路与代码
1.首先统计字符串中除了M和T以外的字符的个数记为add。
2.操作次数为k因此最多可以min(k,add)将个字符变为M和T
3.再加上之前的M和T字符的个数。
4.结果为n-addmin(k,add);
C:
#include bits/stdc.h
using namespace std;
int main() {int n, k, sum 0;cin n k;string s;cin s;int add 0;for (int i 0; i s.size(); i) {if (s[i] ! M s[i] ! T) {add;}}sum n - add min(k, add);cout sum \n;return 0;
}Java:
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n, k, sum 0;n scanner.nextInt();k scanner.nextInt();String s scanner.next();int add 0;for (int i 0; i s.length(); i) {if (s.charAt(i) ! M s.charAt(i) ! T) {add;}}sum n - add Math.min(k, add);System.out.println(sum);}
}二.小美的数组询问
小美拿到了一个由正整数组成的数组但其中有一些元素是未知的用 0 来表示。
现在小美想知道如果那些未知的元素在区间[l,r]范围内随机取值的话数组所有元素之和的最小值和最大值分别是多少
共有q次询问。
输入描述
第一行输入两个正整数n,q代表数组大小和询问次数。
第二行输入n个整数ai其中如果输入ai的为 0那么说明ai是未知的。
接下来的q行每行输入两个正整数l,r代表一次询问。
1n,q10^5
0ai10^9
1lr10^9
输出描述
输出q行每行输出两个正整数代表所有元素之和的最小值和最大值。
示例 1
输入
3 2
1 0 3
1 2
4 4
输出
5 6
8 8
说明
只有第二个元素是未知的。
第一次询问数组最小的和是 1135最大的和是 1236。
第二次询问显然数组的元素和必然为 8。
思路与代码
1.循环一遍sum记录非0的情况下的和res统计0的数量。
2.最小值就是0的数量 * 区间左值(res*l)反之最大值就是0的数量*区间右值(res*r)。
3.答案就是最小sumres*l,最大sumres*r;
C
#include bits/stdc.h
using namespace std;int main() {int n, q;cin n q;vectorint a(n);for (int i 0; i n; i) {cin a[i];}int res 0;int sum 0;for (int i 0; i n; i) {if (a[i] 0) {res;}sum a[i];}for (int i 0; i q; i) {int l, r;cin l r;cout sum res *l sum res *r endl;}return 0;
}Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int q sc.nextInt();int[] a new int[n];for (int i 0; i n; i) {a[i] sc.nextInt();}int res 0;int sum 0;for (int i 0; i n; i) {if (a[i] 0) {res;}sum a[i];}for (int i 0; i q; i) {int l sc.nextInt();int r sc.nextInt();System.out.println((sum res * l) (sum res * r));}}
}三.小美的平衡矩阵
小美拿到了一个n*n 的矩阵其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在小美希望你回答有多少个i*i的完美矩形区域。你需要回答1in的所有答案。
输入描述
第一行输入一个正整数n代表矩阵大小。
接下来的n行每行输入一个长度为n的01 串用来表示矩阵。
输出描述
输出n行第i行输出的i*i完美矩形区域的数量。
示例 1
输入
4
1010
0101
1100
0011
输出
0
7
0
1
思路与代码
二维前缀和。n200.所以可以n^3进行解决题目
1.枚举所有的边长i的正方形.
2.如果0和1的数量各一半那么就是判断正方形的和是否为i*i / 2如果是就。
3.计算时
第一层循环枚举矩形长度i
第二三层循环分别枚举矩形的左上角的端点x,y
对应右下角的端点则为xi-1,yi-1
C:
#include bits/stdc.h
using namespace std;
const int N 510;
int n;
char a[N][N];
int s[N][N];
int main() {cin n;for (int i 1; i n; i) {for (int j 1; j n; j) {cin a[i][j];}}for (int i 1; i n; i )for (int j 1; j n; j )s[i][j] s[i][j - 1] s[i - 1][j] - s[i - 1][j - 1] (a[i][j] 1);for (int i 1; i n; i) {int cnt 0;for (int x 1; x n - i 1; x) {for (int y 1; y n - i 1; y) {int sum s[x i - 1][y i - 1] - s[x i - 1][y - 1] - s[x - 1][y i - 1] s[x - 1][y - 1];if (sum * 2 i * i) {cnt;}}}cout cnt endl;}return 0;
}
Java: import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N 510;int n scanner.nextInt();char[][] a new char[N][N];int[][] s new int[N][N];for (int i 1; i n; i) {for (int j 1; j n; j) {a[i][j] scanner.next().charAt(0);}}for (int i 1; i n; i) {for (int j 1; j n; j) {s[i][j] s[i][j - 1] s[i - 1][j] - s[i - 1][j - 1] (a[i][j] 1 ? 1 : 0);}}for (int i 1; i n; i) {int cnt 0;for (int x 1; x n - i 1; x) {for (int y 1; y n - i 1; y) {int sum s[x i - 1][y i - 1] - s[x i - 1][y - 1] - s[x - 1][y i - 1] s[x - 1][y - 1];if (sum * 2 i * i) {cnt;}}}System.out.println(cnt);}}
}四.小美的区间删除
小美拿到了一个大小为n的数组她希望删除一个区间后使得剩余所有元素的乘积末尾至少有k个 0。小美想知道一共有多少种不同的删除方案
输入描述
第一行输入两个正整数nk。第二行输入n个正整数ai代表小美拿到的数组。
1n,k10^5
1ai10^9
输出描述
一个整数代表删除的方案数。
示例 1
输入
5 2
2 5 3 4 20
输出
4
说明
第一个方案删除[3]。
第二个方案删除[4]。
第三个方案删除[3,4]。
第四个方案删除[2]。
思路与代码
2和5的因子个数。2*5102^i*5^j min(i,j)0的数量 2*510
使用双指针
区间的一个长度越大那么末尾0的个数越多单调性
使用双指针
1.我们首先统计整个数组的2和5的因子3数量和每个元素对应的5的因子数量。
2.维护2个指针l,r
3.如果l,r的区间min(cnt2,cnt5)k,我们答案就累加l-r1
C:
#include bits/stdc.h
using namespace std;
const int N 1e6 10;
int a2[N], a5[N];
int cnt2 0, cnt5 0;
int n, k, x;void cnt2_cnt5_count() {for (int i 0; i n; i ) {cin x;while (x % 2 0) {a2[i] ;x / 2;cnt2 ;}while (x % 5 0) {a5[i] ;x / 5;cnt5 ;}}
}int main() {cin n k;cnt2_cnt5_count();int l 0;long long res 0;for (int r 0; r n; r ) {cnt2 - a2[r];cnt5 - a5[r];while (min(cnt2, cnt5) k l r) {cnt2 a2[l];cnt5 a5[l];l ;}res (long long)(r - l 1);}cout res endl;return 0;
}
Java:
import java.util.Scanner;public class Main {static final int N 1000010;static int[] a2 new int[N];static int[] a5 new int[N];static int cnt2 0, cnt5 0;static int n, k, x;public static void cnt2Cnt5Count() {Scanner input new Scanner(System.in);for (int i 0; i n; i) {x input.nextInt();while (x % 2 0) {a2[i];x / 2;cnt2;}while (x % 5 0) {a5[i];x / 5;cnt5;}}}public static void main(String[] args) {Scanner input new Scanner(System.in);n input.nextInt();k input.nextInt();cnt2Cnt5Count();int l 0;long res 0;for (int r 0; r n; r) {cnt2 - a2[r];cnt5 - a5[r];while (Math.min(cnt2, cnt5) k l r) {cnt2 a2[l];cnt5 a5[l];l;}res (long) (r - l 1);}System.out.println(res);}
} 五.小美的朋友关系
小美认为在人际交往中但是随着时间的流逝朋友的关系也是会慢慢变淡的最终朋友关系就淡忘了。
现在初始有一些朋友关系存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中某两人是否可以通过朋友介绍互相认识
事件共有 2 种
1 u v代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
注介绍可以有多层比如 2 号把 1 号介绍给 3 号然后 3 号再把 1 号介绍给 4 号这样 1 号和 4 号就认识了。
输入描述
第一行输入三个正整数n,m,q代表总人数初始的朋友关系数量发生的事件数量。接下来的m行每行输入两个正整数u,v代表初始编号u的人和编号v的人是朋友关系。接下来的q行每行输入三个正整数op,u,v含义如题目描述所述。
1n 10^9
1 m,q 10^5
1 u,v n
1 op 2
保证至少存在一次查询操作。
输出描述
对于每次 2 号操作输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识则输出Yes。否则输出No。
示例 1
输入
5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3
输出
Yes
No
No
说明
第一次事件1 号和 5 号本来就不是朋友所以无事发生。
第二次事件是询问1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问显然 1 号和 4 号无法互相认识。
第四次事件1 号和 2 号淡忘了。
第五次事件此时 1 号无法再经过 2 号和 3 号互相认识了。
思路与代码
离线处理数据(map)并查集逆向思维。
1.离线处理因为这里的n非常大1e9,后面是使用并查集构造n个节点father数组肯定装不下.
2.并查集处理加边,删边转换下思路
3.如果我们已经找出所有可能要删除的边然后假设所有边都删除了构建一个最终的并查集(这个并查集并不影响后面的删边的情况)。
4.逆向遍历所有的q次操作如果是查询1操作使用并查集直接查出即可如果是删除(2操作)则往并查集添加边。
C
#include bits/stdc.h
using namespace std;unordered_mapint, int father;
int find(int x) {return father[x] x ? x : (father[x] find(father[x]));
}void merge(int x, int y) {int i find(x), j find(y);if (i ! j)father[i] j;
}struct node {int op;int u;int v;
};int main() {int n, m, p;cin n m p;vectornode all(p);setpairint, int q;setpairint, int q_del;for (int i 0; i m; i ) {int u, v;cin u v;father[u] u;father[v] v;q.insert({u, v});//初始化需要建立的边}for (int i 0; i p; i ) {cin all[i].op all[i].u all[i].v;father[all[i].u] all[i].u;father[all[i].v] all[i].v;if (all[i].op 1) {q_del.insert({all[i].u, all[i].v});//需要删除的边}}for (auto e : q_del) {int u e.first, v e.second;if (q.count({u, v}) || q.count({v, u})) {q.erase(e);}}for (auto e : q) {merge(e.first, e.second);}vectorstring res;for (int i p - 1; i 0; i --) {if (all[i].op 1) {merge(all[i].u, all[i].v);} else {if (find(all[i].u) find(all[i].v)) {res.push_back(Yes);} else {res.push_back(No);}}}reverse(res.begin(), res.end());for (string s : res) {cout s endl;}return 0;
}
Java
import java.util.*;class Main {static MapInteger, Integer father;public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int p scanner.nextInt();father new HashMap();ListNode all new ArrayList();SetPair q new HashSet();SetPair q_del new HashSet();for (int i 0; i m; i) {int u scanner.nextInt();int v scanner.nextInt();father.put(u, u);father.put(v, v);q.add(new Pair(u, v)); // 初始化需要建立的边}for (int i 0; i p; i) {int op scanner.nextInt();int u scanner.nextInt();int v scanner.nextInt();all.add(new Node(op, u, v));father.put(u, u);father.put(v, v);if (op 1) {q_del.add(new Pair(u, v)); // 需要删除的边}}for (Pair e : q_del) {int u e.first, v e.second;if (q.contains(new Pair(u, v)) || q.contains(new Pair(v, u))) {q.remove(e);}}for (Pair e : q) {merge(e.first, e.second);}ListString res new ArrayList();for (int i p - 1; i 0; i--) {if (all.get(i).op 1) {merge(all.get(i).u, all.get(i).v);} else {if (find(all.get(i).u) find(all.get(i).v)) {res.add(Yes);} else {res.add(No);}}}Collections.reverse(res);for (String s : res) {System.out.println(s);}}static int find(int x) {return father.get(x) x ? x : find(father.get(x));}static void merge(int x, int y) {int i find(x);int j find(y);if (i ! j) {father.put(i, j);}}static class Node {int op;int u;int v;Node(int op, int u, int v) {this.op op;this.u u;this.v v;}}static class Pair {int first;int second;Pair(int first, int second) {this.first first;this.second second;}Overridepublic boolean equals(Object obj) {if (this obj) {return true;}if (obj null || getClass() ! obj.getClass()) {return false;}Pair pair (Pair) obj;return first pair.first second pair.second;}Overridepublic int hashCode() {return Objects.hash(first, second);}}
}最后
觉得讲解不错的可以关注反响不错的话会更新此系列讲解视频最后的最后祝大家offer满满
