刷题 ACM, LeetCode, OJ等类型的刷题

用Dijkstra算法求解无向图的最短路径

  |   0 评论   |   649 浏览

Dijkstra 算法是典型的算法。Dijkstra 算法是很有代表性的算法。Dijkstra 一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用 OPEN, CLOSE 表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      

微软编程比赛里面的一道难度系数 5% 的编程题目如下:

image
image

Dijkstra 算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用 Dijkstra 算法来解决这个问题。

image

ACM刷题之-内存分配(POJ-1193 )

  |   0 评论   |   356 浏览

摘要: 内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。 经典的内存分配过程是这样进行的: 1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从 0 开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 i 开始的 s 个连续的内存单元称为首地址为 i 长度为 s 的地址片。 2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻 T,需要内存单元数 M 及运行时间 P。在运行时间 P 内(即 T 时刻开始,T+P 时刻结束),这 M 个被占用的内存单元不能再被其他进程使用。 3、假设在 T 时刻有一个进程申请 M 个单元,且运行时间为 P,则: 1. 若 T 时刻...

算法分析:

  1. 维护一个进程的链表,每个节点存有进程开始时间 t,进程运行时间 p, 在内存中的首地址 s,占用内存大小 m,和下一节点指针。

  2. 维护一个队列,表示还没有空间运行的进程。

  3. 维护一个释放内存的最早时间 nexttime,每读入一个新进程的时候,若进程开始时间不小于 nexttime,表示有进程在这之前已结束(可能不止一个),将其从链表删除,并循环检测队首

世界名画陈列馆问题(回溯法)

  |   0 评论   |   333 浏览

算法问题描述:

世界名画陈列馆问题。世界名画陈列馆由 m× n 个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。

算法问题形式化表示

本问题的 m*n 的陈列室的解可表示如下图所示。其中 1 代表在该陈列室设置警卫机器人哨位,0 表示未在该陈列室设置警卫机器人哨位。

问题描述

最为极端的情况是所有元素的值为 1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为 1 或 0,有 m*n 个元素,有 种可能满足约束条件的矩阵,要从 种可能中遍历找到满足约束条件的 1 的个数最小的矩阵。由此可见这是一个 NP 问题。这里的约束条件就是当某一个元素为 1 时,相邻的 4 个方向上的

ACM刷题之-POJ-1002(487-3279)

  |   0 评论   |   286 浏览

Description

Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. Yo

ACM刷题之-POJ-1011(Sticks)

  |   0 评论   |   259 浏览

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line con

ACM刷题之-POJ-1014(Dividing)

  |   0 评论   |   258 浏览

Description

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbl

ACM刷题之-POJ-1061(青蛙的约会)

  |   0 评论   |   302 浏览

Description

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B,并且规定纬度线上东经 0 度处为原点,由东往西为正方向,单位长度 1 米,这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x,青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米,青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行 5 个整数 x,y,m,n,L,其中 x≠ y < 2000000000,0 < m、n < 2000000000,0 < L < 21

ACM刷题之-POJ-1396(Simple Arithmetics)

  |   0 评论   |   235 浏览

Description

One part of the new WAP portal is also a calculator computing expressions with very long numbers. To make the output look better, the result is formated the same way as is it usually used with manual calculations.

Your task is to write the core part of this calculator. Given two numbers and the requested operation, you are to compute the result and print it in the form specified below. With addition and subtraction, the numbers are written below each other. Multiplication

ACM刷题之-POJ-2192(Zipper)

  |   0 评论   |   238 浏览

Description

Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee

ACM刷题之-2015微软编程之美资格赛

  |   0 评论   |   307 浏览

题目一:2 月 29

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

给定两个日期,计算这两个日期之间有多少个 2 月 29 日(包括起始日期)。
只有闰年有 2 月 29 日,满足以下一个条件的年份为闰年:

  1. 年份能被 4 整除但不能被 100 整除
  2. 年份能被 400 整除

输入

第一行为一个整数 T,表示数据组数。

之后每组数据包含两行。每一行格式为"month day, year",表示一个日期。month 为{"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}中的一个字符串。day 与 year 为两个数字。

数据保证给定的日期合法且第一个日期早于或等于第二个日期。

输出

对于每组数据输出一行,形如"Case #X: Y"。X 为数据组数,从 1 开始,Y 为答案。

数据范围

ACM刷题之-POJ-3749(破译密码)

  |   0 评论   |   243 浏览

Description

据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第 5 个字母替换(例如:消息原文中的每个字母 A 都分别替换成字母 F)。而你要获得消息原文,也就是要将这个过程反过来。
密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M
原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

注意:只有字母会发生替换,其他非字母的字符不变,并且消息原文的所有字母都是大写的。

Input

最多不超过 100 个数据集组成,每个数据集之间不会有空行,每个数据集由 3 部分组成:
起始行:START
密码消息:由 1 到 200 个字符组成一行,表示凯撒发出的一条消息.
结束行:END
在最后一个数据集之后,是另一行:ENDOFINPUT

Output

每个数据集对应一行,是凯撒的原始消息。

Sample Input

START NS BFW, JA

ACM刷题之-POJ-1191(棋盘分割)

  |   0 评论   |   322 浏览

Description

将一个 8 * 8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
image
原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi 为第 i 块矩形棋盘的总分。
请编程对给出的棋盘及 n,求出 O'的最小值。

Input

第 1 行为一个整数 n(1 < n < 15)。
第 2 行至第 9 行每行为 8 个小于 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

Output

仅一个数,为 O'(四舍五入精确到小数点后三位)。

Sample Input

3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

ACM刷题之-POJ-3662(Telephone Lines)

  |   0 评论   |   296 浏览

Description

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable

ACM刷题之-POJ-3333(Co-workers from Hell)

  |   0 评论   |   276 浏览

Description

A watchman has to check a number of chambers in the factory each night according to a schedule which specifies the order in which the chambers must be visited and the time it takes to check each chamber. The watchman starts his job each night starting from the first chamber and leaves the factory and goes home when he checks the final chamber. He normally checks all other chambers, but in our story he may not actually do so. Having access to this schedule, a co-worker wants to

ACM刷题之-POJ-3006(Dirichlet's Theorem on Arithmetic Progre)

  |   0 评论   |   252 浏览

Description

If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, ..., contains infinitely many prime numbers. This fact is known as Dirichlet's Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837.

For example, the arithmetic sequence beginning with 2 and i