A - 棋盘问题
JavaC++ B - Perket
JavaC++ C - 全排列
JavaC++ D - 自然数拆分
JavaC++ E - Prime Ring Problem
JavaC++ F - Red and Black
JavaC++ G - Knight Moves
JavaC++ H - Oil Deposits
C++ I - Lake Counting
JavaC++ J - 二叉树先序遍历
JavaC++ K - 迷宫(一)
Java L - 马走日
JavaC++ M - 八皇后问题
JavaC++ N - 选数
JavaC++ O - 打开灯泡 Switch the Lamp On
C++ 总结 A - 棋盘问题
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Sample Input
2 1#..#4 4...#..#..#..#...-1 -1
21
思路:深度优先遍历,一行一行判断能否放棋子,每一行需要判断每一列能否放能放,能放/不能放也都递归到下一行(这样能包含所有放棋子的情况),注意回溯。
Javaimport java.util.Scanner;public class Main { static int n, k, cnt; static char[][] array; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { n = sc.nextInt(); k = sc.nextInt(); if (n == -1 && k == -1) break; cnt = 0; array = new char[n][n]; used = new boolean[n]; sc.nextLine(); for (int i = 0; i < n; i++) { array[i] = sc.nextLine().toCharArray(); } dfs(0, 0); System.out.println(cnt); } } public static void dfs(int i, int sum) { if (i == n) { if (sum == k) { cnt++; } return; } for (int j = 0; j < n; j++) { if (array[i][j] == '.') continue; if (!used[j]) { used[j] = true; dfs(i+1, sum+1); used[j] = false; } }dfs(i+1, sum); }}
C++#include
你有 N 种配料,每种配料有酸度 S 和苦度 B 。用这些配料做成Perket时,总的酸度为所有配料酸度的乘积,总的苦度是所有配料苦度的和。你至少需要添加一种配料。
为了使口感适中,总的酸度和苦度之差的绝对值应该尽可能小,求这个最小值。
41 72 63 84 9
1
Javaimport java.util.Scanner;public class Main { static int n, k, cnt; static int[][] array; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); array = new int[n][2]; cnt = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { array[i][0] = sc.nextInt(); array[i][1] = sc.nextInt(); } dfs(0, 1, 0, 0); System.out.println(cnt); } public static void dfs(int i, int a, int b, int k) { if (i == n) { if (k > 0) cnt = Math.min(cnt, Math.abs(a - b)); return; } dfs(i+1, a*array[i][0], b + array[i][1], k+1); dfs(i+1, a, b, k); }}
C++#include
思路:n<=10,数据较小,暴力求解,每一个都试试加入和不加入两种情况,取最小值,来源:大佬博客
#include
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。我们假设对于小写字母有’a’< ‘b’< …<‘y’<‘z’,而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入格式
输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到6之间。
输出格式
输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。
abc
abcacbbacbcacabcba
Java参考:洛谷 P1706 全排列问题(Java版)
import java.util.Scanner;public class Main { static int n, k, cnt; static int[][] array; static char[] arr; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); arr = sc.nextLine().toCharArray(); used = new boolean[arr.length]; Arrays.sort(arr); fullSort(new StringBuilder()); } public static void fullSort(StringBuilder res) { if (res.length() == arr.length) { System.out.println(res.toString()); return; } for (int i = 0; i < arr.length; i++) { if (!used[i]) { used[i] = true; res.append(arr[i]); fullSort(res); res.deleteCharAt(res.length()-1); used[i] = false; } } }}
C++#include
对于任意大于 1 的自然数 n,总是可以拆分成若干个小于 n 的自然数之和。
现请你编写程序求出 n 的所有拆分。
5
5=1+1+1+1+15=1+1+1+25=1+1+35=1+2+25=1+45=2+3
思路:通过不断进行分层,来进行求解,每一层的初始位置从上一次分解的位置开始,可以保证所有解都可以求出,另外排除5=5,这种情况
Javaimport java.util.Scanner;public class Main { static int n, k, cnt; static int[] arr; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); arr = new int[n]; k = -1; fullSort(0, 1); } public static void fullSort(int sum, int x) { if (sum > n) return; if (sum == n) { System.out.print(n+"="); for (int i = 0; i < k; i++) { System.out.print(arr[i] + "+"); } System.out.println(arr[k]); return; } for (int i = x; i < n; i++) { k++; arr[k] = i; fullSort(sum+i, i); k--; } }}
C++#include
输入正整数n,把整数1,2…,.排成一个环,使得相邻两个整数之和均为素数。输出时,从整数1开始逆时针排列。同一个环恰好输出一次。n≤16,保证一定有解。
多组数据,读入到EOF结束。
第i组数据输出前加上一行Case i :
相邻两组输出中间加上一个空行。
68
Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2
Java行末无空格
最后一个Case输出后不换行
思路:规定第一个数为1,其余数按照全排列的方法进行即可,判断条件加上相邻两个数为素数的条件,最后输出格式需要注意一下
超时!
package WinterCamp.StringTest;import java.util.Scanner;public class C { static int n, k; static int[] arr; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int flag = 0; while (sc.hasNext()) { n = sc.nextInt(); arr = new int[n+1]; used = new boolean[n+1]; arr[1] = 1; k = 1; if (flag++ > 0) System.out.println(); System.out.println("Case "+flag+":"); fullSort(2); } } public static void fullSort(int x) { if (x == n+1) { if (judge(arr[1]+arr[k])) { for (int i = 1; i < k; i++) System.out.print(arr[i]+" "); System.out.println(arr[k]); } return; } for (int i = 2; i <= n; i++) { if (used[i]) continue; if (judge(arr[k]+i)) { used[i] = true; k++; arr[k] = i; fullSort(x + 1); used[i] = false; k--; } } } public static boolean judge(int x) { if (x == 1) return false; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; }}
C++#include
有一个长方形的房间,覆盖了正方形的磁砖。每块磁砖的颜色,要么是红色,要么是黑色。一名男子站在一块黑色的磁砖上。他可以从一块磁砖移至相邻四块磁砖中的某一块。但是,他不允许在红色磁砖上移动,他只允许在黑色磁砖上移动。
编写一个程序,使得他允许重复上述的移动,判断他所能到达的黑色磁砖的数量。
6 9....#......#..............................#@...#.#..#.11 9.#..........#.#######..#.#.....#..#.#.###.#..#.#..@#.#..#.#####.#..#.......#..#########............11 6..#..#..#....#..#..#....#..#..###..#..#..#@...#..#..#....#..#..#..7 7..#.#....#.#..###.###...@...###.###..#.#....#.#..0 0
4559613
Javaimport java.util.Scanner;public class Main { static int n, k, cnt, a, b, sx, sy; static char[][] arr; static boolean[][] used; static int[] orient = {0, 1, 0, -1, 0}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { a = sc.nextInt(); b = sc.nextInt(); if (a == 0 && b == 0) break; cnt = 1; arr = new char[b+1][a+1]; used = new boolean[b+1][a+1]; for (int i = 1; i <= b; i++) { String s = sc.next(); s = " " + s; if (s.contains("@")) { sx = i; sy = s.indexOf("@"); } arr[i] = s.toCharArray(); } dfs(sx, sy); System.out.println(cnt); } } public static void dfs(int x, int y) { used[x][y] = true; for (int i = 0; i < 4; i++) { int xx = x + orient[i], yy = y + orient[i+1]; if (xx < 1 || yy < 1 || xx > b || yy > a || used[xx][yy] || arr[xx][yy] == '#') continue; if (arr[xx][yy] == '.') { cnt++; dfs(xx, yy); } } }}
C++#include
编写一个程序,计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。骑士一步可以移动到的位置由下图给出。
输入格式
第一行给出骑士的数量n。
在接下来的3n行中,每3行描述了一个骑士。其中,
·第一行一个整数L表示棋盘的大小,整个棋盘大小为L×L;
·第二行和第三行分别包含一对整数(z,g),表示骑士的起始点和终点。假设对于每一个骑士,起始点和终点均合理。
输出格式
对每一个骑士,输出一行一个整数表示需要移动的最小步数。如果起始点和终点相同,则输出0。
380 07 01000 030 50101 11 1
5280
思路:搜索题目,单向bfs搜索超时,所以用双向的,用bfs的原因是求最短路径且数据较大
双向bfs:
单向BFS只从起点一端开始搜索,双向BFS则是从起点和终点两边扩展节点,当节点发生重合时即找到最优解。
实现方法为:维护两个队列,分别保存从起点和终点扩展到的下一层,这样保证了两个队列中的节点处于相同的深度(即:距离起点或者终点深度相同)。则当拓展到时一定发生重合,得到最优解。
Java有bug的代码!
import java.util.*;public class C { static int k, cnt, a, b; static char[][] arr; static boolean[][] used; static int[] orient = {0, 1, 0, -1, 0}; static int[] ori = {1, 2, -1, -2, 1, -2, -1, 2, 1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Queue
#include
参考2:
#include
参考3:一个简单的马走日问题,其中每一个点到达的8个地点都需要记录步数。
#include
某公司负责探测地下油层,每次处理一个大的矩形区域。先创建一个网格,将土地划分为许多方形块,然后用传感设备分别探测每个地块,以确定该地块是否含有石油。一块含有石油的土地叫做pocket。如果两个pocket边相邻或对角相邻,则它们属于同一油层的一部分。你的工作是确定在一个网格有多少不同的油层。
1 1*3 5*@*@***@***@*@*1 8@@****@*5 5 ****@*@@*@*@**@@@@*@@@**@0 0
0122
C++思路:本题目属于连通图题目,从一个点出发将能遍历的全部遍历一遍,有多少个出发点就有多少个联通块
#include
10 12W........WW..WWW.....WWW....WW...WW..........WW..........W....W......W...W.W.....WW.W.W.W.....W..W.W......W...W.......W.
3
Javaimport java.util.Arrays;import java.util.Scanner;public class Main { static int cnt, m, n; static int[] ori = {0, 1, 0, -1, 0, 1, 1, -1, -1, 1}; static char[][] arr; static boolean[][] vis; public static void main(String[] args) { Scanner sc = new Scanner(System.in); m = sc.nextInt(); n = sc.nextInt(); int cnt = 0; arr = new char[m][n]; vis = new boolean[m][n]; for (int i = 0; i < m; i++) { arr[i] = sc.next().toCharArray(); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'W' && !vis[i][j]) { dfs(i, j); cnt++; } } } System.out.println(cnt); } public static void dfs(int x, int y) { vis[x][y] = true; for (int i = 0; i < 9; i++) { int xx = x + ori[i]; int yy = y + ori[i+1]; if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue; if (arr[xx][yy] == 'W' && !vis[xx][yy]) dfs(xx, yy); } }}
C++#include
输入一个整数n(n <= 100000),表示二叉树中节点个数,编号为1~n。约定1号节点为二叉树的根节点。然后输入n行,每行包括两个整数,第i行表示编号为i的节点的左子节点和右子节点的编号。如果某个节点没有左子节点,那么对应输行的第一个整数为0;如果某个节点没有右子节点,那么对应行的第二个整数为0。
先序遍历输出此二叉树每个节点的编号,每行输出一个编号。
先序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、前序遍历、前序周游,可记做根左右。前序遍历首先访问根节点然后遍历左子树,最后遍历右子树。
Javaimport java.util.Scanner;public class Main{ static int l[], r[], res[]; static int i = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); l = new int[n+1]; r = new int[n+1]; res = new int[n+1]; for (int j = 1; j <= n; j++) { l[j] = sc.nextInt(); r[j] = sc.nextInt(); } dfs(1); for (int j = 1; j <= n; j++) { System.out.println(res[j]); } } public static void dfs(int x) { res[++i] = x; if (l[x] > 0) { dfs(l[x]); } if (r[x] > 0) { dfs(r[x]); } }}
C++#include
3 4S**.....***T
yes
Javaimport java.util.Scanner;public class Main{ static int n, m, ex, ey; static char arr[][]; static int[] ori = {0, 1, 0, -1, 0}; static boolean flag; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); arr = new char[n][m]; int x = 0, y = 0; sc.nextLine(); for (int i = 0; i < n; i++) { String s = sc.next(); if (s.contains("S")) { x = i; y = s.indexOf("S"); } if (s.contains("T")) { ex = i; ey = s.indexOf("T"); } arr[i] = s.toCharArray(); } dfs(x, y); if (flag) { System.out.println("yes"); } else { System.out.println("no"); } } public static void dfs(int x, int y) { if (x == ex && y == ey) { flag = true; return; } arr[x][y] = '*'; for (int i = 0; i < 4; i++) { int xx = x + ori[i]; int yy = y + ori[i+1]; if (xx < 0 || yy < 0 || xx >= n || yy >= m || arr[xx][yy] == '*') continue; dfs(xx, yy); } }}
L - 马走日马在中国象棋以日字形规则移动。请编写一段程序,给定n*m大小的棋盘,以及马的初始位置(x,y),要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点。
Java马走日问题(Java版)
C++#include
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 18 19 20 21 22 23 2425 26 27 28 29 30 31 3233 34 35 36 37 38 39 4041 42 43 44 45 46 47 4848 50 51 52 53 54 55 5657 58 59 60 61 62 63 64
260
需要判断对角线abs(i-x)==abs(j-y),以及记录八个棋子的坐标:l[i]、r[i]
Java洛谷 P1219 [USACO1.5]八皇后 Checker Challenge(Java版)
C++#include
4 33 7 12 19
1
Java思路:全排列问题改变,每次从出发点往后选择数据,确保种类不重复,即避免出现结果编号重复
import java.util.Scanner;public class Main { static boolean[] vis; static int[] arr; static int cnt, n, m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); arr = new int[n+1]; vis = new boolean[n+1]; for (int i = 1; i <= n; i++) { arr[i] = sc.nextInt(); } dfs(0, 0, 0); System.out.println(cnt); } public static void dfs(int step, int sum, int s) { if (s == m) { if (judge(sum)) { cnt++; } } if (step > n) return; for (int i = step + 1; i <= n; i++) { if (vis[i]) continue; vis[i] = true; dfs(i, sum + arr[i], s+1); vis[i] = false; } } public static boolean judge(int sum) { if (sum == 1) return false; for (int i = 2; i * i <= sum; i++) { if (sum % i == 0) return false; } return true; }}
C++#include
达达是来自异世界的魔女,她在漫无目的地四处漂流的时候,遇到了善良的少女翰翰,从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障,导致无法启动。
电路板的整体结构是一个R行C列的网格(R,C≤500),如下图所示。
样例输入3 5\/\\////\\样例输出1
思路:最短路径策略,将二维表格离散化,可以到达的点进行连接,构成无向图,将原本达到的边代价设为0,反转90度之后的边代价设为1,找最短路径即可。
C++#include ,greater > que; for(int i=0;i<=tot+10;i++) d[i]=inf; ll s=1; d[s]=0; que.push({d[s],s}); while(!que.empty()){ P p=que.top(); que.pop(); ll u=p.second; //cout<d[u])continue; //vis[u]=1; for(int i=0;i
搜索专题确实用很久时间才算是勉强搞定。在此期间间断的做了一道两道,没有集中时间去练。主要是想学点C++的语法,以及oj题的编写参考ACM大神博客 容艾假 进行学习,衷心感谢并致敬!
加油!
感谢!
努力!