數(shù)學(xué)找規(guī)律的題，先暴力打表觀察有什么規(guī)律八回，發(fā)現(xiàn)每個(gè)數(shù)只需要三個(gè)以內(nèi)的三角形數(shù)的和就可以表示。
用限制步數(shù)的DFS搜索驾诈，到最后一步時(shí)加上二分優(yōu)化缠诅。
打表是很重要的。
#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;
}