深度优先

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

0%

发表于 分类于
本文字数： 3.6k 阅读时长 ≈ 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
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][3];
			int[][] arr=new int[n][2];
			int t=0;
			for (int i = 0; i < n; i++) {
				int a=sc.nextInt();
				int b=sc.nextInt();
				arr[i][0]=a;
				arr[i][1]=b;
				boolean fa=true;
				for (int j = 0; j < n; j++) {
					if(data[j][0]==a&&data[j][1]==b){
						data[j][2]++;
						fa=false;
						break;
					}
				}
				if(fa){
					data[t][0]=a;
					data[t][1]=b;
					data[t][2]=1;
					t++;
				}
			}

			for (int i = 0; i < n; i++) {
				if(data[i][2]>1){
					int count=0;
					String str="";
					for (int j = 0; j < n; j++) {
						if(arr[j][0]==data[i][0]&&arr[j][1]==data[i][1]){
							str=str+(j+1);
							count++;
						}
					}
					if(count!=n){
						System.out.println(str);
					}else
						System.out.println(0);
					return;
				}
			}
			System.out.println("NoSolution.");
		}
	}
}

算法训练 数的统计

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

问题描述

在一个有限的正整数序列中，有些数会多次重复出现在这个序列中。
如序列：3，1，2，1，5，1，2。其中1就出现3次，2出现2次，3出现1 次，5出现1次。
你的任务是对于给定的正整数序列，从小到大依次输出序列中出现的数及出现的次数。

输入格式

第一行正整数n，表示给定序列中正整数的个数。
第二行是n 个用空格隔开的正整数x，代表给定的序列。

输出格式

若干行，每行两个用一个空格隔开的数，第一个是数列中出现的数，第二个是该数在序列中出现的次数。

样例输入

12
8 2 8 2 2 11 1 1 8 1 13 13

样例输出

1 3
2 3
8 3
11 1
13 2

数据规模和约定

数据：n<=1000；0<x<=1000,000。

代码：

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

public class Main {

	static int[][] data=new int[10000][2];
	public static void main(String[] args) {
		
		for (int i = 0; i <10000; i++) {
			data[i][0]=-1;
			data[i][1]=0;
		}
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int t=0;
			for (int i = 0; i < n; i++) {
				int k=sc.nextInt();
				boolean fa=true;
				for (int j = 0; j < n; j++) {
					if(data[j][0]==k){
						data[j][1]++;
						fa=false;
						break;
					}
				}
				if(fa){
					data[t][0]=k;
					data[t][1]=1;
					t++;
				}
			}
			//排序
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(data[i][0]<data[j][0]){
						int m=data[i][0];
						data[i][0]=data[j][0];
						data[j][0]=m;
						
						int p=data[i][1];
						data[i][1]=data[j][1];
						data[j][1]=p;
					}
				}
			}
			for (int i = 0; i < n; i++) {
				if(data[i][1]!=0)
				System.out.println(data[i][0]+" "+data[i][1]);
			}
		}
	}
}

算法训练 友好数

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

问题描述

有两个整数，如果每个整数的约数和（除了它本身以外）等于对方，我们就称这对数是友好的。例如：
9的约数和有：1+3=4
4的约数和有：1+2=3
所以9和4不是友好的。
220的约数和有：1 2 4 5 10 11 20 22 44 55 110=284
284的约数和有：1 2 4 71 142=220
所以220和284是友好的。
编写程序，判断两个数是否是友好数。

输入格式

一行，两个整数，由空格分隔

输出格式

如果是友好数，输出”yes”，否则输出”no”，注意不包含引号。

样例输入

220 284

样例输出

yes

数据规模和约定

两个整数都小于10000

分别算下就是的，代码：

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

public class Main {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int num1=sc.nextInt();
			int num2=sc.nextInt();
			int n1=0,n2=0;
			for (int i = 1; i < num1; i++) {
				if(num1%i==0)
					n1+=i;
			}
			if(n1!=num2){
				System.out.println("no");
				return;
			}else{
				for (int i = 1; i < num2; i++) {
					if(num2%i==0)
						n2+=i;
				}
				if(n2==num1){
					System.out.println("yes");
				}else{
					System.out.println("no");
				}
			}
		}
	}
}

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

算法训练 寂寞的数

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

问题描述

道德经曰：一生二，二生三，三生万物。
对于任意正整数n，我们定义d(n)的值为为n加上组成n的各个数字的和。例如，d(23)=23+2+3=28, d(1481)=1481+1+4+8+1=1495。
因此，给定了任意一个n作为起点，你可以构造如下一个递增序列：n,d(n),d(d(n)),d(d(d(n)))….例如，从33开始的递增序列为：
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, …
我们把n叫做d(n)的生成元，在上面的数列中，33是39的生成元，39是51的生成元，等等。有一些数字甚至可以有两个生成元，比如101，可以由91和100生成。但也有一些数字没有任何生成元，如42。我们把这样的数字称为寂寞的数字。

输入格式

一行，一个正整数n。

输出格式

按照升序输出小于n的所有寂寞的数字，每行一个。

样例输入

40

样例输出

1
3
5
7
9
20
31

数据规模和约定

n<=10000

1到n每个数都做生成元，代码：

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

public class Main {

	static int[] data=new int[100*100+1];
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=getNum(0);
		while(k!=-1){
			int t=k;
			while(t<n){
				int sum=t;
				while(t>0){
					sum+=t%10;
					t/=10;
				}
				if(sum<=n)
					data[sum]=1;
				t=sum;
			}
			k=getNum(k);
		}
		for (int i = 1; i <= n; i++) {
			if(data[i]==0)
				System.out.println(i);
		}
	}
	private static int getNum(int t) {
		for (int i = t+1; i < data.length; i++) {
			if(data[i]==0)
				return i;
		}
		return -1;
	}
}

算法训练 连续正整数的和

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

问题描述

78这个数可以表示为连续正整数的和，1+2+3，18+19+20+21，25+26+27。
输入一个正整数 n(<=10000)
输出 m 行(n有m种表示法)，每行是两个正整数a，b，表示a+(a+1)+…+b=n。
对于多种表示法，a小的方案先输出。

样例输入

78

样例输出

1 12
18 21
25 27

用数学累加求和的公式，代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		
		for (int i = 1; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				double sum=(double)(j-i+1)*(i+j)/2;
				if(sum==n)
					System.out.println(i+" "+j);
			}
		}
	}
}

算法训练 学做菜

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

问题描述

涛涛立志要做新好青年，他最近在学做菜。由于技术还很生疏，他只会用鸡蛋，西红柿，鸡丁，辣酱这四种原料来做菜，我们给这四种原料标上字母A,B,C,D。
涛涛现在会做的菜有五种：
1、 西红柿炒鸡蛋 原料：AABDD
2、 酸辣鸡丁 原料：ABCD
3、 宫保鸡丁 原料：CCD
4、 水煮西红柿 原料：BBB
5、 怪味蛋 原料：AD
这天早上，开开去早市给涛涛买了一些原料回来。由于事先没有什么计划，涛涛决定，对于现存的原料，每次尽量做菜单上靠前（即编号小）的菜。
现在请你写一个程序，判断一下开开和涛涛中午能吃到哪些菜。

输入格式

共4个整数a,b,c,d。分别表示开开买的A,B,C,D这4种原料的数量。每种原料不会超过30份。

输出格式

输出5行。其中第i行表示涛涛做的第i种菜的数目。

样例输入

3
1
2
4

样例输出

1
0
1
0
1

一个个的做就是了，代码：

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

public class Main {
	static int[] data=new int[4];
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		while(sc.hasNext()){
			int[] data=new int[4];
			int[] arr=new int[5];
			for (int i = 0; i < data.length; i++) {
				data[i]=sc.nextInt();
			}
			//1
			while(data[0]>1&&data[1]>0&&data[3]>1){
				arr[0]++;
				data[0]-=2;
				data[1]-=1;
				data[3]-=2;
			}
			//2
			while(data[0]>0&&data[1]>0&&data[2]>0&&data[3]>0){
				arr[1]++;
				data[0]-=1;
				data[1]-=1;
				data[2]-=1;
				data[3]-=1;
			}
			//3
			while(data[2]>1&&data[3]>0){
				arr[2]++;
				data[2]-=2;
				data[3]-=1;
			}
			//4
			while(data[1]>2){
				arr[3]++;
				data[1]-=3;
			}
			//5
			while(data[0]>0&&data[3]>0){
				arr[4]++;
				data[0]-=1;
				data[3]-=1;
			}
			for (int i = 0; i < arr.length; i++) {
				System.out.println(arr[i]);
			}
		}
	}
}

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

算法训练 Representative Sampling (30_points)

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

【题目描述】
来自ABBYY的小明有一个与“细胞与遗传学研究所”的合作。最近，研究所用一个新的题目考验小明。题目如下。
有由n个细胞组成的一个集合（不一定不同）每个细胞是一个由小写拉丁字母组成的字符串。科学家给小明提出的问题是从给定集合中选出一个大小为k的子集，使得所选子集的代表值最大。
小明做了些研究并得出了一个结论，即一个蛋白质集合的代表制可以用一个方便计算的整数来表示。我们假设当前的集合为{a1, …, ak}，包含了k个用以表示蛋白质的字符串。那么蛋白质集合的代表值可以用如下的式子来表示：

其中f(x, y)表示字符串x和y的最长公共前缀的长度，例如：
f(“abc”, “abd”) = 2 ， f(“ab”, “bcd”) = 0.
因此，蛋白质集合{“abc”, “abd”, “abe”}的代表值等于6，集合{“aaa”, “ba”, “ba”}的代表值等于2。
在发现了这个之后，小明要求赛事参与者写一个程序选出，给定蛋白质的集合中的大小为k的子集中，能获得最大可能代表性值得一个子集。帮助他解决这个问题吧！
【输入格式】
输入数据第一行包含2个正整数n和k（1≤k≤n），由一个空格隔开。接下来的n行每一行都包含对蛋白质的描述。每个蛋白质都是一个仅有不超过500个小写拉丁字母组成的非空字符串。有些字符串可能是相等的。

输出格式

输出一个整数，表示给定蛋白质集合的大小为k的子集的代表值最大可能是多少。

【数据规模】
20%的数据保证：1 ≤ n ≤ 20
50%的数据保证：1 ≤ n ≤ 100
100%的数据保证：1 ≤ n ≤ 2000

【样例输入1】
3 2
aba
bzd
abq
【样例输出1】
2

【样例输入2】
4 3
eee
rrr
ttt
qqq
【样例输出2】
0
【样例输入3】
4 3
aaa
abba
abbc
abbd
【样例输出3】
9

这个题比较有意思，做了不少时间。用的是全排列，穷举，结果只得了10分。都是超时，测试数据太大了。

代码：

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

public class Main {
	
	static int k,max;
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			String ss=sc.nextLine();
			String[] ch=ss.split(" ");
			int n=Integer.parseInt(ch[0]);
			k=Integer.parseInt(ch[1]);
			String[] data=new String[n];
			for (int i = 0; i < data.length; i++) {
				data[i]=sc.nextLine();
			}
			f(data,0);
			System.out.println(max);
		}
	}

	private static void f(String[] data, int w) {
		
		if(k==w){
			getK(data);
		}
		
		for (int j = w; j < data.length; j++) {
			{String t=data[w];data[w]=data[j];data[j]=t;}//试探
			f(data,w+1);
			{String t=data[w];data[w]=data[j];data[j]=t;}//回溯
		}
	}

	private static void getK(String[] data) {
		int sum=0;
		for (int i = 0; i < k; i++) {
			for (int j = i+1; j < k; j++) {
				int count=0;
				for (int t = 0; t < data[i].length()&&t < data[j].length(); t++) {
					if(data[i].charAt(t)!=data[j].charAt(t))
						break;
					count++;
				}
				sum+=count;
			}
		}
		if(sum>max)
			max=sum;
	}
}