题解：P11925 [PA 2025] 显像管 / Migawka

_droplet_ · 2025-07-17 19:37:48 · 题解

令 i 为最小的非负整数，满足 (10\cdot i-1)^2\ge x，则得分为 \min(100,10\cdot i)。

手搓可以发现，我们至少要有 9801 个状态。

可以通过一行一行的向下蛇形更新状态来实现，考虑这个思路。

1. 构建像素

先构建出一个 错误的 像素，如下。

Time 0
01
10

2. 向右移动

接下来构建出能向右走一整行的 2 \times 100 的像素矩形，如下。

Time 0
011111
100000

Time 1
101111
010000

Time 5
101010
010101

3. 向下移动

下一步要让这个矩形向下移动一格，同时不能继续向下。

Time 5
101010
010101
xxxx10
xxxx00

Time 6
010101
101010
xxxx01
xxxx00

4. 向左移动

接下来向左移动，左侧可以类比第一次向右走。

5. 重复步骤

同上，先向下，在类比之前变换向右。

以此类推，直到最后到最下方无法更新，发现矩阵数刚好为 99 \times 99 + 1 = 9802，可以通过此题。

总结上方推导，得出初始矩形，如下。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<'0';
    for(int j=2;j<=N;j++) cout<<'1'; cout<<'\n';
    for(int i=2;i<=N;i++){
        cout<<'1';
        for(int j=1;j<N-1;j++) cout<<i%2;
        cout<<"0\n";
    }
    return 0;
}