CCPC Harbin

GYM 104813 B

题目描述

给定一个数列 \(A\)，你要对每个 \(\sum \limits_{j=1}^i 2^{j-i}\cdot A_j\) 判断其正负性。

思路

首先我们可以让其变为 \(\sum \limits_{j=1}^i 2^{j-1}\cdot A_j\)，这里介绍一种叫做平衡三进制的做法。

平衡三进制类似于二进制，不同的是，其中一位上可以是 \(-1\)。平衡三进制的优点是可以不用处理退位的问题，只需进位。我们用 set 记录哪些位上不为 \(0\) 和其值。判断正负性只需看最高位即可。

空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N\log A_i)\)。

思路

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;const int MAXN = 100001;int n;
set<pii> s;void add(int p, int x) {auto it = s.lower_bound({p, -1});if(it != s.end() && it->first == p) {int v = it->second + x;s.erase(it);if(v == 2) {add(p + 1, 1);}else if(v == -2) {add(p + 1, -1);}}else {s.insert({p, x});}
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1, x; i <= n; ++i) {cin >> x;for(int j = 0; j <= 30; ++j) {if((abs(x) >> j) & 1) {add(j + i - 1, max(-1, min(1, x)));}}if(s.empty()) {cout << 0;}else {int x = prev(s.end())->second;cout << (x > 0 ? '+' : '-');}}return 0;
}

GYM 104813 D

题目描述

我们定义正整数 \(x\) 的质因子数量为 \(\omega (x)\)。我们把正整数看做结点，那么结点 \(x,y\) 之间有一条边权为 \(\omega(\operatorname{lcm}(x,y))\) 的边。求仅包含结点 \(l,l+1,\dots,r\) 的子图的最小生成树。

思路

首先 \(\omega(\operatorname{lcm}(x,y))=\omega(x)+\omega(y)-\omega(\gcd(x,y))\)。所以我们可以枚举 \(\gcd=x\)。接着我们枚举 \(x\) 的倍数 \(y\)，找到