CHAPTER 2
Section 2.1
Graph Theory
The Castle
In a stroke of luck almost beyond imagination, Farmer John was sent a ticket to the Irish Sweepstakes (really a lottery) for his birthday. This ticket turned out to have only the winning number for the lottery! Farmer John won a fabulous castle in the Irish countryside.
Bragging rights being what they are in Wisconsin, Farmer John wished to tell his cows all about the castle. He wanted to know how many rooms it has and how big the largest room was. In fact, he wants to take out a single wall to make an even bigger room.
Your task is to help Farmer John know the exact room count and sizes.
The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their “outer edges” to keep out the wind and rain.
Consider this annotated floorplan of a castle:
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # -># | | | | # #
#############################
# = Wall -,| = No wall
-> = Points to the wall to remove to
make the largest possible new room
By way of example, this castle sits on a 7 x 4 base. A “room” includes any set of connected “squares” in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).
Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.
The castle always has at least two rooms and always has a wall that can be removed.
一个矩形由N*M个房间组成，每个房间之间有墙或者没墙，房间之间的连通性，
求最大有多少房间联通
拆掉一堵墙，可以获得的最大房间联通
Ordered Fractions
Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.
Here is the set when N = 5:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.
有顺序的分数
Sorting a Three-Valued Sequence
Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.
In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.
You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.
数组中只有[1,2,3],将数组排序需要的最小两两交换次数
DFS剪枝
Healthy Holsteins
Farmer John prides himself on having the healthiest dairy cows in the world. He knows the vitamin content for one scoop of each feed type and the minimum daily vitamin requirement for his cows. Help Farmer John feed the cows so they stay healthy while minimizing the number of scoops that a cow is fed.
Given the daily requirements of each kind of vitamin that a cow needs, identify the smallest combination of scoops of feed a cow can be fed in order to meet at least the minimum vitamin requirements.
Vitamins are measured in integer units. Cows can be fed at most one scoop of any feed type. It is guaranteed that a solution exists for all contest input data.
PROGRAM NAME: holstein
INPUT FORMAT
Line 1: integer V (1 <= V <= 25), the number of types of vitamins
Line 2: V integers (1 <= each one <= 1000), the minimum requirement for each of the V vitamins that a cow requires each day
Line 3: integer G (1 <= G <= 15), the number of types of feeds available
Lines 4..G+3: V integers (0 <= each one <= 1000), the amount of each vitamin that one scoop of this feed contains. The first line of these G lines describes feed #1; the second line describes feed #2; and so on.
SAMPLE INPUT (file holstein.in)
4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399
OUTPUT FORMAT
The output is a single line of output that contains:
the minimum number of scoops a cow must eat, followed by:
a SORTED list (from smallest to largest) of the feed types the cow is given
If more than one set of feedtypes yield a minimum of scoops, choose the set with the smallest feedtype numbers.
SAMPLE OUTPUT (file holstein.out)
2 1 3
用勺子喂奶牛维生素
一共有V种维生素，奶牛每一种维生素有一个最小需求量
每勺中含有不同的维生素量，求至少需要几勺，并且每一勺都只能出现一次
有多种方案时，取勺的id最小的
BFS 广度搜索
Hamming Codes
Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords.
The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4)(a hex digit requires four bits):
0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
Bit differences: -XXX -XX- ——
Since five bits were different, the Hamming distance is 5.
Section 2.2
Data Structures
Dynamic Programming
Preface Numbering
A certain book’s prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set:
I 1 L 50 M 1000
V 5 C 100
X 10 D 500
As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:
III is 3
CCC is 300
Any mark that has the value 5x10n can not be used consecutively.
Generally (with the exception of the next rule), marks are connected together and written in descending order to form even more numbers:
CCLXVIII = 100+100+50+10+5+1+1+1 = 268
Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes:
IV = 4
IX = 9
XL = 40
This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct).
Compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. 90 is expressed XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).
Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I’s, V’s, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. Do not print letters that do not appear in the page numbers specified.
If N = 5, then the page numbers are: I, II, III, IV, V. The total number of I’s is 7 and the total number of V’s is 2.
罗马数字编码
分别计算 个位数 十位数 百位数的 编码
Subset Sums
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:
{3} and {1,2}
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, … 7} so that each partition has the same sum:
{1,6,7} and {2,3,4,5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.
Subset Sums 问题
Runaround Numbers
Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:
* If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
* Repeat this cycle (this time for the six counts designed by the \`6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
* Repeat again (two digits this time): 8 1
* Continue again (one digit this time): 3
* One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.
Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.
全排列 从小到大的顺序
然后判断是否是 Runaround Numbers
标记位1
2
3
4
5
6
7
8for (int i = 1; i <= 9; i++) {
if (vFlag[i] == false) {
vFlag[i] = true;
vChar[index] = i + '0';
permutation(index + 1, n);
vFlag[i] = false;
}
}
Party Lamps
To brighten up the gala dinner of the IOI’98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.
The lamps are connected to four buttons:
- Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
- Button 2: Changes the state of all the odd numbered lamps.
- Button 3: Changes the state of all the even numbered lamps.
- Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,…
A counter C records the total number of button presses.
When the party starts, all the lamps are ON and the counter C is set to zero.
You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.
在IOI98 的节日宴会上,我们有N(10<=N<=100)盏彩色灯,他们分别从1 到N 被标上号码.
这些灯都连接到四个按钮:
按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮.
按钮2:当按下此按钮,将改变所有奇数号的灯.
按钮3:当按下此按钮,将改变所有偶数号的灯.
按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯.例如:1,4,7…
一个计数器C 记录按钮被按下的次数.
当宴会开始,所有的灯都亮着,此时计数器C 为0.
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态. 写一个程序去找出所有的灯最后可能的与所给出信息相符的状态,并且没有重复.
全排列
每个开关按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按，一共有2^4=16中开关状态。枚举每个按钮是否按下，然后生成结果，看是否满足条件，排序输出即可（注意判重）。
另外，根据四种开关的操作效果，灯状态的周期为6，因此当N>=6时只需处理前6个灯, 排序时转换为10进制数, 输出时反复输出二进制的前6个的状态.