P100 · 极值构型 · 经典问题

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

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

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

纪录对比

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

严格定义

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

当前展示:起步布局

已验证构造130 个 1

帮助理解

一对列能用几次?

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

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

起步布局

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

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

答案怎么写

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

起步布局答案

{
  "rows": [
    "1101000000001000000100000",
    "1010001100000000000001000",
    "0110100000100000001000000",
    "0011010010000000000010000",
    "1000110000000100100000100",
    "0001101000010001000000001",
    "0100010100000011000000010",
    "0100001011000000010000100",
    "0001000101000100001000000",
    "0000010001110000000001000",
    "0000000110101000100000001",
    "1000000010010010001000000",
    "0010000000011100010000010",
    "0000100001001010000010000",
    "0000001000100110000100000",
    "0010000001000001100100000",
    "1000000000100001010010000",
    "0001000000000010110001000",
    "0000010000000000011100001",
    "0000001000000000101010010",
    "0000000100010000000110100",
    "0000000000001001001001100",
    "0000100010000000000101010",
    "0100000000000100000011001",
    "0001000000100000000000110"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 25
}

起步布局答案

{
  "rows": [
    "1101000000001000000100000",
    "1010001100000000000001000",
    "0110100000100000001000000",
    "0011010010000000000010000",
    "1000110000000100100000100",
    "0001101000010001000000001",
    "0100010100000011000000010",
    "0100001011000000010000100",
    "0001000101000100001000000",
    "0000010001110000000001000",
    "0000000110101000100000001",
    "1000000010010010001000000",
    "0010000000011100010000010",
    "0000100001001010000010000",
    "0000001000100110000100000",
    "0010000001000001100100000",
    "1000000000100001010010000",
    "0001000000000010110001000",
    "0000010000000000011100001",
    "0000001000000000101010010",
    "0000000100010000000110100",
    "0000000000001001001001100",
    "0000100010000000000101010",
    "0100000000000100000011001",
    "0001000000100000000000110"
  ]
}

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

DISCUSSION

讨论区

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

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