串中的 “_” 处要么都向左走要么都向右走

class Solution {
public:int furthestDistanceFromOrigin(string moves) {int t = 0;for (auto x: moves)if (x != 'R')t--;elset++;int res = abs(t);t = 0;for (auto x: moves)if (x != 'L')t++;elset--;res = max(res, abs(t));return res;}
};

贪心：升序枚举正数，用集合维护当前数组中已有的数

class Solution {
public:long long minimumPossibleSum(int n, int target) {long long res = 0;set<int> vis;for (int i = 1; vis.size() != n; i++)if (!vis.count(target - i)) {res += i;vis.insert(i);}return res;}
};

贪心：首先只有 $nums$ 的数组和小于 $target$ 才无解，若有解则从低位到高位枚举 $target$ 的二进制表示的各位，设当前位对应 $2^i$ ，且 $target$ 第 $i$ 位为 $1$，有两种情况：

• $nums$中不超过 $2^i$ 的数的和 $\ge$ $2^i$ ：则一定存在若干个不超过 $2^i$ 的数之和恰好为$2^i$
• $nums$中不超过 $2^i$ 的数的和 $<$ $2^i$ ：需要把 $nums$ 中一个最小的大于 $2^i$ 的数 $2^j$ 操作若干次来生成一个 $2^i$

第二种情况会产生操作数，枚举过程种注意维护不超过 $2^i$ 的数的和。

class Solution {
public:int minOperations(vector<int> &nums, int target) {if (accumulate(nums.begin(), nums.end(), 0LL) < target)return -1;unordered_map<int, int> cnt;for (auto x: nums)cnt[x]++;int res = 0;long long ps = 0;//nums中不超过2^i的数之和for (int i = 0, e = 1; i < 31; i++, e <<= 1) {//逐位枚举ps += 1LL * cnt[e] * e;if (!(target >> i & 1))continue;if (ps >= e) {ps -= e;continue;}int j = i + 1;while (cnt[1 << j] <= 0)//找nums中大于2^i的最小的2^jj++;res += j - i;//记录操作数cnt[1 << j]--;for (int k = i + 1; k < j; k++)cnt[1 << k] = 1;ps += e;}return res;}
};

倍增：设 $g[i][j]$ 为球最初在 $i$ 手里，传 $2^j$ 次球的过程中每次接触球玩家的编号之和。设 $v[i][j]$ 表示球最初在 $i$ 手里，传 $2^j$ 次球后球在$v[i][j]$手里。预处理求处理 $g$ 和 $v$，之后枚举 $i\in [0,n)$，然后枚举 $k$ 二进制各位来求 $f[i]$。

class Solution {
public:long long getMaxFunctionValue(vector<int> &receiver, long long k) {int n = receiver.size();long long g[n][35], v[n][35];for (int j = 0; j < 35; j++)for (int i = 0; i < n; i++)if (j != 0) {g[i][j] = g[i][j - 1] + g[v[i][j - 1]][j - 1] - v[i][j - 1];v[i][j] = v[v[i][j - 1]][j - 1];} else {g[i][j] = i + receiver[i];v[i][j] = receiver[i];}long long res = 0;for (int i = 0; i < n; i++) {long long cur = 0;int last = i;for (long long j = 0; j < 35; j++)if (k >> j & 1) {//枚举k二进制各位cur += g[last][j] - last;last = v[last][j];}res = max(res, i + cur);}return res;}
};