app开发者平台在数字化时代的重要性与发展趋势解析
928
2022-08-28
图论,二叉树,dfs,bfs,dp,最短路专题
目录
1167 逆序数(大数据)1179 Shortest PathProblem C 1195 Large PopulationProblem D 1245 Lisa's PuzzleProblem E 1250 BonusProblem F 1288 Binary Search TreeProblem G 1302 Balance TreeProblem H 1369 Black White ChessProblem L 1389 二叉查找树Problem P 1418 消星星Problem R 1433 Swap Digits
1167 逆序数(大数据)
题目描述 给你一个序列x1,x2,…,xn,如果数对< xi,xj >,其中i< j,而xi> xj我们称之为逆序数对。 一个序列的逆序数对的数目,称为这个序列的逆序数。 比如说序列 3 1 2 ,逆序数对为 ❤️,1>和<3,2>,所以这个序列的逆序数为2。 现在给你一个数字序列,请求其逆序数。
输入 每个样例为两行,第一行为一个整数n(n≤10,000),表示序列中数字的个数,如果n为0,则表示输入结束,不需要处理。 第二行是n个整数xi,0≤xi≤100,000。输入数据保证序列中没有相同整数。
输出 每行输出一个整数,表示其序列数。
样例输入 3 3 1 2 4 1 2 3 4 0
样例输出 2 0
简单来说,就是直接套用递归算法的模板,进行一些变通。
import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner in=new Scanner (System.in); PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); while(in.hasNext()) { int n=in.nextInt(); if(n==0) return; int [] a=new int [n]; for(int i=0;i 1179 Shortest Path 题目描述 N(3≤N≤1,000)个城市(编号从1~N),M(N-1≤M≤10,000)条公路连接这些城市,每条公路都是双向通车的。 你想从1号城市出发,到达N号城市,期间你希望通过按顺序经过K(0≤K≤3)个指定的城市(这K+2个城市只允许达到1次),求最短的里程。 输入 存在多个样例。 每个样例的第一行是三个整数N,M,K。如果N,M,K为0,则表示输入结束。 以后是M行表示M条公路,每行三个整数x(1≤x≤N),y(1≤y≤N),c(1≤c≤1,000),表示城市x与城市y之间有一条距离为c的公路。输入保证任意两座城市之间至少存在一条路。然后的一行包含K个城市的序号,序号属于[2,N-1]。 输出 每行输出一个样例的结果,为一个整数。如果不存在这样的方案,输出“Impossible”。 样例输入 3 3 1 1 2 3 2 3 4 1 3 2 2 0 0 0 样例输出 7 import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.util.Arrays;import java.util.Scanner;public class Main { static int [][]mmap=new int [1105][1105]; static int c[]=new int [20]; static int dis[]=new int [1100]; static int vis[]=new int [1100]; static int n,k; static int inf=99999999;//如果这里写成Integer.MAX_VALUE会wa public static void main(String[] args) { // TODO Auto-generated method stub Scanner in=new Scanner (System.in); PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); int m=0; while(in.hasNext()) { n=in.nextInt(); m=in.nextInt(); k=in.nextInt(); if(n==0&&m==0&&k==0) { return ; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { mmap[i][j]=inf; } } for(int i=1;i<=n;i++) { mmap[i][i]=0; } for(int i=0;i Problem C 1195 Large Population 题目描述 很多城市人口众多,政府决定在不同城市之间修建高速公路提高相互之间的交通条件。 但是由于修建费用昂贵,所以政府只要能保证所有城市都可以通过高速公路互联就可以了。 但是政府又想这些公路的容量之和尽可能的大。请你设计一下线路,看最大容量和是多少? 输入 第一行是一个整数K,表示样例数。 每个样例的第一行是两个整数N和M(2≤N≤1000;N-1≤M≤10000), N表示N个城市,其中城市代号用1到N表示;M表示可以修建的高速公路条数。 以后的M行为每条高速公路的容量情况。 每行为三个整数X,Y,C,其中1≤X,Y≤N,C≤10^6。 输出 每行输出一个样例的结果,为一个整数。 Sample Input 2 2 1 1 2 1 3 3 1 2 1 1 3 2 2 3 3 Sample Output 1 5 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;import java.util.Arrays;import java.util.Scanner; public class Main { public static int size = 510;//点的个数,多开10个防止越界 public static int INF = 0x3f3f3f3f;//可以认为是正无穷 public static int n, m; public static int[] dist = new int[size];//dist[i]存放i这个点到最小生成树集合的距离 public static boolean[] st = new boolean[size];//st[i]表示这个点是否已经加入了集合 public static int[][] map = new int[size][size];//存放图的关系 public static void Init() { Arrays.fill(dist, INF);//初始化点到集合的距离为正无穷 for (int i = 0; i <= n; i++) {//初始化各个点之间的距离为正无穷 Arrays.fill(map[i], INF); } } public static int prim() { int result = 0;//最小生成树集合大小 for (int i = 0; i < n; i++) {//遍历n次,每次加入一个点 int temp = -1; for (int j = 1; j <= n; j++) {//找到还没有加入集合当中距离集合最近的点 if (st[j] == false && (temp == -1 || dist[temp] > dist[j])) temp = j; } if (i != 0 && dist[temp] == INF)//如果这个点不是第一个点并且与集合的距离为正无穷,直接返回,因为最小的点距离集合的距离都为正无穷的,其他的点也是一样的 return INF; if (i != 0) {//如果这个点不是第一个点,将这个点到集合的距离加入最小生成树 result += dist[temp]; } st[temp] = true;//将这个点标记为加入集合 for (int j = 1; j <= n; j++)//用上面找到的点来更新其他点到集合的距离 dist[j] = Math.min(dist[j], map[temp][j]); } return result;//返回结果 } public static void main(String[] args) throws IOException { StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken(); int k=(int)in.nval; while(k-->0) { in.nextToken(); n = (int)in.nval; in.nextToken(); m = (int)in.nval; Init(); for (int i = 0; i < m; i++) { in.nextToken(); int a = (int)in.nval; in.nextToken(); int b = (int)in.nval; in.nextToken(); int c = (int)in.nval; c=c*(-1); map[a][b] = Math.min(map[a][b], c);//有重边 map[b][a] = map[a][b];//两边都打通 } int t = prim(); if (t == INF) {//如果返回的结果为正无穷,表示没有生成最小生成树 System.out.println("impossible"); } else System.out.println(t*(-1)); } } } Problem D 1245 Lisa’s Puzzle 题目描述 5的二进制是101,13的二进制是1101,所以在二进制上,5是13的后缀。Lisa获得了一个长长的正整数列表,她想知道在列表中每一个数是列表中多少个其他数的后缀? 输入 第一行是一个整数N,1≤N≤100000,表示整数的个数。 以后N行,每行一个正整数,每个都可以使用一个32位int表示,而且所有的数都是唯一的。 输出 每个整数对应的结果输出一行, 样例输入 5 5 13 1 2 3 样例输出 1 0 3 0 0 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;public class Main { static class Tree{ int value; Tree left; Tree rigth; public Tree() {//默认为0时,这里可以不写 value=0; } } public static void main(String[] args) throws IOException { StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken(); int n=(int)in.nval; Tree root =new Tree(); long a[]=new long[n]; for(int i=0;i Problem E 1250 Bonus 题目描述 要过年了,老板准备发年终奖,老板准备根据员工的平时表现对比发放奖金,最低发888,每档再增加1000块。 由于工作表现记录有点问题,可能存在矛盾的描述,所以,如果无法发放的话,则所有人,每人发888元。 老板把这个任务交给你,希望你帮他算出一共需要给多少奖金,每人需要发多少奖金? 输入 第一行是一个整数K,表示样例的个数。 每个样例的第一行是两个整数n(1≤n≤10000)和m(0≤m≤50000),分别表示员工的人数以及工作表现记录的数目,员工的编号从1到n。 以后的m行为两个整数a和b(1≤a≠b≤n),表示员工a的工作表现比b好。 输入数据保证工作表现不会有重复记录。 输出 每个样例先输出一行为奖金总数,然后再输出一行,按员工号的顺序,输出每个员工的奖金数,中间用一个空格隔开。 样例输入 2 3 2 1 2 2 3 3 2 1 2 2 1 样例输出 5664 2888 1888 888 2664 888 888 888 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class Main{ static int[]a; static List[]list; static int n; static int []time; static class Node{ int x; int y; public Node(int x,int y) {//这里一定要写 this.x=x; this.y=y; } } static void dfs() { Queue Problem F 1288 Binary Search Tree 题目描述 给1∼n的一个排列,把这个排列的数字按顺序依次插入一棵空的二叉查找树,得到一棵由这个排列建立的二叉查找树。 比如第一个样例的第1和2个排列最后得到的二叉查找树分别如下图中的左图和右图。 现在有m+1个排列,请问后m个排列建立的各个二叉查找树和第一个排列建立的二叉查找树是否相同。 输入 第一行是一个整数T(1≤T≤1000),表示样例的个数。 每个样例的第1行是两个整数n(1≤n≤100),m(1≤m≤min(100,(n−1)!)。 每个样例的第2∼m+2行,每行是n个整数,表示排列。 输出 对于每个样例的后m每个序列的结果,先输出序列的序号,从1开始,然后输出一个英文冒号和空格,再输出结果,如果相同输出“Yes”,否则输出“No”。 每个样例最后输出一个空行。 样例输入 2 5 5 3 2 5 1 4 3 1 2 5 4 3 2 1 5 4 3 5 2 1 4 3 5 4 2 1 3 2 4 5 1 3 2 1 2 3 1 3 2 3 2 1 样例输出 1: No 2: Yes 3: Yes 4: Yes 5: No 1: No 2: No import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;public class Main { static int n; static StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); static class Tree{ int x; Tree left; Tree right; public Tree(int v) { x=v; } /* * 等同于 * public Tree(int x){ * this.x=x; * } */ } static void f(Tree root) throws IOException { for(int i=1;i Problem G 1302 Balance Tree 题目描述 我们将数字序列按顺序依次插入一棵空的二叉查找树,得到一棵由这个序列建立的二叉查找树。 如果对于任何节点,其左右子树的高度相差不超过1,那么我们称其是平衡的。 请你写一个程序,判断一下,对于一个数字序列得到的二叉排序树是否是平衡的? 输入 第一行是一个整数T(1≤T≤1000),表示样例的个数。 每个样例的第一行是一个整数n(1≤n≤1000),表示数字序列的长度。 每个样例的第二行是n个互不相同的整数ai(1≤ai≤109)。 输出 每行输出一个样例的结果,如果是平衡的,输出Yes,否则输出No。 样例输入 3 5 4 3 2 1 5 5 3 4 2 1 5 5 4 2 1 3 5 样例输出 No Yes Yes 提示 第一个样例: 4 / \ 3 5 /2 / 1 第二个样例: 3 / \ 2 4 / \1 5 第三个样例: 4 / \ 2 5 / \ 1 3 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;import java.util.StringTokenizer;public class Main { static StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); static int n; static void read(Tree head) { for(int i=1;i Problem H 1369 Black White Chess 题目描述 一个4×4的格子棋盘,每个格子上有白棋或者黑棋,我们可以做下面三种操作: 把同一行的棋子翻转(白变成黑,黑变成白) 把同一列的棋子翻转 把一个2×2的格子里的棋子翻转 求最少多少步操作,我们可以得到全部是黑的或者全部是白的棋局。 输入 第一行是一个整数T(1≤T≤100000),表示样例的个数。 以后每行一个样例,每行是一个16位的二进制码,依次表示从第1行到第4行的棋局。 输出 每行输出一个样例的结果,如果无法达到目标,输出“-1”。 样例输入 5 0000000000000000 1111111111111111 0000111100001111 1000000000000000 1100000000000011 样例输出 0 0 2 -1 4 样例解释 第三个样例棋局如下 0000 1111 0000 1111 此时,翻转第1,3行可以得到全白;或者翻转第2,4行可以得到全黑。 第五个样例棋局如下 1100 0000 0000 0011 此时,依次翻转左上角在(1,1),(2,1),(3,1)的2×2的块,再翻转第4行,可以得到全白。 import java.io.IOException;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.util.HashSet;import java.util.Scanner;public class Main { private static String bb(String s, int t) { // TODO Auto-generated method stub if(t<4) {//列变换 char[]st=s.toCharArray(); for(int i=0;i<4;i++) { if(st[i*4+t]=='1') { st[i*4+t]='0'; }else { st[i*4+t]='1'; } } return new String (st); }else if(t<8) { t-=4; char[]st=s.toCharArray(); for(int i=0;i<4;i++) { if(st[t*4+i]=='1') { st[t*4+i]='0'; }else { st[t*4+i]='1'; } } return new String (st); }else { t-=8; int x=t/3; int y=t%3; char[]st=s.toCharArray(); if(st[x*4+y]=='1') { st[x*4+y]='0'; }else { st[x*4+y]='1'; } x=x+1; if(st[x*4+y]=='1') { st[x*4+y]='0'; }else { st[x*4+y]='1'; } x=x-1;y=y+1; if(st[x*4+y]=='1') { st[x*4+y]='0'; }else { st[x*4+y]='1'; } x=x+1; if(st[x*4+y]=='1') { st[x*4+y]='0'; }else { st[x*4+y]='1'; } return new String (st); } } //这道题的思路就是先预处理出,从初始状态到最终状态的所有情况,所需的步数 //之后就进行字符串的读入,直接出答案 public static void main(String[] args) throws IOException { Scanner in=new Scanner(System.in); PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); int t=in.nextInt(); HashSet Problem L 1389 二叉查找树 题目描述 n个元素,依次插入一颗初始为空的二叉查找树。对于第i个元素,其所在二叉查找书的左右子树深度差的绝对值为di,求max{di}。 输入格式 第一行是一个整数T (1≤T≤1000),表示样例的个数。 每个样例的第一行是一个整数n (1≤n≤1000),表示元素的个数。 第二行是n个整数ai,(1≤ai≤109),表示第i个元素的值,所有元素的值是唯一的。 输出格式 依次每行输出一个样例的结果,为一个整数。 样例输入 2 5 3 2 1 4 5 5 4 5 3 2 1 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;public class Main{ static long max=0; static StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out)); static int n; public static class Tree{ int value; Tree l; Tree r; int height; public Tree(int val,int deep) { value=val; this.height=deep; } } static void read(Tree head) throws IOException { for(int i=1;i Problem P 1418 消星星 题目描述 小代最近迷上了消灭星星,所以没时间给程设考试出题了。消灭星星游戏规则介绍: 输入 第一行一个t(1≤t≤10),表示样例个数; 接下来每个样例的第一行是正整数n,m(1≤n,m≤103),表示矩阵的大小。 接下来n行m列字符,表示地图,其中所有的字符都是小写字母。 输出 对于每个样例,每行输出一个答案,表示消灭所有星星至少需要多少能量。 样例输入 2 2 2 ab ba 3 3 aab cab ccb 样例输出 4 3 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;public class Main { static int n,m; static char a[][]; static boolean [][]flag; static void dfs(int i,int j) { flag[i][j]=true; if(i>0&&!flag[i-1][j]&&a[i][j]==a[i-1][j]) { dfs(i-1,j); } if(j>0&&!flag[i][j-1]&&a[i][j]==a[i][j-1]) { dfs(i,j-1); } if(i Problem R 1433 Swap Digits 题目描述 一个十进制整数n,你最多可以任意交换相邻的两个数码k次,请问能得到多少个不同的无前导0的数? 输入 第一行是一个整数T(1≤T≤200)。 以后每行一个样例,为两个整数n(1≤n≤109),k(1≤k≤20) 输出 每行输出一个样例的结果。 样例输入 2 10 1 123 2 样例输出 1 5 样例解释 第一个样例只能得到10;第二个样例可以得到123,132,213,312,231。 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static HashSet
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
0) { in.nextToken(); n=(int)in.nval; in.nextToken(); int m=(int)in.nval; list=new List[n+1];//List容器 for(int i=0;i<=n;i++) { list[i]=new ArrayList
发表评论
暂时没有评论,来抢沙发吧~