[POJ - 2100] Graveyard Design(尺取法)

題目傳送門：Here

來源：Northeastern Europe 2004, Northern Subregion

Time Limit: 10000MS Memory Limit: 64000K

Case Time Limit: 2000MS

Description

King George has recently decided that he would like to have a new

design for the royal graveyard. The graveyard must consist of several

sections, each of which must be a square of graves. All sections must

have different number of graves. After a consultation with his

astrologer, King George decided that the lengths of section sides must

be a sequence of successive positive integer numbers. A section with

side length s contains s^2 graves. George has estimated the total

number of graves that will be located on the graveyard and now wants

to know all possible graveyard designs satisfying the condition. You

were asked to find them.

Input

Input file contains n — the number of graves to be located in the

graveyard (1 <= n <= 10^14 ).

Output

On the first line of the output file print k — the number of

possible graveyard designs. Next k lines must contain the descriptions

of the graveyards. Each line must start with l — the number of

sections in the corresponding graveyard, followed by l integers —

the lengths of section sides (successive positive integer numbers).

Output line’s in descending order of l.

Sample Input

Sample Output

2
4 21 22 23 24
3 25 26 27
           

解析

給一個數，存在連續遞增序列的平方和等于此數，并将這些序列按照長度遞減順序獨立一行輸出，并且每一行的開頭要輸出序列長度（如題，21,22,23,24平方和等于2030）

某段連續序列滿足條件，聯想到尺取法。先截取到的長度一定是最長的，但是題目要求統計序列數量，即序列需要儲存下來等待輸出，是以我開了兩個數組進行左右端點的儲存（整個序列循環來存處理上比較麻煩，況且沒必要）

C語言代碼

#include <stdio.h>
int main(void)
{
    long long S;
    while(~scanf("%lld",&S))			//爆int要開long long
    {
        int r[5000],l[5000];
        long long i=1,j=1,sum=0;
        int m,n,cnt=0;
        while(1)		//尺取代碼
        {
	            while(j*j<=S&&sum<S)		
	                sum+=j*j,j++;
	            if(sum<S) break;
	            if(sum==S)	//滿足條件時的處理
	            {
	                l[cnt]=i;	//儲存左端點
	                r[cnt]=j;	//儲存右端點
	                cnt++;		//記錄序列個數
	            }
	            sum-=i*i;
	            i++;
        }
        //以下為輸出的代碼
        printf("%d\n",cnt);
        for(m=0;m<cnt;m++)
        {
            printf("%d",r[m]-l[m]);
            for(n=l[m];n<r[m];n++)
                printf(" %d",n);
            printf("\n");
        }
    }
}
           

淺談

尺取的思想了解起來并不困難，抓住左右端點移動的條件就好。做了幾道尺取的題目後發現：不滿足條件右端點右移（+），否則左端點右移（-）也可記成 滿減少加。

(滑稽.jpg)