题目1：abc252_f

题意

• 有一个长度为 \(l\) 的面包，要把这块面包切成 \(n\) 段，$a_1, a_2, \dots,a_n $，有剩下的不分配。将一块长度为 \(k\) 的面包切成两块的代价为 \(k\)，问要将面包切成 \(n\) 段的最小代价。

• \(1 \le n \le 10^5, 1 \le a_i \le 10^9, \sum\limits_{i = 1}^n a_i\le l \le 10^{15}\)，输入均为整数。

思路

• 首先我们可以发现，这块面包最后分成了：\(a_1, a_2, \dots a_n, l - \sum\limits_{i = 1}^n a_i\)（最后一段有没有取决于它的长度是否 \(>0\)）。所以题目简化为每次将两块面包合起来，问把这些面包合成一块的最小代价。而这不就是合并果子吗。

• 时间复杂度：贪心时用堆求答案，\(O(n \times \log n)\)。

using ll = long long;

const int MAXN = 2e5 + 5;

int n;
ll ans, l, s, x, y;
priority_queue<ll, vector<ll>, greater<ll>> pq;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> l ;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    pq.push(x), s += x;
  }
  if (l > s) {
    pq.push(l - s);
  }
  while (pq.size() > 1) { // 贪心
    x = pq.top(), pq.pop();
    y = pq.top(), pq.pop();
    ans += x + y, pq.push(x + y);
  }
  cout << ans;
  return 0;
}

题目2：洛谷 P5658

题意

有一棵有 \(n\) 个结点，根是 \(1\) 的括号树，每个节点为左或右括号，用 \(t_i\) 表示。结点 \(i(2 \le i \le n)\) 的父亲为 \(f_i\)。令 \(S_i\) 为：将根结点到 \(i\) 的简单路径上的括号，设 \(s_i\) 里有 \(k_i\) 个合法括号子串。请输出 \(((1\times k_1) xor (2 \times k_2) xor \cdots xor (n \times k_n))\)。

思路

• 这道题是 \(dp\)，令 \(dp_i\) 表示 \(S_i\) 中以 \(i\) 为结尾的合法子串数量。我们用栈 \(stk\) 记录左括号，当枚搜索到 \(i\) 时，有如下几种情况：

if (a[x] == '(') { //左括号
  stk[++top] = x;
} else if (top) { //右括号，有可以匹配的左括号
  p = stk[top--];
  dp[x] = dp[fa[p]] + 1; //首先 p ~ i 一定合法，而且和可以用以 dp[fa[p]] 为结尾的合法括号串接上 p~i
}

• 当然我们深搜时需要回溯，注意一下。当然还要注意我们的 \(dp_i\) 是以 \(i\) 结尾的合法子串个数，不是整个 \(S_i\) 的合法子串个数，需要开前缀和，每次将父亲信息传递到儿子。

• 时间复杂度：\(O(n)\)。

const int MAXN = 5e5 + 5;

char a[MAXN];
vector<int> son[MAXN];
int n, fx, top, stk[MAXN], fa[MAXN];
long long ans, s[MAXN], dp[MAXN];

void Dfs(int x) {
  int p = 0;
  if (a[x] == '(') {
    stk[++top] = x;
  } else if (top) {
    p = stk[top--];
    dp[x] = dp[fa[p]] + 1, s[x] += dp[x];
  }
  ans ^= s[x] * x; //记录答案
  for (int y : son[x]) {
    s[y] = s[x], Dfs(y);
  }
  // 回溯
  if (p) {
    stk[++top] = p;
  } else if(a[x] == '(') {
    top--;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 2; i <= n; i++) {
    cin >> fx, son[fx].push_back(i), fa[i] = fx;
  }
  Dfs(1);
  cout << ans;
  return 0;
}