深度优先

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

0%

喷水装置(一)

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

难度:3

描述

现有一块草坪,长为20米,宽为2米,要在横中心线上放置半径为Ri的喷水装置,每个喷水装置的效果都会让以它为中心的半径为实数Ri(1<Ri<15)的圆被湿润,这有充足的喷水装置i(1<i<600)个,并且一定能把草坪全部湿润,你要做的是:选择尽量少的喷水装置,把整个草坪的全部湿润。

输入

第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n,n表示共有n个喷水装置,随后的一行,有n个实数ri,ri表示该喷水装置能覆盖的圆的半径。

输出

输出所用装置的个数

样例输入

1
2
3
4
5
2
5
2 3.2 4 4.5 6
10
1 2 3 1 2 1.2 3 1.1 1 2

样例输出

1
2
2

5

题目表述的不准确,应该是R>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
import java.util.Arrays;
import java.util.Scanner;

public class T2喷水装置1 {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] out=new int[n];

for (int i = 0; i < out.length; i++) {
int t=sc.nextInt();
double[] data=new double[t];
for (int j = 0; j < data.length; j++) {
data[j]=sc.nextDouble();
}
out[i]=getNum(data);
}
for (int i = 0; i < out.length; i++) {
System.out.println(out[i]);
}
}
}

private static int getNum(double[] data) {
Arrays.sort(data);
int ans=0;
double m=20.0;
for (int i = data.length-1; i >= 0; i--) {
if(m>0){
m=m-2*Math.pow(data[i]*data[i]-1, 0.5);
ans++;
}else break;
}
return ans;
}
}

无聊用Jquery写的一个九宫格拼图游戏。。。。

代码部分:

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
<html xmlns="http://www.w3.org/1999/xhtml">
<meta charset="utf-8"/>
<head>
<title>拼图游戏--九宫格</title>
<script src="Scripts/jquery-1.4.1.min.js" type="text/javascript"></script>
<script type="text/javascript">
var kong = 9;
var cunts = 0;
var kaishi=false;
var zhanting=false;
$(function () {
/*给所以方块注册点击事件*/
$(".cl").click(function () {
if(!kaishi){
alert('请先点击开始游戏吧~~~!');
return;
}
var t = this.id;/*获取单击块的id*/
var index = Number(t.substring(3, t.length));/*获取块的编号*/
var m ="#"+ t + " img";
var s = $(m)[0].src;
var arr=s.split('/');
s='images/'+arr[arr.length-1];

/*判断两个块,能不能交换,上下左右,编号时用到一个技巧*/
//编号为 /*1 2 3 */
/*5 6 7 */
/*9 10 11 */
/*上下 只需判断做差的绝对值是否为4,左右 只需判断做差的绝对值是否为1*/

if (Math.abs(index - kong) == 1 || Math.abs(index - kong) == 4){
var a = "#Div" + kong;
var b = "#Div" + index;

var img1 = '<img src="'+s+'" id="img11" />';
var img2 = '<img src="images/9.jpg" id="img11" />';

/*动画效果*/
$(m).toggle(200,function(){
$(a).html(img1);
$(b).html(img2);
});

$(a).removeClass("click");
$(this).addClass("click");/*添加点击样式*/
kong = index;
cunts++;
$("#myCunts").attr('value',cunts);
}
else {
$(this).hide(200,function(){

});
$(this).show(200,function() {

});
}
});

/*给所有方块注册鼠标进入事件,将背景变成黄色*/
$(".cl").mousemove(function () {
$(this).addClass("move");
});

/*给所有方块注册鼠标移出事件,去除鼠标进入时的样式*/
$(".cl").mouseout(function () {
$(this).removeClass("move");
});

/*开始游戏,打乱卡片,随机生成两个数,然后交换两个卡片*/
$("#start").click(function(){
if(kaishi){
alert('游戏已经开始了哦~~~!!');
return;
}
kaishi=true;

for (var i = 0; i < 20; i++) {

var r1=Math.round(Math.random()*(11));
var r2=Math.round(Math.random()*(11));

if(r1==0||r1==4||r1==8||r1==9||r2==0||r2==4||r2==8||r2==9) continue;

var a='#Div'+r1;
var b='#Div'+r2;

var m =a + " img";
var s = $(m)[0].src;
var arr=s.split('/');
s='images/'+arr[arr.length-1];

var mb =b + " img";
var sb = $(mb)[0].src;
var arrb=sb.split('/');
sb='images/'+arrb[arrb.length-1];

var img1 = '<img src="'+s+ '" />';
var img2 = '<img src="'+sb+'" />';

$(a).html(img2);
$(b).html(img1);
}
myclock();
});
$("#stop").click(function(){
if(kaishi==true&&zhanting==false)
alert('好吧,你说停就停吧!待会继续!');
else
alert('还没开始暂停个毛线的啊~~~');
});
$("#oneGet").click(function(){
if(confirm('这么容易就要放弃了吗?'))
{
location.reload();
}
});

/*游戏模式设置*/
$("#g33").click(function(){
alert('当前就是3*3模式呢!!');
});
$("#g44").click(function(){
alert('ggg正在加班开发中,请稍等哦~~~!!');
});
$("#g55").click(function(){
alert('ggg正在加班开发中,请稍等哦~~~!!');
});
});
/*计时开始*/
var times;
function myclock(){
var t=$("#time").val();
t=t.substring(0,t.length-2);
t=1+Number(t)+'ms';
$("#time").attr('value',t);
times=setTimeout("myclock()",100);
}
</script>
<style type="text/css">
body
{
text-align:center;
font-family: 'myface', serif;
font-size: 24px;
background-image: url('images/bg.jpg');
color: #7605F7;
}
#node input{
font-family: 'myface', serif;
font-size: 14px;
color: #272822;
}
#jishi input{
font-family: 'myface', serif;
font-size: 16px;
color: #f0f;
width: 150px;
}
@font-face {
font-family: 'myface';
src: url('ttf/myface.ttf');
}
#box
{
width:550px;
height:550px;
background:#ccc;
margin:0 auto;
padding: 10px;
margin-left: 500px;
border: 2px solid #fff;
}
.cl
{
width:180px;
height:180px;
margin-left:3px;
margin-top:3px;
background:#fff;
float:left;
font-size:180px;
}
/*鼠标进入样式*/
.move
{
background:#f0f;
}
/*鼠标单击样式*/
.click
{
background: #0026ff;
}
/*鼠标单击样式*/
img
{
width:170px;
height:170px;
margin:5px;
}
#shezhi,#jishi,#nandu{
width: 300px;
height: 80px;
float: left;
margin: 20px;
text-align: left;
}
#node{
width: 300px;
height: 400px;
float: left;
margin-left: 100px;
}
#jishi{
font-size: 19px;
text-align: left;
line-height: 40px;
}
</style>
</head>
<body>
<form id="form1" runat="server">
<h3>九宫格--拼图游戏</h3>
<div id="node">
<div id="shezhi">
<fieldset>
<legend>操作设置</legend>
<input type="button" name="" value="开始游戏" id="start">
<input type="button" name="" value="暂停游戏" id="stop">
<input type="button" name="" value="重新开始" id="oneGet">
</fieldset>
</div>
<div id="nandu">
<fieldset>
<legend>难度设置</legend>
<input type="button" name="" value="3*3模式" id="g33">
<input type="button" name="" value="4*4模式" id="g44">
<input type="button" name="" value="5*5模式" id="g55">
</fieldset>
</div>
<div id="jishi">
<fieldset>
<legend>记录情况</legend>
移动次数:<input type="text" name="" value="0" id="myCunts"><br>
用时情况:<input type="text" name="" value="0000ms" id="time"><br>
最好成绩:<input type="text" name="" value="20"><br>
</fieldset>
</div>
</div>
<div id="box">
<div id="Div1" class="cl">
<img src="images/1.jpg" id="img1" />
</div>
<div id="Div2" class="cl">
<img src="images/2.jpg" id="img2" />
</div>
<div id="Div3" class="cl">
<img src="images/3.jpg" id="img3" />
</div>
<div id="Div5" class="cl">
<img src="images/5.jpg" id="img5" />
</div>
<div id="Div6" class="cl">
<img src="images/6.jpg" id="img6" />
</div>
<div id="Div7" class="cl">
<img src="images/7.jpg" id="img7" />
</div>
<div id="Div9" class="cl">
<img src="images/9.jpg" id="img9" />
</div>
<div id="Div10" class="cl">
<img src="images/10.jpg" id="img10" />
</div>
<div id="Div11" class="cl">
<img src="images/11.jpg" id="img11" />
</div>
</div>
</form>
</body>
</html>

#1504 : 骑士游历
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在8x8的国际象棋棋盘上给定一只骑士(俗称“马”)棋子的位置(R, C),小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。

输入
第一行包含三个整数,N,R和C。

对于40%的数据, 1 <= N <= 1000000

对于100%的数据, 1 <= N <= 1000000000 1 <= R, C <= 8

输出
从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大,你只需要输出答案模1000000007的余数。

样例输入
2 1 1
样例输出

12

一个通俗的想法:f[k][i][j],第k步可以到达(i,j)的步法总数。
f[k+1][i][j]是在第k步的基础上走1步到达(i,j)的步法总数。

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 long[][][] data=new long[2][12][12];
static int[] dx=new int[]{-2,-2,-1,-1,1,1,2,2};
static int[] dy=new int[]{-1,1,-2,2,-2,2,-1,1};
static int pre=0,cur=0;
static int mod=1000000007;
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int r=sc.nextInt();
int c=sc.nextInt();

data[0][r][c]=1;
pre=0;
cur=1;

for (int step = 1; step <= n; step++) {
for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
data[cur][i][j]=0;
}
}

for (int i = 1; i <= 8; i++) {
for (int j = 1; j <= 8; j++) {
//八个方向
for (int f = 0; f < 8; f++) {
int x=i+dx[f];
int y=j+dy[f];
if(x>=1 && x<=8 && y>=1 && y<=8)
data[cur][x][y]=(data[cur][x][y]+data[pre][i][j])%mod;
}
}
}
pre=pre^1;
cur=cur^1;
}
long ans=0;
for (int i = 1; i <= 8; i++) {
for (int j = 1; j < 8; j++) {
ans=(ans+data[pre][i][j])%mod;
}
}
System.out.println(ans);
}
}
}