第十六周.

绝地灬酷狼 2022-10-08 02:30 217阅读 0赞

### 16周 ###

*  问题 A: yangftc的时间安排
 *  问题 B: 自守数
 *  问题 C: 相聚HNUCM校园食堂
 *  问题 D: 0-1背包问题（回溯法）
 *  问题 E: 旅行售货员(TSP)
 *  问题 F: 简单递归求和
 *  问题 G: 文件存储
 *  问题 H: 递归求和
 *  问题 I: 最大收益
 *  问题 J: 排列蛋卷

# 问题 A: yangftc的时间安排 #

**题目描述**

*  yangftc需要安排他的时间，有很多事情做，每个事情都有固定的开始和结束时间，因为yangftc每次只能做一件事情，如果有两个或者多个事情的时间重合了那么他就会说  
    NO，否则他就会说 YES 。

**输入**

*  第一个数字t代表样例数量， 后面t个样例，每个样例输入一个n表示事情的数量，后面n行每行两个数字l r表示这个事情的开始和结束时间；

**输出**

*  判断yangftc会说什么 YES或者 NO 。 数据范围 1<=t<=500 1<=n<=100 1<=l<=r<=100000

**样例输入 Copy**

2
    3
    1 3
    4 5
    6 7
    2
    1 3
    3 4

**样例输出 Copy**

YES
    NO

**代码：**

import java.util.Scanner;
    
    public class Main { 
    
    	static int n;
    	static void swap(int i,int k,int []start,int []end) { 
    	 
    		int t1 = start[i];
    		start[i] = start[k];
    		start[k] = t1;
    		int t2 = end[i];
    		end[i] = end[k];
    		end[k] = t2;
    		
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int T = sc.nextInt();//两组案例
    			
    			for(int i=1;i<=T;i++) { 
    				n = sc.nextInt();//n组数据
    				int start[] = new int[n];//活动开始时间
    				int end[] = new int[n];//活动结束时间
    				
    				for(int j=0;j<n;j++) { 
    					start[j] = sc.nextInt();
    					end[j] = sc.nextInt();
    				}
    				for(int j=0;j<n;j++) 
    					for(int k=j+1;k<n;k++)
    					    if(end[j]>end[k])
    						    swap(j,k,start,end);
    				
    				boolean flag = true;
    				for(int j=1;j<n;j++) 					
    					if(start[j]<=end[j-1]) { 
    						flag = false;
    						break;
    					}
    						
    				
    				if(flag)
    				    System.out.println("YES");
    				else
    					System.out.println("NO");
    			}
    		}
    	}
    }

# 问题 B: 自守数 #

**题目描述**

*  自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 =  
    87909376。请求出n以内的自守数的个数。

**输入**

*  int型整数。

**输出**

*  n以内自守数的数量。

**样例输入 Copy**

2000

**样例输出 Copy**

**代码：**

【第一种方法容易溢出，我班大佬建议打表】

import java.util.Comparator;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.TreeMap;
    
    public class Main { 
    	
    // static boolean judge(int n ) { 
    // int m = n;//输入的数
    // int ping = n * n;//平方
    // while(n != 0) {//循环判断
    // if(n % 10 != ping % 10) {//两个数的尾数不相等
    // return false;
    // }
    // n = n / 10;//除去尾数剩余的数
    // ping = ping / 10;
    // }
    // return true;
    // }
    // 
    // static int solve(int n) { 
    // int count = 0;//用来统计有多少个自守数
    // while(n >= 0) { 
    // if(judge(n)) { 
    // count++;
    // }
    // n--;
    // }
    // return count;
    // }
    
    	static void solve(long T) { 
    		Map<Integer, Integer> map = new TreeMap<>(new Comparator<Integer>() { 
                @Override
                public int compare(Integer o1, Integer o2) { 
                    return o2.compareTo(o1);
                }
            });
            map.put(0, 1);
            map.put(1, 2);
            map.put(5, 3);
            map.put(6, 4);
            map.put(25, 5);
            map.put(76, 6);
            map.put(376, 7);
            map.put(625, 8);
            map.put(9376, 9);
            map.put(90625, 10);
            map.put(109376, 11);
            map.put(890625, 12);
            map.put(2890625, 13);
            map.put(7109376, 14);
            map.put(12890625, 15);
            map.put(87109376, 16);
            map.put(212890625, 17);
            map.put(787109376, 18);
            map.put(1787109376, 19);
            for (Map.Entry<Integer, Integer> m : map.entrySet()) { 
                if (T >= m.getKey()) { 
                    System.out.println(m.getValue());
                    break;
                }
            }
    	}
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) { 
                long T = sc.nextInt();
                solve(T);
            }
    
        }
    }

# 问题 C: 相聚HNUCM校园食堂 #

**题目描述**

*  HNUCM的食堂重新装修了，小明决定约上朋友去食堂相聚，在食堂里，小明看到了M位男同学，N位女同学，小明是一个颜值控，因此他对每一位男生和女生都有一个颜值打分，他心里yy着想为这些单身狗们进行配对，小明真是一个关心同学的人！但小明认为配对同学的颜值之差不能超过5，注意必须是一位男同学和一位女同学才能配对，虽然小明对于可以配对的人数已经有了答案，但他想考考你的编程能力，因此他想请你帮他用编程算一下最多可以配对多少个人。(本题介绍仅作题目背景使用，无任何其他观点)

**输入**

*  每个测试文件仅有一条测试数据。
 *  第一行输入M，N，分别表示男同学的数量，女同学的数量。(1<=M<=100,1<=N<=100)
 *  第二行输入M个正整数，分别表示男同学们的颜值。
 *  第三行输入N个正整数，分别表示女同学们的颜值。
 *  注意，所有人的颜值分数范围在\[1,100\]

**输出**

*  输出最多可以配对的总人数。

**样例输入 Copy**

5 4
    10 65 23 67 80
    5 15 60 90

**样例输出 Copy**

*  提示
 *  样例中第一位男同学和第一位女同学配对，
 *  第二位男同学和第三位女同学配对。
 *

**代码：**

> 【这个代码是我自己写的嗷！但是也是提交了两遍，第一遍是因为没有做好判断的内容，第二遍是没有排序】

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int m = sc.nextInt();//男同学的数量
    			int n = sc.nextInt();//女同学的数量
    			
    			int man[] = new int[m];//男同学的颜值
    			for(int i=0;i<m;i++)
    				man[i] = sc.nextInt();
    			
    			int woman[] = new int[n];//女同学的颜值
    			for(int i=0;i<n;i++)
    				woman[i] = sc.nextInt();
    			
    			Arrays.sort(man);
    			Arrays.sort(woman);
    			
    			int countman = 0;//统计配对个数
    			int countwoman = 0;
    			for(int i=0;i<m;i++)//男同学的颜值
    				for(int j=0;j<n;j++) //女同学的颜值
    					if(Math.abs(man[i]-woman[j])<=5&&man[i]!=0&&woman[j]!=0) { 
    						countman++;//把这个男生记录
    						countwoman++;//把这个女生记录
    						man[i] = 0;
    						woman[j] = 0;
    					}
    						
    			System.out.println(countman+countwoman);
    		}
    
    	}
    
    }

# 问题 D: 0-1背包问题（回溯法） #

**题目描述**

*  有n个物品，第i个物品重量为wi，价值为vi，现有一背包容量为C，要求把物品装入背包得到最大价值，并且要求出这些选取的物品。
 *  要求用回溯法求解。

**输入**

*  多组测试数据，请处理到文件尾，一个整数表示物品的数量n，后一行有n个整数，代表价值，再后一行有n个整数，代表重量，最后有一个整数C代表背包容量,1<=n<=15,1<=vi<=30,1<=wi<=30,1<=C<=80。

**输出**

*  背包的最大总价值和所选取的物品，
 *  如果选取的方案有多种，请输出字典序最小的那种方案，
 *  每组测试数据应输出一行，
 *  在这里字典序最小的意思是，我们假设存在两种不同方案S,T所能得到的总价值相同且是最大的，
 *  对于方案S种选取|S|种物品，方案T选取|T|种物品，对于i=1,2…j-1，我们有si= ti，但sj < tj,则方案的S的字典序比方案T的字典序要小。
 *  由于没有使用special judge，所以如果选取得方案是S，请按照从小到大的顺序输出方案S中的物品下标。

**样例输入 Copy**

5
    6 3 6 5 4
    2 2 4 6 5
    8

**样例输出 Copy**

15 1 2 3

**代码：**

[戳我戳我！][Link 1]

import java.util.Scanner;
    public class Main{ 
    	static int n, C,cw,cv,bestv;
    	static int v[],w[],way[],bestway[];
    	
    	static void backtrack(int i) { 
    		if(i>n){ //如果放到最后一个物品，那一定是最佳方案
    			if(cv>bestv){ //判断当前的最佳和之前的最佳方案
    			bestv=cv;//交換
    			for (int j = 1; j <=n; j++) 
    				bestway[j] = way[j];//交換 
    			}
    		}
    		else { //第一种选
    		if(cw>=w[i]){ //当前剩余容量
    			cw-=w[i];//更新剩余容量
    			cv+=v[i];//更新当前最佳容量
    			way[i]=1;//将选中的物品标志更改为
    			backtrack(i+1);//继续回溯
    			cw+=w[i];
    			cv-=v[i];
    			way[i]=0;
    		}//第二种不选
    		if(bound(i+1)+cv>bestv)
    			backtrack(i+1);//当前物品大于剩余容量，但是除了他不放，把之后的物品都放入还可以得到一个优于现有解
    		//当前物品不选继续递归下一个
    	    }
    	}
    	
    	static int bound(int k) { 
    		int bound=0;
    		for(int j=k;j<=n;j++)
    			bound+=v[j];
    		return bound;
    	}
    	
    	static void print() { 
    		System.out.print(bestv+" ");
    		for (int i=1;i<=n;i++) 
    			if(bestway[i]==1)
    				System.out.print(i+" ");		
    	}
    	
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();//物品数量
    			v = new int[n+1];//价值背包
    			w = new int[n+1];//重量背包
    			way = new int[n+1];//当前背包
    			bestway = new int[n+1];//最好背包
    			for(int i=1;i<=n;i++) 
    				v[i] = sc.nextInt();//依次放价值
    			
    			for(int i=1;i<=n;i++) 
    				w[i] = sc.nextInt();//依次放价值
    			
    			C = sc.nextInt();//最大背包容量
    			
    			cw = C;//背包容量赋值
    			cv = 0;//当前最佳
    			bestv = 0;//最终最佳
    			backtrack(1);
    			print();
    		}
    	}	
    }

# 问题 E: 旅行售货员(TSP) #

**题目描述**

*  有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，问如何事先确定一条最短的线路以保证路径最短？

**输入**

*  输入两个整数n，m分别代表城市数量，边数量，2<=n<=8,n-1<=m<=2\*n
 *  接下来m行每行输入有3个整数x，y，z代表x和y城市之间有一条长为z的路,保证输入的图是连通的，旅行商总是从1城市出发。

**输出**

*  要求求出最短的路径，和该路径的长度，如果不存在这样的路径你只需要输出-1。

**样例输入 Copy**

4 6
    1 2 30
    1 3 6
    1 4 4
    2 3 5
    2 4 10
    3 4 20

**样例输出 Copy**

1 3 2 4 1
    25

**代码：**

【大佬地文章，[戳我戳我！][Link 2]】

import java.util.Scanner;
    
    public class Main { 
        static int n,m;//n城市数量,m边数量
        static int graph[][];
        static int cd,bd;//当前距离，最短距离
        static int x[],bestx[];//当前路线，最好的路线
        static int MAX = Integer.MAX_VALUE;
        
      
        static void swap(int t, int i) { 
            int temp=x[t];
            x[t]=x[i];
            x[i]=temp;
        }
        
    
        static void backtrace(int t) { 
            if(t==n) { 
                if(graph[x[n-1]][x[n]]!=MAX && //准备去第n个城市 判断当前售货员与第n个点有没有路线，没路线剪掉
                   graph[x[n]][1]!=MAX && //判断第n个点与起点1有没有路线，没有剪掉
                  (cd+graph[x[n-1]][x[n]]+graph[x[n]][1]<bd || //判断走完这条路线，回原点的总距离小于已知的最短距离?如大于剪掉
                   bd==-1)) {  //如果都符合，就要做更新操作 
                    for(int i=1;i<=n;i++) 
                        bestx[i] = x[i];
                    bd = cd+graph[x[n-1]][x[n]]+graph[x[n]][1];
                    }
            }else { 
                for(int i=t;i<=n;i++) { 
                    if(graph[x[t-1]][x[i]]<MAX && //剪枝条件：t-1表示现在售货员所在的城市，i表示要准备去的城市,两者之间必须要有边
                      (cd+graph[x[t-1]][x[i]]<bd || //bd = -1 表示第一次走
                       bd==-1)) { 		
                        swap(t,i);//符合条件 交换
                        cd = cd+graph[x[t-1]][x[t]];
                        backtrace(t+1);
                        cd = cd-graph[x[t-1]][x[t]];
                        swap(t,i);
    
                    }
                }
            }
    
        }
        
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) { 
                n = sc.nextInt();
                m = sc.nextInt();
                graph = new int[n + 1][n + 1];
                x = new int[n + 1];
                bestx = new int[n + 1];
                cd = 0;
                bd = -1;
                
                for (int i = 1; i <= n; i++) { 
                    x[i] = i;
                    for (int j = 1; j <= n; j++) { 
                        graph[i][j] = MAX;//初始化地图
                    }
                }
                for (int i = 1; i <= m; i++) { 
                    int S1 = sc.nextInt();
                    int S2 = sc.nextInt();
                    int length = sc.nextInt();
    
                    graph[S1][S2] = length;
                    graph[S2][S1] = length;//把所有的边存储起来
    
                }
                backtrace(2);
                if (bd != -1) { 
                    for (int i = 1; i <= n; i++) 
                        System.out.print(bestx[i] + " ");
                    System.out.println("1");
                    System.out.println(bd);
                } else 
                    System.out.println("-1");
            }
        }
    }

# 问题 F: 简单递归求和 #

**题目描述**

*  使用递归编写一个程序求如下表达式前n项的计算结果： (n<=100) 1 - 3 + 5 - 7 + 9 - 11 +…
 *  输入n，输出表达式的计算结果。

**输入**

*  多组输入，每组输入一个n，n<=100。

**输出**

*  输出表达式的计算结果。

**样例输入 Copy**

1
    2

**样例输出 Copy**

1
    -2

**代码：**

> 【第一个没用到递归~，第二个用到了递归】

import java.util.Scanner;
    public class Main { 	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner  sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int n = sc.nextInt();
    			int sum = 0;			
    			for(int i=1,count=1;count<=n;i+=2,count++) { //1 3 5 7... 
    				if(count%2==1)
    					sum+=i;
    				else
    					sum-=i;				
    			}
    			System.out.println(sum);
    		}
    	}
    }
    
    //递归求和
    
    import java.util.Scanner;
    public class Main { 
    	static int solve(int n) { 
    		if(n==0)
    			return 0;
    		if(n==1)
    			return 1;
    		return (int) (Math.pow(-1,n-1)*(2*n-1)+solve(n-1));
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner  sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int n = sc.nextInt();
    			System.out.println(solve(n));
    		}
    	}
    }

# 问题 G: 文件存储 #

**题目描述**

*  如果有n个文件\{F1,F2,F3,…,Fn\}需要存放在大小为M的U盘中，文件i的大小为Si，1<=i<=n。请设计一个算法来提供一个存储方案，使得U盘中存储的文件数量最多。

**输入**

*  多组输入，对于每组测试数据，每1行的第1个数字表示U盘的容量M（以MB为单位，不超过256\*1000MB），第2个数字表示待存储的文件个数n。  
    第2行表示待存储的n个文件的大小（以MB为单位）。

**输出**

*  输出最多可以存放的文件个数。

**样例输入 Copy**

10000 5
    2000 1000 5000 3000 4000

**样例输出 Copy**

代码:

> 【仔细看，这其实是一个最优装载的问题】

# 问题 H: 递归求和 #

**题目描述**

*  使用递归编写一个程序求如下表达式的计算结果： (1<n<=20) S(n) = 1*4 + 4*9 + 9*16 + 16*25 +  
    … + ((n-1)2)\*n2 输入n，输出表达式S(n)的结果。

**输入**

*  单组输入，输入一个正整数n，1<n<=20。

**输出**

*  输出表达式S(n)的计算结果。

**样例输入 Copy**

**样例输出 Copy**

**代码：**

import java.util.Scanner;
    
    public class Main { 
    
    	//S(n) = 1*4 + 4*9 + 9*16 + 16*25 + ... + ((n-1)^2)*n^2
    	static int solve(int n) { 
    		if(n==0)
    			return 0;
    		if(n==1)
    			return 0;
    		return (int) (((Math.pow(n-1,2))*Math.pow(n,2))+solve(n-1));
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int n = sc.nextInt();
    			System.out.println(solve(n));
    		}
    
    	}
    
    }

# 问题 I: 最大收益 #

**题目描述**

*  小X是一位精明的投资人，他每次都能够做出正确的投资判断。
 *  现在有N个项目，每个项目的总投资额和总收益已知，并且每一个项目都允许小X只投资一部分，当然也就只能拿到一部分收益。
 *  现在小X决定拿出M万元钱来进行投资，请你帮他设计一个算法来计算最大收益和。

**输入**

*  单组输入，对于每一组数据，第1行包含两个正整数，分别是M和N，其中M<=10^6，N<=100。
 *  接下来N行每行均包含两个正数（不一定是正整数），第1数字表示第N个项目的总投资额（万元），第2个数字表示第N个项目的总收益（万元），两个数字之间用空格隔开。

**输出**

*  小X可以获得的最大收益和（万元，结果四舍五入保留两位小数）。

**样例输入 Copy**

100 4
    50 10 
    20 10 
    40 10 
    50 20

**样例输出 Copy**

37.50

**代码：**

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
     
    //结构体
    class Element{ 
        double w;
        double v;
        double p;//单位重量价值
    };
    
    //自定义以单位重量价值排序排序
    class cmp implements Comparator<Element>{ 
        public int compare(Element a, Element b) { 
            if(a.p<b.p) 
                return 1;
            else
                return -1;
        }
    }
    
    public class Main { 
    	
        static double bestv;    //最大价值
        static double[] x = new double[1000];
        static int c,n;
        static Element[] bag;//背包
        
        static void knapsack(){  //求解背包问题并返回总价值
        	bestv = 0;          //初始化最大价值为0
            double weight = c;    //背包中能够装入的剩余重量
            int i=1;
    // if(i<n) {}
            	while(i<=n && bag[i].w<=weight){ //物品i能够全部装入时循环
                    x[i]=1;            //装入物品i
                    weight-=bag[i].w;  //减少背包中能装入的剩余重量
                    bestv+=bag[i].v;   //累计总价值
                    i++;               //继续循环
                }
                if(i<=n && weight>0){                 //余下重量大于0
                    x[i]=(1.0)*weight/bag[i].w;    //将物品i的一部分装入
                    bestv+=x[i]*bag[i].v;    //累计总价值
                }
                System.out.println(String.format("%.2f", bestv)); 
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){ 
            	c = sc.nextInt();  
                n = sc.nextInt();
                
                bag = new Element[n+1];
                for(int i=1; i<=n; i++){ 
                	bag[i] = new Element();
                	bag[i].w = sc.nextDouble();//第N个项目的总投资额
                	bag[i].v = sc.nextDouble();//第N个项目的总收益
                }
                
                for(int i=1; i<=n; i++)
                	bag[i].p = bag[i].v/bag[i].w;//单位重量价值
                        
                Arrays.sort(bag,1,n+1,new cmp());//排序
    // 
    // for(int i=1;i<=n;i++) { 
    // System.out.println(bag[i].w+" "+bag[i].v);
    // }
                knapsack();
                
            }
        }
    }

# 问题 J: 排列蛋卷 #

**题目描述**

*  刚考完研的TC同学这段时间在家闲得慌，因此他决定学点新手艺。今天他学习的内容是：做蛋卷。
 *  由于是第一次做蛋卷，TC同学做出来蛋卷长短不一。看着这些长度都不一样的蛋卷，TC同学的强迫症又犯了。他希望能够拿出其中部分蛋卷，使得留下来的蛋卷能够按照长度从大到小的次序排列。
 *  请问他最少需要拿出多少根蛋卷？

**输入**

*  单组输入，对于每一组测试数据，第1行N表示蛋卷的总数量（n<=1000)。
 *  第2行包含N个正整数，分别表示每一根蛋卷的长度。（单位：厘米）
 *  保证在同一组输入数据中每一根蛋卷的长度均不一样。

**输出**

*  输出最少需要拿出的蛋卷数量。

**样例输入 Copy**

5
    15 18 17 11 12

**样例输出 Copy**

**代码：**

> 【这是一个最长递减子序列的变形】

[戳我戳我！][Link 3]

import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int n = sc.nextInt();
    			int a[] = new int[n+1];
    			int b[] = new int[n+1];//存储对应的上升子序列
    			for(int i=0;i<n;i++) { 
    				a[i] = sc.nextInt();
    			}
    			b[0] = 1;
    			
    			for(int i=0;i<n;i++)
    				for(int j=0,k=0;j<i;j++) { 
    					if(a[j]>a[i] && k<b[j])
    						k = b[j];
    					b[i] = k+1;
    	
    				}
    			int maxlen = 0;
    			for(int i=0;i<n;i++)
    				if(b[i]>maxlen)
    					maxlen = b[i];
    			System.out.println(n-maxlen);
    		}
    
    	}
    
    }

> 【在大佬的帮助下，万幸做完了，周末还要期末考试，我还没复习，难受，哭唧唧~，还是先做课设吧】
> 
> “当你烦恼的时候，想想人生就是减法，见一面少一面，活一天就少一天，还有什么好烦恼的呢，不忘人恩，不念人过，不思人非，不计人怨。不缺谁，不少谁，对得起良心就好。”

[Link 1]: https://blog.csdn.net/weixin_43927892/article/details/93473678
[Link 2]: https://blog.csdn.net/qq_45353823/article/details/106242718
[Link 3]: https://blog.csdn.net/cxllyg/article/details/7631215