回答 2 已采纳 Little Dara has recently learned how to write a few letters of the English alphabet (say k letters). He plays a game with his little sister Sara. He draws a grid on a piece of paper and writes p instances of each of the k letters in the grid cells. He then asks Sara to draw as many side-to-side horizontal and/or vertical bold lines over the grid lines as she wishes, such that in each rectangle containing no bold line, there would be p instances of one letter or nothing. For example, consider the sheet given in Figure 1, where Sara has drawn two bold lines creating four rectangles meeting the condition above. Sara wins if she succeeds in drawing the required lines. Dara being quite fair to Sara, wants to make sure that there would be at least one solution to each case he offers Sara. You are to write a program to help Dara decide on the possibility of drawing the right lines.
Figure 1. Part of a sample sheet and two dividing bold lines: The
data for this figure is given in the first test case of the sample input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case consists of two integers k (1 <= k <= 26), the number of different letters, and p (1 <= p <= 10), the number of instances of each letter. Followed by the first line, there are k lines, one for each letter, each containing p pairs of integers (xi, yi) for 1 i p. A pair indicates coordinates of the cell on the paper where one instance of the letter is written. The coordinates of the upper left cell of the paper is assumed to be (1,1). Coordinates are positive integers less than or equal to 1,000,000. You may assume that no cell contains more than one letter.
There should be one line per test case containing a single word YES or NO depending on whether the input paper can be divided successfully according to the constraints stated in the problem.
6 4 8 4
4 2 2 1
2 3 2 4
1 1 3 1 5 1
2 1 4 1 6 1
2 2 4 2 8 1
回答 1 已采纳 Problem Description
You are given a long string and looking for certain patterns in the string.
The string contains only lowercase letters (a−z), and it is represented in a compressed format. Denoting S1,S2,... as compressed strings, another compressed string S is defined recursively in one of the following ways:
⋅ S can be any string consisting of only lowercase letters (a−z).
⋅ S can be generated by repeating another string for any times. Specifically, S is represented as “R(S1)”, which means that the content of S1 is repeated R times.
⋅ S can also be the concatenation of other strings. Specifically, S is represented as “S1,S2...SL”, which means S is the concatenation of S1,S2,...,SL.
⋅An empty string (“”) is also a valid representation.
Formally, the Backus–Naur Form (BNF) specification of the syntax is
::= “” | | | “(” “)”
For example, the string “baaabbaaab” can be compressed as “b3(a)2(b)3(a)b”. It can also be compressed as “2(b3(a)b)”.
On the other hand, you find deterministic finite automaton (DFA) as powerful way to describe the patterns you are looking for. A DFA contains a finite set of states Q and a finite set of input symbols called the alphabet Σ. Initially, the DFA is positioned at the start state q0∈Q. Given the transition function δ(q,a) and an input symbol a, the DFA transit to state δ(q,a) if its current state is q.
Let w=a1a2...an be a string over the alphabet Σ. According to the above definition, the DFA transits through the following sequence of states.
The DFA also contains a set of accept states F⊆Q. If the last state qn is an accept state, we say that the DFA accepts the string w. The set of accepted strings is referred as the language that the DFA represents.
Now you are given a compressed string S and a DFA A. You want to know if A accepts the decompressed content of S.
The first line of input contains a number T indicating the number of test cases (T≤200).
The first line of each test case contains a non-empty compressed string S, as described above. The length of S is not greater than 10000, and 0≤R≤109. It is guaranteed that the representation of S is valid.
The description of the DFA follows.
The first line of the description contains three integers N, M, and K, indicating the number of states, the number of rules describing the transition function, and the number of accept states (1≤K≤N≤1000,0≤M≤26N). The states are numbered from 0 to N−1. The start state is always 0.
The second line contains K integers representing the accept states. All these numbers are distinct.
Each of the next M lines consists of two states p and q, and an input symbol a, which means that the DFA transits from p to q when it receives the symbol a. The symbol a is always a lowercase letter. It is guaranteed that, given p and a, the next state q is unique.
For each test case, output a single line consisting of “Case #X: Y”. X is the test case number starting from 1. Y is “Yes” if the DFA accepts the string, or “No” otherwise.
2 3 1
0 1 b
1 0 b
1 1 a
2 2 1
0 1 b
1 0 a
2 4 1
0 1 b
0 1 a
1 0 a
1 0 b
Case #1: Yes
Case #2: No
Case #3: Yes
回答 1 已采纳 Problem Description
The Romans used letters from their Latin alphabet to represent each of the seven numerals in their number system. The list below shows which
letters they used and what numeric value each of those letters represents:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
Using these seven numerals, any desired number can be formed by following the two basic additive and subtractive rules. To form a number using
the additive rule the Roman numerals are simply written from left to right in descending order, and the value of each roman numeral is added
together. For example, the number MMCLVII has the value 1000 + 1000 + 100 + 50 + 5 + 1 + 1 = 2157. Using the addition rule alone could lead to
very long strings of letters, so the subtraction rule was invented as a result. Using this rule, a smaller Roman numeral to the left of a larger one is
subtracted from the total. In other words, the number MCMXIV is interpreted as 1000 - 100 + 1000 + 10 - 1 + 5 = 1914.
Over time the Roman number writing system became more standardized and several additional rules were developed. The additional rules used today
1. The I, X, or C Roman numerals may only be repeated up to three times in succession. In other words, the number 4 must be represented as IV
and not as IIII.
2. The V, L, or D numerals may never be repeated in succession, and the M numeral may be repeated as many 2. times as necessary.
3. Only one smaller numeral can be placed to the left of another. For example, the number 18 is represented as XVIII but not as XIIX.
4. Only the I, X, or C can be used as subtractive numerals.
5. A subtractive I can only be used to the left of a V or X. Likewise a X can only appear to the left of a L or C, and a C can only be used to the
left of a D or M. For example, 49 must be written as XLIX and not as IL.
Your goal is to write a program which converts Roman numbers to base 10 integers.
The input to this problem will consist of the following:
A line with a single integer "N" (1 ≤ N ≤ 1000), where N indicates how many Roman numbers are to be converted.
A series of N lines of input with each line containing one Roman number. Each Roman number will be in the range of 1 to 10,000 (inclusive)
and will obey all of the rules laid out in the problem's introduction.
For each of the N Roman numbers, print the equivalent base 10 integer, one per line.
回答 3 已采纳 Erlang中的变量大部分情况下是"不可变"的(进程数据区域等特殊的除外), 据称是和并行相关, 不过这里我比较困惑, 既然Erlang进程设置了消息系统, 理论上讲消息都是一个一个处理的, 即:同一个进程中的消息处理不存在并行情况, 因此无需要"边量不变". 如果是在多进程情况下, 由于进程的数据之间是切分开的, 看起来也不太需要"变量不变"这个特性, why???
备注: 本人初学Erlang, 理解错误的地方希望前辈们指点.
根据night_stalker的回答, 看起来immutable是和"并行"没有太大关系的了... 还有别的方面的特性决定需要使用immutable的么???
感谢night_stalker, 又去查了下资料, 应该是和进程调度有关, 详细见这里 : http://hi.baidu.com/timeless/blog/item/3f3dafc3cb84835db319a8ae.html
另, to night_stalker, Erlang里应该不直接支持global-var的把...每个进程都有自己独立的数据区域, 相互之间应该是不share的...