1.大衣构造字符串

问题描述

已知对于一个由小写字母构成的字符串，每次操作可以选择一个索引，将该索引处的字符用三个相同的字符副本替换。

现有一长度为 NN 的字符串 UU，请帮助大衣构造一个最小长度的字符串 SS，使得经过任意次数操作后该字符串能转换为字符串 UU。

保证存在唯一满足条件的字符串。

输入格式

第一行输入一个正整数 NN 表示字符串的长度。

第二行输入一个长度为 NN 的字符串 U​U​。

输出格式

输出一个最小长度的字符串 SS，使得经过任意次数操作后该字符串能转换为字符串 UU。

样例输入1

6
aaabbb

样例输出1

ab

样例输入2

7
abbbbbc

样例输出2

abc

样例输入3

4
abcd

样例输出3

abcd

AC代码 

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();scan.nextLine();String u=scan.nextLine();String ans="";for(int i=0;i<n;i++) {if(i+1<n&&i+2<n&&u.charAt(i)==u.charAt(i+1)&&u.charAt(i)==u.charAt(i+2)) {ans=ans+u.charAt(i);i+=2;}else {ans=ans+u.charAt(i);}}System.out.println(ans);scan.close();}
}

2.大衣的异或回文对

问题描述

大衣有一个长度为 NN 的数组 AA，大衣想知道数组中有多少对 (i,j)(1≤i≤j≤N)(i,j)(1≤i≤j≤N) 满足 Ai⊕AjAi​⊕Aj​ 的十进制数是回文的，⊕⊕ 表示按位异或。

你能回答大衣吗的问题吗？

输入格式

第一行输入一个正整数 NN 表示数组的长度。

第二行输入 NN 个整数 A1,A2,⋯,AN​A1​,A2​,⋯,AN​​ 表示数组中的元素。

输出格式

输出一个数字表示答案。

样例输入1

4
13 27 12 26

样例输出1

8

样例输入2

3
2 2 2

样例输出2

6

AC代码

import java.util.*;
public class exercise1{private static boolean pd(String s) {for(int i=0;i<s.length()/2;i++) {if(s.charAt(i)!=s.charAt(s.length()-i-1))return false;}return true;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n];for(int i=0;i<n;i++) {a[i]=scan.nextInt();}int ans=0;for(int i=0;i<n;i++) {for(int j=i;j<n;j++) {int temp=a[i]^a[j];String st=String.valueOf(temp);if(pd(st))ans++;}}System.out.println(ans);scan.close();}
}

 3.金苹果群岛的建设

问题描述

探险家们发现了一片由 nn 个岛屿组成的群岛，命名为金苹果群岛。这些岛屿之间通过地脉相连，每一对相连的岛屿都可以通过地脉通往其他相连的岛屿。现在，探险家们计划在某些岛屿之间建设桥梁，以便每个岛屿都能够相互到达。桥梁是双向通行的。

已知有 mm 条地脉，每条地脉都连接了两个岛屿。你的任务是计算至少需要建设多少座桥梁，才能实现探险家们的计划。

输入格式

第一行包含两个整数 nn 和 mm ，分别表示岛屿的数量和地脉的数量。

接下来的 mm 行，每行包含两个整数 aa 和 bb，表示第 aa 个岛屿和第 bb 个岛屿之间有一条地脉。

输出格式

输出一个整数，表示至少需要建设的桥梁数量。

样例输入

5 3
1 2
2 3
4 5

样例输出

1

评测数据范围

1≤n≤1051≤n≤105 ，0≤m≤1050≤m≤105 ，1≤a,b≤n1≤a,b≤n ，a≠ba=b。

AC代码

（1）通过80%

import java.util.*;
public class exercise1{static int[] f;private static int find(int x) {if(f[x]==x)return x;else return f[x]=find(f[x]);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();f=new int[n+1];for(int i=1;i<=n;i++) {f[i]=i;}for(int i=0;i<m;i++) {int a=scan.nextInt();int b=scan.nextInt();int fa=find(a);int fb=find(b);if(fa!=fb)f[fa]=fb;}int ans=0;for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++) {int fi=find(i);int fj=find(j);if(fi!=fj) {ans++;f[fi]=fj;}}}System.out.println(ans);scan.close();}
}

（2）通过100%。

优化部分：避免双重循环合并集合。在原始代码里的 for 循环中 find(i) 和 find(j) 的操作可能会导致重复查询，应该只统计连通块的数量，而不再二次合并。先统计不同连通块数量（只有根节点才计数），最终答案就是连通块数量-1。

import java.util.*;
public class exercise1{static int[] f;private static int find(int x) {if(f[x]==x)return x;else return f[x]=find(f[x]);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();f=new int[n+1];for(int i=1;i<=n;i++) {f[i]=i;}for(int i=0;i<m;i++) {int a=scan.nextInt();int b=scan.nextInt();int fa=find(a);int fb=find(b);if(fa!=fb)f[fa]=fb;}int ans=0;for(int i=1;i<=n;i++) {if(f[i]==i)ans++;}System.out.println(ans-1);scan.close();}
}

4.大衣的飞机场

问题描述

大衣有 NN 台飞机，第 ii 台飞机在 AiAi​ 时间降落，在 Bi​Bi​​ 时间起飞。

由于降落和起飞都需要占用轨道，每条轨道在某一时间只能被一台飞机使用，请问最少需要多少条轨道才能让所有飞机正常起降。

输入格式

第一行输入一个正整数 NN 表示飞机的数量。

第二行输入 NN 个整数 A1,A2,⋯,ANA1​,A2​,⋯,AN​ 表示每台飞机降落的时间。

第三行输入 NN 个整数 B1,B2,⋯,BN​B1​,B2​,⋯,BN​​ 表示每台飞机起飞的时间。

输出格式

输出一个数字表示能让所有飞机正常起降需要的最少轨道数。

样例输入1

3
1 1 2
2 2 3

样例输出1

3

样例输入2

4
1 5 4 3
4 6 10 4

样例输出2

3

样例输入3

3
1 4 3
2 6 5

样例输出3

1

AC代码

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n+1];int[] b=new int[n+1];Map<Integer,Integer> M=new HashMap<>();int ans=0;//每个数字的最大数量for(int i=1;i<=n;i++) {a[i]=scan.nextInt();if(M.get(a[i])==null) {M.put(a[i], 1);}else {M.put(a[i], M.get(a[i])+1);ans=Math.max(ans,M.get(a[i]));}}for(int i=1;i<=n;i++) {b[i]=scan.nextInt();if(M.get(b[i])==null) {M.put(b[i], 1);}else {M.put(b[i], M.get(b[i])+1);ans=Math.max(ans,M.get(b[i]));}}System.out.println(ans);scan.close();}
}

 5.回文字符串

问题描述

小蓝最近迷上了回文字符串，他有一个只包含小写字母的字符串 SS，小蓝可以往字符串 SS 的开头处加入任意数目个指定字符： l、q、bl、q、b（ASCIIASCII 码分别为： 108、113、98108、113、98）。小蓝想要知道他是否能通过这种方式把字符串 SS 转化为一个回文字符串。

输入格式

输入的第一行包含一个整数 TT，表示每次输入包含 TT 组数据。

接下来依次描述 TT 组数据。

每组数据一行包含一个字符串 SS 。

输出格式

输出 TT 行，每行包含一个字符串，依次表示每组数据的答案。如果可以将 SS 转化为一个回文字符串输出 Yes，否则输出 No。

样例输入

3
gmgqlq
pdlbll
aaa

样例输出

Yes
No
Yes

AC代码

import java.util.*;
public class exercise1{private static boolean pd(String s) {int l=0,r=s.length()-1;while(l<=r) {char L=s.charAt(l);char R=s.charAt(r);if(L==R) {l++;r--;}else { //S的开头处可加（左边可加，右边不可以）if(R=='l'||R=='q'||R=='b') {r--;}else {return false;}}}return true;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int t=scan.nextInt();scan.nextLine();for(int i=1;i<=t;i++) {String s=scan.nextLine();if(pd(s))System.out.println("Yes");else System.out.println("No");}scan.close();}
}

6.七夕节之通讯

问题描述

小蓝需要通过每个地区的通信装置才能与其他地区联系。现在每个地区被抽象为一个点，按照 1,2,...,n1,2,...,n 标号。在线路完好的情况下，小蓝可以从第一个点按顺序依次联系到第 nn 个点，即 [1↔2↔...↔n][1↔2↔...↔n]。但是由于地震、暴雨等自然灾害的影响，可能部分点的通信装置被破坏。

例如当小蓝处在 55 号点时，如果仅有 33 号点被破坏，其他点正常，那么小蓝只能联络到 [4,n][4,n] 号点，即 [1↔2,4↔5↔n][1↔2,4↔5↔n]。当某个地区的通信装置被自然灾害破坏时，工作人员也会尽力抢修。

现在给定 qq 次操作，每次操作为破坏点、恢复点和查询当前点可以联络多少个点（包括自身在内）进行通讯，请你输出对应的查询结果。

注意：初始状态时，所有通讯点均为正常通讯点。

输入格式

输入共 q+1q+1 行：

第一行为两个正整数 n,qn,q，依次表示通讯点数量和操作次数。

接下来 qq 行，每行两个正整数 ins、xins、x。当 ins==0ins==0 时，若 点 xx 为正常通讯点，则破坏该点为中断点；若 xx 为中断点，则恢复该点为正常通讯点。当 ins==1ins==1 时，查询点 xx 可以至多通讯多少个点。

输出格式

输出所有 ins==1ins==1 时的查询结果，结果按查询先后顺序依次输出，结果仅包含一个整数且独占一行。

样例输入

5 5
1 1
0 2
1 1
1 4
1 2

样例输出

5
1
3
0

AC代码

import java.util.*;
public class exercise1{private static void update(int x) {}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int q=scan.nextInt();Set<Integer>s =new TreeSet<>();//TreeSet自动升序，去重复元素for(int i=1;i<=q;i++) {int ins=scan.nextInt();int x=scan.nextInt();if(ins==0) {if(s.contains(x))s.remove(x);else s.add(x);}else {if(s.contains(x)) {System.out.println(0);continue;}else {int last=0,next=0;for(int u:s) {if(x<u) {next=u;//只要找到离x最近的nextbreak;}last=u;}if(next==0) {System.out.println(n-last);}else {System.out.println(next-last-1);}}}}scan.close();}
}

7.蛋糕盛宴

问题描述

在一个奇幻的游戏世界中，你作为勇敢的冒险者，来到了一个神秘的蛋糕王国。这个王国以美味的蛋糕闻名于世，而你正准备挑战一个有趣的任务。

在王国的宫殿里，有一个特殊的矩形蛋糕盘子，它的大小为 n×mn×m。你的任务是在这个盘子里放置尽可能多的半径为 rr 的圆形蛋糕，但是要注意，蛋糕的每一部分都不能超出盘子的边界。

现在，请你告诉我，在这个挑战中，你能最多放置多少个圆形蛋糕？

输入格式

第一行输入三个整数 n,m,rn,m,r，表示蛋糕盘子的大小和圆形蛋糕的半径，其中 1≤n,m,r≤1001≤n,m,r≤100。

输出格式

输出仅一行，包含一个整数，表示你能放置的蛋糕的最大数量。

样例输入

1 2 3

样例输出

0

AC代码

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int r=scan.nextInt();System.out.println((n/(2*r))*(m/(2*r)));scan.close();}
}

 8.蓝桥商场【算法赛】

问题描述

随着双十一的来临，蓝桥商场迎来了一场狂欢，共有 nn 家店铺开展了免费试吃活动。

活动结束后，每家店铺都还剩下一些试吃食物，第 ii 家店铺剩下 aiai​ 份食物未被消耗完。

商场保安小蓝接到指令要处理这些剩余食物，但他觉得浪费太可惜。因此，他决定亲自吃完这些食物。每分钟，小蓝可以选择以下操作之一：

1. 选择一家仍有剩余食物的店铺，吃掉其中的一份食物。在下一分钟，小蓝不能再选择同一家店铺的食物。
2. 休息，不吃任何食物。

请问，小蓝需要多少分钟才能吃完所有店铺剩余的食物呢？

输入格式

第一行输入一个整数 n(1≤n≤105)n(1≤n≤105) 表示店铺的数量。

第二行输入 nn 个整数 a1,a2,a3,⋯,an(1≤ai≤105)a1​,a2​,a3​,⋯,an​(1≤ai​≤105) 表示每家店铺剩余的食物数量。

输出格式

输出一个整数表示答案。

样例输入

3
1 1 3

样例输出

5

AC代码

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n+1];int maxx=0;int sum=0;for(int i=1;i<=n;i++) {a[i]=scan.nextInt();sum+=a[i];maxx=Math.max(a[i],maxx);}int num=maxx-(sum-maxx);if(num>1) {sum+=num-1;}System.out.println(sum);scan.close();}
}

 9.最优操作

问题描述

有一个包含 nn 个元素的数组 aa ，我们将对其进行 mm 次操作。mm 次操作可以按任意顺序执行。每次操作给你两个整数 xx 和 yy，你需要在数组中选择 0∼x0∼x 个数，将它们永久变成 yy 。完成所有操作后，请问数组的元素和最大可能是多少。

输入格式

第一行包含两个整数 nn 和 mm ，表示数组的元素个数和操作次数。

第二行包含 nn 个整数，表示数组 aa 的元素。

接下来 mm 行，每行两个整数，表示操作中的 xx 和 yy 。

输出格式

输出一个整数，表示操作完成后，数组的最大元素和。

样例输入

3 2
5 1 4
2 3
1 5

样例输出

14

AC代码

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[] a=new int[n];//优先队列默认最小堆，堆顶为最小值PriorityQueue<Integer>q =new PriorityQueue<>();//最大堆PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());long sum=0;for(int i=0;i<n;i++) {a[i]=scan.nextInt();sum+=a[i];q.add(a[i]);}for(int i=0;i<m;i++) {int x=scan.nextInt();int y=scan.nextInt();while(x>0) {if(q.peek()<y) {sum-=q.poll();q.add(y);sum+=y;}else {break;}x--;}}System.out.println(sum);scan.close();}
}

10.神秘括号匹配之谜

问题描述

在神奇的魔法大陆中，勇敢的冒险者小蓝和他的伙伴们进入了一座神秘的迷失森林。这个森林被古老的魔法所笼罩，隐藏着许多谜题和危险。小蓝希望通过解决这些谜题，找到通往宝藏的路径。

在迷失森林的某个地方，小蓝发现了一块神秘的石碑。石碑上刻有一串由括号组成的神秘字符串，只包含 ( 和 ) 两种字符。小蓝相信这个字符串中蕴含着通往宝藏的线索。他发现，只有当括号字符能够正确匹配时，才能解开谜题。

括号的匹配定义如下：对于每个 (，必须找到与之对应的 )。例如，对于字符串 (()) 和 ()()，都具有匹配的括号对，数量均为 22。

小蓝希望知道在这串神秘字符串中，最多能够匹配多少个括号对。请你帮助小蓝解决这个谜题。

输入格式

第一行输入一个整数 nn（1≤n≤1041≤n≤104），表示字符串的长度。

第二行输入一个长度为 nn 的字符串 ss，字符串中只包含 ( 和 ) 两种字符。

输出格式

输出仅一行，包含一个整数，表示在字符串中最多能够匹配的括号对数量。

样例输入

5
(()))

样例输出

2

AC代码

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();scan.nextLine();String s=scan.nextLine();//new Queue<>()不行，Queue是一个接口Queue<Character>q=new LinkedList<>();int ans=0;for(int i=0;i<s.length();i++) {if(s.charAt(i)=='(') {q.add('(');}else {if(q.size()>0) {q.poll();ans++;}}}System.out.println(ans);scan.close();}
}