AtCoder Regular Contest 122

比赛链接：Here

A - Many Formulae

给n个数，中间添加+或者-，得到答案，算出所有情况的答案的和。不存在两个连续的负号。

我们应该做DP来找到形成公式前缀的方法的数目，以便 跟随 +或 -。

更具体地说，我们应该让 是排列 符号总数的方法数，这样就不会有两个 - 出现在一行中，最后一个符号是 + 的前提条件是如果 或 。

每 ，如果我们修正了在 之前的符号，我们就可以独立地决定第一个 个标志和最后一个 符号，我们可以用上面 中的值找到设置它们的方法。

• #card=math&code=%5Cmathcal%7BO%7D%28n%29)

const int mod = 1e9 + 7, N = 1e5 + 10;
ll f[N], g[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<ll>a(n + 1);
    f[1] = 1, f[2] = 2;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (i >= 3)f[i] = (f[i - 1] + f[i - 2]) % mod;
    }
    g[1] = 0;
    g[2] = a[n] + a[n - 1];
    for (int i = 3; i < n; ++i)
        g[i] = (g[i - 1] + g[i - 2] + f[i] * a[n - i + 1] + f[i - 1] * (-a[n - i + 1] + a[n - i + 2])) % mod;
    cout << (g[n - 1] + a[1] * f[n]) % mod;
}

B - Insurance

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<ll>a(n);
    for (ll &x : a)cin >> x;
    sort(a.begin(), a.end());
    double cnt = 0, x = a[n / 2] * 0.5;
    for (ll i : a)
        cnt += (x + i - min(i, a[n / 2]));
    cout << fixed << setprecision(12) << cnt * 1.0 / n;
}

C - Calculator

官方证明：here

交替进行3，4操作可以构造Fib数列，

如果在其中插入1个1或2操作，得到的会是 ，继续进行得到

将 转化为 #card=math&code=Fib%7Ba1%7D%20%2B%20Fib%7Ba2%7D%2B…%2BFib_%7Bat%7D%28a_1%5Cle%20a_2%5Cle…%5Cle%20a_t%29)

按如上方法构造

ll fib[110] = {1, 1};
bool op[110];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n; cin >> n;
    int k = 0, cnt = 0;
    for (int i = 2; i <= 86; ++i) fib[i] = fib[i - 1] + fib[i - 2];
    for (int i = 86; i >= 1; --i) {
        if (n >= fib[i]) {
            n -= fib[i];
            op[i] = true;
            ++cnt;
            if (!k) k = i;
        }
    }
    cout << k + cnt << "\n";
    for (int i = k; i >= 1; --i) {
        if (op[i]) cout << (i & 1 ? 2 : 1) << '\n';
        if (i & 1)cout << 3 << "\n";
        else cout << 4 << "\n";
    }
}

另一种做法：

ll find(ll x) {
    ll y = x * (std::sqrt(5) - 1) / 2;
    while ((__int128(y + 1) * 2 + x) * (__int128(y + 1) * 2 + x) <= __int128(5) * x * x)
        y++;
    while ((__int128(y) * 2 + x) * (__int128(y) * 2 + x) > __int128(5) * x * x)
        y--;
    return y;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n; cin >> n;
    vector<int>ans;
    ll x = n, y = find(x);
    while (x && y) {
        if (x >= y) {
            x -= y;
            ans.push_back(3);
            ll t = find(y);
            while (x > t + 1) {
                ans.push_back(1);
                x--;
            }
        } else {
            y -= x;
            ans.push_back(4);
            ll t = find(x);
            while (y > t + 1) {
                ans.push_back(2);
                y--;
            }
        }
    }
    while (x) { ans.push_back(1); x--;}
    while (y) { ans.push_back(2); y--;}
    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int i : ans)cout << i << "\n";
}