深度优先

这个家伙好懒，除了文章什么都没留下

0%

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

算法训练 接水问题

时间限制：1.0s 内存限制：64.0MB

锦囊1

模拟即可，要加速可以使用堆优化。

锦囊2

本题的数据范围比较小，可以直接按照题库模拟，或者也可以使用堆来优化算法。

问题描述

学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的 供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打 开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m−n’个龙头关闭。 现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

输入格式

第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同 学的接水量。

输出格式

输出只有一行，1 个整数，表示接水所需的总时间。

样例输入

5 3
4 4 1 2 1

样例输出

4

样例输入

8 4
23 71 87 32 70 93 80 76

样例输出

163

输入输出样例 1 说明

第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完
水，4 号同学接替3 号同学开始接水。
第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接
水量为1。
第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接
水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。
第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接
水量为1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为4 秒。

数据规模和约定

1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；
1 ≤ wi ≤ 100。

这个题难度中等，不那么难，也不是说一下就出来的。模拟是可以解出来的，有几个地方可以优化下。比如直接求出最小的，然后有一个接口没人时，只用最大的放完就行了。

代码，通过了100%的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Scanner;

public class 接水问题 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		int[] data=new int[n];
		int[] shui=new int[m];
		
		for (int i = 0; i < data.length; i++) {
			data[i]=sc.nextInt();
			if(i<m)
				shui[i]=data[i];
		}
		int count=0;
		while(getBool(shui)){
			int min=getMin(shui);
			count+=min;
			for (int i = 0; i < shui.length; i++) {
				shui[i]-=min;
				if(shui[i]==0&&m<data.length)
					shui[i]=data[m++];
			}
		}
		System.out.println(count);
	}

	private static int getMin(int[] shui) {
		int k=100*100;
		for (int i = 0; i < shui.length; i++) {
			if(k>shui[i]&&shui[i]>0)
				k=shui[i];
		}
		return k;
	}

	private static boolean getBool(int[] shui) {
		for (int i = 0; i < shui.length; i++) {
			if(shui[i]>0)
				return true;
		}
		return false;
	}
}

发表于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

算法训练 黑色星期五

时间限制：1.0s 内存限制：512.0MB

问题描述
有些西方人比较迷信，如果某个月的13号正好是星期五，他们就会觉得不太吉利，用古人的说法，就是“诸事不宜”。请你编写一个程序，统计出在某个特定的年份中，出现了多少次既是13号又是星期五的情形，以帮助你的迷信朋友解决难题。
说明：（1）一年有365天，闰年有366天，所谓闰年，即能被4整除且不能被100整除的年份，或是既能被100整除也能被400整除的年份；（2）已知1998年1月1日是星期四，用户输入的年份肯定大于或等于1998年。
输入格式：输入只有一行，即某个特定的年份（大于或等于1998年）。
输出格式：输出只有一行，即在这一年中，出现了多少次既是13号又是星期五的情形。
输入输出样例

样例输入

1998

样例输出

3

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int week=3;
		int days=0;
		for (int i = 1998; i < n; i++) {
			if(getYP(i)){
				days+=366;
			}else{
				days+=365;
			}
		}
		int k=(days+week)%7;
		int q=getYP(n)?1:0;
		int[] arr=new int[]{31,28+q,31,30,31,30,31,31,30,31,30,31};
		
		int sum=13+k,count=0;
		for (int i = 0; i < 12; i++) {
			if(sum%7==5){
				count++;
			}
			sum+=arr[i];
		}
		
		System.out.println(count);
	}

	private static boolean getYP(int n) {
		
		if((n%4==0&&n%100!=0)||n%400==0)
			return true;
		return false;
	}
}

其他的几题太简单了

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

算法训练 黑白无常

时间限制：1.0s 内存限制：256.0MB

问题描述

某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）

输入格式

第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。

输出格式

一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0

样例输入

2
1 0
1 0

样例输出

0

样例输入

5
3 1
0 4
1 3
4 0
1 3

样例输出

35

数据规模和约定

n<=8

为什么又发这道题呢（昨天发过）？因为昨天做的有问题，准确的说是错了。昨天想的是找一组说真假一致的则这两个人说的就是对的，今天突然又想了下，如果两个假的说的是一样的呢，所以就会出问题。

今天还是中规中矩的用穷举，把所有的情况考虑进去，然后验证说的真假。真的的验证说的是真的，假的验证是否说的是假的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int[][] data=new int[n][2];
			for (int i = 0; i < n; i++) {
				data[i][0]=sc.nextInt();
				data[i][1]=sc.nextInt();
			}
			int max=(int)Math.pow(2, n);
			int[] arr=new int[n]; 
			
			for (int i = 1; i < max; i++) {
				int k=getEr(arr,i);//得到二进制，k为说真话的人数
				
				boolean fa=true;
				for (int j = 0; j < arr.length; j++) {
					if(arr[j]==1){//讲真话的说的对
						if(k-1!=data[j][0]||n-k!=data[j][1]){
							fa=false;
						}
					}else{//讲假话的说得不对 
						if(k==data[j][0]&&n-k-1==data[j][1]){
							fa=false;
						}
					}
				}
				if(fa){
					break;
				}
			}
			String str="";
			int co=0;
			for (int i = 0; i < arr.length; i++) {
				if(arr[i]==1){
					str=str+(i+1);
					co++;
				}
			}
			//如果说真话的人数等于总人数，那么可以知道所有人说的都是一样的，那么这些人都说的是假话也是可以的
			//如果说真话的人数为0，那么可以知道这道题无解的。这说的好像还是有点问题
			if(co==n)
				System.out.println(0);
			else if(co==0)
				System.out.println("NoSolution.");
			else
				System.out.println(str);
		}
	}

	private static int getEr(int[] arr, int i) {
		int m=0;
		int count=0;
		while(i>0){
			arr[m]=i%2;
			if(arr[m]==1)
				count++;
			i/=2;
			m++;
		}
		return count;
	}
}

算法训练 最大体积

时间限制：1.0s 内存限制：256.0MB

问题描述

每个物品有一定的体积（废话），不同的物品组合，装入背包会战用一定的总体积。假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，附中的OIER想要研究一下物品不能装出的最大体积。题目保证有解，如果是有限解，保证不超过2，000，000，000
如果是无限解，则输出0

输入格式

第一行一个整数n（n<=10），表示物品的件数
第2行到N+1行: 每件物品的体积(1<= <=500)

输出格式

一个整数ans，表示不能用这些物品得到的最大体积。

样例输入

3
3
6
10

样例输出

17

动态规划，之前讲到过一个最大买不到的数，糖果包装的问题。这题和那个类似，庆幸自己还记得，感觉和上次写的还要好。一道很好的复习题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Scanner;

public class 最大体积 {

	static int[] dp=new int[2*1000*1000];
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int[] data=new int[n];
			int sum=0,a=0,min=500;
			for (int i = 0; i < data.length; i++) {
				a=sc.nextInt();
				data[i]=a;
				sum+=a;
				if(a<min)
					min=a;
			}

			//初始化
			for (int i = 0; i <= sum; i++) {
				for (int j = 0; j < data.length; j++) {
					if(i%data[j]==0){
						dp[i]=1;
						break;
					}
				}
			}

			//找最大找不到的数
			int count=0,k=min-1;
			for (int i = min+1; i <dp.length; i++) {
				
				if(dp[i]!=1)
				for (int j = 0; j < data.length; j++) {
					if(i>data[j]&&dp[i-data[j]]==1){
						dp[i]=1;
						break;
					}
				}
				
				if(dp[i]==1){
					count++;
					dp[i]=1;
					if(count==min){
						System.out.println(k);
						break;
					}
				}else{
					count=0;
					k=i;
				}
			}
		}
	}
}