---
title: "区块反转"
created: 2025-11-28
tags:
  - 算法
---

# 区块反转

## 题目 [区块反转](https://www.acwing.com/problem/content/description/4280/)

![[image-47bdae28.png]]

## 思路分析

思路如 翻转单词顺序

先直接用下标做地址模拟存入

然后利用所有值都是由addr索引到的特性

可以直接对addr进行几次翻转操作

使得后面的addr顺序存放在q中

q[i]为当前地址 q[i+1]为下一个地址

![[image-c487ded5.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int e[N],ne[N];

int q[N];

int h,n,m;

int main()

{

    cin>>h>>n>>m;

    while(n--){

        int addr,data,nextaddr;

        cin>>addr>>data>>nextaddr;

        e[addr]=data;

        ne[addr]=nextaddr;//在addr下标处 对应存放数据和指针（地址）

    }

    //把所有的地址取出来进行操作 因为数据都是靠地址索引的 所以只需要对地址操作即可

    int cnt=0;

    for(int i=h;i!=-1;i=ne[i])

        q[cnt++]=i;

    reverse(q,q+cnt);

    for(int i=cnt-1;i>=0;i-=m){

        reverse(q+max(0,i-m+1),q+i+1);

    }

    for(int i=0;i<cnt;i++){

        //经过几次翻转后 现在的对应关系在q中 可以用q中存的addr索引到e里的值

        int addr=q[i],nextaddr=q[i+1];

        printf("%05d %d ",addr,e[addr]);

        if(i==cnt-1)

            cout<<"-1"<<endl;

        else

            printf("%05d\n",nextaddr);

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/链表相关问题/共享|共享]] 🏠 [[00-刷题理模型]] ➡️ [[围圈报数|围圈报数]]