选择题忘光了
编程题
1.喝咖啡能提高改bug的效率。n表示bug数，a表示改bug效率的提升倍数，x表示咖啡的杯数。一杯咖啡只能在一个小时内有效，求最短能用多少时间改bug。
输入：
n=8
a=2
x=2
60
60
60
60
60
60
60
60
输出：240
输入：
n=4
a=3
x=3
333
77
100
13
输出：175
先做的第三题，最后没时间了，A了45
2.输入n和t，n是食物的种类，t是总价钱。接着是n行，每行三个数，分别是价钱，满意度，数量，问满意度最大是多少？
背包？又见背包？怎么每次笔试都有背包？A了11。
3.一个字符串方块，再给一个字符串数组，求字符串里面的字符串是否在方块里面，可以上下左右搜寻，跟贪吃蛇似的。
AC，dfs来做，要求按照字典序返回。
import java.lang.reflect.Array;
import java.util.*;
public class Main{
public static void sortDic(String[] arr){
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if(arr[i].compareTo(arr[j]) > 0){
swap(arr, i, j);
}
}
}
}
public static void swap(String[] arr, int i, int j){
String t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
char[][] map = new char[n][255];
int count = 0;
for (int i = 0; i < n; i++) {
String str = in.next();
char[] ch = str.toCharArray();
for (int j = 0; j < ch.length; j++) {
map[i][j] = ch[j];
}
}
int m = in.nextInt();
String[] s = new String[m];
for (int i = 0; i < m; i++) {
s[i] = in.next();
}
sortDic(s);
for (int i = 0; i < m; i++) {
if(judge(map,s[i])){
System.out.println(s[i]);
}
}
}
public static boolean judge(char[][] map, String str){
char[] w = str.toCharArray();
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
if(dfs(map,w,i,j,0)) return true;
}
}
return false;
}
public static boolean dfs(char[][] map,char[] ch, int i, int j, int pos){
if(pos == ch.length - 1) return true;
if(i < 0|| i >= map.length || j < 0 || j >= map[0].length||map[i][j] != ch[pos]) return false;
char tmp = map[i][j];
map[i][j] = '0';
boolean res = dfs(map, ch ,i+1 , j,pos+1) ||
dfs(map, ch ,i-1 , j,pos+1) ||
dfs(map, ch , i , j+1,pos+1) ||
dfs(map, ch , i , j-1,pos+1);
map[i][j] = tmp;
return res;
}
}
/*
5
uvwxy
g
gobi
aos
tds
2
good
dos
*/
全部评论
(6) 回帖