归档:2012年3月月

探寻C++最快的读取文件的方案

蓝飞 蓝飞 | 时间:2012-03-31, Sat | 6,570 views
编程算法 

在竞赛中,遇到大数据时,往往读文件成了程序运行速度的瓶颈,需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头,于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的,C++选手只能干着急。难道C++真的低Pascal一等吗?答案是不言而喻的。一个进阶的方法是把数据一下子读进来,然后再转化字符串,这种方法传说中很不错,但具体如何从没试过,因此今天就索性把能想到的所有的读数据的方式都测试了一边,结果是惊人的。

(阅读全文…)

[ACM_HDU_2046]骨牌铺方格

蓝飞 蓝飞 | 时间:2012-03-31, Sat | 7,517 views
编程算法 

骨牌铺方格

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

Description

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:

骨牌铺方格

Input

输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

Output

对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。

(阅读全文…)

[ACM_ZOJ_1002]Fire Net

蓝飞 蓝飞 | 时间:2012-03-31, Sat | 25,537 views
编程算法 

Fire Net

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as 

many

blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Fire Net

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer 

n

that is the size of the city; 

n

will be at most 4. The next 

n

lines each describe one row of the map, with a '

.

' indicating an open space and an uppercase '

X

' indicating a wall. There are no spaces in the input file.

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

(阅读全文…)

[ACM实验三]ACM程序设计基础(1)

蓝飞 蓝飞 | 时间:2012-03-31, Sat | 4,394 views
编程算法 
从实验三开始使用scanf与printf进入输入输出,具体原因详见:[ACM学习心得]关于sync_with_stdio(false);

实验项目:ACM程序设计基础(1)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:

1.输入年、月、日,计算该日是该年的第n天,输出n。

2.对于大于等于6的偶数,可以表示为2个素数之和,请判断一个数是否是对称数,如果该数为对称数而且是偶数,输出其和等于该数的2个素数。

3.Fire Net问题, 要求输出最优值和最优值对应的最优解。

4.附加题:0-1背包问题:有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是w[i]。物品(1.可以;2.不可)切割出来只是装一部分,求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大,先输入物品数n和背包容量v,然后输入各个物品费用和价值,输出最大价值。

(阅读全文…)

[ACM实验二]C++STL泛型编程(2)

蓝飞 蓝飞 | 时间:2012-03-31, Sat | 4,293 views
编程算法 

实验项目:C++STL泛型编程(2)
实验目的:掌握C++STL string向量容器等的应用。
实验要求:使用VC++6.0实现实验要求。
实验内容:

1.输入一串小写字母字符,输出该字符串中每个字母的个数,例如输入:aadsef,输出:
a 2
d 1
e 1
f 1
s 1

2. 古代一位国王和他的张、王、李、赵、钱五位将军一同出外打猎,各人的箭上都刻有自己的姓氏。打猎中,一只鹿中箭倒下,但不知是何人所射。
张说:"或者是我射中的,或者是李将军射中的。"
王说:"不是钱将军射中的。"
李说:"如果不是赵将军射中的,那么一定是王将军射中的。"
赵说:"既不是我射中的,也不是王将军射中的。"
钱说:"既不是李将军射中的,也不是张将军射中的。"
国王让人把射中鹿的箭拿来,看了看,说:"你们五位将军的猜测,只有两个人的话是真的."请判断是谁射中鹿。

3. 输入一个自然数N(2≤N≤9),要求输出如下的魔方阵,即边长为N行N列,元素取值为1至N*N,1在左上角,呈顺时针方向依次放置各元素。如输入4,输出:
1 2 3 412  13  14   511  16  15   610   9   8   7

附加题:
给定一个N×M的整数矩阵,找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和,子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。

(阅读全文…)