Browsed by
月份:2014年10月

HDU 1142 A Walk Through The Forest

HDU 1142 A Walk Through The Forest

Problem Description

A Walk Through the Forest

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5891    Accepted Submission(s): 2168

Problem Description
Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable.
The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take.

 

Input
Input contains several test cases followed by a line containing 0. Jimmy has numbered each intersection or joining of paths starting with 1. His office is numbered 1, and his house is numbered 2. The first line of each test case gives the number of intersections N, 1 < N ≤ 1000, and the number of paths M. The following M lines each contain a pair of intersections a b and an integer distance 1 ≤ d ≤ 1000000 indicating a path of length d between intersection a and a different intersection b. Jimmy may walk a path any direction he chooses. There is at most one path between any pair of intersections.

 

Output
For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed 2147483647

 

Sample Input

Sample Output
2 4

话说这个题和并查集有神马关系啊喂!!想了5个小时没有想到如何用并查集来处理,于是去看别人的博客了这分明是一个最短路+搜索喂     (╯#-_-)╯~~~~~~~~~~~~~~~~~╧═╧ 大力掀

 

好了买萌结束 = =开始学习Dijkstra 算法 以及 可能的话 学习SPFA 算法

Dijkstra算法学习

Laravel 学习笔记 #1 Installation and Configuration

Laravel 学习笔记 #1 Installation and Configuration

听力猫猫巨巨的话,准备开始学PHP的框架 ,查了一下PHP框架的排名,准备学习Laravel框架 (* ^_^ *)   本人的系统是Ubuntu14.10  PHP已经安装了 Apache也安装了 如果上不去那个Laravel的话,怎么解决你们懂的…

安装和配置

安装

  1. 我们采用Composer+Laravel Installer 的方式进行安装  首先 安装 Composer,因为我的电脑里有curl了 ,所以用第一种方式下载Composer即可 如下

    没有curl的话 就要用下面的代码下载
  2. 安装好Composer后 运行如下这些指令 一条条来
  3. 这样就构建好了一个Laravel的PHP框架 在你当前的目录下的 YourProjectName文件夹下   WARNING: 如果遇到这个错误:                                  [GuzzleHttpExceptionRequestException]
    Error creating resource. [url] http://cabinet.laravel.com/latest.zip [
    type] 2 [message] fopen(http://cabinet.laravel.com/latest.zip): failed
    to open stream: php_network_getaddresses: getaddrinfo failed: Name or
    service not known [file] /home/void-admin/.composer/vendor/guzzlehttp
    /guzzle/src/Adapter/StreamAdapter.php [line] 367                                               那是 因为 安装laravel时候需要去lookup的服务器找不到 这时就要翻墙了 不然 会没法新建这个框架
  4. 配置文件 在 app/config/config.php 下 有明确的文档说明
  5. 关于 URL Rewrite (Semantic URL)   这里应用官方的文档  因为我自己还不了解什么是URL Rewrite

Pretty URLs

Apache

The framework ships with a public/.htaccess file that is used to allow URLs without index.php. If you use Apache to serve your Laravel application, be sure to enable the mod_rewrite module.

If the .htaccess file that ships with Laravel does not work with your Apache installation, try this one:

 

 

POJ 1300 Door Man 欧拉路&字符串处理TAT

POJ 1300 Door Man 欧拉路&字符串处理TAT

Door Man
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 2140 Accepted: 859

Description

You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc…). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and closing the doors behind you. Your biggest problem is determining whether it is possible to find a path through the sloppy rooms where you:

  1. Always shut open doors behind you immediately after passing through
  2. Never open a closed door
  3. End up in your chambers (room 0) with all doors closed

In this problem, you are given a list of rooms and open doors between them (along with a starting room). It is not needed to determine a route, only if one is possible.

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components: 

  1. Start line – A single line, “START M N”, where M indicates the butler’s starting room, and N indicates the number of rooms in the house (1 <= N <= 20).
  2. Room list – A series of N lines. Each line lists, for a single room, every open door that leads to a room of higher number. For example, if room 3 had open doors to rooms 1, 5, and 7, the line for room 3 would read “5 7”. The first line in the list represents room 0. The second line represents room 1, and so on until the last line, which represents room (N – 1). It is possible for lines to be empty (in particular, the last line will always be empty since it is the highest numbered room). On each line, the adjacent rooms are always listed in ascending order. It is possible for rooms to be connected by multiple doors!
  3. End line – A single line, “END”

Following the final data set will be a single line, “ENDOFINPUT”.

Note that there will be no more than 100 doors in any single data set.

Output

For each data set, there will be exactly one line of output. If it is possible for the butler (by following the rules in the introduction) to walk into his chambers and close the final open door behind him, print a line “YES X”, where X is the number of doors he closed. Otherwise, print “NO”.

Sample Input

Sample Output

首先,需要搞清楚如何处理输入  参考我的上一篇文章,可知道应该用什么函数进行输入和输出 。 先把输入处理的代码放上 ,下面代码可以把数据读入并且记录每一个节点的度数值

实际上上面代码有问题 ,不过 在我写的时候还没有发现问题所在,下面先说这道题的思路,其实这个题很简单就是一个一笔画问题, 每一个房间代表一个节点,每一个开着的门代表一条节点之间的边,图为无向图,问是否存在从节点 m到 0 的一条路径,使得图中每一个边都被经过仅一次。

没有什么太多需要注意的,直接拿判断条件去判断就可以了,判断条件就是,当 m!=0时  即非Euler回路 ,这时要求 有两个奇节点 m 0 其它节点均为偶节点 当m=0时 要求所有节点均为偶节点 然后 根据边数=度数/2我们可以算出来有多少个门

因此我们只需要开个数组记录一下度数 就好了,

下面是AC代码 之前错了一次 是因为字符处理上出问题了,由于最初我gets读入空行的时候,会当作读入了一个数字 0 结果导致出问题 修改代码后就没有问题了 AC代码如下

 

把基本输入 scanf getchar gets 的区别

把基本输入 scanf getchar gets 的区别

在写控制台程序的时候,难免会遇到各种各样的输入格式读取,下面比较一下 scanf  getchar 和 gets的区别

首先我们要知道,当用户从键盘键入一个字符串的时候,就会在IO缓冲区内写入信息,这个缓冲区是一个队列,  我们用下面几段代码来检验一下,不同函数对缓冲区的读取效果

这一段代码是测试这三个函数到底读取了哪些字符

代码如下

这段代码中,首先用注释掉的scanf来接受输入  输入 test加回车后 输出的只有 test  输入test+tab也是同样的输出,这说明 scanf读取缓冲区时,每一次读取读到TAB 和 ENTER 前 (空格就不用说了 当然不读 ) 当scanf被调用时缓冲区里最前面的元素为有回车和空格符 或TAB scanf直接跳过他们不读

同理测试 gets  发现 gets每一次读取到一个回车前,TAB 和SPACE 它都读。当gets被调用时,缓冲区内第一个元素为ENTER时,gets不读这个ENTER

再测试getchar 简单修改代码即可测试  getchar 会读取所有的字符,但是只有当遇到回车的时候才会输出  这种性质叫务回显,而与它不同的 getch就有回显

 

HDU 1116 Play on words 欧拉路+并查集

HDU 1116 Play on words 欧拉路+并查集

Problem Description

Play on Words

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5576    Accepted Submission(s): 1831

Problem Description

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm” can be followed by the word motorola”. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

 

Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a’ through ‘z’ will appear in the word. The same word may appear several times in the list.

 

Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence “Ordering is possible.”. Otherwise, output the sentence “The door cannot be opened.”.

 

Sample Input
3 2 acm ibm 3 acm malform mouse 2 ok ok

 

Sample Output
The door cannot be opened. Ordering is possible. The door cannot be opened.
具体实现 用 Euler路+并查集来做
先学习欧拉路去 _(:3 [_)_
好啦在看了各个blog的代码之后总算写对啦   一次AC还好
这个题可以抽象出一个图模型  给出这个例子 (图中的数字代表字母 如 1代表 a  2代表 b … 而 (1,2)就代表一个以a开头以b结尾的单词 ,中间部分无用我们忽略即可 )
以26个字母为节点   以单词的首尾字母为边表示链接关系(这里省略了入度和出度都为0的节点)
如何判断可以开门呢,判断的依据就是用上面的方法产生的图是否为Euler图
这样就需要知道什么是Euler图
Euler图有两种
Euler 通路 和Euler回路  这个题是判断有向图是否存在Euler通路或者Euler回路
下面给出Euler通路和回路的判断定理:

②.欧拉路径存在性的判定一。无向图
一个无向图存在欧拉通路,当且仅当   该图所有顶点的度数为偶数   或者  除了两个度数为奇数外其余的全是偶数。

二。有向图
一个有向图存在欧拉通路 当且仅当有且仅有一个节点的出度-入度=1 有且仅有一个节点的入度-出度=1,其余节点入度=出度

有向图存在欧拉回路 当且仅当各个节点的入度=出度

 

因此 我们就可以根据这个来判断是否为欧拉图  分为两步

1.检查图的连通性

2.检查每个节点的出入度数

检查图的连通性我们要用到的算法就是并查集 每次并查集记录这个节点的父节点,父节点就是它的直接or间接后继节点,最终找到BOSS节点 即所有节点的最终根节点 上图中按照下面的算法BOSS节点就是 6

并查集算法如下:

 

下面给出Union Find算法执行后的运行的图示

红色的表示最后一次执行后,再次对所有的节点进行UF算法 各个节点的BOSS是谁  可以看出来都是 6

如果不连通肯定不能开门,连通的话就要判断一下度数关系,这时候判断一下Euler通路和回路就好

 

因此 我们主要要存的信息是  每个节点的father  每个节点的度数 每个节点是否被访问过的状态,其余的都是一些标记变量 。下面是AC代码 代码较长,应该有很多地方能够简化

 

Time To Go on

Time To Go on

开学这段时间,事情很多很杂,被社团活动占据了主要时间,还有由于我们队伍没有去成Regional,大家最近都没有怎么刷题,我就更不用说了。

一直以来也没有找到好的方法,来提高自己的ACM能力。今天去知乎上请教了大神们,如何搞ACM,大神们给了一些建议,也指出了我是不够努力这个原因。

 

徐犇彳人禾牛牛牛

我的经验是学习和刷题交替进行。比如0基础的人,一开始需要看些编程语言的书,然后开始刷题(例如去各大oj找基本输入输出等超级大水题刷);直到感觉刷不动题了,再找书看,学些基本数据结构和算法;然后又一轮刷题,这次能刷的题肯定又有很多了;一直刷到又刷不动了,再进行下一轮学习,学更高级的算法与数据结构等;如此反复循环……
当然,我说的是在大的方面,系统学习和做题是交替的;在细节方面,肯定会有交叉,具体自己把握……

补充一下:学习算法要充分利用各种大牛的书、博客等,还有各大OJ,好多OJ都会有题目难度分级功能,还有各种前辈会对OJ的题目进行总归和分类。只有这样,才能做到有的放矢,不然的话,这么多内容,初学者确实会无从下手。
个人见解,希望对你有所帮助。

楼上的意见 ,和我的想法比较像,做题&刷题结合,一轮轮攻克,不急于求成,大方法上,就是应该这样,不过,在处理有些问题我都没法分清楚这是什么难度的题目的时候,我感觉,不太好区分 ,,  不过我会努力的
说到底 还是自己不够坚定    各种事都在我乱成一团,,不会合理的安排
提升自己吧,,我要坚定算法这条道路
毕竟和我们的老师也聊过了,算法这个路我没有走错
VOID  GO ON
Linux XAMPP 安装

Linux XAMPP 安装

首先到官网下载最新版本的XAMPP

然后 chmod a+x 对应的那个 .run文件名  给予程序执行权限

然后再 sudo 那个.run文件 ,就进入了安装界面

 

点击 NEXT

 

这就开始安装了 0.0第一次在Linux下见到这种界面的安装程序,想起了Windows下的安装界面 = =

安装好之后,修改一下DocumentRoot就可以了 然后 记住 本地正在运行的apache要关掉不然没法启动Apache

 

PHP $_SESSION 超级全局变量 的使用

PHP $_SESSION 超级全局变量 的使用

SESSION 变量,是给每个不同的用户分配一个不同的UID然后把相应的变量的值存储在服务器端,画个图就是这样的:

如这个图片所示,有两个用户接入了某个服务器 一个是User1 UID=001 一个是User2 UID=002 那么,他们同时向服务器发出请求的时候,服务器端要对身份进行认证,只有username=admin的用户才有权限访问,这时候,在服务器端就要用到下面的代码 :

这段代码的作用是:当用户访问了该页面的时候,先检测用户的username是否为admin 如果是的话,执行其它代码 否则返回登录页面 。具体的识别机制就是上面的那样,首先,要使用 session_start()函数,而且,这个函数要用在所有输出操作未进行之前,不然就没法建立会话了,建立会话之后,服务器端在login页面会给用户分配一个UID如上图,当然,分配的是加密的ID 然后并且在服务器端给这个UID建立相应的PHPSESSION 数组,具体实现是给用户发送了一个SESSION Cookie 在关闭浏览器的时候,就会把Cookie销毁,然后,在用户向服务器发送访问页面请求的时候,服务器端会根据这个用户的UID找到这个用户的SESSION 变量,并且该用户的SESSION变量不会被别人访问到。然后 当用户存在 $_SESSION[‘username’]这个变量时,就登录成功,否则失败。