P100 · 极值构型 · 经典问题

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

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

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

纪录对比

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

严格定义

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

当前展示:起步布局

已验证构造186 个 1

帮助理解

一对列能用几次?

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

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

起步布局

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

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

答案怎么写

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

起步布局答案

{
  "rows": [
    "1101000000001000000100000010000",
    "1010001100000000000001000100000",
    "0110100000100000001000000001000",
    "0011010010000000000010000000010",
    "1000110000000100100000100000000",
    "0001101000010001000000001000000",
    "0100010100000011000000010000000",
    "0100001011000000010000100000000",
    "0001000101000100001000000000001",
    "0000010001110000000001000010000",
    "0000000110101000100000001000000",
    "1000000010010010001000000000100",
    "0010000000011100010000010000000",
    "0000100001001010000010000100000",
    "0000001000100110000100000000010",
    "0010000001000001100100000000100",
    "1000000000100001010010000000001",
    "0001000000000010110001000001000",
    "0000010000000000011100001100000",
    "0000001000000000101010010010000",
    "0000000100010000000110100001000",
    "0000000000001001001001100000010",
    "0000100010000000000101010000001",
    "0100000000000100000011001000100",
    "0001000000100000000000110100100",
    "0010000000000010000000101010001",
    "0000000010000101000000000111000",
    "1000000001000000000000011001010",
    "0000100100000000010000000010110",
    "0000011000001000000000000001101",
    "0100000000010000100000000100011"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 31
}

起步布局答案

{
  "rows": [
    "1101000000001000000100000010000",
    "1010001100000000000001000100000",
    "0110100000100000001000000001000",
    "0011010010000000000010000000010",
    "1000110000000100100000100000000",
    "0001101000010001000000001000000",
    "0100010100000011000000010000000",
    "0100001011000000010000100000000",
    "0001000101000100001000000000001",
    "0000010001110000000001000010000",
    "0000000110101000100000001000000",
    "1000000010010010001000000000100",
    "0010000000011100010000010000000",
    "0000100001001010000010000100000",
    "0000001000100110000100000000010",
    "0010000001000001100100000000100",
    "1000000000100001010010000000001",
    "0001000000000010110001000001000",
    "0000010000000000011100001100000",
    "0000001000000000101010010010000",
    "0000000100010000000110100001000",
    "0000000000001001001001100000010",
    "0000100010000000000101010000001",
    "0100000000000100000011001000100",
    "0001000000100000000000110100100",
    "0010000000000010000000101010001",
    "0000000010000101000000000111000",
    "1000000001000000000000011001010",
    "0000100100000000010000000010110",
    "0000011000001000000000000001101",
    "0100000000010000100000000100011"
  ]
}

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

DISCUSSION

讨论区

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

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