2019 ICPC EC Final

题解

M

牛客题目链接

题目描述

Pang believes that one cannot make an omelet without breaking eggs.

For a subset $A$ of $\{1,2,\ldots,n\}$, we calculate the score of $A$ as follows:

1. Initialize the score as {0}0.
2. For any $i \in A$, add $a_i$ to the score.
3. For any pair of integers $(i, j)$ satisfying $i \ge 2$, $j \ge 2$, $i \in A$, if there exists positive integer $k \gt 1$ such that $i^k=j$, subtract $b_j$ from the score.

Find the maximum possible score over the choice of $A$.

思考

我任意选择一个子集$A$，只考虑条件2，可以得到的分值为$\sum_{i\in{A}}{a_i}$
如果需要扣除$b_j$的得分，必定存在某个$i^k=j$
那么就可以反过来思考，我枚举所有的$i^k$，$k \ge 1$，$i^k \le n$，例如：

• $\{2,4,8,16,32,\ldots\}$
• $\{3,9,27,91,\ldots\}$
• $\{5,25,125,625,\ldots\}$
• $\{6,36,\ldots\}$
• $\ldots$

对于以上每个集合，分别考虑里面的数字选与不选，比如第一个$2^k$的集合，当我没有选择2但选择了4的时候，所有$b_j(j \in A \And j=4^k)$都需要扣除，那么对于单个集合计算的复杂度就是$\log_{i}{n} \times 2^{\log_{i}{n}}$，那么总体复杂度的上界就是$\sum_i^n{\log_{i}{n} \times 2^{\log_{i}{n}}}$，用起算器算一下当$n=100000$的时候，上界不超过$2000000$的

代码

// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define bt(x, k) (((x) >> k) & 1)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define mst(t, v, n) memset(t, v, sizeof(decltype(*(t))) * (n))
#define sf(x) scanf("%d", &(x))
#if (not defined(ACM_LOCAL) || defined(ACM_TEST))
#define endl '\n'
#endif

const int N = 1e5 + 10;
const int MOD = 998244353;

const int M = 30;

int n, m;
// a表示题目输入的a,b，b来存放当前i的i^k的所有数字的a,b组合
pii a[N], b[N];
// c表示当前枚举集合的第j个=数字要选的时候需要被减去几次
int c[N] = {0};
// 表示当前i是否被访问过，比如需要跳过4,8,9之类的数字
bool vis[N];
ll rst;

void dfs(int k, ll w) {
    if (k > m) {
        rst = max(rst, w);
        return;
    }
    dfs(k + 1, w);
    w += b[k].first;
    w -= 1ll * b[k].second * c[k];
    for (int i = k; i <= m; i += k) {
        c[i]++;
    }
    dfs(k + 1, w);
    for (int i = k; i <= m; i += k) {
        c[i]--;
    }
}

void solve() {
    while (cin >> n) {
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= n; i++) cin >> a[i].first;
        for (int i = 1; i <= n; i++) cin >> a[i].second;

        ll ans = a[1].first;
        for (int i = 2; i <= n; i++) {
            if (vis[i]) continue;
            m = 0;
            for (ll k = i; k <= n; k *= i) {
                vis[k] = true;
                b[++m] = a[k];
            }
            rst = 0;
            dfs(1, 0);
            ans += rst;
        }
        cout << ans << endl;
    }
}

int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
//    freopen("./data/std.out", "w", stdout);
#endif
#if (not defined(ACM_LOCAL) || defined(ACM_TEST))
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

#ifdef ACM_LOCAL
    clock_t start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    clock_t end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}