P1
题目
小美的平衡矩阵
小美拿到了一个n*nn∗n的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i*ii∗i的完美矩形区域。你需要回答1≤i≤n的所有答案。
n <= 200
思路
此题数据量较少，简单思路为遍历所有点，取到所有面，统计面中0和1的数量即可。但时间复杂度过高，遍历所有点为O（n^2)再遍历对角点为O（n^3）再统计数量为O（n^5）。数据量虽小，这样也明显不适合。
因为要统计范围内总数，常见的思路为前缀和数组，本题最优解应建立二维前缀和数组
时间复杂度应为：
建立数组：O(n^2);
遍历点：O（n^2）;
遍历对角点：O（n）；
得出结果为：O（1）；
总时间复杂度为O（n^3）;
答题时直接用一维数组记录列的前缀和即通过，时间复杂度为O（n^4）
代码
import ;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner();
int n = (());
int[][] grap = new int[n][n];
int[][] preOne = new int[n][n];
for (int i = 0; i < n; i++) {
char[] s = ().toCharArray();
for (int j = 0; j < n; j++) {
grap[i][j] = s[j] == '0' ? 0 : 1;
if (i == 0) {
preOne[i][j] = grap[i][j] == 1 ? 1 : 0;
} else {
preOne[i][j] = preOne[i - 1][j];
preOne[i][j] += grap[i][j] == 1 ? 1 : 0;
}
}
}
int[] ans = new int[n + 1];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
// pointX (i,j)
for (int m = i + 1, k = j + 1; m < n && k < n; m++, k++) {
//pointY(m,k)
int c = m - i + 1;
int sum = (int) (m - i + 1, 2);
int countOne = 0;
for (int l = j; l <= k; l++) {
countOne += preOne[m][l] - (i - 1 >= 0 ? preOne[i - 1][l] : 0);
}
if (sum - countOne == countOne ) {
ans[c]++;
}
}
}
}
for(int i = 1;i <= n;i++){
(ans[i]);
}
}
}P2
题目
小美的数组询问
小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间[l,r][l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有qq次询问。
输入描述：
第一行两个正整数nq代表数组长度与询问次数
接下来一行为数组
加下来q行为询问
示例1
输入例子：
3 2 1 0 3 1 2 4 4
输出例子：
5 6 8 8
例子说明：
只有第二个元素是未知的。 第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。 第二次询问，显然数组的元素和必然为 8。
思路
只要注意数据范围即可，记录下数组和以及0的个数，用最大最小值简单运算即可。要着重注意数据范围，可能卡数据。
代码
import ;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner();
int n = ();
int q = ();
long tmp, zeroCnt = 0, nonZeroSum = 0;
for (int i = 0; i < n; i++) {
tmp = ();
if (tmp == 0) {
zeroCnt++;
} else {
nonZeroSum += tmp;
}
}
while (q-- > 0) {
long l = ();
long r = ();
((nonZeroSum + zeroCnt * l) + " " + (nonZeroSum + zeroCnt * r));
}
}
}
P3
题目
MT 是美团的缩写，因此小美很喜欢这两个字母。
现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个'M'和'T'字符？
思路
此题思路清晰，遍历字符串统计M，T次数即可，最后+k和数组长度取最小值。
代码
import ;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner();
String[] nk = ().split(" ");
int n = (nk[0]);
int k = (nk[1]);
char[] s = ().toCharArray();
int res = 0;
for(int i = 0;i < n;i++){
if(s[i] == 'M' || s[i] == 'T'){
res++;
}
}
res += k;
(res > n ? n : res);
}
}P4
题目
小美的朋友关系
小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 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，含义如题目描述所述。
1\leq n \leq 10^9
1\leq m,q \leq 10^5
1\leq u,v \leq n
1\leq op \leq 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 号互相认识了。
思路
很自然可以想到用并查集可解，但并查集并不能删除边，也无法还原他们本身的关系。所以此题应该逆向思维，正难则反。根据关系生成好并查集，再逆序判断，遇到2时间查询，1时间合并即可。
最终时间复杂度还是超了，据分析时间复杂度应该是O（n） + O（q）但n已超过10^8次方，也没想到更低的方法。
代码
import .*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static class Union{
int[] parent;
int n;
public Union(int n){
= n;
parent = new int[n];
for(int i = 0;i < n;i++){
parent[i] = i;
}
}
public int find(int node){
int res = parent[node];
int[] stack = new int[n];
int size = 0;
while(parent[res] != res){
stack[size++] = res;
res = parent[res];
}
while(--size >= 0){
parent[stack[size]] = res;
}
return res;
}
public void union(int a,int b){
int parentA = find(a);
int parentB = find(b);
if(parentA != parentB){
parent[parentA] = parentB;
}
}
public boolean isUnion(int a,int b){
return find(a) == find(b);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner();
int n = ();
int m = ();
int q = ();
Union union = new Union(n);
HashSet<String> set = new HashSet<>();
while(m-- > 0){
int u = () - 1;
int v = () - 1;
String s = (u <= v )? u + " " + v : v + " " + u;
(s);
}
int[][] query = new int[q][3];
for(int i = 0;i < q;i++){
query[i][0] = ();
query[i][1] = () - 1;
query[i][2] = () - 1;
}
int co = 0;
for(int i = 0;i < q;i++){
if(query[i][0] == 1){
int u = query[i][1];
int v = query[i][2];
String s = (u <= v )? u + " " + v : v + " " + u;
if((s)){
(s);
}
co++;
}
}
boolean[] ans = new boolean[q - co];
for(String s : set){
int a = ((" ")[0]);
int b = ((" ")[1]);
(a,b);
}
int index = ;
for(int i = q - 1;i >= 0;i--){
switch(query[i][0]){
case(1):
(query[i][1],query[i][2]);
break;
case(2):
ans[--index] = (query[i][1],query[i][2]);
break;
}
}
for(int i = 0;i < ;i++){
(ans[i] ? "Yes" : "No");
}
}
}import .*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static class Union{
int[] parent;
int n;
public Union(int n){
= n;
parent = new int[n];
for(int i = 0;i < n;i++){
parent[i] = i;
}
}
public int find(int node){
int res = parent[node];
int[] stack = new int[n];
int size = 0;
while(parent[res] != res){
stack[size++] = res;
res = parent[res];
}
while(--size >= 0){
parent[stack[size]] = res;
}
return res;
}
public void union(int a,int b){
int parentA = find(a);
int parentB = find(b);
if(parentA != parentB){
parent[parentA] = parentB;
}
}
public boolean isUnion(int a,int b){
return find(a) == find(b);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner();
int n = ();
int m = ();
int q = ();
Union union = new Union(n);
HashSet<String> set = new HashSet<>();
while(m-- > 0){
int u = () - 1;
int v = () - 1;
String s = (u <= v )? u + " " + v : v + " " + u;
(s);
}
int[][] query = new int[q][3];
for(int i = 0;i < q;i++){
query[i][0] = ();
query[i][1] = () - 1;
query[i][2] = () - 1;
}
int co = 0;
for(int i = 0;i < q;i++){
if(query[i][0] == 1){
int u = query[i][1];
int v = query[i][2];
String s = (u <= v )? u + " " + v : v + " " + u;
if((s)){
(s);
}
co++;
}
}
boolean[] ans = new boolean[q - co];
for(String s : set){
int a = ((" ")[0]);
int b = ((" ")[1]);
(a,b);
}
int index = ;
for(int i = q - 1;i >= 0;i--){
switch(query[i][0]){
case(1):
(query[i][1],query[i][2]);
break;
case(2):
ans[--index] = (query[i][1],query[i][2]);
break;
}
}
for(int i = 0;i < ;i++){
(ans[i] ? "Yes" : "No");
}
}
}P5
题目
小美的区间删除
小美拿到了一个大小为nn的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有kk个 0。小美想知道，一共有多少种不同的删除方案？
输入描述：
第一行输入两个正整数n,k。
第二行输入n个正整数a_i，代表小美拿到的数组。
1\leq n,k \leq 10^5
1\leq a_i \leq 10^9
输出描述：
一个整数，代表删除的方案数。
示例1
输入例子：
5 2
2 5 3 4 20
输出例子：
4
例子说明：
第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。
思路
遇到末尾0或10的倍数等问题，最先想到的就应该是2和5组成10，根据2和5的个数必定递增，可以建立单调性，有单调性的问题一般可用二分或滑动窗口解图，此题又是数组区间问题，对于区间问题首先想道的应为滑动窗口。
此题按滑动窗口统计2和5的个数最小值即可，减去窗口内的个数判断是否满足条件即可。滑动窗口亦有模板。
代码
import ;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner();
int n = ();
int k = ();
int twos = 0;
int fivs = 0;
int[] tws = new int[n];
int[] fis = new int[n];
long num;
for (int i = 0; i < n; i++) {
num = ();
while (num % 2 == 0) {
twos++;
tws[i]++;
num /= 2;
}
while (num % 5 == 0) {
fivs++;
fis[i]++;
num /= 5;
}
}
//[r + 1] - [l]
long ans = 0;
for (int l = 0, r = 0; r < n; r++ ) {
twos -= tws[r];
fivs -= fis[r];
while (l <= r && (twos, fivs) < k) {
twos += tws[l]; fivs += fis[l];
++ l;
}
ans += r- l + 1;
}
(ans);
}
}