没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全poj解题笔记1

poj解题笔记1

数据结构

需积分: 0 0 下载量 23 浏览量 2022-08-08 22:31:32 上传评论收藏 212KB DOCX 举报

温馨提示

试读

98页

借助队列，先将农夫的位置存进队列，然后将农夫在当前位置可以到达的所有位置存进队列中，并用-1分隔开农夫每步走到的位置，然后依次弹出队列的元素，重复操作直到走到了

资源详情

资源评论

资源推荐

poj 3278

1 原题目

赶上那头牛

时限： 2000MS

内存限制： 65536K

提交总数： 149574

接受的： 45849

描述 http://poj.org/problem?id=3278

农夫约翰已被告知一头逃犯的位置，并希望立即抓住她。他开始于一个点 Ñ

（0≤ Ñ ≤100,000）上的数线和牛是在点 ķ（0≤ ķ 上相同数目的线≤100,000）。农

夫约翰有两种运输方式：步行和传送。

*步行：FJ 可以在一分钟内从任意点 X 移至点 X -1 或 X + 1。

*传送：FJ 可以在一分钟内从任意点 X 移至点 2× X。

如果没有意识到它的追捕能力的母牛完全没有动弹，那么农夫约翰要花多长时

间？

输入项

第 1 行：两个以空格分隔的整数：N 和 K

输出量

第 1 行：农夫约翰用最少的时间（以分钟为单位）捉住逃犯。

样本输入

5 17

样本输出

暗示

农夫约翰到达逃亡者牛的最快方法是沿着以下路径移动：5-10-9-18-17，这需要

4 分钟。

2 题目分析

农夫只能往前走一步，或往后走一步，或者直接到达他现在位置二倍的地方，让农夫走最少

的步数来到达牛的位置。

3 基础知识

3.1 数据结构

无。

3.2 算法

广度优先搜索（解法一用到）

4 解法

4.1 解法 1（java 已过）

利用广度优先搜索来解题，并利用标记数组来去重。

因为是一条直线，所以我们可以将农夫走过的位置进行标记，如果下次又到了标记的位置就

不走这个位置。

借助队列，先将农夫的位置存进队列，然后将农夫在当前位置可以到达的所有位置存进队列

中，并用-1 分隔开农夫每步走到的位置，然后依次弹出队列的元素，重复操作直到走到了

牛的位置。

本人代码：

import java.util.*;//包含java.util包中所有的类

public class Main {//用广度优先搜索来做

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while(in.hasNext()) {//输入多组数据

int map[] = new int[100001];//标记数组

Queue<Integer> queue = new LinkedList<Integer>();//队列

int n,k,num = 0;

n = in.nextInt();

k = in.nextInt();

queue.add(n);//压入队列

map[n] = 1;

queue.add(-1);//-1是用来将每一步可以到达的点隔开

while(!queue.isEmpty()) {

int temp = queue.poll();//从队列弹出

if(temp == -1) {

num++;//步数加1

queue.add(-1);

continue;

}

else {

if(temp == k)//等于k时说明找到了

break;

//存入当前点所有可能走过的点并进行去重

if(temp - 1 >= 0 && map[temp - 1] == 0) {

queue.add(temp - 1);

map[temp - 1] = 1;

}

if(temp + 1 <= k && map[temp + 1] == 0) {

queue.add(temp + 1);

map[temp + 1] = 1;

}

if(temp * 2 <= 100000 && map[temp * 2] == 0) {

queue.add(temp * 2);

map[temp * 2] = 1;

}

System.out.println(num);

}

poj 3126

1 原题目

主要路径

时限： 1000MS

内存限制： 65536K

提交总数： 36147

接受： 19404

描述 http://poj.org/problem?id=3126

内阁大臣对安全首长的信息感到非常

不安，他们说他们都必须更改办公室

四位数的房间号。

—时不时地改变这些事情，以使敌人

陷入黑暗是安全的问题。

-但是，我有充分的理由选择了我的号

码 1033。我是总理，你知道的！

—我知道，因此您的新电话号码 8179

也是素数。您只需要在办公室门上的

四个旧数字上粘贴四个新数字。

—不，不是那么简单。假设我将第一

个数字更改为 8，那么该数字将显示

8033，这不是质数！

—我知道，作为总理，即使坐了几秒

钟，也无法忍受门口有非总理数字。

—正确！因此，我必须发明一种方

案，通过从质数到 1033 到 8179 的质

数路径，其中只有一位从一个质数变

为下一个质数。

现在，一直在窃听的财政部长介入了。

—请不要不必要的支出！我碰巧知道一个数字的价格是一磅。

—嗯，在那种情况下，我需要一个计算机程序以最小化成本。您不了解一些非

常便宜的软件专家，对吗？

—事实上，我愿意。您会看到，这场编程竞赛正在进行中...帮助总理找到在两

个给定的四位数素数之间最便宜的素数路径！当然，第一位必须为非零。这是

上述情况的解决方案。

1033

1733

3733

3739

3779

8779

8179

该解决方案的成本为 6 磅。请注意，在步骤 2 中粘贴的数字 1 不能在最后一步

中重复使用-必须购买新的 1。

输入项

一行带有正数：测试用例的数量（最多 100 个）。然后，对于每个测试用例，

用两个数字用空格分隔的一行。这两个数字都是四位数的质数（无前导零）。

输出量

每种情况只用一行，或者用数字表示最低费用，或包含“不可能”一词。

样本输入

1033 8179

1373 8017

1033 1033

样本输出

2 题目分析

给定两个素数 a b，求 a 变幻到 b 需要几步，并且变幻时只有一个数字不同，并且是素数。

3 基础知识

3.1 数据结构

队列（解法一用到）

3.2 算法

广度优先搜索（解法一用到）

4 解法

4.1 解法 1（C++已过）

广度优先搜索，将 a 素数每一位依次用 0 到 9 替换，其他位暂且不变（要满足替换后的数

字是素数这个条件）存进队列中，然后对队列中的数字进行同样的操作，直到找到素数 b

或者队列为空。

本人代码：

剩余97页未读，继续阅读

内容反馈

申增浩

粉丝: 18
资源: 297

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

poj解题笔记1

评论0

最新资源

poj解题笔记1

评论0

poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告

北大poj解题报告

80道POJ解题报告

本人整理的POJ解题报告大全

poj 3414解题报告

poj 1012解题报告

poj 2329解题报告

poj 1440解题报告

poj 3083解题报告

poj 1659解题报告

北大POJ 大量解题代码

poj1691解题报告

北大POJ解题报告_打包下载

poj 3720解题报告

poj解题报告（一百多道题）

poj2828解题报告

poj_3613解题报告

poj 1061 解题报告 有源码

poj解题报告2395

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

安全认证cisp教材全套

OpenVAS GVM 中文翻译补丁

2024最新：Hvv中常见的面试问题

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

全面的安全基线核查清单

最新资源

poj 1061 解题报告有源码