LGOJ P1254 | 扇区填数

Portal

有一个圆,当输入一个整数 n(1n8)n(1\leq n\leq 8) 后,它被分成 nn 个扇区。

所以圆中有 nn 条分割线。从圆中选取 2 条分割线,可以将圆分割为由连续扇区组成的两部分。又选择所有扇区是被允许的,所以:

i2Cn2+1=n2n+1i\leq 2\cdot C_n^2 +1=n^2-n+1

因为 n8n\leq 8 ,所以 i57i\leq 57。但通过手算,可以 大胆猜想 在本题中上式可以取等号。并且不难发现:当 n5n\leq 5 时,扇区中可以填的最大数为 ii;当 n>5n>5 时,扇区中可填最大数为 22。所以只需爆搜出每一位即可。

Tips & Tricks

  • 计算前缀和来快速枚举区间和
  • 复制一遍是一种处理环形数据的简单方法
  • 用「桶」标记一个数可以被表示

然后就可以写出下面这个四不像:

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
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
#include <algorithm>
int sectorNum, maxSum, currentSum, maxSingle;
int sector[17], prefix[17],flag[23], bucket[58];
void fastWrite(int res) {
if(res > 9) finalWrite(res / 10);
putchar(res % 10 + 48);
return;
}
int fullComb() {
memset(bucket, 0, sizeof bucket);
memcpy(sector + sectorNum +1, sector + 1, sectorNum << 2);
for(int i = 1; i <= sectorNum << 1; ++i)
prefix[i] = prefix[i - 1] + sector[i];
for(int i = 0; i < sectorNum; ++i)
for (int j = i + 1; j <= sectorNum + i; ++j)
bucket[prefix[j] - prefix[i]] = 1;
for(int i = 1; i<= maxSum; ++i) if(!bucket[i]) return 0;
return 1;
}
void depthFirstSearch(int index) {
if(index <= sectorNum)
for(int i = 1; i <= maxSingle; ++i) {
if(flag[i]) continue;
sector[index] = i;
flag[i] = 1;currentSum += i;
if(currentSum <= maxSum) depthFirstSearch(index + 1);
flag[i] = 0;currentSum -= i;
}
else if(currentSum == maxSum && fullComb()) {
for(int i = 1; i <= sectorNum; ++i) fastWrite(sector[i]),putchar(' ');
puts("");
}
return;
}
int main() {
scanf("%d", &sectorNum);
printf("%d\n", maxSum = sectorNum * (sectorNum - 1) + 1);
sector[1] = currentSum = 1;maxSingle = std::min(22, maxSum);
depthFirstSearch(2);
return 0;
}

Download

然而 #6 怎么都卡不过去,吸氧气都没用,所以一定是 Intel Xeon Gold 6149 @ 3.10GHz 单线程性能太蒻。用吸吸夫的 87k 肯定能跑进 700ms。不过考虑到数据范围非常小,所以可以直接打表出省一:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main

import . "fmt"

func main() {
var n int
Scan(&n)
switch n {
case 1:
Print("1\n1")
case 2:
Print("3\n1 2")
case 3:
Print("7\n1 2 4\n1 4 2")
case 4:
Print("13\n1 2 6 4\n1 3 2 7\n1 3 2 7\n1 7 2 3")
case 5:
Print("21\n1 3 10 2 5\n1 5 2 10 3")
case 6:
Print("31\n" +
"1 2 5 4 6 13\n" +
"1 2 7 4 12 5\n" +
"1 3 2 7 8 10\n" +
"1 3 6 2 5 14\n" +
"1 5 12 4 7 2\n" +
"1 7 3 2 4 14\n" +
"1 10 8 7 2 3\n" +
"1 13 6 4 5 2\n" +
"1 14 4 2 3 7\n" +
"1 14 5 2 6 3")
case 7:
Print("43")
case 8:
Print("57\n" +
"1 2 10 19 4 7 9 5\n" +
"1 3 5 11 2 12 17 6\n" +
"1 3 8 2 16 7 15 5\n" +
"1 4 2 10 18 3 11 8\n" +
"1 4 22 7 3 6 2 12\n" +
"1 5 9 7 4 19 10 2\n" +
"1 5 15 7 16 2 8 3\n" +
"1 6 12 4 21 3 2 8\n" +
"1 6 17 12 2 11 5 3\n" +
"1 8 2 3 21 4 12 6\n" +
"1 8 11 3 18 10 2 4\n" +
"1 12 2 6 3 7 22 4")
default:
Print("你谷药丸")
}
}

Download

通过打表可知,上面的猜想对 n=7n=7 不成立,不过这题没有对应的测试数据。另外,两年前这是一个黑题。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。