[北大集训 2021] 末日魔法少女计划

Luogu

IDLGP8984

Time2000ms

Memory512MB

DifficultyP7

2021Special JudgeO2优化CTT（清华集训/北大集训）

对于给定的 $n,k$，你需要构造一个只含 $0,1$ 的矩阵 $A_{i,j}$，$0\le i,j\le n$，满足： 1. $A_{i,i}=1$； 2. $A_{i,i+1}=1$； 3. 对 $i>j$ 有 $A_{i,j}=0$； 4. 若 $A_{i,j}=1$，$j-i>1$，则存在 $i<t<j$，满足 $A_{i,t}=A_{t,j}=1$； 5. 对 $i\le j$ 有 $(A^k)_{i,j}>0$。你需要输出满足 $A_{i,j}=1$ 且 $j-i>1$ 的每个 $(i,j)$，设这样的 $(i,j)$ 共有 $m$ 个。若输出不满足要求，则不能得到该测试点的任何分数。若输出满足要求，则根据 $m$ 进行评分。 ## Input 一行，两个整数 $n,k$。 ## Output 第一行一个整数 $m$，接下来 $m$ 行，每行两个整数 $i,j$，依次表示每个满足 $A_{i,j}=1$ 且 $j-i>1$ 的二元组 $(i,j)$。 [samples] ## Background CTT2021 D1T1 ## Note - $1900\le n\le 2000$； - $2\le k\le 15$。 | $k$ | $f(k)$ | $s(k)$ | | :--: | :------: | :----: | | $2$ | $7.9870$ | $22$ | | $3$ | $3.8085$ | $14$ | | $4$ | $2.3960$ | $11$ | | $5$ | $1.9610$ | $9$ | | $6$ | $1.6065$ | $7$ | | $7$ | $1.4515$ | $6$ | | $8$ | $1.2540$ | $5$ | | $9$ | $1.1980$ | $5 $ | | $10$ | $1.0995$ | $4$ | | $11$ | $1.0705$ | $4 $ | | $12$ | $1.0345$ | $4$ | | $13$ | $1.0120$ | $3$ | | $14$ | $1.0015$ | $3 $ | | $15$ | $0.9940$ | $3$ | 每个 $2\le k\le 15$ 对应一个总分为 $s(k)$ 的子任务，每个子任务的得分是子任务中每个测试点的得分的最小值。每个测试点的得分为所在子任务的总分的 $\max\left(0,1-\sqrt{\max\left(0,\frac{m}{n\cdot f(k)}-1\right)}\right)$ 倍。

Samples

Input #1

3 2

Output #1

1
0 2

API Response (JSON)

{
  "problem": {
    "name": "[北大集训 2021] 末日魔法少女计划",
    "description": {
      "content": "对于给定的 $n,k$，你需要构造一个只含 $0,1$ 的矩阵 $A_{i,j}$，$0\\le i,j\\le n$，满足： 1. $A_{i,i}=1$； 2. $A_{i,i+1}=1$； 3. 对 $i>j$ 有 $A_{i,j}=0$； 4. 若 $A_{i,j}=1$，$j-i>1$，则存在 $i<t<j$，满足 $A_{i,t}=A_{t,j}=1$； 5. 对 $i\\le j$ 有 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8984"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于给定的 $n,k$，你需要构造一个只含 $0,1$ 的矩阵 $A_{i,j}$，$0\\le i,j\\le n$，满足：\n\n1. $A_{i,i}=1$；\n2. $A_{i,i+1}=1$；\n3. 对 $i>j$ 有 $A_{i,j}=0$；\n4. 若 $A_{i,j}=1$，$j-i>1$，则存在 $i<t<j$，满足 $A_{i,t}=A_{t,j}=1$；\n5. 对 $i\\le j$ 有 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments