|
Problem Statement
|
|||||||||||||
|
|
 F is a function that is defined on all real numbers from
the closed interval [1,N]. You are given a vector <int> Y with N
elements. For each i (1 <= i <= N) we have F(i) = Y[i-1]. Additionally,
you know that F is piecewise linear: for each i, on the interval [i,i+1] F is
a linear function. The function F is uniquely determined by this information.
For example, if F(4)=1 and F(5)=6 then we must have F(4.7)=4.5.As another example, this is the plot of the function F for Y = {1, 4, -1, 2}. You are also given a vector <int> query. For each i, compute the number of solutions to the equation F(x) = query[i]. Note that sometimes this number of solutions can be infinite. Return a vector <int> of the same length as query. For each i, element i of the return value should be -1 if the equation F(x) = query[i] has an infinite number of solutions. Otherwise, element i of the return value should be the actual number of solutions this equation has. |
||||||||||||
|
Definition
|
|||||||||||||
|
|
|
||||||||||||
|
|
|||||||||||||
|
Constraints
|
|||||||||||||
|
-
|
Y will contain between 2 and 50 elements,
inclusive.
|
||||||||||||
|
-
|
Each element of Y will be between -1,000,000,000
and 1,000,000,000, inclusive.
|
||||||||||||
|
-
|
query will contain between 1 and 50 elements,
inclusive.
|
||||||||||||
|
-
|
Each element of query will be between
-1,000,000,000 and 1,000,000,000, inclusive.
|
||||||||||||
|
Examples
|
|||||||||||||
|
0)
|
|||||||||||||
|
|
|
||||||||||||
|
1)
|
|||||||||||||
|
|
|
||||||||||||
|
2)
|
|||||||||||||
|
|
|
||||||||||||
|
3)
|
|||||||||||||
|
|
|
||||||||||||
This problem statement is the exclusive and proprietary
property of TopCoder, Inc. Any unauthorized use or reproduction of this
information without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
[Thoughts]
把Y中连续的两个数字作为一个区间，然后对于每一个Q[i]，遍历所有Y区间，统计覆盖次数即可。
[Code]
1: #include<vector>
2: using namespace std;
3: class PiecewiseLinearFunctionDiv2
4: {
5: public:
6: vector <int> countSolutions(vector <int> Y, vector <int> query)
7: {
8: vector<int> result;
9: for(int i =0; i< query.size(); i++)
10: {
11: int searchNum = query[i];
12: int start = 0;
13: int solution=0;
14: if(searchNum == Y[start]) solution++;
15: for(int j =1; j< Y.size(); j++)
16: {
17: if(max(Y[start], Y[j]) > searchNum && min( Y[start], Y[j]) < searchNum)
18: {
19: solution++;
20: }
21: if(searchNum == Y[j])
22: {
23: if(searchNum == Y[start])
24: {
25: solution =-1;
26: break;
27: }
28: solution++;
29: //j++;
30: }
31: start = j;
32: }
33: result.push_back(solution);
34: }
35: return result;
36: }
37: };
Problem Statement 1000P |
|||||||||||||
| In this problem, all strings consist of uppercase English letters
only. That is, there are 26 distinct letters. The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L. For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.) You are given a int L. Consider all strings of length L. Compute the weight of each of these strings. The strings with the minimum weight among all of them are called light. Your task is to count the number of light strings of length L. Since this count may be very large, return it modulo 1,000,000,009. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | L will be between 1 and 1000, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
[Thoughts]
这题就是一个排列组合题。
首先当L<=26的时候，毫无疑问，最小的字符串就是由不同的字符构成的，权重为0，那么等价于在26个字符中，挑L个进行组合，结果就是P(26,L) = (26!)/(L!). （P是指排列数）
那么当L>26的时候呢？我们可以把问题缩小规模，来看看规律。
假设当前问题是，给定{a,b,c}三种字符，问当L=4的时候，权重最小的字符串有哪些？
我们已经知道L=3的时候，最小的字符有6个：
ABC
ACB
BAC
BCA
CAB
CBA
现在要再加一个字符，怎么加？以ABC为例，无论再加一个什么字符，这个字符都得和同样的字符在一起才能获得最小权重，这个很容易理解，因为同类的放在一起，right-left是最小的。那么ABC的衍生就有
AABC 权重1
ABBC 权重1
ABCC 权重1
同理推导其他最小权重字符的时候，都适用同样的规则，即同样的字符放在一起，最终的权重是最小的。
这样，问题就简单了，对于任意L的长度，我们把它切成26段，每一段赋给一个独立的字符就好了，那么这种排列组合共有多少个呢？
如上图，把L长度的字符串切成26段，这就意味着在(L-1)个空挡中挑出25个来插入分界符， 有C(L-1, 25)种可能（C是指组合数），对于26段，每段给一个字符的话，有P(26,26)种排列方式，所以这样的排列组合数共有
C(L-1, 25) * P(26, 26) = (L-1)!/( (L-26)! * (25!) ) * 26! = P(L-1, 25) *26
这里之所以要做这一步转换的原因，是为了避免处理基于余数的除法。组合数是带除法的，而排列数仅是乘法，实现简单。
[Code]
1: int mod = 1000000009;
2: class StringWeightDiv2
3: {
4: public:
5: long Permutation(int n, int m)
6: {
7: long result=1;
8: for(int i =0; i< m; i++)
9: {
10: result*=n;
11: result%=mod;
12: n--;
13: }
14: return result;
15: }
16: int countMinimums(int L)
17: {
18: if(L<=26) return Permutation(26, L);
19: else
20: return Permutation(L-1, 25)*26%mod;
21: }
22: };
