「网络流24题」魔术球问题-题解

题目传送门: 「Luogu P2765」魔术球问题

题目大意

输入柱子数$n$
满足如下规则

• 每次只能在某根柱子的最上面放球。
• 在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
  输出在第$n$根柱子上最多能放多少球和放置方案

题解

并不打算使用网络流,用贪心即可
贪心策略: 如果可以的话尽可能放在已有的柱子上

代码

#include <bits/stdc++.h>
using namespace std;

vector<int> a[110];
bool can[4010];
int n, ans = 1, cnt;

int main() {
    scanf("%d", &n);
    for (int i = 1; i * i <= 4000; ++i) {
        can[i * i] = true;
    }
    while (true) {
        for (int i = 1; i <= cnt; ++i) {
            if (can[ ans + a[ i ][ a[i].size() - 1 ] ]) {
                a[i].push_back(ans++);
                i = 0;
                continue;
            }
        }
        if (cnt < n) {
            cnt++;
            a[cnt].push_back(ans++);
        } else break;
    }
    printf("%d\n", ans - 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}