题目概览
描述
Shakespeare is a widely known esoteric programming language in which programs look like plays by Shakespeare, and numbers are given by combinations of ornate epithets. In this problem we will have a closer look at the way the numbers are described in Shakespeare.
Each constant in Shakespeare is created from non-negative powers of 2 using arithmetic operations. For simplicity we'll allow only addition and subtraction and will look for a representation of the given number which requires a minimal number of operations.
You are given an integer n. You have to represent it as n = a_1 + a_2 + ... + a_m, where each of a_i is a non-negative power of 2, possibly multiplied by -1. Find a representation which minimizes the value of m.
输入
The only line of input contains a positive integer n, written as its binary notation. The length of the notation is at most 10^6. The first digit of the notation is guaranteed to be 1.
输出
Output the required minimal m. After it output m lines. Each line has to be formatted as +2^x or -2^x, where x is the power coefficient of the corresponding term. The order of the lines doesn't matter.
大意
给出长度为 l(1\leq l \leq 10^6) 的一个 01 串 n，将其分解为 m 个 2 次幂（或其相反数）的和，要求输出 m 的最小值和对应的方案 (+2^x 或 -2^x , x 为指数)。
思路
很容易能够想到一种非最优的构造方法：设 01 串中 1 的索引（即其所处的位数）分别为 p_1, p_2, ..., p_m ，则 n = 2^{p_1}+2^{p_2}+...+2^{p_m} ，其中 m 为 01 串中 1 的个数。
考虑对上述构造方式进行优化。对于在索引 (p, q) 上连续的 1 串，有 2^p+2^{p+1}+...+2^q=2^{q+1}-2^p 。通过这一等量关系，我们可以在整个 01 串中提取出若干个 1 串，对于长度为 1 ，索引为 p 的 1 串，其可以表示为 2^p，对 m 的贡献为 1；对于长度大于 1 ，索引区间为 (p,q) 的 1 串，其可以表示为 2^{q+1}-2^p，对 m 的贡献为 2。
只需遍历一遍 01 串，就可以得到一个看似已经最优的 m，实则不然。
对于
01串11011，按照上述方式可以得到\min m=4。其是否存在一个更优的解？
显然，11011=100000-100-1=2^5-2^2-2^0，此时 m=3 ，其比上述解更优。
上述操作可视为将整个 01 串当作 1 串，再在其基础上减去中间的 0 。
假设 01 串 s 中间只有一串连续的 ，其长度为 len，则 m=len+2，而原有的构造方法得到的 m\in[2...4]，也就是说，只有对于 len=1 的情况，这种方法得到的解才有可能更优。
再分类讨论原有的构造方法得到的解 m_0：
s两端的1串长度都为1。此时m_0=2<3，因此新方法反而会得到一个更劣的解；s一端的1串长度为1，另一端的1串长度大于1。此时m_0=3，最优解不变；s两端的1串长度都大于1。此时m_0=4>3，可以得到一个更优的解。
我们可以直接在原有的构造方法上加一步判定：如果遍历过程中遇到单个 0 ，且前面所遍历的 1 串长度大于 1 ，则按照上述方法，将前后两串看作一个整体，并在其基础上加一步减去中间的 0 的过程 。
这样一来，我们就可以得到 m 的最小值了。
实现
#include <bits/stdc++.h>
#define CNO cout << "NO\n"
#define CYES cout << "YES\n"
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int n, arr[200010];
ll ans = 0;
string str;
bitset<1000010> s;
vector<pii> v, w;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
cin >> s;
int cnt = s.count(), p = 0;
while (cnt) {
if (s[p] == 1) cnt--;
p++;
}
p--;
cnt = 0;
bool bit = 1;
for (int i = p; i >= 0; --i) {
if (s[i] == bit)
cnt++;
else {
if (bit) {
if (cnt > 1) {
if (i == 0) {
v.push_back({0, 1});
break;
} else if (s[i - 1] == 1) {
cnt++;
v.push_back({0, i});
continue;
}
v.push_back({1, p + 1});
v.push_back({0, i + 1});
} else {
v.push_back({1, p});
}
}
cnt = 1;
bit = !bit;
p = i;
}
}
if (bit) {
if (cnt > 1) {
v.push_back({1, p + 1});
if (s[0]) v.push_back({0, 0});
} else {
v.push_back({1, p});
}
}
cout << v.size() << endl;
for (auto i : v) {
if (i.first) {
cout << "+2^" << i.second << endl;
} else {
cout << "-2^" << i.second << endl;
}
}
}
return 0;
}因为特判失误而导致的大量 WA qwq
