首页 > ACM题库 > HDU-杭电 > hdu 3734 How Many W待解决[解题报告]C++
2015
02-22

hdu 3734 How Many W待解决[解题报告]C++

How Many W

问题描述 :

Given a sequence (S_1, S_2, …, S_N) (1 <= S_i <= 1,000,000,000, S_i != S_j), count the number of W, which can be regarded as a quintuple (a, b, c, d, e) satisfying a < b < c < d < e, S_b < S_c < S_a, S_d < S_c < S_e.

输入:

The beginning of the input is an integer T, which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 100,000), which denotes the length of the sequence. The second line is N integer S_1, S_2, …, S_N, which denote the sequence.

输出:

The beginning of the input is an integer T, which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 100,000), which denotes the length of the sequence. The second line is N integer S_1, S_2, …, S_N, which denote the sequence.

样例输入:

2
5
5 1 3 2 4
6
6 1 3 4 2 5

样例输出:

1
3


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。