Codeforces Round #470 (Div. 1)

Codeforces

Contests 链接：Codeforces Round #470 (Div. 1)
过题数：3
排名：315/1183

A. Primal Sport

题意

$Alice$ 和 $Bob$ 两人在玩一个游戏，$Alice$ 先开始，两人轮流进行，第 $i$ 次游戏中，对于一个整数 $X_i$，选择一个素数 $p<X_i$，然后找到一个最小的整数 $Y$，使得 $Y\geq X$ 且 $Y$ 能被 $p$ 整除，将这个数字作为下一次游戏的新值 $X_{i+1}$ 继续进行游戏，现在游戏已经进行了两次，得到了 $X_2$ 的值，问最小的可能的 $X_0~(X_0\geq3)$ 的值为多少。

输入

输入为一个整数 $X_2~(4\leq X_2\leq10^6)$，数据保证 $X_2$ 是合数。

输出

输出最小的可能的 $X_0$ 的值。

样例

题解

我们可以根据 $X_i$ 的值确定 $X_{i-1}$ 的合法的取值区间：$[X_i-p+1,X_i]$，其中 $p$ 为 $X_i$ 的最大的质因子，对于 $X_{i-1}\geq X_i-p+1$ 的值，只要选择质数 $p$ 就可以通过 $X_{i-1}$ 得到 $X_i$ 的值，对于 $X_{i-1}<X_i-p+1$ 的值，如果选择质数 $p$，则只能得到 $X_i-p$ 的值，如果选择其他质数，由于 $p$ 是最大的质因数，选择其他质数能够改变的增量一定小于 $p$，所以 $X_i'<X_i$。但是最小的 $X_{i-1}$ 并不能得到最小的 $X_{i-2}$，因此对于 $X_2$ 我们需要枚举所有可能的 $X_1$ 的值，来找到最小的 $X_0$ 的值。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
int cnt, n;
bool vis[maxn];
int prime[maxn];
void Prime() {
    for(int i = 2; i < maxn; ++i) {
        if(!vis[i]) {
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt && i < maxn / prime[j]; ++j) {
            int k = i * prime[j];
            vis[k] = true;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}
int Find(int x) {
    int ret;
    int xx = x;
    for(int i = 0; i < cnt && prime[i] <= xx / prime[i]; ++i) {
        while(x % prime[i] == 0) {
            x /= prime[i];
            ret = prime[i];
        }
    }
    if(x != 1) {
        ret = x;
    }
    return ret;
}
int main() {
    #ifdef LOCAL
        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    Prime();
    while(scanf("%d", &n) != EOF) {
        int Start = Find(n);
        int ans = INT_MAX;
        for(int i = n - Start + 1; i <= n; ++i) {
            int tmp = i - Find(i) + 1;
            if(tmp >= 3) {
                ans = min(ans, tmp);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Producing Snow

题意

$Bob$ 从第 $1$ 天到第 $n$ 天每天堆体积为 $V_i$ 体积的雪人，第 $i$ 天的时候每一个已经堆好的雪人会融化 $T_i$ 的体积，问在第 $i$ 天当天所有已经堆好的且没有完全融化的雪人会融化的总的体积。

输入

第一行包含一个整数 $n~(1\leq n\leq10^5)$，第 $2$ 行包含 $n$ 个整数 $V_1,V_2,\cdots,V_n~(0\leq V_i\leq10^9)$，第 $3$ 行包含 $n$ 个整数 $T_1,T_2,\cdots,T_n~(0\leq T_i\leq10^9)$。

输出

输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天融化的雪人体积。

样例

题解

假设第 $1$ 天堆起来的雪人体积为无穷大，那么到第 $i$ 天的时候这个雪人融化的体积就为 $\sum_{j=1}^iT_j$，第 $i$ 天刚堆起来的雪人没有受到前 $i-1$ 天融化的影响，但是可以假设这个雪人是从第 $1$ 天堆起来的，第 $i$ 天的时候融化了 $\sum_{j-1}^{i-1}T_i$ 的体积，导致它第 $i$ 天的体积为 $V_i$，因此可以认为这个雪人在第 $1$ 天堆起来的时候的体积为 $V_i+\sum_{j=1}^{i-1}T_j$，我们将到第 $i$ 天的所有雪人的体积都转化为 $V_i'=V_i+\sum_{j=1}^{i-1}T_j$ 后放入 $map$ 中，到第 $i$ 天完全融化的雪人就是 $V_k'\leq\sum_{j=1}^iT_j$ 的雪人，将这些雪人在第 $i$ 天融化的体积（$V_k'-\sum_{j=1}^{i-1}T_j$）计算出来，然后从 $map$ 中删去它们，再计算第 $i$ 天能融化体积 $T_i$ 的雪人的个数 $cnt$（可以 $O(1)$ 维护），于是第 $i$ 天融化的雪人体积就为 $\sum(V_j'-\sum_{k=1}^{i-1}T_k)+T_i\times cnt$，其中 $\sum_{k=1}^{i-1}T_k<V_j'\leq \sum_{k=1}^iT_k$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, cnt;
LL mp_cnt;
map<LL, int> mp;
map<LL, int>::iterator it, itt;
LL v[maxn], t[maxn];
map<LL, int>::iterator del[maxn];
int main() {
    #ifdef LOCAL
        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        mp_cnt = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &v[i]);
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &t[i]);
            t[i] += t[i - 1];
        }
        mp.clear();
        LL ans;
        for(int i = 1; i <= n; ++i) {
            ans = 0;
            cnt = 0;
            v[i] += t[i - 1];
            ++mp[v[i]];
            ++mp_cnt;
            it = mp.upper_bound(t[i]);
            for(itt = mp.begin(); itt != it; ++itt) {
                ans += ((itt->first) - t[i - 1]) * (itt->second);
                del[cnt++] = itt;
                mp_cnt -= itt->second;
            }
            for(int j = 0; j < cnt; ++j) {
                mp.erase(del[j]);
            }
            ans += mp_cnt * (t[i] - t[i - 1]);
            if(i != 1) {
                printf(" ");
            }
            printf("%I64d", ans);
        }
        printf("\n");
    }
    return 0;
}

C. Perfect Security

题意

有两个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 和 $b_1,b_2,\cdots,b_n$，对于每一个 $a_i$，在 $b$ 序列中找到一个数字与其异或，成为新序列的第 $i$ 个元素 $c_i$，然后从 $b$ 序列中删去被选中的数字，求能够构成的新序列中字典序最小的序列。

输入

第一行包含一个整数 $n~(1\leq N\leq3\times10^5)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i<2^{30})$，第三行为 $n$ 个整数 $b_1,b_2,\cdots,b_n~(0\leq b_i<2^{30})$。

输出

输出 $n$ 个整数，第 $i$ 个整数表示所求新序列的第 $i$ 项。

样例

题解

将所有 $b$ 序列中的数字建一棵字典树，从 $1$ 到 $n$ 对于每一个 $i$，都取一个 $b$ 序列中与 $a_i$ 异或值最小的，然后将这个数字在字典树中出现的次数 $-1$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxm = 300000 + 100;
const int maxn = 300000 * 32 + 100;
const int Size = 2;
struct Trie {
    int root, cnt;
    int val[maxn], tree[maxn][Size];
    int creat() {
        ++cnt;
        memset(tree[cnt], 0, sizeof(tree[cnt]));
        val[cnt] = 0;
        return cnt;
    }
    void Init() {
        cnt = 0;
        root = creat();
    }
    int id(int x, int dig) {
        return ((x >> (31 - dig)) & 1);
    }
    void add(int x) {
        int pos = root;
        for(int i = 0; i < 32; ++i) {
            int w = id(x, i);
            if(tree[pos][w] == 0) {
                tree[pos][w] = creat();
            }
            pos = tree[pos][w];
            ++val[pos];
        }
    }
    int query(int x) {
        int ret = 0;
        int pos = root;
        for(int i = 0; i < 32; ++i) {
            int w = id(x, i);
            if(tree[pos][w] == 0 || val[tree[pos][w]] == 0) {
                w = !w;
                ret |= (1 << (31 - i));
            }
            pos = tree[pos][w];
            --val[pos];
        }
        return ret;
    }
};
Trie t;
int n, x;
int num[maxn];
int main() {
    #ifdef LOCAL
        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        t.Init();
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &x);
            t.add(x);
        }
        for(int i = 0; i < n; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", t.query(num[i]));
        }
        printf("\n");
    }
    return 0;
}