首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

Codeforces 558 C/D/E 綜合題解:化學轉換、二叉樹出口、字符串區間排序

     編輯:關於C++

558C Amr and Chemistry:最少操作統一數組

題意:n 個數,每次可將某數 ×2 或 ÷2(整除)。求使所有數相等的最少總操作數。

核心觀察:每個數通過除 2 可到達其祖先鏈(如 7→3→1→0),再通過乘 2 可擴展。對於每個數,枚舉其所有可達值及對應步數,統計 cnt[v](有多少數能到達 v)與 sum[v](總步數)。答案為滿足 cnt[v]==n 的最小 sum[v]。

技巧:奇數(除 1 外)除 2 後乘 2 可達 x-1(如 7→3→6),步數 +2。因此向下枚舉時,奇數額外嘗試 x/2*2 並繼續乘 2 擴展。

558D Guess Your Way Out! II:完全二叉樹出口推理

題意:深度 n 的完全二叉樹,葉子節點編號 [2^{n-1}, 2^n-1]。q 個提示:第 dep 層區間 [l,r] 是/否包含出口。判斷:唯一出口、多解、矛盾。

解法:將所有提示映射到葉子層(區間擴展:l<<=1, r=r<<1|1)。對「否」提示轉化為兩個「是」區間(左側、右側)。使用差分映射 map 記錄覆蓋次數,掃描統計被覆蓋 q 次的葉子數:0→矛盾,1→唯一,>1→多解。

558E A Simple Task:字符串區間排序

題意:長度 n 字符串,m 次操作:區間 [l,r] 升序/降序排列。輸出最終字符串。

解法:建 26 棵線段樹(每字母一棵),維護區間字母計數。每次操作:
1. 查詢 26 棵樹得區間內各字母計數。
2. 將區間所有樹計數歸 0。
3. 按順序/逆序依次填充計數。
複雜度 O(26 m log n),需延遲標記(-1 無標記,0 全 0,1 全 1)。

關鍵代碼片段(558E 線段樹)

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved