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

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

题目大意

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

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

题解

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

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

https://blog.tonycrane.cc/p/f2e850c0.html

作者

TonyCrane

发布于

2019-05-02

更新于

2020-05-05

许可协议

评论