荧光显微镜下的搜寻

tobyforever LV 5 SU @ 2025-12-2 11:33:58

C++ 标准解答 (NOIP C++14)

这份代码使用了最直观的四层循环（枚举位置+求和），非常适合初学者理解二维数组的结构。

/**
 * 题目: 荧光显微镜下的搜寻 (Microscope Search)
 * 知识点: 二维数组遍历, 嵌套循环, 子矩阵求和
 */

#include <iostream>
#include <algorithm> // 用于 max

using namespace std;

// 定义稍微大一点的数组，防止溢出
// 全局变量存储在静态区，通常比栈区空间大
int grid[60][60];

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    // 1. 读取二维数组
    // 使用 0-based 索引 (0 到 n-1)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    long long max_fluorescence = -1; // 初始化为一个很小的值

    // 2. 枚举观察窗的左上角位置 (i, j)
    // 行下标范围: 0 到 n-k
    // 列下标范围: 0 到 m-k
    for (int i = 0; i <= n - k; i++) {
        for (int j = 0; j <= m - k; j++) {
            
            // 3. 计算当前 KxK 窗口内的总和
            long long current_sum = 0;
            
            // 遍历窗口内的每一个像素
            for (int x = 0; x < k; x++) {
                for (int y = 0; y < k; y++) {
                    // grid 的绝对坐标是 [i+x][j+y]
                    current_sum += grid[i + x][j + y];
                }
            }

            // 4. 打擂台更新最大值
            if (current_sum > max_fluorescence) {
                max_fluorescence = current_sum;
            }
        }
    }

    cout << max_fluorescence << endl;

    return 0;
}

数据生成器 (Generator)

这个生成器已经更新，确保生成的第 1 组数据与题目描述中的样例完全一致。

请保存为 gen_microscope.cpp 并运行。

/**
 * Project: Microscope Search (Data Generator)
 * Author: Isaac Asimov (AI)
 * Fixed: Sample 1 matches the problem description perfectly.
 */

#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑 (The Ground Truth)
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n, m, k;
        cin >> n >> m >> k;
        
        // 使用 vector 动态管理内存，或直接定义大数组
        vector<vector<int>> grid(n, vector<int>(m));
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                cin >> grid[i][j];

        long long max_sum = -1;
        
        // 枚举左上角
        for(int i=0; i<=n-k; i++) {
            for(int j=0; j<=m-k; j++) {
                long long cur = 0;
                // 计算区域和
                for(int x=0; x<k; x++)
                    for(int y=0; y<k; y++)
                        cur += grid[i+x][j+y];
                
                if(cur > max_sum) max_sum = cur;
            }
        }
        cout << max_sum << endl;
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int n, m, k;
    vector<vector<int>> matrix;

    if (case_id == 1) {
        // 严格复现题目样例 1
        n = 3; m = 4; k = 2;
        matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 1, 2, 3}
        };
    }
    else if (case_id == 2) {
        // 单像素窗口: 找最大值
        n = 5; m = 5; k = 1;
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(1, 100);
    }
    else if (case_id == 3) {
        // 全图窗口: 整个矩阵求和
        n = 6; m = 4; k = 4; // k = min(n,m)
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(1, 10);
    }
    else if (case_id <= 7) {
        // 常规随机
        n = rand_int(10, 20);
        m = rand_int(10, 20);
        k = rand_int(2, min(n, m) - 1);
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(0, 500);
    }
    else {
        // 最大范围
        n = 50; m = 50;
        k = rand_int(5, 15);
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(0, 1000);
    }

    // 写入文件
    fout << n << " " << m << " " << k << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            fout << matrix[i][j] << (j == m-1 ? "" : " ");
        }
        fout << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Microscope Data (Fixed) ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

tobyforever LV 5 SU @ 2025-12-2 11:33:46

C++ 标准解答 (NOIP C++14)

这份代码使用了最直观的四层循环（枚举位置+求和），非常适合初学者理解二维数组的结构。

/**
 * 题目: 荧光显微镜下的搜寻 (Microscope Search)
 * 作者: Isaac Asimov (AI)
 * 知识点: 二维数组遍历, 嵌套循环, 子矩阵求和
 */

#include <iostream>
#include <algorithm> // 用于 max

using namespace std;

// 定义稍微大一点的数组，防止溢出
// 全局变量存储在静态区，通常比栈区空间大
int grid[60][60];

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    // 1. 读取二维数组
    // 使用 0-based 索引 (0 到 n-1)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    long long max_fluorescence = -1; // 初始化为一个很小的值

    // 2. 枚举观察窗的左上角位置 (i, j)
    // 行下标范围: 0 到 n-k
    // 列下标范围: 0 到 m-k
    for (int i = 0; i <= n - k; i++) {
        for (int j = 0; j <= m - k; j++) {
            
            // 3. 计算当前 KxK 窗口内的总和
            long long current_sum = 0;
            
            // 遍历窗口内的每一个像素
            for (int x = 0; x < k; x++) {
                for (int y = 0; y < k; y++) {
                    // grid 的绝对坐标是 [i+x][j+y]
                    current_sum += grid[i + x][j + y];
                }
            }

            // 4. 打擂台更新最大值
            if (current_sum > max_fluorescence) {
                max_fluorescence = current_sum;
            }
        }
    }

    cout << max_fluorescence << endl;

    return 0;
}

数据生成器 (Generator)

这个生成器已经更新，确保生成的第 1 组数据与题目描述中的样例完全一致。

请保存为 gen_microscope.cpp 并运行。

/**
 * Project: Microscope Search (Data Generator)
 * Author: Isaac Asimov (AI)
 * Fixed: Sample 1 matches the problem description perfectly.
 */

#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑 (The Ground Truth)
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n, m, k;
        cin >> n >> m >> k;
        
        // 使用 vector 动态管理内存，或直接定义大数组
        vector<vector<int>> grid(n, vector<int>(m));
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                cin >> grid[i][j];

        long long max_sum = -1;
        
        // 枚举左上角
        for(int i=0; i<=n-k; i++) {
            for(int j=0; j<=m-k; j++) {
                long long cur = 0;
                // 计算区域和
                for(int x=0; x<k; x++)
                    for(int y=0; y<k; y++)
                        cur += grid[i+x][j+y];
                
                if(cur > max_sum) max_sum = cur;
            }
        }
        cout << max_sum << endl;
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int n, m, k;
    vector<vector<int>> matrix;

    if (case_id == 1) {
        // 严格复现题目样例 1
        n = 3; m = 4; k = 2;
        matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 1, 2, 3}
        };
    }
    else if (case_id == 2) {
        // 单像素窗口: 找最大值
        n = 5; m = 5; k = 1;
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(1, 100);
    }
    else if (case_id == 3) {
        // 全图窗口: 整个矩阵求和
        n = 6; m = 4; k = 4; // k = min(n,m)
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(1, 10);
    }
    else if (case_id <= 7) {
        // 常规随机
        n = rand_int(10, 20);
        m = rand_int(10, 20);
        k = rand_int(2, min(n, m) - 1);
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(0, 500);
    }
    else {
        // 最大范围
        n = 50; m = 50;
        k = rand_int(5, 15);
        matrix.resize(n, vector<int>(m));
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                matrix[i][j] = rand_int(0, 1000);
    }

    // 写入文件
    fout << n << " " << m << " " << k << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            fout << matrix[i][j] << (j == m-1 ? "" : " ");
        }
        fout << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Microscope Data (Fixed) ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

ID: 19246
时间: 1000ms
内存: 32MiB
难度: 10
标签: (无)
递交数: 1
已通过: 1
上传者: tobyforever

2 条题解

C++ 标准解答 (NOIP C++14)

数据生成器 (Generator)

C++ 标准解答 (NOIP C++14)

数据生成器 (Generator)

信息

状态

开发

支持

关于

2 条题解

C++ 标准解答 (NOIP C++14)

数据生成器 (Generator)

C++ 标准解答 (NOIP C++14)

数据生成器 (Generator)

荧光显微镜下的搜寻

信息

状态

开发

支持

关于

还没有账户？

登录