Codeforces gym 102409 Semana i 2019部分题解(A,B,C,E,F,G,H,I)

A. Easy Math

这题是一道高精度问题，所以我选择了Java提交，但你假如直接按照它给的公式算的话，在32测试点的时候好像会出现科学计数法而导致wa32。

所以你可以选择两种方法:
第一种是使用java的toPlainString()方法直接显示，不用科学计数法表示。
第二种方法就是按照官方题解说的分子乘以 $10^{50}$ 再稍微模拟下。

这里我就只给出第一种代码。

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while (T > 0) {
            BigDecimal a = cin.nextBigDecimal();
            BigDecimal b = cin.nextBigDecimal();
            BigDecimal c = cin.nextBigDecimal();
            BigDecimal d = a.add(b);
            d = d.divide(c, 50, BigDecimal.ROUND_DOWN);
            System.out.println(d.toPlainString());
            T--;
        }
        cin.close();
    }
}

B. Xor Sums

B题是签到题，假如你不知道异或的性质的话，我们可以通过打表来观察规律。它是具有循环节的。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int t;
    int sum = 0;
    cin >> t;
    ll n;
    while (t--) {
        cin >> n;
        if ((n % 4) == 0) cout << n <<endl;
        else if ((n % 4) == 1) cout << 1 <<endl;
        else if ((n % 4) == 2) cout << (n + 1) <<endl;
        else cout << 0 <<endl;
    }
    return 0;
}

C. Xor in Tree

这是一道经典的树上异或和的问题了，我们可以先通过DFS预处理出根节点到其他每一个子节点的距离异或和。

又因为A ^ B == (A ^ C) ^ (B ^ C)，所以我们在求任意两点的异或和时，就等于他们到根节点的异或和的异或值(emmm描述起来有点小绕)。

然后我们要求所有路径异或和的加和的话，就需要在预处理出根节点到其他每一个子节点的距离异或和的同时处理出对应二进制位上1的个数，记作cnt，则其0的个数为(n - cnt)。那么这n-cnt个节点到达cnt个节点的路径异或值这一位为1，在res中加上这一位的十进制值。就（n-cnt）* cnt种路径组合。

最后对二进制位上每一位计算组合数量，乘该二进制位的十进制值求和即可。

res += 1ll * (1 << i) * (n - cnt[i]) * cnt[i];

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

struct Edge {
    int to, val;
};

int n, xorSum[maxn], cnt[32];
vector<Edge> G[maxn];

void dfs(int root, int pre) {
    for (int i = 0; i < G[root].size(); i++) {
        Edge tmp = G[root][i];
        if (tmp.to != pre) {
            xorSum[tmp.to] = xorSum[root] ^ tmp.val;
            dfs(tmp.to, root);
        }
    }
    for (int i = 0; i <= 30; i++) if (xorSum[root] & (1 << i)) cnt[i]++;
}

int main() {
    int n, u, v, w;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    xorSum[1] = 0;
    dfs(1, 0);
    ll res = 0;
    for (int i = 0; i <= 30; i++) {
        res += 1ll * (1 << i) * (n - cnt[i]) * cnt[i];
    }
    printf("%lld\n", res);
    return 0;
}

E. Googles wants to maximize

这题的n很小，所以我们能直接枚举出所有情况就好了，这里就直接用的STL里的全排列函数。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;

int n, a[30], pre[30], sum;

int getMax() { // 求区间最大值
    int x = 0;
    for (int i = 0; i < n / 2; i++) x += a[i]; // 因为前面n×2了，所以这里才除以2
    int res = max(x, sum - x);
    for (int i = n / 2; i < n - 1; i++) {
        x += a[i] - a[i - n / 2];
        res = max(res, max(sum - x, x));
    }
    return res;
}

int main() {
    scanf("%d", &n);
    n *= 2;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), sum += a[i];

    sort(a, a + n);
    pre[0] = 1;

    for (int i = 1; i <= 12; i++) pre[i] = pre[i - 1] * i; //当n=i时共有多少种排列方式

    int now, minn = inf, id = 0;

    for (int i = 0; i < pre[n - 1]; i++) {
        now = getMax();
        if (now < minn) {
            minn = now;
            id = i;
        }
        next_permutation(a, a + n); // 全排列
    }

    sort(a, a + n);

    for (int i = 0; i < pre[n - 1]; i++) {
        if (i == id) { 
            for (int j = 0; j < n; j++) printf("%d ", a[j]);
            return 0;
        }
        next_permutation(a, a + n);
    }
    return 0;
}

F. Ironical Solution 1

F题也是签到级别的，我们可以直接用lrj的紫书中枚举所有子集的代码。我用的是二进制法。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6 + 5;

char s[maxn];
int a[maxn];
vector<int> v;

void print_subset(int n,int b) {
    int sum = 0;
    for (int i=0;i<n;i++)
        if (b&(1<<i)) sum += a[i];
    v.push_back(sum);
}

void p_s(int n){
    for (int i=0;i<(1<<n);i++) print_subset(n,i);
}

int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    for (int i = 0; s[i]; i++) a[i] = s[i];
    p_s(n);
    sort(v.begin(), v.end());
    for (auto x : v) printf("%d ", x);
    printf("\n");
    return 0;
}

G. Ironical Solution 2

G题受F题的影响秒交了一发假算法。以为可以直接输出前n个数就可以了(除了第一个0以外)，wa17后仔细想想发现可能俩数相加可以比第三个数小，例如1 2 4 6，你出来的前几个子集是1 2 3 4...这时候你就可能取出一个错误答案。

所以正确做法是从前往后取，并且将前面取过的数字的任意俩数之和存起来。将每次第一次出现的数字加入到你的答案当中直到答案中的数字个数==n的时候跳出循环即可。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6 + 5;

int main() {
    int n, cnt, tmp, x = 0;
    scanf("%d", &n);
    cnt = (1 << n); // 2的n次方
    vector<int> v(cnt), res;
    map<int, int> mp;
    scanf("%d", &tmp);
    for (int i = 1; i < cnt; i++) {
        scanf("%d", &v[i]);
        if (mp[v[i]]) mp[v[i]]--;
        else {
            res.push_back(v[i]);
            if (res.size() == n) break;
            for (int j = 1; j < i; j++) {
                mp[v[i] + v[j]]++;
            }
        }    
    }

    for (auto g : res) printf("%c", g);
    printf("\n");
    return 0;
}

H. Maximizing Coins

首先我们可以确定的是，金币能花费的地方我们都花费。然后对于走的方案数的话我们可以用逆向思维dp一下。
官方题解说用线段树来维护，但这里只维护了个区间和，所以我就直接用的树状数组。（多亏了9ls教我的这题）

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

ll c[maxn], k[maxn], dp[maxn], a[maxn], v[maxn];
int n;

ll lowbit(ll x) {
    return x & (-x);
}

void add(int i, ll x) {
    while (i <= n) {
        v[i] += x;
        i += lowbit(i);
    }
}

ll getSum(int i) {
    ll res = 0;
    while (i > 0) {
        res += v[i];
        i -= lowbit(i);
    }
    return res % mod;
}

ll query(int l, int r) {
    return (getSum(r) - getSum(l - 1)) % mod;
}

int main() {
    scanf("%d", &n);
    ll money = 0;
    for (int i = 1; i < n; i++) scanf("%lld", &c[i]), money += c[i];
    for (int i = 1; i < n; i++) scanf("%lld", &k[i]);

    int cnt = 0;
    dp[n] = 1;

    for (int i = n; i >= 1; i--) {
        a[i] = cnt;
        if (!c[i]) cnt++;
        else cnt = 0;
    }

    add(n, 1);

    for (int i = n - 1; i >= 1; i--) {
        dp[i] = query(i, min(i + k[i], i + a[i] + 1));
        add(i, dp[i]);
    }

    printf("%lld %lld\n", money, dp[1]);
    return 0;
}

I. Thanos's snap

这题我个人认为是一道逆元的好题，学会这题后逆元基本就差不多了。

首先这题不难想出公式为： ${P_i \ =\ \sum_{i = k}^{K}\frac{C_{K}^{i}}{2^K}}$ ，其中K=5000000。

然后我们可以通过递推公式预处理下，因为它是从k开始一直累加到K，所以我们可以从后往前dp一下 ${dp[i] \ = \ dp[i + 1]} \ + \ C_{K}^{i} \ * \ 195206359$ ，其中195206359为题目中给出 $2^{5000000}$ 的逆元

剩下的一个难点就是处理组合数的问题了。

这里的解决方案是先预处理出1~5000000的阶乘（注意取模），再通过线性求逆元将阶乘的逆元也求出来。

因为组合数可以转化成阶乘形式的公式 ${C_{n}^{m} \ = \ \frac{n!}{m!(n\ -\ m)!}}$

同时要对取模的话我们就应该将乘法转化为乘法的形式 ${C_{n}^{m}\ =\ n!\ *\ inv(m!)\ *\ inv((n\ -\ m)!)}$

代码如下

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int maxn = 5e6 + 5;
const int mod = 1e9 + 7;
ll fac[maxn], inv[maxn], dp[maxn];

ll C(int m, int n) {
    if (n == m || m == 0) return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= 5000000; i++) fac[i] = (fac[i - 1] * i) % mod;

    inv[5000000] = qpow(fac[5000000], mod - 2);
    for (int i = 4999999; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mod;

    dp[5000000] = 195206359;
    dp[0] = 1;
    for (int i = 4999999; i >= 0; i--) dp[i] = (dp[i + 1] + C(i, 5000000) * 195206359) % mod;

}


int main() {
    init();
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n] << endl;
    }
}

蒟蒻能力有限，有错误还请多多指出。