ZJU 3768 Continuous Login

数学找规律的题，先暴力打表观察有什么规律，发现每个数只需要三个以内的三角形数的和就可以表示。
用限制步数的DFS搜索，到最后一步时加上二分优化。
打表是很重要的。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define OUT(x) cerr << #x << ": " << (x) << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long LL;

int points(int x) {
    return x * (x + 1) / 2;
}
vector<int> tri;

void output(const vector<int>& out) {
    for (int i = 0; i < SZ(out); ++i) {
        if (i) printf(" ");
        printf("%d", out[i]);
    }
    printf("\n");
}

bool dfs(int N, int cnt, int offset, vector<int>* ans) {
    if (cnt == 1) {
        int k = lower_bound(tri.begin() + offset, tri.end(), N) - tri.begin();
        if (k < SZ(tri) && tri[k] == N) {
            ans->push_back(k);
            output(*ans);
            ans->pop_back();
            return true;
        } else {
            return false;
        }
    }

    for (int i = offset; i >= 0; --i) {
        ans->push_back(i);
        if (dfs(N - tri[i], cnt - 1, i, ans)) {
            return true;
        }
        ans->pop_back();
    }
    return false;
}

int main() {
    tri.reserve((int)sqrt(2.0 * 123456789));
    for (int i = 0; points(i) <= 123456789; ++i) {
        tri.push_back(points(i));
    }

    int T, N;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        vector<int> ans;
        int offset = upper_bound(tri.begin(), tri.end(), N) - tri.begin() - 1;
        for (int cnt = 1; cnt <= 3; ++cnt) {
            if (dfs(N, cnt, offset, &ans)) break;
        }
    }
    return 0;
}