深度优先

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

0%

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

寻找最大数

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述

请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大，

比如当n=92081346718538，m=10时，则新的最大数是9888

输入

第一行输入一个正整数T，表示有T组测试数据
每组测试数据占一行，每行有两个数n,m（n可能是一个很大的整数，但其位数不超过100位，并且保证数据首位非0，m小于整数n的位数）

输出

每组测试数据的输出占一行，输出剩余的数字按原次序组成的最大新数

样例输入

1
2
3
2
92081346718538 10
1008908 5

样例输出

1
2
9888
98 
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
import java.util.Scanner;

public class T6寻找最大数 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=Integer.parseInt(sc.nextLine());
			
			String[] out=new String[n];
			for (int i = 0; i < out.length; i++) {
				String num=sc.next();
				int m=Integer.parseInt(sc.next());
				out[i]=getMax(num,m);
			}
			for (int i = 0; i < out.length; i++) {
				System.out.println(out[i]);
			}
		}
	}

	private static String getMax(String num, int m) {
		
		int k=num.length();
		while(m!=0){
			
			for (int j = 0; j < k; j++) {
				for (int i = 0; i < num.length()-1; i++) {
					if(num.charAt(i)<num.charAt(i+1)){
						num=num.substring(0,i)+num.substring(i+1);
						m--;
						if(m==0)return num;
						break;
					}
				}	
			}
			if(m!=0){
				num=num.substring(0,num.length()-m);
				m=0;
			}
		}
		if(num.length()==0)return "0";
		return num;
	}
}

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

田忌赛马

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

Here is a famous story in Chinese history.

“That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others.”

“Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser.”

“Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian’s. As a result, each time the king takes six hundred silver dollars from Tian.”

“Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match.”

“It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king’s regular, and his super beat the king’s plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?”

Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian’s horses on one side, and the king’s horses on the other. Whenever one of Tian’s horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching…

However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses — a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.

In this problem, you are asked to write a program to solve this special case of matching problem.

输入

The input consists of many test cases. Each case starts with a positive integer n (n <= 1000) on the first line, which is the number of horses on each side. The next n integers on the second line are the speeds of Tian’s horses. Then the next n integers on the third line are the speeds of the king’s horses.

输出

For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.

样例输入

1
2
3
4
5
6
7
8
9
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18

样例输出

1
2
3
200
0
0

一本ACM书上面的一道原题，照着书上敲的居然没有AC，那本书出的确实不太好。

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
68
69
import java.util.Scanner;

public class T12田忌赛马 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int[] tian=new int[n];
			int[] qi=new int[n];
			
			for (int i = 0; i < tian.length; i++) {
				tian[i]=sc.nextInt();
			}
			
			for (int i = 0; i < qi.length; i++) {
				qi[i]=sc.nextInt();
			}

			for (int i = 0; i < qi.length; i++) {
				for (int j = 0; j < qi.length; j++) {
					
					if(tian[i]>tian[j]){
						int t=tian[i];
						tian[i]=tian[j];
						tian[j]=t;
					}
					
					if(qi[i]>qi[j]){
						int t=qi[i];
						qi[i]=qi[j];
						qi[j]=t;
					}
				}
			}
			int l1=0,l2=0,r1=n-1,r2=n-1,ans=0;
			while(l1<=r1){
				if(tian[l1]>qi[l2]){
					ans+=200;
					l1++;
					l2++;
				}
				else if(tian[l1]<qi[l2]){
					ans-=200;
					r1--;
					l2++;
				}
				else if(tian[l1]==qi[l2]&&tian[r1]>qi[r2]){
					ans+=200;
					r1--;
					r2--;
				}
				else if(tian[l1]==qi[l2]&&tian[r1]<qi[r2]){
					if(tian[r1]<qi[l2]){
						ans-=200;
					}
					r1--;
					l2++;
				}
				else if(tian[l1]==qi[l2]&&tian[r1]==qi[r2]){
					r1--;
					l1++;
				}
			}
			System.out.println(ans);
		}
	}
}

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

背包问题

时间限制：3000 ms | 内存限制：65535 KB

难度：3
描述

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入

第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。

输出

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

样例输入

1
2
3
4
5
6
1
3 15
5 10
2 8
3 9

样例输出

1
65

背包问题，我靠，以为是dp结果发现想多了，代码也写复杂了。

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
import java.util.Scanner;

public class T1背包问题 {

	public static void main(String[] args) {
	
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int[] out=new int[n];
			for (int i = 0; i < out.length; i++) {
				int s=sc.nextInt();
				int m=sc.nextInt();
				int[][] data=new int[s][2];
				for (int j = 0; j < data.length; j++) {
					data[j][0]=sc.nextInt();
					data[j][1]=sc.nextInt();
				}
				data=sort(data);
				int sum=0;
				for (int j = 0; j < data.length; j++) {
					if(m>0){
						if(m>=data[j][1]){
							sum+=data[j][0]*data[j][1];
							m-=data[j][1];
						}else{
							sum+=data[j][0]*m;
							break;
						}
					}
				}
				out[i]=sum;
			}
			for (int i = 0; i < out.length; i++) {
				System.out.println(out[i]);
			}
		}
	}

	private static int[][] sort(int[][] data) {
		
		int a,b;
		for (int i = 0; i < data.length; i++) {
			for (int j = i+1; j < data.length; j++) {
				if(data[i][0]<data[j][0]){
					
					a=data[i][0];
					data[i][0]=data[j][0];
					data[j][0]=a;
					
					b=data[i][1];
					data[i][1]=data[j][1];
					data[j][1]=b;
				}
			}
		}
		
		return data;
	}
}