P100 · 极值构型 · 经典问题

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

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

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

纪录对比

1 的个数 · 越大越好
纪录数值 / 区间作者 / 持有人来源
已证明最优165Narjess Afzaly & Brendan McKayExtremal Graphs and Turan Numbers ↗
本站纪录暂无选手纪录——

严格定义

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

当前展示:起步布局

已验证构造165 个 1

帮助理解

一对列能用几次?

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

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

起步布局

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

最优值已获严格证明,无法继续提升提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
ANSWER FORMAT

答案怎么写

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

起步布局答案

{
  "rows": [
    "11010000000010000001000000100",
    "10100011000000000000010001000",
    "01101000001000000010000000010",
    "00110100100000000000100000000",
    "10001100000001001000001000000",
    "00011010000100010000000010000",
    "01000101000000110000000100000",
    "01000010110000000100001000000",
    "00010001010001000010000000000",
    "00000100011100000000010000100",
    "00000001101010001000000010000",
    "10000000100100100010000000001",
    "00100000000111000100000100000",
    "00001000010010100000100001000",
    "00000010001001100001000000000",
    "00100000010000011001000000001",
    "10000000001000010100100000000",
    "00010000000000101100010000010",
    "00000100000000000111000011000",
    "00000010000000001010100100100",
    "00000001000100000001101000010",
    "00000000000010010010011000000",
    "00001000100000000001010100000",
    "01000000000001000000110010001",
    "00010000001000000000001101001",
    "00100000000000100000001010100",
    "00000000100001010000000001110",
    "10000000010000000000000110010",
    "00001001000000000100000000101"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 29
}

起步布局答案

{
  "rows": [
    "11010000000010000001000000100",
    "10100011000000000000010001000",
    "01101000001000000010000000010",
    "00110100100000000000100000000",
    "10001100000001001000001000000",
    "00011010000100010000000010000",
    "01000101000000110000000100000",
    "01000010110000000100001000000",
    "00010001010001000010000000000",
    "00000100011100000000010000100",
    "00000001101010001000000010000",
    "10000000100100100010000000001",
    "00100000000111000100000100000",
    "00001000010010100000100001000",
    "00000010001001100001000000000",
    "00100000010000011001000000001",
    "10000000001000010100100000000",
    "00010000000000101100010000010",
    "00000100000000000111000011000",
    "00000010000000001010100100100",
    "00000001000100000001101000010",
    "00000000000010010010011000000",
    "00001000100000000001010100000",
    "01000000000001000000110010001",
    "00010000001000000000001101001",
    "00100000000000100000001010100",
    "00000000100001010000000001110",
    "10000000010000000000000110010",
    "00001001000000000100000000101"
  ]
}

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

DISCUSSION

讨论区

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

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