题目链接1：点击打开链接
题目链接2：点击打开链接
题目大意：略。
解题思路：
1、输入初始化
2、从头走到尾一遍，统计有效个数，并把最后一个结点的 next = -1
3、从头开始，每 k 个反转链表并将反转后的结果传到最终输出的容器里（注意：不到 k 个无需反转，不要忘记把每段反转以后的新的链表接起来）
4、注意 k==1 的情况，有两个点（3、4 测试点）是搞这个的，我是自己特判处理的（因为无需反转）。换句话说：一是结点数能整除 K 的，二是不能整除的。当能整除时，一定注意调整最后的那个-1。以及 K 也有可能大于有效节点数。
5、考虑 cout、cin 容易超时的问题，用 scanf、printf 替代。
未 AC 代码（测试点5 WA，就是那组数据很大的那组，真不知道什么情况没考虑到~）
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; struct node { int id,cur,nx,pre; }nds[maxn], ndrs[maxn]; int l, len, F; node tnd; void showInit(int h) { puts("-----------------------"); int cur=h; for(int i=0;i<len;i++) { printf("%05d %d %05d\n",nds[cur].cur,nds[cur].id,nds[cur].nx); cur=nds[cur].nx; } puts("-----------------------"); } void reverseList(int s, int e) { if(l>0) ndrs[l-1].nx=e; int cur=e,pre,jde=nds[s].pre; while(1) { pre=nds[cur].pre; nds[cur].nx=pre; ndrs[l++]=nds[cur]; if(jde==pre) return; cur=pre; } } int main() { int h,n,k; while(~scanf("%d%d%d",&h,&n,&k)) { int cur,id,nx; for(int i=0;i<n;i++) { scanf("%d%d%d",&cur,&id,&nx); nds[cur].id=id, nds[cur].cur=cur, nds[cur].nx=nx; } // if(h==-1){ puts("-1"); continue; } // 从头走到尾一遍，统计有效个数，并把它们各自的前置地址找到，以及把最后一个结点的 next = -1 int pre=-2; cur=h; len=0; int f=1; while(1) { nds[cur].pre=pre; pre=cur; cur=nds[cur].nx; len++; if(len==k) F=pre; if(cur==-1 || nds[cur].id==0) { nds[pre].nx=-1; break; } } if(len<k) k=1; // printf("Last == cur : %05d, nx : %d\n",pre,nds[pre].nx); // cout<<len<<endl; // showInit(h); // 从头开始，每 k 个反转链表并将反转后的结果传到最终输出的容器里（注意：不到 k 个无需反转，而且每次把上一组的衔接修复好） l=0; cur=h; int th, t=0, tcur; while(k!=1) // k==1 无需反转 { cur=nds[cur].nx; t++; if(t==k-1 && cur!=-1) { // printf("h: %05d, t: %05d\n",h,cur); t=0; th=nds[cur].nx; reverseList(h,cur); tcur=cur=h=th; // show(); } if(cur==-1) break; } if(len%k!=0) ndrs[l-1].nx=tcur; // 修复好最后一组未修复的 while(len%k!=0 && tcur!=-1) { ndrs[l++]=nds[tcur]; tcur=nds[tcur].nx; } if(k==1) // 特判 { while(1) { ndrs[l++]=nds[cur]; cur=nds[cur].nx; if(cur==-1) break; } } for(int i=0;i<l;i++) { if(i==len-1) printf("%05d %d -1\n",ndrs[i].cur,ndrs[i].id); else printf("%05d %d %05d\n",ndrs[i].cur,ndrs[i].id,ndrs[i].nx); // cur=ndrs[cur].nx; } } return 0; } /* 附赠一些有代表性的测试用例 00100 6 4 00000 4 99999 00100 1 12300 68288 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 8 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 12345 7 45678 45678 8 98765 00100 2 1 00100 1 12309 12309 2 -1 -1 1 1 00100 1 -1 00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 -1 99999 5 68237 12309 2 33218 */
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+5; int da[maxn], nx[maxn], a[maxn]; int main() { int first,n,k,t,len; while(~scanf("%d%d%d",&first,&n,&k)) { for(int i=0;i<n;i++) { scanf("%d",&t); scanf("%d%d",&da[t],&nx[t]); } len=0; while(first!=-1) { a[len++]=first; first=nx[first]; } int times=len/k; for(int i=0,j=0; j<times; i+=k, j++) reverse(a+i,a+i+k); for(int i=0;i<len-1;i++) printf("%05d %d %05d\n",a[i],da[a[i]],a[i+1]); printf("%05d %d -1\n",a[len-1],da[a[len-1]]); } return 0; }
