1110 区块反转

Powered by:NEFU AB-IN

Link

• 1110 区块反转
• • 题意
  • 思路
  • 代码

• 题意

  给定一个单链表 L，我们将每 K 个结点看成一个区块（链表最后若不足 K 个结点，也看成一个区块），请编写程序将 L 中所有区块的链接反转。例如：给定 L 为 1→2→3→4→5→6→7→8，K 为 3，则输出应该为 7→8→4→5→6→1→2→3。

• 思路

  建立单链表后遍历，将每组的头节点放入vector，并逆序，最后输出即可

• 代码

  #include 
  using namespace std;
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            
      ios::sync_with_stdio(false);                                                                                       
      cin.tie(0);                                                                                                        
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair PII;
  const int N = 1e6 + 10;
  
  int h, e[N], ne[N];
  int n, k;
  signed main()
  {
      IOS;
      cin >> h >> n >> k;
      for (int i = 1; i <= n; ++i)
      {
          int addr, data, nxt;
          cin >> addr >> data >> nxt;
          e[addr] = data;
          ne[addr] = nxt;
      }
      vector lst;
      int cnt = 0;
      for (int i = h; ~i; i = ne[i])
      {
          if (cnt == 0)
          {
              lst.push_back(i);
          }
          cnt += 1;
          if (cnt == k)
              cnt = 0;
      }
      vector ans;
      reverse(lst.begin(), lst.end());
      for (auto addr : lst)
      {
          for (int i = addr, cnt = 0; ~i && cnt < k; i = ne[i], cnt++)
          {
              ans.push_back(i);
          }
      }
      for (int i = 0; i < SZ(ans); ++i)
      {
          if (i != SZ(ans) - 1)
              printf("%05d %d %05dn", ans[i], e[ans[i]], ans[i + 1]);
          else
              printf("%05d %d -1n", ans[i], e[ans[i]]);
      }
      return 0;
  }