橙白oj 2017级《算法分析与设计》-练习02

小灰灰 2024-04-18 12:10 31阅读 0赞

### 注：A题我以为给新生出的，应该贼简单，是按顺序消灭，卡了十几分钟，成了最后一个ac的题，真是菜的真实。 ###

##  ##

## Problem A: ##

## Description ##

![format_png][]

白细胞是人体与疾病斗争的“卫士”。当病菌侵入人体体内时，白细胞能通过变形而穿过毛细血管壁，集中到病菌入侵部位，将病菌包围﹑吞噬。如果体内的白细胞的数量高于正常值，很可能是身体有了炎症。

现在，白细胞遇到了一群杂菌，它有n（0<n<1000）点体力，现在有m个杂菌，每个杂菌需要ai点体力去消灭（0<ai<1000）。请问，白细胞最多能消灭多少个杂菌呢？

## Input ##

第一行有两个数n和m，分别代表白细胞的体力和杂菌数量 第二行有m个数，a0，a1,...a(m-1),分别代表消灭其需要的体力。

## Output ##

最大能消灭多少个杂菌。

## Sample Input ##

6 3
    1 2 3

## Sample Output ##

解析：模拟消灭杂菌的过程：排序，先消灭较小的数字。

import java.util.Scanner;
    import java.util.Arrays;
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n=sc.nextInt();
    		int m=sc.nextInt();
    		int[] arr=new int[m];
    		for(int i=0;i<m;i++)arr[i]=sc.nextInt();
    		Arrays.sort(arr);
    		int ak=0;
    		while(ak<m && n>=arr[ak]) {
    			n-=arr[ak];
    			ak++;
    		}
    		System.out.println(ak);
    	}
    }

## Problem B: ##

## Description ##

![format_png 1][]

红细胞也称红血球，在常规化验英文常缩写成RBC，是血液中数量最多的一种血细胞，同时也是脊椎动物体内通过血液运送氧气的最主要的媒介，同时还具有免疫功能。哺乳动物成熟的红细胞是无核的，这意味着它们失去了DNA。红细胞也没有线粒体，它们通过分解葡萄糖释放能量。运输氧气，也运输一部分二氧化碳。运输二氧化碳时呈暗紫色，运输氧气时呈鲜红色

红细胞会生成于骨髓之内，开始在白细胞内生长。红细胞老化后，易导致血管堵塞，所以会自动返回骨髓深处，由白细胞负责销毁；或是在经过肝脏时，被枯否细胞分解成为胆汁。

32767号红细胞正在把氧气运送到目的地，她面前是一层层的血管网，到达目的地之前一共有很多层血管网，对于每一层血管网，红细胞都可以有很多条路径通过，从而到达层与层之间的节点，最终到达终点。

32767号红细胞是个路痴，请帮她计算出一共有多少条路径。

## Input ##

第一行输入一个整数n（0<n<20）代表血管层数。

第二行输入n个整数ai，代表每层一共有多少条路径。（0<ai<1000）。

## Output ##

一个整数，代表路径的总数

且保证答案在long long范围之内（py选手不用管）

## Sample Input ##

5 10 20 30 40 50

## Sample Output ##

12000000

解析：经过分析，数字相乘即可。

import java.util.Scanner;
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n=sc.nextInt();
    		long ak=1;
    		for(int i=0;i<n;i++)ak*=sc.nextInt();
    		System.out.println(ak);
    	}
    }

## Problem C: ##

## Description ##

![format_png 2][]

细胞毒性T细胞（cytotoxic T cell，Tc或CTL），也称杀伤性T细胞。是一种监控并在需要时杀死靶细胞的细胞。记忆细胞毒性T细胞对带抗原的靶细胞有记忆功能，由细胞毒性T细胞分化而成。一旦发现带特异性抗原的靶细胞，会刺激效应细胞毒性T细胞产生效应细胞毒性T细胞，消灭被感染的细胞或癌细胞。

癌细胞出现了！杀手T细胞出动！

杀手T细胞需要迅速到达癌细胞的位置，他离癌细胞有n米的距离，它每次可以选择走1米或者跑2米，问，杀手T细胞有多少种方式到达癌细胞的位置。

例如：杀手T细胞离癌细胞3米，他可以每次都走1米，或者第一次走1米，第二次跑2米，也可以第一次跑2米，第二次走1米，一共三种方式到达癌细胞的位置。

## Input ##

输入包含若干行，每行包含一个正整数n(1<=n<=30)，n代表杀手T细胞离癌细胞的位置。

## Output ##

一个正整数，代表杀手T细胞到达癌细胞的方法数目。

## Sample Input ##

5
    8
    10

## Sample Output ##

8
    34
    89

解析：

杀手T细胞离癌细胞1米，有一种方法。

杀手T细胞离癌细胞2米，可以分两次或者一次，有两种方法。

之后，因为第n米只可能是通过n-1或n-2跳来的，所以到达第n米的方法数等于ak\[n\]=ak\[n-1\]+ak\[n-2\]，按顺序求出答案即可。

import java.util.Scanner;
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		long[] ak=new long[35];
    		while(sc.hasNextInt()) {
    			int n=sc.nextInt();
    			ak[1]=1;
    			ak[2]=2;
    			for(int i=3;i<=n;i++)ak[i]=ak[i-1]+ak[i-2];
    			System.out.println(ak[n]);
    		}
    	}
    }

## Problem D: 水仙花数 ##

## Description ##

请判断一个数是不是水仙花数。  
其中水仙花数定义各个位数立方和等于它本身的三位数。

## Input ##

有多组测试数据，每组测试数据以包含一个整数n(100<=n<1000) 输入0表示程序输入结束。

## Output ##

如果n是水仙花数就输出Yes 否则输出No

## Sample Input ##

153  
154  
0

##    Sample Output ##

Yes
    No

解析：求出各个位数的立方和，和本身作比较即可（小号交的循环求，怕查重，手打三个位数）

import java.util.Scanner;
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		while(true) {
    			int n=sc.nextInt();
    			if(n==0)break;
    			int a=n/100;
    			int b=(n/10)%10;
    			int c=n%10;
    			if(a*a*a+
    				b*b*b+
    				c*c*c==n) {
    				System.out.println("Yes");
    			}else {
    				System.out.println("No");
    			}
    		}
    	}
    }

## Problem E: 合并 ##

## Description ##

现在给你两堆数，每个堆中有n个数。你的任务是把这两个堆并成一个堆，并把合并后的堆中的元素按从小到大的顺序输出。例如当n=5时，第一个堆是\{1,2,3,4,5\}，第二个堆是\{5,6,7,8,9\}，那么你就应该输出1 2 3 4 5 6 7 8 9。（一堆中可能有重复的数）

## Input ##

第一行输入一个整数T（1≤T≤100），表示有T组测试数据。 每组数据先输入一个整数N（1≤N≤10），表示每个堆中元素的个数。然后输入N个整数A（0≤A<100），最后输入N个整数B（0≤B<100）。

## Output ##

把合并后的堆中的元素按从小到大的顺序输出。

## Sample Input ##

2
    5
    1 2 3 4 5
    5 6 7 8 9
    6
    18 88 43 5 10 78 
    94 99 37 92 3 52

## Sample Output ##

1 2 3 4 5 6 7 8 9 
    3 5 10 18 37 43 52 78 88 92 94 99

解析:合并两组数并且去重按顺序输出，由题意得，数字均小于100，范围较小，考虑采用桶思想，数组记录对应下标的数字出没出现过即可。

另：注意输出格式，找出第一个数字，不打印空格。

之后的数字，前面打印空格。

import java.util.Arrays;
    import java.util.Scanner;
    public class main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n=sc.nextInt();
    		while(n-->0) {
    			int[] ak=new int[100];
    			int m=sc.nextInt();
    			for(int i=0;i<2*m;i++)ak[sc.nextInt()]=1;
    			int i;
    			for(i=0;i<100;i++) {
    				if(ak[i]==1) {
    					System.out.print(i);
    					break;
    				}
    			}
    			for(i++;i<100;i++)
    				if(ak[i]==1)
    					System.out.print(" "+i);
    			System.out.println();
    		}
    	}
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL29qLnlvdXl1LmltL3VwbG9hZC9pbWFnZS8yMDE4MDgxMy8yMDE4MDgxMzE4MDczOF82MDk5NS5qcGc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL29qLnlvdXl1LmltL3VwbG9hZC9pbWFnZS8yMDE4MDgxMy8yMDE4MDgxMzE4MzMwN184MTE1NC5qcGc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL29qLnlvdXl1LmltL3VwbG9hZC9pbWFnZS8yMDE4MDgxMy8yMDE4MDgxMzE5MTMyOV8zOTU5My5qcGc?x-oss-process=image/format,png