1

XiangChao LV 3 @ 7 months ago

h, v, m = map(int, input().split())
i = 0
matrix = []
for i in range(v):
    matrix.append(list(range(i*h, (i+1)*h)))
    i += 1

for i in range(m):
    ID = int(input())
    x, y = ID // h, ID % h
    res = []

    # up
    res.append(str(matrix[x-1][y]))

    # left
    if y != 0:
        res.append(str(matrix[x][y-1]))

    # down
    res.append(str(matrix[(x+1)%v][y]))

    # right
    if y != h-1:
        res.append(str(matrix[x][y+1]))

    # self
    res.append(str(ID))
    print(" ".join(res))

1

fffgrid LV 3 @ 8 months ago

第13组测试数据是不是错了，对于一个列向量的输入，每一个id不都只有上、下和自己有值吗？为什么输出还能有5个数？

1

五哈哈哈 LV 6 @ 8 months ago

给的python if x % n != 1:错了，应该是不等于0

0

hasaki LV 5 @ 8 months ago

这题java解法怎么写都只能过一半用例啊，剩下一半都是超时

import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();// 一行个数
        int v = sc.nextInt();//一列个数
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int target = sc.nextInt();
            //上
            System.out.print((h * v + target - h) % (h * v) + " ");
            //左
            if (target % h != 0) {
                System.out.print((target - 1) + " ");
            }
            //下
            System.out.print((h * v + target + h) % (h * v) + " ");
            //右
            if (target % h != h - 1) {
                System.out.print((target + 1) + " ");
            }
            //中
            System.out.println(target) ;
        }
    }
}

hasaki @ 8 months ago

询问了chatgpt如何优化，将最终结果用stringbuilder包装再输出，可以有效较少io次数，可以通过全部用例，好东西

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();  // 一行个数
        int v = sc.nextInt();  // 一列个数
        int m = sc.nextInt();  // 询问次数
        int size = h * v;      // 总方块数量
        
        StringBuilder result = new StringBuilder();  // 用于存储最终输出，减少I/O调用
        
        for (int i = 0; i < m; i++) {
            int target = sc.nextInt();
            
            // 计算上、下、左、右的块ID
            int top = (size + target - h) % size;
            int below = (size + target + h) % size;
            int left = (target % h != 0) ? target - 1 : -1;
            int right = (target % h != h - 1) ? target + 1 : -1;
            
            // 构建结果
            result.append(top).append(" ");  // 上
            if (left != -1) {
                result.append(left).append(" ");  // 左
            }
            result.append(below).append(" ");  // 下
            if (right != -1) {
                result.append(right).append(" ");  // 右
            }
            result.append(target).append("\n");  // 中
        }
        
        // 最后统一输出结果，减少 I/O 次数
        System.out.print(result.toString());
    }
}

0

TaZi SU @ 9 months ago

题目描述：塔子哥正在设计一个二维平面音游，其中有一个由 (H) 个水平方块和 (V) 个垂直方块组成的网格。每个方块的方块组是指与该方块相邻的所有方块及它自己，垂直方向的方块是首尾相连的。给定一个方块的 (ID)，要求输出该方块组中的所有方块 (ID)，并按照从上到下、逆时针排列的顺序，最后输出的方块 (ID) 放在组的末尾。

输入格式：第一行包含三个正整数 (H), (V), (M)。接下来的 (M) 行，每行输入一个方块的 (ID)。

输出格式：对于每个输入的方块 (ID)，输出对应的方块组，方块 (ID) 以空格分隔。

思路

在这个问题中，我们需要处理的是一个由 ( n ) 行和 ( m ) 列组成的网格，方块的 ID 从 0 到 ( n × m - 1 )。我们的任务是为每个给定的方块 ID 计算它的方块组，即它自己及其周围的方块 ID。

是否构图

首先，我们观察到，给定 ( n ) 和 ( m ) 后，整个图形的结构是固定的。也就是说，方块的相对位置不随时间改变，因此我们不需要动态地构建整个网格，只需通过数学运算来定位方块及其邻居。

如何查询

对每个方块 ID ( x ) 的处理逻辑如下：

垂直方向：
- 上方方块的 ID 可以表示为 ( x - n )，下方方块的 ID 表示为 ( x + n )。
- 由于垂直方向上是首尾相连的，我们可以通过对 ( x - n ) 和 ( x + n ) 进行调整来处理边界情况。具体来说：
  - 如果 ( x - n < 0 )，则我们需要加上 ( n × m )。
  - 如果 ( x + n >= n × m )，则我们需要减去 ( n × m )。
- 为了简化这些操作，我们可以直接将这两个表达式加上 ( n × m )，再取模 ( n × m ) 来确保结果在有效范围内。
水平方向：
- 水平方向的处理相对简单，因为它并不是首尾相连的。我们只需检查 ( x - 1 ) 和 ( x + 1 ) 是否在合法范围内：
  - ( x - 1 ) 必须检查 ( x ) 是否在当前行的最左侧（即 ( x % n != 0 )）。
  - ( x + 1 ) 必须检查 ( x ) 是否在当前行的最右侧（即 ( (x + 1) % n != 0 )）。

时间复杂度分析

对于每个方块 ID 的查询，我们的算法在常数时间内 ( O(1) ) 计算出它的方块组。由于需要处理 ( k ) 个查询，总的时间复杂度为 ( O(k) )。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int main(){
    cin >> n >> m >> k;//输入
    for(int i = 0; i < k; i++){
        int x;
        cin >> x;//输入询问ID
        cout << (x - n + n * m) % (n * m) << " ";//输出ID上方的数字
        if(x % n != 0)cout << x - 1 << " ";//输出ID左方的数字
        cout << (x + n + n * m) % (n * m) << " ";//输出ID下方的数字
        if((x + 1) % n != 0)cout << x + 1 << " ";//输出ID右方的数字
        cout << x << endl; //输出ID
    }
}

python

n, m, k = map(int, input().split())#输入

for _ in range(k):
    x = int(input())#输入询问ID
    print((x - n + n * m) % (n * m), end=" ")#输出ID上方的数字
    if x % n != 1:
        print(x - 1, end=" ")#输出ID左方的数字
    print((x + n + n * m) % (n * m), end=" ")#输出ID下方的数字
    if (x + 1) % n != 0:
        print(x + 1, end=" ")#输出ID右方的数字
    print(x)#输出ID

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//输入
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        for (int i = 0; i < k; i++) {
            int x = scanner.nextInt();//输入询问ID
            System.out.print((x - n + n * m) % (n * m) + " ");//输出ID上方的数字
            if (x % n != 1) {
                System.out.print(x - 1 + " ");//输出ID左方的数字
            }
            System.out.print((x + n + n * m) % (n * m) + " ");//输出ID下方的数字
            if ((x + 1) % n != 0) {
                System.out.print(x + 1 + " ");//输出ID右方的数字
            }
            System.out.println(x);//输出ID
        }
    }
}

Go

package main

import "fmt"

func main() {
    var n, m, k int
    fmt.Scan(&n, &m, &k)//输入

    for i := 0; i < k; i++ {
        var x int
        fmt.Scan(&x)//输入询问ID
        fmt.Printf("%d ", (x-n+n*m)%(n*m))//输出ID上方的数字
        if x%n != 1 {
            fmt.Printf("%d ", x-1)//输出ID左方的数字
        }
        fmt.Printf("%d ", (x+n+n*m)%(n*m))//输出ID下方的数字
        if (x+1)%n != 0 {
            fmt.Printf("%d ", x+1)//输出ID右方的数字
        }
        fmt.Println(x)//输出ID
    }
}

Js

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', (line) => {
    const [n, m, k] = line.trim().split(' ').map(Number);//输入
    for (let i = 0; i < k; i++) {
        rl.on('line', (x) => {
            x = Number(x);//输入询问ID
            process.stdout.write(((x - n + n * m) % (n * m)) + ' ');//输出ID上方的数字
            if (x % n !== 1) {
                process.stdout.write((x - 1) + ' ');//输出ID左方的数字
            }
            process.stdout.write(((x + n + n * m) % (n * m)) + ' ');//输出ID下方的数字
            if ((x + 1) % n !== 0) {
                process.stdout.write((x + 1) + ' ');//输出ID右方的数字
            }
            console.log(x);//输出ID
        });
    }
});

5 solutions

思路

是否构图

如何查询

时间复杂度分析

代码

CPP

python

Java

Go

Js

2023.05.17-暑期实习-第一题-方格音游

Information

Status

Development

Support