P100 · 极值构型 · 经典问题

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

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

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

纪录对比

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

严格定义

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

当前展示:起步布局

已验证构造105 个 1

帮助理解

一对列能用几次?

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

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

起步布局

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

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

答案怎么写

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

起步布局答案

{
  "rows": [
    "110100010000000000001",
    "101000100100000010000",
    "011010000000010100000",
    "001101000000101000000",
    "100011001000000001000",
    "000110100010000000010",
    "010001100001000000100",
    "001000011001000000010",
    "000010010100100000100",
    "010000001110001000000",
    "000001010010010010000",
    "100000000011100100000",
    "000100000101010001000",
    "000000101000110000001",
    "000000110000001101000",
    "000010000001001010001",
    "000100001000000110100",
    "010000000000100011010",
    "100000000000011000110",
    "001000000010000001101",
    "000001000100000100011"
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 21
}

起步布局答案

{
  "rows": [
    "110100010000000000001",
    "101000100100000010000",
    "011010000000010100000",
    "001101000000101000000",
    "100011001000000001000",
    "000110100010000000010",
    "010001100001000000100",
    "001000011001000000010",
    "000010010100100000100",
    "010000001110001000000",
    "000001010010010010000",
    "100000000011100100000",
    "000100000101010001000",
    "000000101000110000001",
    "000000110000001101000",
    "000010000001001010001",
    "000100001000000110100",
    "010000000000100011010",
    "100000000000011000110",
    "001000000010000001101",
    "000001000100000100011"
  ]
}

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

DISCUSSION

讨论区

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

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