寻宝

GitHub跳转原题关系图返回列表

记录每层楼梯位置，用循环下标直接定位第 x 个可上楼房间。

OJ: noi_openjudge

题目 ID: ch0112-06

难度:普及+/提高

标签:模拟二分python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

从底层给定房间出发，每层按门牌数字选择循环方向上的第 xx 个有楼梯房间，并累加每层进入房间的门牌数。

思路

每层预处理所有楼梯房间编号。bisect_left 找到从当前房间开始遇到的第一个楼梯，其在楼梯列表中的位置加上 x - 1 再对楼梯数取模，就是目标房间。这样无需逐个数到 xx，适合门牌数字很大的情况。

代码

Python代码

python
from bisect import bisect_left

floor_count, room_count = map(int, input().split())
floors = []

for _ in range(floor_count):
    rooms = [tuple(map(int, input().split())) for _ in range(room_count)]
    stairs = [room for room, (has_stairs, _) in enumerate(rooms) if has_stairs]
    floors.append((rooms, stairs))

room = int(input())
password = 0
for rooms, stairs in floors:
    has_stairs, number = rooms[room]
    password = (password + number) % 20123
    first_stair = bisect_left(stairs, room) % len(stairs)
    room = stairs[(first_stair + number - 1) % len(stairs)]

print(password)

C++代码

cpp
#include <cstdio>
#define mod 20123

int n,m,s;
struct _room {
    int up; //是否有楼梯
    int val; //门牌号
};
_room room[10005][105];

void init(){
    scanf("%d%d",&n,&m);
    int i,j,t1,t2;
    for (i=1;i<=n;i++){
        for (j=0;j<m;j++){
            scanf("%d%d",&room[i][j].up,&room[i][j].val);
        }
    }
    scanf("%d",&s);
}

int cnt= 0;
int men[10005];
int main(){
    init();
    int ans = 0;
    int i,j;
    for (i=1;i<=n;i++){
        cnt=0;
        ans = (ans + room[i][s].val) % mod;
        int first_idx = -1;
        int x = room[i][s].val;
        while(1){
            if( room[i][s].up ) break;
            s = (s+1) % m;
        }
        for (j=0;j<m;j++){
            if( room[i][j].up ){
                men[++cnt] = j;
                if( j == s) first_idx = cnt;
            }
        }
        int pos = (first_idx+x-1) % cnt;
        if( pos == 0)
            pos = cnt;
        s = men[pos];
    }
    printf("%d\n",ans%20123);
    return 0;
}

复杂度

预处理时间和空间为 O(NM)O(NM)，每层定位为 O(log⁡M)O(\log M)。

总结

循环选择第 xx 个元素时，转化为下标加法和取模可避免线性模拟。