P100 · 极值构型 · 经典问题 · 难

无矩形 0–1 矩阵 · n = 43

在 n × n 方格中尽量多填 1。任取两行和两列,四个交点不能全是 1。

子题n = 43
目标最大化 1 的个数

纪录对比

1 的个数 · 越大越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好290user480282015MathOverflow ↗
本站纪录暂无选手纪录——

严格定义

  • 容器n 行 n 列的方格,每格填 0 或 1。
  • 矩形取两个不同的行号和两个不同的列号。对应的四格最多有三个 1,矩形内部可以任意填写。
  • 提交提交整张矩阵。全零行和全零列也计入矩阵的大小。
  • 目标每个 1 得一分,求最高总分。
放大编辑并提交 ↗

当前展示:起步布局

已验证构造290 个 1

帮助理解

一对列能用几次?

一行中填了三个 1,就占用了三对列。其他任何一行只要再次占用其中一对,这四个 1 就围成了矩形。

无矩形 0–1 矩阵 n = 43 的当前构型
构型与历史

起步布局

查看构型、求解笔记与纪录历史。

挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
ANSWER FORMAT

答案怎么写

提交 rows 数组,每行是一个长度为 n 的字符串,只含 0 和 1。

起步布局答案

{
  "rows": [
    "0000000010000000010110000000000010011000000",
    "0000001010010000000000000010000001000001001",
    "1000000001000100000000001000010000000101000",
    "0100000101000000000000010100000000010000001",
    "0010000000000101100000000001000000010000000",
    "1000100110000000101000000000000000100000000",
    "1000011000000001000101010000000000000000000",
    "1001000000000000000010000111000100000000000",
    "0010100000000000000001000100000000001001000",
    "0000000000100000000010010000100000100001000",
    "1010000000001000010000000000101000000000001",
    "0000000001100000100000100010001000001000000",
    "1000000000010010000000100000000000010010000",
    "0000000010100011000000001100000000000000010",
    "0101010010000100000000100000100000000000000",
    "0000000100010001000000000000100100001100000",
    "0000000010000000000000010001001000000100100",
    "0000100000000001000010100000010000000000101",
    "0000000000000000100100000100110001000010000",
    "0000000000100100001100000000000100000000001",
    "0000001000000000000000000000011100110000010",
    "0001000000000000100001000000000010000100011",
    "0001000001000001010000000000000001100000000",
    "0000000000000000001001001010100000010000100",
    "0000010000000000000000001001000000101010001",
    "0000100000000100010000010010000000000010010",
    "0000000011001000000001000000000100000010000",
    "0000101001000010000000000001100010000000000",
    "0100000000000001001000000000001010000011000",
    "0011001100100000000000000000000000000010100",
    "0000000100000110000011000000001001000000000",
    "0100001000001000100010001000000000000000000",
    "0100000000110000010001000001010000000000000",
    "0000000000011100000000000100000010100000100",
    "0000000100001000000100100001000000000001010",
    "0001000000001010001000010000010000001000000",
    "0000110000101000000000000000000001010100000",
    "0110000000000010000100000010000000100100000",
    "0000010000000010110000000000000100000001100",
    "0010000000000000000000111000000111000000000",
    "1100000000000000000000000000000001001000110",
    "0000001000000000011000100100000000000100000",
    "0010010001010000001010000000000000000000010"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 43
}

起步布局答案

{
  "rows": [
    "0000000010000000010110000000000010011000000",
    "0000001010010000000000000010000001000001001",
    "1000000001000100000000001000010000000101000",
    "0100000101000000000000010100000000010000001",
    "0010000000000101100000000001000000010000000",
    "1000100110000000101000000000000000100000000",
    "1000011000000001000101010000000000000000000",
    "1001000000000000000010000111000100000000000",
    "0010100000000000000001000100000000001001000",
    "0000000000100000000010010000100000100001000",
    "1010000000001000010000000000101000000000001",
    "0000000001100000100000100010001000001000000",
    "1000000000010010000000100000000000010010000",
    "0000000010100011000000001100000000000000010",
    "0101010010000100000000100000100000000000000",
    "0000000100010001000000000000100100001100000",
    "0000000010000000000000010001001000000100100",
    "0000100000000001000010100000010000000000101",
    "0000000000000000100100000100110001000010000",
    "0000000000100100001100000000000100000000001",
    "0000001000000000000000000000011100110000010",
    "0001000000000000100001000000000010000100011",
    "0001000001000001010000000000000001100000000",
    "0000000000000000001001001010100000010000100",
    "0000010000000000000000001001000000101010001",
    "0000100000000100010000010010000000000010010",
    "0000000011001000000001000000000100000010000",
    "0000101001000010000000000001100010000000000",
    "0100000000000001001000000000001010000011000",
    "0011001100100000000000000000000000000010100",
    "0000000100000110000011000000001001000000000",
    "0100001000001000100010001000000000000000000",
    "0100000000110000010001000001010000000000000",
    "0000000000011100000000000100000010100000100",
    "0000000100001000000100100001000000000001010",
    "0001000000001010001000010000010000001000000",
    "0000110000101000000000000000000001010100000",
    "0110000000000010000100000010000000100100000",
    "0000010000000010110000000000000100000001100",
    "0010000000000000000000111000000111000000000",
    "1100000000000000000000000000000001001000110",
    "0000001000000000011000100100000000000100000",
    "0010010001010000001010000000000000000000010"
  ]
}

提交 rows 数组,每行是一个长度为 n 的字符串,只含 0 和 1。 · 验证器 v1.0.0

DISCUSSION

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖;发言使用与排行榜一致的公开署名,并附带唯一注册编号(#UID)以防冒名。新发言经审核后公开。

暂无讨论,欢迎发表第一篇帖子。