P100 · 极值构型 · 经典问题

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

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

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

纪录对比

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

严格定义

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

当前展示:起步布局

已验证构造115 个 1

帮助理解

一对列能用几次?

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

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

起步布局

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

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

答案怎么写

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

起步布局答案

{
  "rows": [
    "11010000001000000000010",
    "10100100000010000000001",
    "01101000010000000001000",
    "00110001100000001000000",
    "10001010100000000000100",
    "00010110010000010000000",
    "00001101001000100000000",
    "01000011000010000010000",
    "00000000111100000000001",
    "01000100000101001000000",
    "00100010000100100000010",
    "10000001000100010100000",
    "00011000000011000100000",
    "10000000010001100010000",
    "00100000001001010000100",
    "00000000100010110001000",
    "00000010001000001101000",
    "00001000000000011010001",
    "00000100100000000110010",
    "00010000000100000011100",
    "00000000010010001000110",
    "01000000000000100100101",
    "00000001000001000001011"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 23
}

起步布局答案

{
  "rows": [
    "11010000001000000000010",
    "10100100000010000000001",
    "01101000010000000001000",
    "00110001100000001000000",
    "10001010100000000000100",
    "00010110010000010000000",
    "00001101001000100000000",
    "01000011000010000010000",
    "00000000111100000000001",
    "01000100000101001000000",
    "00100010000100100000010",
    "10000001000100010100000",
    "00011000000011000100000",
    "10000000010001100010000",
    "00100000001001010000100",
    "00000000100010110001000",
    "00000010001000001101000",
    "00001000000000011010001",
    "00000100100000000110010",
    "00010000000100000011100",
    "00000000010010001000110",
    "01000000000000100100101",
    "00000001000001000001011"
  ]
}

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

DISCUSSION

讨论区

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

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