lanqiao

蓝桥杯算法总结

Java进制转换

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 18;
		int x= 2;
		System.out.println(n + "的x进制是：" + Integer.toString(n, x));
		
		String s = "10010";
		System.out.println(s + "的10进制是：" + Integer.parseInt(s, 2));
}

Calendar控件 API

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
// 2013.1
public class t1 {
	public static void main(String[] args) {
		Calendar calendar = Calendar.getInstance();	//获取Calendar实例
		for (int i = 1999; i < 10000; i+=100) {		//从1999到9999年
			calendar.set(Calendar.YEAR, i);			//第i年
			calendar.set(Calendar.MONTH, 11);		//12月
			calendar.set(Calendar.DAY_OF_MONTH,31); //31日
			System.out.println(i + " " + calendar.get(Calendar.DAY_OF_WEEK));//输出第i年12月31日是星期几
			if(calendar.get(Calendar.DAY_OF_WEEK) == 1) {	//第i年12月31日是星期一
				System.out.println(i);
				break;
			}
		}
	}
}

/*Calendar类的使用
// 使用默认时区和语言环境获得一个日历
Calendar cal = Calendar.getInstance();
// 赋值时年月日时分秒常用的6个值，注意月份下标从0开始，所以取月份要+1
System.out.println("年:" + cal.get(Calendar.YEAR));			//年份
System.out.println("月:" + (cal.get(Calendar.MONTH) + 1));  //月份-1
System.out.println("日:" + cal.get(Calendar.DAY_OF_MONTH)); //日
System.out.println("时:" + cal.get(Calendar.HOUR_OF_DAY));  //时 24小时制
System.out.println("分:" + cal.get(Calendar.MINUTE));       //分
System.out.println("秒:" + cal.get(Calendar.SECOND));	   //秒
System.out.println("星期：" + cal.get(Calendar.DAY_OF_WEEK));  //周几（星期天是1，星期六是7）

// 或者6个字段分别进行设置，由于月份下标从0开始赋值月份要-1
cal.set(2018, 1, 15, 23, 59, 59);
System.out.println(cal.getTime());
cal.set(Calendar.YEAR, 2018);
cal.set(Calendar.MONTH, Calendar.FEBRUARY);
cal.set(Calendar.DAY_OF_MONTH, 15);
cal.set(Calendar.HOUR_OF_DAY, 23);
cal.set(Calendar.MINUTE, 59);
cal.set(Calendar.SECOND, 59);
System.out.println(cal.getTime());

//加法，按照指定的时间加
cal.add(Calendar.SECOND, 1);
System.out.println(cal.getTime());

*/

// 2015.2
public class t2 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Calendar calendar = Calendar.getInstance();
		calendar.set(2014, 10, 9);
		calendar.add(Calendar.DATE, 1000);
		System.out.println(calendar.getTime().toLocaleString());
	}
}

递推

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 2013.2  振兴中华 
public class t2 {    //在任何位置往下或往右都是合法的
	//从我做起振
	//我做起振兴
	//做起振兴中
	//起振兴中华
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int ans = f(0,0);
		System.out.println(ans);
	}
	private static int f(int i, int j) {
		if (i == 3 || j == 4)
			return 1;
		return f(i+1,j)+f(i,j+1);
	}
}

//2014.2
//有酒两斗，遇店翻一倍，遇花喝一斗，中途遇到了5个店，10朵花，酒刚好喝完，求花和店有多少种排列顺序
public class t22 {
	static int ans = 0;
	public static void main(String[] args) {
		f(5,10,2);
		System.out.println(ans);
	}
	private static void f(int i, int j, int k) {
		// TODO Auto-generated method stub
		if (i == 0 && j == 0 && k == 0) {
			ans++;
			return;
		}
		if (k <= 0 || i < 0 || j < 0) return;
		if (i != 0) f(i-1, j, k*2);
		if (j != 0) f(i, j-1, k-1);
	}
}


//2014.7 绳圈  100绳 200绳头 两两配对    形成多少个绳圈的概率最大
// 难点主要是递推公式
public class t7 {
	public static void main(String[] args) {
		double f[][] = new double[101][101];
		f[1][1] = 1;
		for (int sheng = 2; sheng <= 100; sheng++) {
			f[sheng][1] = f[sheng - 1][1] * (sheng - 1) * 2 / (2 * sheng - 1);
			for (int quan = 2 ; quan <= sheng ; quan++) {
				f[sheng][quan] = (f[sheng-1][quan] * (sheng - 1) * 2 + f[sheng-1][quan-1])/(2*sheng-1);
			}
		}
		double max = -1;
		int ans = -1;
		for (int i = 0; i <= 100; i++) {
			if (f[100][i] > max) {
				max = f[100][i];
				ans = i;
			}
		}
		System.out.println(ans);	
	}
}


//2014.9 斐波那契数列  求(f(1)+f(2)+...+f(n)) % f(m) % mod
// 使用的简单的方法，难的用数组解 放弃   40分程序
public class t93 {
	static int m,n,mod;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		mod = sc.nextInt();
		sc.close();
		fib();
	}
	private static void fib() {
		// TODO Auto-generated method stub
		long a = 1, b = 1;
		if (m >= n + 2) {
			for (int i = 3; i <= n + 2; i++) {
				long t = a;
				a = b;
				b += t;
			}
			System.out.println((b-1)%mod);
		} else {
			long fibN = 0,fibM = 0; 
			for (int i = 3; i <= n + 2; i++) {
				long t = a;
				a = b;
				b += t;
				if (i == m) fibM = b;
			}
			fibN = b;
			System.out.println((fibN-1) % fibM % mod);
		}
	}
}

BigInteger API使用

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
// 2013.3  梅森素数 
public class t32 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BigInteger a = BigInteger.valueOf(2);
		String b = a.pow(11213).toString();
		String s = b.substring(b.length() - 100);
		System.out.println(s);
	}
}


//2018.3 复数乘法  (a+bi)(a+bi)=(a*a-b*b+(a*b+b*a)i)
public class t3 {
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		BigInteger a = BigInteger.valueOf(2);	//记录第一次的乘数
		BigInteger b = BigInteger.valueOf(3);	
		BigInteger two = BigInteger.valueOf(2);	//记录乘数 2，3i
		BigInteger three = BigInteger.valueOf(3);
		BigInteger aa = null;				    //暂存乘数的实部
		BigInteger bb = null;					//暂存乘数的虚部
		for (int i = 0; i < 123455 ; i++) {		// 123456次
			aa = a.multiply(two).subtract(b.multiply(three));
			bb = a.multiply(three).add(b.multiply(two));
			a = aa;
			b = bb;
		}
		System.setOut(new PrintStream(new File("D:\\out3.txt")));	//控制台无法输出
		System.out.println(aa + (bb.compareTo(BigInteger.ZERO) < 0 ? "":"+") + bb + "i");
	}
}


//g2016.t1 9999的阶乘的二进制表示一共有多少位？
public class t1 {
	public static void main(String[] args) throws FileNotFoundException {
		BigInteger a = BigInteger.ONE;
		BigInteger b = BigInteger.ONE;
		for (int i = 0; i < 9999; i++) {
			a = a.multiply(b);
			b = b.add(BigInteger.ONE);
		}
		String s = new BigInteger(a.toString(), 10).toString(2);   //将十进制数的String转化为二进制数的String
		System.out.println(s.length());
	}
}

模拟

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
// 2013.4
// 颠倒的价牌   思想不难（穷举），代码较多  
public class t4 {
	public static void main(String[] args) {
		ArrayList<Price> a1 = new ArrayList<Price>();   //存储亏200多的所有可能
		ArrayList<Price> a2 = new ArrayList<Price>(); 	//存储赚800多的所有可能
		for (int i = 1000; i < 10000; i++) {
			String s = ""+i;			//3 4 7 不能逆转，跳过所有包含这些数字的
			if (s.contains("3") || s.contains("4") || s.contains("7"))
				continue;
			String reverse = reverse(s);
			int i1 = Integer.parseInt(reverse);			//逆转后的数字
			if (i1 - i < -200 && i1 - i > -300) {		//亏200多的
				a1.add(new Price(i, i1 - i));
			}
			if (i1 - i < 900 && i1 - i > 800)			//赚800多的
				a2.add(new Price(i, i1 - i));
		}
		for (Price p1 : a1) {							//穷举
			for (Price p2 : a2) {
				if (p1.plus + p2.plus == 558) {
					System.out.println(p1.p + " " + p1.plus);
					System.out.println(p2.p + " " + p2.plus);
				}
			}
		}
	}

	private static String reverse(String s) {			  //逆转
		// TODO Auto-generated method stub
		char[] ans = new char[s.length()];
		for (int i = ans.length-1,j=0; i >= 0; i--,j++) { //两个变量的for
			char c = s.charAt(i);
			if (c == '6') ans[j] = '9';
			else if (c == '9') ans[j] = '6';
			else ans[j] = c;
		}
		return new String(ans);
	}
}

class Price{
	int p;	   // 价格
	int plus;  // 差价
	public Price(int p, int plus) {
		super();
		this.p = p;
		this.plus = plus;
	}
}



// 2013.7  错误票据
// 重号和断号		主要是Collections.sort()和sc.nextLine()吃掉换行符
public class t7 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<>();
		int N = sc.nextInt();
		sc.nextLine();
		for (int i = 0; i < N; i++) {
			String line = sc.nextLine();
			String[] split = line.split(" ");
			for (int j = 0; j < split.length; j++) {
				list.add(Integer.parseInt(split[j]));
			}
		}
		
		Collections.sort(list);
		int a = 0,b = 0;
		for (int i = 0; i < list.size(); i++) {
			if (list.get(i) - list.get(i-1) == 2) {
				a = list.get(i) - 1;
			}
			if (list.get(i).equals(list.get(i - 1))) {
				b = list.get(i);
			}
			System.out.println(a + " " + b);
		}
	}
}

//2014.3 神奇算式   四个数组成一个乘法算式，其乘积仍是这四个数组成   暴力法
public class t3 {
	private static int ans = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 1 ; i <= 9 ; i++) {
			for (int j = 0 ; j <= 9 ; j++) {
				if (i != j) {
					for (int k = 0 ; k <= 9 ; k++) {
						if (k!=i && k!=j) {
							for (int l = 0 ; l <= 9 ; l++) {
								if (l!=i && l!=j && l!=k) {
									int src = i*1000+j*100+k*10+l;
									if (j != 0) {
										int r1 = i*(j*100+k*10+l);
										if(check(src,r1)) {
											System.out.printf("%d * (%d * 100 + %d * 10 + %d)",i,j,k,l);
											ans++;
										}
									}
									if (k!=0) {
										int r2 = (i*10+j)*(k*10+l);
										if(check(src,r2)) {
											System.out.printf("(%d * 10 + %d) * (%d * 10 + %d)",i,j,k,l);
											ans++;
										}
									}
									if (l!=0) {
										int r3 = (i*100+j*10+k)*l;
										if(check(src,r3)) {
											System.out.printf("(%d * 100 + %d * 10 + %d) * %d",i,j,k,l);
											ans++;
										}
									}
									
								}
							}
						}
					}
				}
			}
		}
		System.out.println();
		System.out.println(ans);
	}
	private static boolean check(int src, int r1) {
		// TODO Auto-generated method stub
		String s1 = String.valueOf(src);
		String r2 = String.valueOf(r1);
		char[] c1 = s1.toCharArray();
		char[] c2 = r2.toCharArray();
		Arrays.sort(c1);
		Arrays.sort(c2);
		return new String(c1).equals(new String(c2));
	}
}


//2014.4 写日志
public class t4 {
	static class A
	{
		private static int n = 1;

		public static void write(String msg) {
			String filename = "t" + n +".log";
			n = n%3 + 1;		//填空位置
			System.out.println("write to file" + filename + " " + msg);
		}
	}
	public static void main(String[] args) {
		A.write("msg");
		A.write("msg");
		A.write("msg");
		A.write("msg");
		A.write("msg");
		A.write("msg");
		A.write("msg");
		A.write("msg");
	}
}

//2014.8 兰顿蚂蚁
// 输入m行n列的一个0，1数组，遇到0左转，遇到1右转，然后前进一格，求k步后的位置
public class t82 {
	static int g[][];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		g = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				g[i][j] = sc.nextInt();
			}
		}
		int x = sc.nextInt();
		int y = sc.nextInt();
		String s = sc.next();
		int k = sc.nextInt();
		sc.close();
		int d = getD(s);
		
		while (true) {
			if (k == 0) {
				System.out.println(x+" "+y);
				break;
			}
			if (g[x][y] == 0) {
				g[x][y] = 1;
				d = (d-1+4) % 4;
			} else if(g[x][y] == 1) {
				g[x][y] = 0;
				d = (d+1)%4;
			}
			if (d==0) x--;
			if (d==1) y++;
			if (d==2) x++;
			if (d==3) y--;
			k--;
		}
	}
	private static int getD(String s) {
		// TODO Auto-generated method stub
		if (s.equals("U")) return 0;
		if (s.equals("R")) return 1;
		if (s.equals("D")) return 2;
		if (s.equals("L")) return 3;
		return 0;
	}
}


//2016.9
//交换瓶子
//打乱的1-N；两两交换之后需要多少次之后变成顺序
public class t9 {
	static int n;
	static int a[];
	static int ans = 0;
	//处理输入
	//遍历 i : 1-N
	//a[i] = i, 已经到位
	//否则找到i在a中的位置pos（i）和i位交换
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new int[n+1];
		for (int i = 1; i <= n; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();
		
		for (int i = 1; i <= n; i++) {
			if(a[i] == i) continue;
			else {
				swap(pos(i),i);
				ans++;
			}
		}
		System.out.println(ans);
	}
	private static void swap(int i, int j) {
		// TODO Auto-generated method stub
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	private static int pos(int x) {
		// TODO Auto-generated method stub
		for (int i = 1; i <= n; i++) {
			if (a[i] == x)
				return i;
		}
		return -1;
	}
}

//g2015.t1
//胡同里门牌号都是连续的正整数，最小的号码不是从1开始
//如果除去小明家不算，胡同里的其它门牌号加起来，刚好是100！
//并且，小明家的门牌号刚好等于胡同里其它住户的个数！
//求小明家的门牌号
public class t12 {
	public static void main(String[] args) {
		for (int i = 2; i < 100; i++) {   //最小的号码从i开始
			int count = 0;                //共多少个（小明家的门牌号+1）
			int sum = 0;                  //这些号码加起来的总和
			for (int j = i; j < 100; j++) {
				sum += j;
				count++;
				if (sum - count + 1 == 100 && (count-1) >= i && (count-1) <= j) {
					System.out.println(i + " " + j + " "+ (count-1));
				}
			}
		}
	}
}


//g2015.t5
//把字符串不重复不遗漏地切成两段，长度分别是t和N-t，N为总长度
//设切成的两段字符串中，前一段中有A个不相同的正回文子串，后一段中有B个不相同的非正回文子串，则该方案的得分为A*B。
//求A*B的最大值
//定义“正回文子串”为：长度为奇数的回文子串。
public class t5 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String str = sc.next();
		sc.close();
		int max = -1;
		int A,B;
        //穷举所有的分割方式
		for (int i = 1; i < n - 1; i++) {
            //panduan求出所有的正回文子串数
			A = panduan(str.substring(0, i));
            //quanbu求出所有的子串数
			B = quanbu(str.substring(i, n)) - panduan(str.substring(i,n));
			if (max < A * B) {
				max = A * B;
			}
		}
		System.out.println(max);
	}
	//找出不相同的非正回文子串（所有字串）
	private static int quanbu(String s) {
		Set<String> set = new HashSet<String>();
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j <= s.length() - i; j++) {
				String ss = s.substring(j, j + i);
				set.add(ss);
			}
		}
		return set.size();
	}
	//找出正回文子串个数
	private static int panduan(String s) {
		Set<String> set = new HashSet<String>();
		set.clear();
		for (int i = 1; i <= s.length(); i += 2) {
			for (int j = 0; j <= s.length() - i; j++) {
				String ss = s.substring(j, j+i);
				if (huiwen(ss) == true) {
					set.add(ss);
				}
			}
		}
		return set.size();
	}
	//判断回文
	private static boolean huiwen(String s) {
		// TODO Auto-generated method stub
		for (int i = 0; i < s.length() / 2; i++) {
			if (s.charAt(i) == s.charAt(s.length()-1-i)) {
				continue;
			}else {
				return false;
			}
		}
		return true;
	}
}

排序

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
//2013.5 三部排序    负数在左边，0在中间，正数在右边
public class t5 {
	static void sort(int[] x) {
		int p = 0;					//遍历指针
		int left = 0;				//最左边
		int right = x.length - 1;	//最右边
		
		while(p <= right) {
			if (x[p] < 0) {			//小于0时
				int t = x[left];	//交换x[p]和x[left]
				x[left] = x[p];
				x[p] = t;
				left ++;			//修改left指针和p指针
				p ++;
			} else if(x[p] > 0) {	//大于0时
				int t = x[right];	//交换x[right]和x[p]
				x[right] = x[p];
				x[p] = t;
				right --;			//修改right指针
 			}else {
 				p++;
 			}
		}
	}
	
	public static void main(String[] args) {
		int []x = {28,18,0,-2,-5,16,33,21,0,29,-16,25,-3,0};
		sort(x);
		for (int i = 0; i < x.length; i++) {
			System.out.print(x[i]);
		}
	}
}

递归 + dfs

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
// 2013.6
// 前缀表达式   返回的第一个数为求值的结果，第二个数表示它已解析的字符数
public class t6 {
	static int[] evaluate(String x) {
		if (x.length() == 0) 
			return new int[] {0,0};
		char c = x.charAt(0);
		if (c >= '0' && c <= '9')			//这个字符为0-9
			return new int[] {c - '0',1};
		
		int[] v1 = evaluate(x.substring(1));
		int[] v2 = evaluate(x.substring(1+v1[1]));   //填空位置  （v1未解析的位置）
		int v = Integer.MAX_VALUE;
		if (c == '+') v = v1[0] + v2[0];
		if (c == '*') v = v1[0] * v2[0];
		if (c == '-') v = v1[0] - v2[0];
		return new int[] {v,1+v1[1]+v2[1]};
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(evaluate("-+3*5+261")[0]);
	}
}

//2013.9
//剪格子，给定一个矩阵，剪成两个和一样大的部分
public class t9 {
	static int[][] g;			//记录输入矩阵
	static int[][] vis;			//记录是否遍历过
	static int m;				//m行
	static int n;				//n列
    static int total = 0;		//记录总大小
    static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		g = new int[n][m];
		vis = new int[n][m];
		for ( int i = 0 ; i < n ; i++) {
			for (int j = 0; j < m; j++) {
				g[i][j] = sc.nextInt();
				total += g[i][j];	//记录总和
			}
		}
		sc.close();
		dfs(0,0,0,0);
		System.out.println(ans);
	}
	private static void dfs(int i, int j, int steps, int sum) {
		if (i<0 || i==n || j<0 || j==m || vis[i][j] == 1) return;
		if (sum == total/2) {
			ans = Math.min(ans, steps);	// 选择步数最少的作为答案
			return;
		}
		vis[i][j] = 1;
		dfs(i-1,j,steps+1,sum+g[i][j]);	//往四个方向走
		dfs(i+1,j,steps+1,sum+g[i][j]);
		dfs(i,j+1,steps+1,sum+g[i][j]);
		dfs(i,j-1,steps+1,sum+g[i][j]);
		vis[i][j] = 0;					//回溯
	}
}

//2015.7 牌型种数 52张牌（A-K每种4张）取13张，不考虑花色只考虑点数 有多少种取法
public class t72 {
	static int ans = 0;
	static int sum = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		dfs(0);
		System.out.println(ans);
	}
	private static void dfs(int k) {  //k为牌的类型
		// TODO Auto-generated method stub
		if (k > 13 || sum > 13) {
			return;
		}
		if (sum == 13) {
			ans++;
			return;
		}
		for (int i = 0; i <= 4; i++) { //每种类型的牌可以取1-4张
			sum += i;
			dfs(k + 1);
			sum -= i;
		}
	}
}

//2016.5
//从N类人中选择五个人，给定一个数组表示每类能选择的最大人数，问又多少种选法，打印每种选法
public class t5 {
	public static void main(String[] args) {
		int a[] = {4,2,2,1,1,3};
		f(a,0,5,"");
	}
	private static void f(int[] a, int k, int n, String s) {
		if(k == a.length) {
			if(n == 0) System.out.println(s);
			return;
		}
		String s2 = s;
		for (int i = 0; i <= a[k]; i++) {
			f(a,k+1,n-i,s2);
			s2 += (char)(k+'A');
		}
	}
}

// 2017.4
//剪纸，剪成对称的  
//从中间开始剪，关于原点对称，剪的时候原点对称的两个点一起剪
public class t4 {
	static int ans;
	//四个方向
	static int dire[][] = {{-1,0},
						   {1, 0},
						   {0, 1},
						   {0,-1}};
	static int vis[][] = new int[7][7];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		dfs(3,3);
		System.out.println(ans/4);
	}
	private static void dfs(int x, int y) {
		// TODO Auto-generated method stub
		if (x==0 || y==0 || x==6 || y==6) {
			ans++;
			return;
		}
		vis[x][y] = 1;
		vis[6-x][6-y] = 1;
		for (int k = 0; k < 4; k++) {
			int nx = x + dire[k][0];
			int ny = y + dire[k][1];
			
			if(nx < 0 || nx > 6 || ny < 0 || ny > 6) continue;
			if (vis[nx][ny]==0)
				dfs(nx,ny);
		}
		vis[x][y] = 0;
		vis[6-x][6-y] = 0;
	}
}

//g2016.4 用A、B垒一个三角形，A只能在AA或BB的肩上，B只能在AB或BA肩上，求方法数
public class t4 {

	static int m,n,ans=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		sc.close();
		int layer = countL(m+n);
		char a[][] = new char[layer][];
		for (int i = 0; i < layer; i++) {
			a[i] = new char[i+1];
		}
		a[0][0] = 'A';
		dfs(a,0,0,m-1,n,1);
		a[0][0] = 'B';
		dfs(a,0,0,m,n-1,1);
		System.out.println(ans);
	}
	//6个参数： 存放所有A、B的数组、当前递归所在的行号和列号、A和B剩余的个数、层数
	private static void dfs(char[][] a, int cm, int cn, int m, int n, int d) {
		if (m < 0 || n < 0)
			return;
		if (m == 0 && n == 0) {   //m,n恰好都为0，方案数+1
			ans++;
			return;
		}
		if (cn == 0) {    //如果是第一列
			if (a[cm][cn] == 'A') {
				a[cm+1][cn] ='A'; a[cm+1][cn+1] = 'A';
				dfs(a, cm+(cn+1)/d, (cn+1)%d, m-2, n, d+(cn+1)/d);
				a[cm+1][cn] = 'B'; a[cm+1][cn+1] = 'B';
				dfs(a, cm+(cn+1)/d, (cn+1)%d, m, n-2, d+(cn+1)/d);
			} else {
				a[cm+1][cn] = 'B'; a[cm+1][cn+1] = 'A';
				dfs(a, cm+(cn+1)/d, (cn+1)%d, m-1, n-1, d+(cn+1)/d);
				a[cm+1][cn] = 'A'; a[cm+1][cn+1] = 'B';
				dfs(a, cm+(cn+1)/d, (cn+1)%d, m-1, n-1, d+(cn+1)/d);
			}
		} else {         //不是第一列
			if (a[cm][cn] == 'A') {
				if (a[cm+1][cn] == 'A') {
					a[cm+1][cn+1] = 'A';
					dfs(a, cm+(cn+1)/d, (cn+1)%d, m-1, n, d+(cn+1)/d);
				} else {
					a[cm+1][cn+1] = 'B';
					dfs(a, cm+(cn+1)/d, (cn+1)%d, m, n-1, d+(cn+1)/d);
				}
			} else {
				if (a[cm+1][cn] == 'A') {
					a[cm+1][cn+1] = 'B';
					dfs(a, cm+(cn+1)/d, (cn+1)%d, m, n-1, d+(cn+1)/d);
				} else {
					a[cm+1][cn+1] = 'A';
					dfs(a, cm+(cn+1)/d, (cn+1)%d, m-1, n, d+(cn+1)/d);
				}
			}
		}
	}
	private static int countL(int n) {
		// TODO Auto-generated method stub
		int l = 0;
		for (int i = 1; i < n; i++) {
			l += i;
			if (l == n) {
				return i;
			}
		}
		return 0;
	}
}

全排列

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
//2013.8  带分数
// 输入一个1000*1000以内的正整数，将其用带分数表示，其中数字只能是1-9，且不能重复，如：
// 100 = 3 + 69258/714
public class t8 {
	static int ans;
	static int N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		sc.close();
		int[] arr = {1,2,3,4,5,6,7,8,9};
		f(0,arr);
		System.out.println(ans);
	}
	//确认某一个排列的第k位,移交下一层去确认k+1位
    //全排列部分
	private static void f(int k,int[] arr) {
		if (k==9) {
			check(arr);
			return;
		}
		for (int i = k; i < arr.length; i++) {
			int t = arr[i];
			arr[i] = arr[k];
			arr[k] = t;
			
			f(k+1,arr);
			
			t = arr[i];
			arr[i] = arr[k];
			arr[k] = t;
		}
	}
    //主要出错部分，注意toInt，第二个参数是起始位置，第三个参数是长度
	private static boolean check(int[] arr) {
		// TODO Auto-generated method stub
		for (int i = 1; i <= 7; i++) {
			int num1 = toInt(arr,0,i);
			if (num1 >= N)
				continue;
			for (int j = 1; j <= 8-i; j++) {
				int num2 = toInt(arr, i, j);
				int num3 = toInt(arr, i+j, 9-i-j);
				if(num2%num3 == 0 && num1 + num2/num3 == N) {
					ans++;
				}
			}
		}
		return true;
	}
    // int数组转int
	private static int toInt(int[] arr, int pos, int len) {
		// TODO Auto-generated method stub
		int t = 1;
		int ans = 0;
		for (int j = pos+len-1; j >= pos; j--) {
			ans += arr[j]*t;
			t*=10;
		}
		return ans;
	}
}

//2014.6 六角填数
public class t62 {
	static int a[] = {2,4,5,6,7,9,10,11,12};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		f(0);
	}
	private static void f(int k) {
		// TODO Auto-generated method stub
		if (k == 9) {
			boolean f = check();
			if (f) {
				System.out.println(a[3]);
			}
			return;
		}
		for (int i = k; i < 9; i++) {
			int t = a[i];
			a[i] = a[k];
			a[k] = t;
			f(k+1);
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
	private static boolean check() {
		// TODO Auto-generated method stub
		int t1 = 1 + a[0] + a[3] + a[5];
		int t2 = 8 + a[3] + a[6] + 3;
		int t3 = 8 + a[0] + a[1] + a[2];
		int t4 = 1 + a[1] + a[4] + a[8];
		int t5 = a[5] + a[6] + a[7] + a[8];
		int t6 = 3 + a[2] + a[4] + a[7];
		if (t1 == t2 && t2 == t3 && t3 == t4 && t4 == t5 && t5 == t6) {
			return true;
		}
		return false;
	}
}

//2015.3  1-9 九数分三组 使得B=2*A && C=3*A   简单全排列
public class t32 {
	static int a[] = {1,2,3,4,5,6,7,8,9};
	static int ans = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		f(0);
	}
	private static void f(int k) {
		// TODO Auto-generated method stub
		if (k == 9) {
			check();
			return;
		}
		for (int i = k; i < 9; i++) {
			int t = a[i];
			a[i] = a[k];
			a[k] = t;
			f(k+1);
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
	private static void check() {
		// TODO Auto-generated method stub
		int t1 = a[0] * 100 + a[1] * 10 + a[2];
		int t2 = a[3] * 100 + a[4] * 10 + a[5];
		int t3 = a[6] * 100 + a[7] * 10 + a[8];
		if (t2 == t1 * 2 && t3 == t1 * 3) {
			ans++;
			System.out.print(t1+ " ");
		}		
	}
}


//2016.3 搭积木 0-9搭一个四层的积木，上面的数比下面两个小 
public class t32 {
	static int a[] = {0,1,2,3,4,5,6,7,8,9};
	static int ans;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		f(0);
		System.out.println(ans);
	}
	private static void f(int k) {
		// TODO Auto-generated method stub
		if (k == 10) {
			check();
			return;
		}
		for (int i = k; i < a.length; i++) {
			int t = a[i];
			a[i] = a[k];
			a[k] = t;
			f(k+1);
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
	private static void check() {
		// TODO Auto-generated method stub
		if (a[0] < a[1] && a[0] < a[2] &&
				a[1] < a[3] && a[1] < a[4] &&
				a[2] < a[4] && a[2] < a[5] &&
				a[3] < a[6] && a[3] < a[7] &&
				a[4] < a[7] && a[4] < a[8] &&
				a[5] < a[9] && a[5] < a[8]) {
			ans++;
		}
	}
}

/*寒假作业 数字1-13选12个数使得 
a[0] + a[1] == a[2] &&
a[3] - a[4] == a[5] &&
a[6] * a[7] == a[8] &&
a[9] / a[10] == a[11] &&
a[9] % a[10] == 0
有多少种选法
在进入下一层之前判断，   记得如果不满足  交换回来
*/
public class t62 {
	static int ans = 0;
	static int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		f(0);
		System.out.println(ans);
	}
	private static void f(int k) {
		// TODO Auto-generated method stub
		if (k == 13) {
			check();
			return;
		}
		for (int i = k; i < 13; i++) {
			int t = a[i];
			a[i] = a[k];
			a[k] = t;
			if (k == 2 && a[0] + a[1] != a[2] ||
					k == 5 && a[3] - a[4] != a[5] ||
					k == 8 && a[6] * a[7] != a[8] ||
					k == 11 && a[9] % a[10] != 0) {
				t = a[i];
				a[i] = a[k];
				a[k] = t;
				continue;
			}
			f(k+1);
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
	private static void check() {
		// TODO Auto-generated method stub
		if (a[0] + a[1] == a[2] &&
				a[3] - a[4] == a[5] &&
				a[6] * a[7] == a[8] &&
				a[9] / a[10] == a[11] &&
				a[9] % a[10] == 0) {
			ans++;
		}
	}
}


//带有重复元素的全排列（抓取法）
public class t72 {
	static int ans= 0;
	static boolean[] vis = new boolean[12];
	static int a[] = {0,0,0,0,0,0,0,1,1,1,1,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] path = new int[12];
		f(0,path);
		System.out.println(ans);
	}
	
	private static void f(int k, int[] path) {
		// TODO Auto-generated method stub
		if (k == 12) {
			ans++;
			for (int i = 0; i < a.length; i++) {
				System.out.print(path[i]);
			}
			System.out.println();
		}
		for (int i = 0; i < 12; i++) {
			if (i>0 && a[i] == a[i-1] && !vis[i-1]) continue;
			if (!vis[i]) {
				vis[i] = true;
				path[k] = a[i];
				f(k+1, path);
				vis[i] = false;
			}
		}
	}
}

//2016.7 剪邮票  带重复元素的全排列+dfs判断连通块
public class t7 {
	static boolean vis[] = new boolean[12];
	static int a[] = {0,0,0,0,0,0,0,1,1,1,1,1}; // 它的每个排列代表着12选5的一个方案
	static int ans = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int path[] = new int[12];
		f(0,path);
		System.out.println(ans);
	}
	//生成不带重复元素的全排列
	private static void f(int k, int path[]) {
		// TODO Auto-generated method stub
		if(k == 12) {
			if(check(path)) {
				ans++;
			}
		}
		for (int i = 0; i < 12; i++) {
			//现在准备抓取的元素和上一个元素相同，但上一个元素还没有被使用 就continue
			if (i > 0 && a[i] == a[i - 1] && !vis[i - 1]) continue;
			if(!vis[i]) {	//没有被用过的元素可以抓入到path中
				vis[i] = true; //标记为以访问
				path[k] = a[i]; //填入到a[]中
				f(k+1, path);
				vis[i] = false; //回溯
			}
		}
	}
	private static boolean check(int path[]) {
		// TODO Auto-generated method stub
		int cnt = 0;   //连通块的数目
		int g[][] = new int[3][4];
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 4; j++) {
				// 把选中的五个格子标记为1
				if (path[i * 4 + j] == 1)
					g[i][j] = 1;
				else
					g[i][j] = 0;
			}
		}
		// dfs连通性检测
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 4; j++) {
				if (g[i][j] == 1) {
					dfs(g,i,j);
					cnt++;
				}
			}
		}
		return cnt == 1;
	}
	private static void dfs(int[][] g, int i, int j) {
		// TODO Auto-generated method stub
		g[i][j] = 0;
		if (i-1>=0 && g[i-1][j] == 1) dfs(g,i-1,j);
		if (i+1<=2 && g[i+1][j] == 1) dfs(g,i+1,j);
		if (j-1>=0 && g[i][j-1] == 1) dfs(g,i,j-1);
		if (j+1<=3 && g[i][j+1] == 1) dfs(g,i,j+1);
	}
}

//g2016.2
public class t2 {
	public static ArrayList<char[]> arrayList=new ArrayList<>();
	public static long []numbers=new long[10];
	public static Set<String>set=new HashSet<>();
	public static void main(String[] args) {
		char[]s={'0','1','2','3','4','5','6','7','8','9'};
		permutaion(s, 0, 9);			//获取全排列，结果存到arrayList中
		for(int i=0;i<arrayList.size();i++){
			dfs(0, arrayList.get(i),0);
		}
		Iterator<String> iterator=set.iterator();
		while(iterator.hasNext()){
			System.out.println(iterator.next());
		}
		System.out.println("总共有："+set.size());
	}
	//三个参数： 当前位置，当前字符串，有几个数
	public static void dfs(int current_location,char []current_s,int num){
		if(current_location==10){                       ///位置0-9已经排列完了
		    long []current_numbers=new long[num];
		    current_numbers=Arrays.copyOf(numbers, num);
		    Arrays.sort(current_numbers);
		    String temp_string="";
		    for(long i:current_numbers){
		    	String temp=""+i;
		    	temp_string=temp_string+"  "+temp;     ///使用空格将其分割开来
		    }
		    set.add(temp_string);
		    return;
		}
		if(current_s[current_location]=='0'){           ///如果是零，直接跳过
			numbers[num]=0;
			dfs(current_location+1, current_s,num+1);
		}else{
			long  sum=0;                               ///使用long防止溢出
			for(int i=current_location;i<current_s.length;i++){
				sum=sum*10+(int)(current_s[i]-'0');
				double temp_sqrt=Math.sqrt(sum);
				if(temp_sqrt==(int)temp_sqrt){
					numbers[num]=(long)sum;
					dfs(i+1, current_s,num+1);
				}
			}
		}
	}
	///实现全排列
	public static void permutaion(char[]s,int from,int to){
		if(from==to){
			char []temp=Arrays.copyOf(s, s.length);
			arrayList.add(temp);
			return;
		}
		for(int i=from;i<=to;i++){
			char temp=s[i];
			s[i]=s[from];
			s[from]=temp;
			permutaion(s, from+1, to);
			temp=s[i];
			s[i]=s[from];
			s[from]=temp;
		}
	}
}


//g2015.2 四阶幻方
// 把1-16填入4*4的方格中，使得行、列以及两个对角线的和都相等，左上角固定为1，有多少种方案
//全排列、剪枝
public class t2 {
	static int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
	static int ans = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		f(1);
		System.out.println(ans);
	}
	private static void f(int k) {
		// TODO Auto-generated method stub
		if (k == 16) {
			check();
			return;
		}
		for (int i = k; i < 16; i++) {
			int temp = a[i];
			a[i] = a[k];
			a[k] = temp;
			if (k==3 && a[0]+a[1]+a[2]+a[3]!=34				  //剪枝
				|| k==7 && a[4]+a[5]+a[6]+a[7]!=34
				|| k==11 && a[8]+a[9]+a[10]+a[11]!=34
				|| k==15 && a[12]+a[13]+a[14]+a[15]!=34
				|| k==15 && a[0] + a[5] + a[10] + a[15] != 34
				|| k==12 && a[3] + a[6] + a[9] + a[12] != 34
				|| k==12 && a[0] + a[4] + a[8] + a[12] != 34
				|| k==13 && a[1] + a[5] + a[9] + a[13] != 34
				|| k==14 && a[2] + a[6] + a[10] + a[14] != 34
				|| k==15 && a[3] + a[7] + a[11] + a[15] != 34) {
				temp = a[i];
				a[i] = a[k];
				a[k] = temp;
				continue;
			}
			f(k+1);
			temp = a[i];
			a[i] = a[k];
			a[k] = temp;
		}
	}
	private static void check() {
		// TODO Auto-generated method stub
		if (a[0] == 1 
			&& a[0] + a[1] + a[2] + a[3]==34
			&& a[4] + a[5] + a[6] + a[7]==34
			&& a[8] + a[9] + a[10] + a[11]==34
			&& a[12] + a[13] + a[14] + a[15]==34
			&& a[0] + a[5] + a[10] + a[15] == 34
			&& a[3] + a[6] + a[9] + a[12] == 34
			&& a[0] + a[4] + a[8] + a[12] == 34
			&& a[1] + a[5] + a[9] + a[13] == 34
			&& a[2] + a[6] + a[10] + a[14] == 34
			&& a[3] + a[7] + a[11] + a[15] == 34)
			ans++;
	}
}

//g2016.t2
//把0~9这10个数字，分成多个组，每个组恰好是一个平方数，不计较顺序有多少种分法
//全排列+dfs+set去重
public class t2 {
	public static ArrayList<char[]> arrayList=new ArrayList<>();
	public static long []numbers=new long[10];
	public static Set<String>set=new HashSet<>();
	public static void main(String[] args) {
		char[]s={'0','1','2','3','4','5','6','7','8','9'};
		permutaion(s, 0, 9);			//获取全排列，结果存到arrayList中
		for(int i=0;i<arrayList.size();i++){
			dfs(0, arrayList.get(i),0);
		}
		//Iterator<String> iterator=set.iterator();
		//while(iterator.hasNext()){
		//	System.out.println(iterator.next());
		//}
		//System.out.println("总共有："+set.size());
		System.out.println(set.size());
	}
	//三个参数： 当前位置，字符数组，有几个数
	public static void dfs(int current_location,char []current_s,int num){
		if(current_location==10){                       //位置0-9已经排列完了
		    long [] current_numbers=new long[num];	    //存储所有的平方数	
		    current_numbers=Arrays.copyOf(numbers, num);//保存到current_numbers
		    Arrays.sort(current_numbers);               //按大小排序
		    String temp_string="";
		    for(long i:current_numbers){                //将这些数拼接成字符串
		    	String temp=""+i;
		    	temp_string=temp_string+"  "+temp;      //使用空格将其分割开来
		    }
		    set.add(temp_string);                       //添加到set
		    return;
		}
		if(current_s[current_location]=='0'){           //如果是零，直接跳过
			numbers[num]=0;
			dfs(current_location+1, current_s,num+1);
		}else{
			long sum=0;                                 //使用long防止溢出
            //遍历所有切割方式
			for(int i=current_location;i<current_s.length;i++){
				sum=sum*10+(int)(current_s[i]-'0');  //sum为当前字符组成的数字
				double temp_sqrt=Math.sqrt(sum);
				if(temp_sqrt==(int)temp_sqrt){       //判断sum开方后是否为整数
					numbers[num]=(long)sum;			 //若为整数，存起来
					dfs(i+1, current_s,num+1);       //继续遍历
				}
			}
		}
	}
	///实现全排列
	public static void permutaion(char[]s,int from,int to){
		if(from==to){
			char []temp=Arrays.copyOf(s, s.length);
			arrayList.add(temp);
			return;
		}
		for(int i=from;i<=to;i++){
			char temp=s[i];
			s[i]=s[from];
			s[from]=temp;
			permutaion(s, from+1, to);
			temp=s[i];
			s[i]=s[from];
			s[from]=temp;
		}
	}
}

博弈问题

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//2016.8 首先输入三个数表示每次可以抓取的数量，然后输入五个数，表示总球数，分别输出五个答案。
public class t8 {
	static int n[] = new int[3];
	static char cache[][][] = new char[1000][2][2];  //存储已经算过的结果
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n[0] = sc.nextInt();
		n[1] = sc.nextInt();
		n[2] = sc.nextInt();
		Arrays.sort(n);
		for (int i = 0; i < 5; i++) {
			int num = sc.nextInt();
			char res = f(num,0,0);
			System.out.print(res+" ");
		}
		System.out.println();
	}
	private static char f(int num, int me, int you) {
		// TODO Auto-generated method stub
		//出口，不够取的情况下返回
		if (num < n[0]) {
			if ((me&1) == 1 && (you&1) == 0) return '+';
			else if ((me&1) == 0 && (you&1) == 1) return '-';
			else return '0';
		}	
		if(cache[num][me][you] != '\0') {
			return cache[num][me][you];
		}
		boolean ping = false;
		for (int i = 0; i < 3; i++) {
			if (num >= n[i]) {
				char res = f(num-n[i],you,(n[i]%2==0 ? me : 1-me)); // 传递me和you的奇偶性
				if(res == '-') {
					cache[num][me][you] = '+';
					return '+';
				}
				if (res == '0') {
					ping = true;
				}
			}
		}
		// 若能走到这行，说明不存在对手输的情况
		if (ping) {
			cache[num][me][you] = '0';
			return '0';
		} else {
			cache[num][me][you] = '-';
			return '-';
		}
	}
}

//g2017.4
//1. 轮到某人填的时候，只能在某个空格中填入L或O
//2. 谁先让字母组成了“LOL”的字样，谁获胜。
//3. 如果所有格子都填满了，仍无法组成LOL，则平局。
//最优方案：能赢绝对不平，能平绝对不输
public class tb4 {
	static Map<String,Integer> map = new HashMap<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		for (int i = 0; i < n; i++) {
			char[] ch = sc.nextLine().toCharArray();
			System.out.println(f(ch));
		}
		sc.close();
	}
	private static int f(char[] ch) {
		String s = new String(ch);
		if (map.containsKey(s)) {
			return map.get(s);
		}
		if (s.contains("LOL")) {  //当你拿到有LOL的局面,说明你已经输了,你还没填就有了
			map.put(s, -1);
			return -1;
		}  
		if (s.contains("*") == false) {  //没有的填了,但没有LOL出现说明你打平了
			map.put(s, 0);
			return 0;
		} 
		int ping  = 0;
		for (int i = 0; i < ch.length; i++) {
			if (ch[i] == '*') {
				try {
					ch[i] = 'L';
					if (f(ch) == -1) {
						map.put(s, 1);
						return 1;
					}
					else if (f(ch) == 0)
						ping = 1;
					ch[i] = 'O';
					if (f(ch) == -1) {
						map.put(s, 1);
						return 1;
					}
					else if (f(ch) == 0)
						ping = 1;
				} finally {
					ch[i] = '*';
				}
			}
		}
		if (ping == 1)
			return 0;
		return -1;
	}
}

bfs

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
//洛谷 p1443
//给定棋盘大小和马的初始位置，输出马到棋盘上所有点的最小步数
public class t1443 {
	static int m,n,x,y;		//棋盘大小和初始位置
	static int dx[] = {1,1,-1,-1,-2,-2,2,2}; //移动方向
	static int dy[] = {-2,2,-2,2,1,-1,1,-1};
	static boolean vis[][];	//是否遍历过
	static int ans[][];		//输出
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		x = sc.nextInt();
		y = sc.nextInt();
		vis = new boolean[n][m];
		ans = new int[n][m];
		sc.close();
		Point p = new Point(x-1, y-1);
		Queue<Point> q = new LinkedList<Point>();
		Queue<Integer> s = new LinkedList<>();
		q.offer(p);
		s.offer(0);
		ans[x-1][y-1] = 0;
        // bfs
		while (!q.isEmpty()) {
			Point po = q.peek();
			vis[po.x][po.y] = true;
			for (int i = 0; i < 8; i++) {		//8个方向
				int nx = po.x + dx[i];
				int ny = po.y + dy[i];
				if (nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny]) {
					q.offer(new Point(nx, ny));
					s.offer(s.peek()+1);
					ans[nx][ny] = s.peek() + 1;
				}
			}
			q.poll();
			s.poll();
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (vis[i][j] == false) {
					System.out.printf("%-5d", -1);
				} else {
					System.out.printf("%-5d", ans[i][j]);
				}
			}
			System.out.println();
		}
		
	}
}
class Point{
	int x,y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}


//g2015.t4
//从A开始走，每次只能走不同于当前格子符号的相邻格子，求到B的最短长度
public class t4 {
	static int n;				   //方阵的大小
	static String[] m;             //存储方阵字符串
	static int dx[] = {1,-1,0,0};  //四个方向
	static int dy[] = {0,0,1,-1};
	static boolean vis[][];        //记录是否遍历
	static char[][] map;		   //存储方阵char数组
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.nextLine();
		m = new String[n];
		vis = new boolean[n][n];
		map = new char[n][n];
		for (int i = 0; i < n; i++) {
			m[i] = sc.nextLine();          //逐行读取输入方阵
			char[] cs = m[i].toCharArray();//变成CharArray
			for (int j = 0,k = 0; j < cs.length; j+=2,k+=1) {
				map[i][k] = cs[j];         //存储到map
			}
		}
		sc.close();
        //bfs模板
		Queue<Point> q = new LinkedList<Point>(); 
		Queue<Integer> s = new LinkedList<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 'A') {
					q.offer(new Point(i, j));
					s.offer(0);
				}
			}
		}
		while(!q.isEmpty()) {
			Point p = q.peek();
			vis[p.x][p.y] = true;
			if (map[p.x][p.y] == 'B') {
				System.out.println(s.peek());
				return;
			}
			for (int i = 0; i < 4; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n 
						&& map[nx][ny]!= map[p.x][p.y] && !vis[nx][ny]) {
					q.offer(new Point(nx, ny));
					s.offer(s.peek()+1);
				}
			}
			q.poll();
			s.poll();
		}
		
	}
}
class Point{
	int x,y;

	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

//g2019.t8
//迷宫可以看成是一个由 n × n 个方阵组成的方阵, 朋友们把迷宫的起点设置在了第 3 行第 3 列，终点设置在了第 n-2 行第 n-2 列。
// 小明在时刻 0 出发，每单位时间可以向当前位置的上、下、左、右移动单位 1 的距离，也可以停留在原地不动。
//初始时占5×5的区域，他会在时刻 k 变成一个胖子，只占用3×3的区域，他会在时刻 2k 变成一个正常人，只占用 1 × 1 的区域。
//小明最少多长时间能走到迷宫的终点
public class t8 {
	static int n,k;
	static char m[][];
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static boolean vis[][];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		sc.nextLine();
		m = new char[n][n];
		vis = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			m[i] = sc.nextLine().toCharArray();
		}
		sc.close();
		Queue<Point> q = new LinkedList<Point>();
		Queue<Integer> s = new LinkedList<>();
		q.offer(new Point(2, 2));
		vis[2][2] = true;
		s.offer(0);
		while(!q.isEmpty()) {
			int t = s.peek();
			int x = q.peek().x;
			int y = q.peek().y;
			vis[x][y] = true;
			if (x == n - 3 && y == n - 3) {
				System.out.println(s.peek());
				return;
			}
            //将原地不动的直接加进去
			q.offer(new Point(x, y));
			s.offer(s.peek()+1);
			for (int i = 0; i < 4; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];
				if (t < k) {
					if (xx>=2 && xx < n-2 && yy>=2 && yy < n-2 && !vis[xx][yy] && check(xx,yy,2)) {
						q.offer(new Point(xx, yy));
						s.offer(s.peek()+1);
					}
				} else if(t < 2 * k) {
					if (xx>=1 && xx < n-1 && yy>=1 && yy < n-1 && !vis[xx][yy] && check(xx,yy,1)) {
						q.offer(new Point(xx, yy));
						s.offer(s.peek()+1);
					}
				} else {
					if (xx>=0 && xx < n && yy>=0 && yy < n && !vis[xx][yy] && check(xx,yy,0)) {
						q.offer(new Point(xx, yy));
						s.offer(s.peek()+1);
					}
				}
			}
			q.poll();
			s.poll();
		}
		
	}
	private static boolean check(int xx, int yy, int i) {
		// TODO Auto-generated method stub
		for (int j = xx - i; j <= xx + i; j++) {
			for (int k = yy - i; k <= yy + i; k++) {
				if (m[j][k] == '*')
					return false;
			}
		}
		return true;
	}
}
class Point{
	int x,y;

	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

动态规划

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
// 洛谷p1048  01背包问题  模板
// 采药  输入背包大小，和物品数量、以及每个物品的重量和价值，求最大收益
public class p1048 {
	static int m,t,c[],v[],dp[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		m = sc.nextInt();
		c = new int[m];
		v = new int[m];
		dp = new int[1005];
		for (int i = 0; i < m; i++) {
			c[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		sc.close();
		for (int i = 0; i < m; i++) {
			for (int j = t; j >= c[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j-c[i]]+v[i]);
			}
		}
		System.out.println(dp[t]);
	}
}

//洛谷t1164 01背包  求有多少种方法能把钱刚好花完  类似上楼梯
//dp[j] += dp[j-v[i]];   类似递推
public class t1164 {
	static int N,M;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int v[] = new int[N];
		int dp[] = new int[M+1];
		dp[0] = 1;
		for (int i = 0; i < N; i++) {
			v[i] = sc.nextInt();
		}
		sc.close();
		for (int i = 0; i < N; i++) {
			for (int j = M; j >= v[i] ; j--) {
				dp[j] += dp[j-v[i]];
			}
		}
		System.out.println(dp[M]);
	}
}

//洛谷t1510 精卫填海   01背包  求最小值
//输入缺少的体积，石头的数量，剩余的体力，以及每个石头的体积和消耗的体力，求最多剩多少体力
//思路：将体力看作钱数，石头看作物品，首先求花最少的钱能买到多少物品，再遍历看最少花多少能达到目标
public class p1501 {
	static int v,n,c,va[],w[],dp[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		v = sc.nextInt();
		n = sc.nextInt();
		c = sc.nextInt();
		va = new int[n]; //体积 == 价值
		w = new int[n];	 //体力 == 重量
		dp = new int[c+1];
		for (int i = 0; i < n; i++) {
			va[i] = sc.nextInt();
			w[i] = sc.nextInt();
		}
		sc.close();
		for (int i = 0; i < n; i++) {
			for (int j = c; j >= w[i] ; j--) {
				dp[j] = Math.max(dp[j], dp[j-w[i]] + va[i]);
			}
		}
		for (int i = 0; i <= c; i++) {
			if (dp[i] >= v) {
				System.out.println(c - i);
				return;
			}
		}
		System.out.println("Impossible");
	}
}

//洛谷t1616 疯狂的采药  完全背包  模板
//给定背包大小，药品种类和每种药品的重量和价值，求可采的最大价值
public class t1616 {
	static int n,m,dp[],w[],v[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();	//背包大小
		n = sc.nextInt();	//药品种类
		w = new int[n];
		v = new int[n];
		dp = new int[m+1];
		for (int i = 0; i < n; i++) {	//每种药品的重量和价值
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		sc.close();
		for (int i = 0; i < n; i++) {
			for (int j = w[i]; j <= m; j++) {	//与01背包反过来
				dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
			}
		}
		System.out.println(dp[m]);
	}
}

//最长上升子序列
public class LongestIncreasingSubString {
	static int a[],dp[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		a = new int[n];
		dp = new int[n+1];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();	//输入
			dp[i] = 1;				//默认最长为1（自身）
		}
		sc.close();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i])
					dp[i] = Math.max(dp[i], dp[j]+1);//遍历比当前数字小的，取他们+1的最大值
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			ans = Math.max(ans, dp[i]);// 答案不是dp[n]，而是1-n最大的值
		}
		System.out.println(ans);
	}
}

//最长公共子序列
public class LCS {
	static String a,b;
	static int dp[][];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		a = sc.nextLine();
		b = sc.nextLine();
		sc.close();
		dp = new int[a.length()+1][b.length()+1];
		char[] csa = ("0"+a).toCharArray();
		char[] csb = ("0"+b).toCharArray();
		
		for (int i = 1; i < csa.length; i++) {
			for (int j = 1; j < csb.length; j++) {
				if (csa[i] == csb[j]) {
					dp[i][j] = dp[i-1][j-1] + 1;
				} else {
					dp[i][j] = 0;
				}
			}
		}
		int max = -1;
		for (int i = 0; i < csa.length; i++) {
			for (int j = 0; j < csb.length; j++) {
				if (dp[i][j] > max)
					max = dp[i][j];
			}
		}
		System.out.println(max);
	}
}

//最长上升公共子序列
public class LCIS {
	static String a,b;
	static int dp[][],ans;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		a = sc.nextLine();
		b = sc.nextLine();
		sc.close();
		dp = new int[a.length()+1][b.length()+1];
		char[] csa = ("0"+a).toCharArray();
		char[] csb = ("0"+b).toCharArray();
		for (int i = 1; i < csa.length; i++) {
			for (int j = 1; j < csb.length; j++) {
				if (csa[i] == csb[j]) {
					if (i == 1 || j == 1)
						dp[i][j] = 1;
					else {
						if (csa[i]>csa[i-1])
							dp[i][j] = dp[i-1][j-1] + 1;
						else
							dp[i][j] = 0;
					}
				} else {
					dp[i][j] = 0;
				}
				if (dp[i][j] > ans) {
					ans = dp[i][j];
				}
			}
		}
		System.out.println(ans);
	}
}


//g2017.t5
//网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。
//小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？
// 分组dp
public class t5 {
	static int N, K, ans = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();       //N个用户
		K = sc.nextInt();		//分差K
		int val[] = new int[100001];
		for (int i = 0; i < N; i++) {
			val[sc.nextInt()]++; //将每个分数的人数放val[]中
		}
		sc.close();
		//如果K为0，则答案为不重复的数字的个数
		if (K == 0) {
			for (int i = 0; i < 100001; i++) {
				if (val[i] != 0) ans++;
			}
		} else {
			int agroup[] = new int[100001];
			int dp[] = new int[100001];
			//一共有k个组，循环每组，找出能过匹配的最大的人数
			for (int i = 0; i < K; i++) {
				int len = 1;
				for (int j = i; j < 100001; j += K) {
					agroup[len++] = val[j];//当前组的第len个值为val[j]
				}
				dp[0] = 0; dp[1] = agroup[1];
				for (int j = 2; j < len; j++) {
					dp[j] = Math.max(dp[j-1], dp[j-2]+agroup[j]);
				}
				ans += dp[len-1];
			}
		}
		System.out.println(ans);
	}
}

并查集

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
// g2018.t4 版本分支
// 除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。
//输入
//第一行包含两个整数N和Q，代表版本总数和查询总数。  
//以下N-1行，每行包含2个整数u和v，代表版本u是版本v的直接父版本。  
//再之后Q行，每行包含2个整数x和y，代表询问版本x是不是版本y的祖先版本。输出“YES” or “NO”
public class t4 {
	static int f[] = new int[100005];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();	//n为总版本数
		int q = sc.nextInt();	//查询数
		for (int i = 1; i < f.length; i++) {
			f[i] = i;			//初始化把所有版本的父版本设为自己
		}
		for (int i = 1; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			f[y] = x;			//将y的父版本设为x
		}
		for (int i = 0; i < q; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			boolean flag = false;
			while(f[y] != y) {		//遍历y的父节点
				if (f[y] == x) {	//若等于x，输出YES
					flag = true;
					break;
				}
				y = f[y];			//将y的父节点赋值给y
			}
			
			if (flag || x==y) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
		sc.close();
	}
}
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一个辣鸡小破站