AtCoder Beginner Contest 169部分题解（ATcoder）

D - Div Game

Solution

对n分解质因数，设某个质因数出现的次数为cnt。每个质因数每次取得越少越好，即构成自然数列1+2+...+n，我们要找的就是最大的n使得$1+2+...+n leq cnt$，这可以二分做。

复杂度$O(frac{sqrt{N}}{log{sqrt{N}}})$。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n, ans;
ll f[51];
int prime[1000010], mark[1000010], tot;
ll find(ll x) {
    ll l = 1, r = 1000000, ret = -1;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (mid * (mid + 1) / 2 <= x) {
            ret = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ret;
}
void get_prime() {
    for (int i = 2; i <= 1000000; i++) {
        if (!mark[i]) prime[++tot] = i;
        for (int j = 1; j <= tot; j++) {
            if (prime[j] * i > 1000000) break;
            mark[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
int main() {
    get_prime();
    for (int i = 1; i <= 50; i++) {
        f[i] = find(i);
    }
    cin >> n;
    for (int i = 1; prime[i] * prime[i] <= n && i <= tot; i++) {
        if (n % prime[i] == 0) {
            ll cnt = 0;
            while (n % prime[i] == 0) {
                cnt++;
                n /= prime[i];
            }
            ans += f[cnt];
        }
    }
    if (n > 1) {
        ans++;
    }
    cout << ans;
    return 0;
}

E - Count Median

结论题，不会证，感性理解吧QWQ。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
long long a[200010], b[200010];
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    if (n % 2) {
        cout << b[n / 2 + 1] - a[n / 2 + 1] + 1;
    } else {
        cout << b[n / 2] + b[n / 2 + 1] - a[n / 2] - a[n / 2 + 1] + 1; 
    }
    return 0;
}

F - Knapsack for All Subsets

Solution

这算是一道非常明显的背包题。

我们可以考虑算出所有可以凑数s的集合，然后再看看它属于多少个集合。

设$f[i][j]$代表选$i$个数，和为$j$的方案数，则答案为$sum_{i=1}^{n}f[i][s] imes 2^{n-i}$。

有转移方程：$f[i][j]+=f[i-1][j-a[i]]$

但是这么dp的复杂度为$O(N^2 imes S)$，显然爆炸，考虑优化。

考虑最后答案的式子，设$g[j]=sum_{i=1}^{n}f[i][j] imes 2^{n-i}$。

我们再来看看f的转移方程，我们发现有$g[j]+=g[j-a[i]]/2$，然后这道题就做完了。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
ll n, s;
ll a[3010];
ll f[3010];
ll inv2;
ll ksm(ll aa, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = (ret * aa) % MOD;
        aa = (aa * aa) % MOD;
        b >>= 1;
    }
    return ret;
}
int main() {
    cin >> n >> s;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    inv2 = ksm(2, MOD - 2);
    f[0] = ksm(2, n);
    for (ll i = 1; i <= n; i++) {
        for (ll k = s; k >= a[i]; k--) {
            f[k] = (f[k] + f[k - a[i]] * inv2) % MOD;//除以2等于乘以2的逆元 
        }
    }
    cout << f[s];
    return 0;
}