[UVA][組合、排容] 12572 - RMQ Overkill
RMQ Overkill
Range minimum query problems are getting more and more common everyday. I used to
consider them as hard problems some years ago, but not anymore. So I decided to make this
harder for everyone. Today you are given a sequence (with 0-based indexing) of non-negative
integers which contains no more than 10000 elements and where each integer is less than 10.
For each possible query (i, j) where (
0| RMQ Overkill |
ij < 10000) [N is the size of the sequence], you
have to find the minimum integer in that range, and add the minimums for all those queries
together. When you are done that, mod the sum with 1000000007 and print.
Input
There will be multiple cases (no more than 120). You must read for cases until EOF.
For each case :
First line, an integer N (
1N10000), the size of the array.
Second line, a string of N characters where i-th character denotes the i-th element of the
sequence.
Output
For each case, one line containing an integer, R, the result described above.
Output Explanation
First case: all possible queries and there results are, (0, 0) = > 1, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 4, (1, 2) = > 3, (2, 2) = > 3. So, R = 1 + 1 + 1 + 4 + 3 + 3 = 13.
Second case: all possible queries and there results are, (0, 0) = > 4, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 1, (1, 2) = > 1, (2, 2) = > 3. So, R = 11.
Third case: all possible queries and there results are, (0, 0) = > 1, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 2, (1, 2) = > 1, (2, 2) = > 1. So, R = 7.
Sample Input
3 143 3 413 3 121
Sample Output
13 11 7
Problem Setter: Pratyai Mazumder
Alternate Solution: Mohammad Hafiz Uddin
題目描述：找出所有區間查詢(最小值)的結果總和。
仔細想一下，所有區間組合個數是 C(n,2) + n。
最後我們用一個特殊的角度去看待這個問題，"請問最小值 <= m 的區間個數有多少個？"
舉個例子：
如 1350432402345604：
問最小值為 0 的個數有多少時，反過來不是 0 是有多少個？
1350432402345604：WAY[0] =
[C(n,2) + n] - [(C(3,2)+3)+(C(4,2)+4)+(C(5,2)+5)+1]
紅色區間獨立抓的時候，自然不會有答案為 0 的區間！藉此得到答案是 0 的區間數。
問最小值 <= 1 的個數有多少時，反過來不是 1 是有多少個？
1350432402345604：WAY[1] =
[C(n,2) + n] - [(C(2,2)+2)+(C(4,2)+4)+(C(5,2)+5)+1]-WAY[0]
紅色區間獨立抓的時候，自然不會有答案為 1 的區間！
記得扣掉答案是 0 的區間個數，藉此得到答案是 1 的區間數。
問最小值 <= 2 的個數有多少時，反過來不是 2 是有多少個？
1350432402345604：WAY[2] =
[C(n,2) + n] - [(C(2,2)+2)+(C(2,2)+2)+1+(C(4,2)+4)+1]-WAY[0]-WAY[1]
紅色區間獨立抓的時候，自然不會有答案為 2 的區間！
記得扣掉答案是 0,1 的區間個數，藉此得到答案是 2 的區間數。
... 類推。希望能明白。
#include <stdio.h>
int main() {
int n;
char s[10005];
while(scanf("%d", &n) == 1) {
scanf("%s", s);
int W[10] = {}, Wtot = 0;
long long ret = 0;
int i, j;
for(i = 0; i < 10; i++) {
int tot = n*(n-1)/2 + n, cnt = 0;
tot -= Wtot;
for(j = 0; j <= n; j++) {
if(s[j] > i+'0')
cnt++;
else {
tot -= cnt*(cnt-1)/2 + cnt;
cnt = 0;
}
}
ret += i * (tot%1000000007);
ret %= 1000000007;
W[i] = tot;
Wtot += tot;
}
printf("%d\n", ret%1000000007);
}
return 0;
}