深度优先

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

0%

skiing

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

难度:5

描述

Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

输入

第一行表示有几组测试数据,输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
后面是下一组数据;

输出

输出最长区域的长度。

样例输入

1
2
3
4
5
6
7
8
1
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

1
25

第一次使用bfs居然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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
*
*/
package 动态规划;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
* @作者: gx_143
* @创建时间: 2017-4-30上午09:32:21
*/
public class T8skiing {

/**
* @param args
*/
static int h,w;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] out=new int[n];

for (int i = 0; i < out.length; i++) {
h=sc.nextInt();
w=sc.nextInt();

int[][] data=new int[h][w];
for (int j = 0; j < data.length; j++) {
for (int l = 0; l < data[0].length; l++) {
data[j][l]=sc.nextInt();
}
}
int max=0;
for (int j = 0; j < data.length; j++) {
for (int l = 0; l < data[0].length; l++) {
int re=f(data,j,l);
if(re>max)
max=re;
}
}
out[i]=max;
}
for (int i = 0; i < out.length; i++) {
System.out.println(out[i]);
}
}
static int[][] stepArr =new int[][]{{-1,0},{1,0},{0,-1},{0,1}};

private static int f(int[][] data, int a,int b) {

int max=0;

Node node=new Node(a,b,data[a][b],1);
Queue<Node> queue=new LinkedList<Node>();
queue.add(node);
while(!queue.isEmpty()){
Node newNode=queue.poll();

if(newNode.step>max)
max=newNode.step;

for(int i=0;i<4;i++){
int x=newNode.x+stepArr[i][0];
int y=newNode.y+stepArr[i][1];

if(x>=0&&y>=0&&x<w&&y<h&&data[newNode.x][newNode.y]>data[x][y]){
Node next=new Node(x,y,newNode.sum+data[x][y],newNode.step+1);
queue.add(next);
}
}
}
return max;
}
private static class Node{
private int x;
private int y;
private int sum;
private int step;

public Node(int x,int y ,int sum,int step){
this.x=x;
this.y=y;
this.sum=sum;
this.step=step;
}
}
}

完全背包

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

难度:4

描述

直接说题意,完全背包定义有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。本题要求是背包恰好装满背包时,求出最大价值总和是多少。如果不能恰好装满背包,输出NO

输入

第一行: N 表示有多少组测试数据(N<7)。
接下来每组测试数据的第一行有两个整数M,V。 M表示物品种类的数目,V表示背包的总容量。(0<M<=2000,0<V<=50000)
接下来的M行每行有两个整数c,w分别表示每种物品的重量和价值(0<c<100000,0<w<100000)

输出

对应每组测试数据输出结果(如果能恰好装满背包,输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包,输出NO)

样例输入

1
2
3
4
5
6
2
1 5
2 2
2 5
2 2
5 1

样例输出

1
2
NO
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
53
54
55
56
57
58
59
60
61
/**
*
*/
package 动态规划;

import java.util.Scanner;

/**
* @作者: gx_143
* @创建时间: 2017-4-30上午08:56:09
*/
public class T7完全背包 {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] out=new int[n];

for (int i = 0; i < out.length; i++) {
int m=sc.nextInt();
int v=sc.nextInt();

int[] need=new int[m+1];
int[] value=new int[m+1];

for (int j = 1; j < value.length; j++) {
need[j]=sc.nextInt();
value[j]=sc.nextInt();
}

out[i]=f(m,v,need,value);
}
for (int i = 0; i < out.length; i++) {
if(out[i]==-1)
System.out.println("NO");
else
System.out.println(out[i]);
}
}

private static int f(int m, int v, int[] need, int[] value) {

int[] dp=new int[v+1];
for (int i = 1; i < dp.length; i++) {
dp[i]=-10000000;
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= v; j++) {
if(j>=need[i])
dp[j]=Math.max(dp[j], dp[j-need[i]]+value[i]);
}
}
if(dp[v]<0)
return -1;
return dp[v];
}
}

标题:密文搜索

福尔摩斯从X星收到一份资料,全部是小写字母组成。
他的助手提供了另一份资料:许多长度为8的密码列表。
福尔摩斯发现,这些密码是被打乱后隐藏在先前那份资料中的。

请你编写一个程序,从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。

数据格式:

输入第一行:一个字符串s,全部由小写字母组成,长度小于1024*1024
紧接着一行是一个整数n,表示以下有n行密码,1<=n<=1000
紧接着是n行字符串,都是小写字母组成,长度都为8

要求输出:
一个整数, 表示每行密码的所有排列在s中匹配次数的总和。

例如:
用户输入:
aaaabbbbaabbcccc
2
aaaabbbb
abcabccc

则程序应该输出:
4

这是因为:第一个密码匹配了3次,第二个密码匹配了1次,一共4次。

资源约定:
峰值内存消耗(含虚拟机) < 512M

CPU消耗 < 5000ms

这个题比较有意思,之前被题目设计的全套给坑了,以给出的密码进行全排列来匹配原字符串,这样做就相当繁琐了。

反过来想,其实很简单的:

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
 /**
*
*/
package 决赛Java大学C组2015;

import java.util.Arrays;
import java.util.Scanner;

/**
* @作者: gx_143
* @创建时间: 2017-4-28下午09:17:41
*/
public class T5改 {

static long ans=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
int n=sc.nextInt();
while(n>=0){
n--;
String s=sc.nextLine();
count(str,sort(s));
}
System.out.println(ans);
}

private static void count(String str, String sort) {

for (int i = 0; i <= str.length()-8; i++) {
String sb=str.substring(i,i+8);
sb=sort(sb);
if(sb.equals(sort))
ans++;
}
}

private static String sort(String s) {

char[] ch=s.toCharArray();
Arrays.sort(ch);
String re=new String(ch);
return re;
}
}