Poj 2100: Graveyard Design

poj2100.md

Poj 2100: Graveyard Design

題目

分析

尋找一個連續區間，他們的平方和等於 q，問這種區間有幾個，分別是那些區間……

爬行法輕鬆解

證明就不給了，很簡單自己證

但要注意題目要求須將這些區間依區間長度由大到小輸出，所以要排序。

AC code

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
typedef long long ll;

struct Range {
    ll l, r;
    bool operator > (const Range& a) const {
        return r - l + 1 > a.r - a.l + 1;
    }
};

vector<Range> ans;

void solve(ll q) {
    ll l = 1, r = 1, sum = 0; // l, r 從 1 開始，而非 0，要不然當 q = 1 之類的會出錯
    for (;;) {
        while (r * r <= q && sum < q) {
            sum += r * r;
            r++;
        }

        if (sum < q)
            break;
        if (sum == q)
            ans.push_back(Range{l, r-1});

        sum -= l * l;
        l++;
    }

    sort(ans.begin(), ans.end(), greater<Range>());
}

int main() {
    ll q;
    scanf("%lld", &q);
    solve(q);

    int K = ans.size();
    printf("%d\n", K);
    for (int i = 0; i < K; i++) {
        printf("%lld", ans[i].r - ans[i].l + 1);
        for (ll j = ans[i].l; j <= ans[i].r; j++)
            printf(" %lld", j);
        printf("\n");
    }

    return 0;
}