首页 > ACM题库 > HDU-杭电 > hdu 3888 Hatsune Miku待解决[解题报告]C++
2015
04-13

hdu 3888 Hatsune Miku待解决[解题报告]C++

Hatsune Miku

问题描述 :

Counting Offspring

Hatsune Miku, Female, Aged 16 (Forever 16…), gain great popularity in 2007 because the “god-like” song “Ievan Polkka”. So, until now, she still often carries a shallot with her…

In order to get fresh shallot any time she wants, she planted many shallots herself in the field. Considered about the lighting and many other reasons, Miku planted her shallot in a straight line (Yeah, one-dimensional if you ask). For convenient, we numbered these shallots from 1 to N. Now we know these N shallots were planted in M times. She planted 1 to L[1] in first time, 1+L[1] to L[1]+L[2] the second time and 1+L[1]+L[2]+…L[M-1] to L[1]+L[2]+…L[M] the Mth time. Of course, L[1]+L[2]+…L[M-1]=N. Each shallot has its height, suppose the ith shallot was planted by Miku in the kth time, then its height is f(i,k)

Counting Offspring

Attention: the mod operation we used here always gives out a non-negative result, that is to say, (-1)%7=6.
One day, Miku comes to her field, finding that the different height is very disturbing, so she decided to use some super power to shave them. Miku has two powers:

  • Slide down: Decrease the height of the shallots numbered from x to y by 1. You can choose x and y freely.(can be slided to negative height, that means into the ground)
  • Pull up: Increase the height of the shallots numbered from x to y by 1. You can choose x and y freely.

Each power costs one minute, Miku wants to let all shallots have the same height. And, in order to remember this special event, Miku decide to plant a shallot seed (treated as a shallot has zero height) between kth and (k+1)th shallot, if kth shallot is the last one, then plant the seed at the end,and of course, this seed must be the same height after shaving. Now Miku wants to know how many different height she can choose as the result height when keep the operation time least.

输入:

Multiple cases (no more than 500), for each case:
The first line contains one integer M(M < 10^4).
Following M sections, each section has two lines.
The first line of the ith section contains three positive integers L[i], D[i] and m[i] (0<L[i], m[i]<10^9, 0<D[i]<10), the second line contains D[i]+1 integers representing A[i][0], A[i][1], … A[i][D[i]] (-100≤A[i][0], A[i][1], … A[i][D[i]]≤100). The last line contains one positive integer K (1≤K≤L[1]+L[2]+…+L[M]).
Input terminates with EOF.

输出:

Multiple cases (no more than 500), for each case:
The first line contains one integer M(M < 10^4).
Following M sections, each section has two lines.
The first line of the ith section contains three positive integers L[i], D[i] and m[i] (0<L[i], m[i]<10^9, 0<D[i]<10), the second line contains D[i]+1 integers representing A[i][0], A[i][1], … A[i][D[i]] (-100≤A[i][0], A[i][1], … A[i][D[i]]≤100). The last line contains one positive integer K (1≤K≤L[1]+L[2]+…+L[M]).
Input terminates with EOF.

样例输入:

1
3 2 10
-2 4 -1
1

样例输出:

1


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。