AcWing 4277. 区块反转
原题链接
简单
作者:
fei0825
,
2023-05-24 10:26:07
,
所有人可见
,
阅读 38
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int e[N], ne[N], h, n, k;
int link[N], idx;
void reverse(int p){
while( p!=-1 ){
link[idx++] = p;
p = ne[p];
}//存下地址
int t = (idx-1) / k; //共有多少块,从0开始
h = link[t*k]; //修改头结点为最后一块的第一个结点
int tail = idx - 1; //最后一块的最后一个结点
for( int i=t-1; i>=0; i-- ){
int j = i * k + k - 1; //第i块的最后一个结点
ne[link[j]] = ne[link[tail]]; //第i块的最后一个结点指向上一块最后一个结点的next
ne[link[tail]] = link[i*k]; //上一块最后一个结点指向第i块的第一个结点
tail = j; //记下第 i 块的最后一个结点
}
}
int main(){
scanf("%05d %d %d", &h, &n, &k);
int addr, val, next;
while( n-- ){
scanf("%05d %d %05d", &addr, &val, &next);
e[addr]=val, ne[addr]=next;
}
reverse(h);
int p = h;
while( p!=-1 ){
printf("%05d %d ", p, e[p]);
if( ne[p]!=-1 ) printf("%05d\n", ne[p]);
else puts("-1");
p = ne[p];
}
return 0;
}