TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes) A-E

科技资讯 投稿 6500 0 评论

TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes) A-E

比赛链接

A

题意

\(n\,找到一组正整数 \(x,y \leq n\,满足 \(x^y \cdot y + y^x \cdot x = n\

题解

知识点:数学。

\(x=1\,显然此时 \(2y = n\,如果 \(n\ 为偶数可以直接求得。

\(x,y\ 奇偶性结果都是偶数,因此 \(n\ 为奇数时无解。

\(O(1\

\(O(1\

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve( {
    int n;
    cin >> n;
    if (n & 1 return false;
    else cout << 1 << ' ' << n / 2 << '\n';
    return true;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int t = 1;
    cin >> t;
    while (t-- {
        if (!solve( cout << -1 << '\n';
    }
    return 0;
}

B

题意

给定一个正整数 \(n\,将其分解为 \(\prod_{i=1}^m a_{i}^{p_{i}}\,其中 \(a_i\ 是不同素数的乘积。

\(\sum_{i=1}^m a_i \cdot p_i\ 的最大值。

题解

知识点:质因数分解,贪心。

\(n\ 质因数分解 \(\prod_{i=1}^m a_{i}^{p_{i}}\,其中 \(a_i\ 为素数。

\(a_i^{p_i},a_j^{p_j}\合并成一个新的数 \((a_i \cdot a_j^{\min(p_i,p_j}\,这样的答案更优,因此我们考虑合并能合并不同的素数。

\(O(\sqrt n\

\(O(1\

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void get_pfactor(int n, vector<pair<int, int>> &pfactor {
    for (int i = 2;i * i <= n;i++ {
        if (!(n % i {
            pfactor.push_back({ i,0 };
            while (!(n % i n /= i, pfactor.back(.second++;
        }
    }
    if (n > 1 pfactor.push_back({ n,1 };//最后可能留一个大于sqrt(n的质数
}

bool solve( {
    int n;
    cin >> n;
    vector<pair<int, int>> pfactor;
    get_pfactor(n, pfactor;
    vector<ll> v(32, 1;
    for (auto [x, y] : pfactor v[y] *= x;
    ll ans = 0;
    for (int i = 30;i >= 1;i-- v[i] *= v[i + 1], ans += (v[i] > 1 * v[i];
    cout << ans << '\n';
    return true;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int t = 1;
    cin >> t;
    while (t-- {
        if (!solve( cout << -1 << '\n';
    }
    return 0;
}

C

题意

给定一组数 \(a_i\\(s\,将 \(a_i,i \in [2,n-1]\ 分解为新的两个非负整数 \(x_i,y_i\ 且满足 \((x_i - s \cdot (y_i - s \geq 0\

\(F = a_1 \cdot x_2 + y_2 \cdot x_3 + \cdots + y_{n-1} \cdot a_n\ 的最小值。

题解

知识点:线性dp,贪心。

\(x_i,y_i\ 满足的不等式,可以理解为 \(x_i,y_i\ 要同时大于等于 \(s\ 或小于等于 \(s\

\(a_i\ 贪心地分解为一个最小值和一个最大值,即当 \(a_i \geq 2s\,可以分解为 \(x_i = s,y_i = a_i-s\ ;当 \(a_i < 2s\,可以分解为 \(x_i = \max(0,a_i-s,y_i = \min(s,a_i\ 。可以如此证明,考虑某一段 \(y_{i-1} \cdot x_i+y_i\cdot x_{i+1} = (y_{i-1}-x_{i+1}\cdot x_i+a_i\cdot x_{i+1}\,无论 \(y_{i-1},x_{i+1}\ 如何,\(x_i\ 的极值点一定是在最小值或最大值处,而且这种选择没有后效性,因此分解只需要分解为一个最小值和一个最大值。

\(f_{i,0/1}\ 表示 \(a_1\cdot x_2 + \cdots+y_{i-1} \cdot x_i\\(x_i\ 是最小值/最大值时 \(F\ 的最小值,我们可以通过 \(f_{i-1,0/1}\ 来转移。

\(O(n\

\(O(n\

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


bool solve( {
    int n, s;
    cin >> n >> s;
    vector<pair<int, int>> p(n + 1;
    for (int i = 1;i <= n;i++ {
        int x;
        cin >> x;
        if (i == 1 p[1] = { 1e9,x };
        else if (i == n p[n] = { x,1e9 };
        else {
            if (x >= 2 * s p[i] = { s,x - s };
            else p[i] = { max(0,x - s,min(x,s };
        }
    }
    array<ll, 2> f{};
    f[0] = f[1] = 0;
    for (int i = 2;i <= n;i++ {
        array<ll, 2> g{};
        auto [x1, y1] = p[i - 1];
        auto [x2, y2] = p[i];
        g[0] = min(f[0] + 1LL * y1 * x2, f[1] + 1LL * x1 * x2;
        g[1] = min(f[0] + 1LL * y1 * y2, f[1] + 1LL * x1 * y2;
        f = g;
    }
    cout << f[0] << '\n';
    return true;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int t = 1;
    cin >> t;
    while (t-- {
        if (!solve( cout << -1 << '\n';
    }
    return 0;
}

D

题意

给定 \(n\ 个数 \(a_i\,从第 \(1\ 个数出发,每次可以跳到第 \(i+a_i\ 个数,直到跳到 \(<1\\(>n\ 的地方游戏结束。

\([-n,n]\ 的任意一个数字,问有多少种改变方式(不改也算一种),能使得游戏结束。

题解

知识点:dfs,枚举。

\(0\ 作为游戏结束的点,那么 \(1\\(0\ 连通表示游戏一定可以结束。

    \(1\ 出发能经过的点。
  1. \(1\ 无关的其他点。

对于第二类点,改变他们并不影响 \(1\ 到终点的连通状态。因此,当 \(1\ 初始已经合法,那么他们能直接贡献 \(2n+1\ 个改变方案,否则没有任何贡献。

\(1\ 无解或路径成环。除去 \(n+1\ 种直接导向 \(0\ 点的方案,他们只能连接那些能到达 \(0\ 且不会使路径成环的点。

\(0\ 的距离(无穷大表示不可达)。第一类点可以导向距离比他小的第一类点,而反之一定成环。对于第二类点,如果他们能导向某个第一类点,那么我们可以认为他们的距离和这个第一类点是一样的,因为他们能不能使得路径成环,取决于他们导向的那个第一类点的距离大小,于是我们可以用相同的策略判断第二类点是否可以被导向。因此,我们把可达的点的距离排个序,每次可以二分查找得到合法点的个数

\(O(n \log n\

\(O(n\

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
int a[200007];
bool vis[200007], vis2[200007];
int dis[200007];

int dfs(int u {
    if (u < 1 || u > n return 0;
    if (vis[u] return dis[u];
    vis[u] = 1;
    return dis[u] = dfs(u + a[u] + 1;
}

int dfs2(int u {
    if (u < 1 || u > n return 0;
    if (vis[u] || vis2[u] return dis[u];
    vis2[u] = 1;
    return dis[u] = dfs2(u + a[u];
}

bool solve( {
    cin >> n;
    for (int i = 1;i <= n;i++ cin >> a[i], dis[i] = 1e9, vis[i] = vis2[i] = 0;
    dfs(1;
    for (int i = 1;i <= n;i++ dfs2(i;
    vector<int> v;
    for (int i = 1;i <= n;i++ if (dis[i] < 1e9 v.push_back(dis[i];
    sort(v.begin(, v.end(;
    ll ans = 0;
    for (int i = 1;i <= n;i++ {
        if (vis[i] ans += n + 1 + (lower_bound(v.begin(, v.end(, dis[i] - v.begin(;
        else if (dis[1] < 1e9 ans += 2 * n + 1;
    }
    cout << ans << '\n';
    return true;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int t = 1;
    cin >> t;
    while (t-- {
        if (!solve( cout << -1 << '\n';
    }
    return 0;
}

E

题意

给定正整数 \(n,k,x\,要求分为恰好 \(k\ 个非空子序列,使得这 \(k\ 个子序列的异或和都为 \(x\

题解

知识点:位运算,贪心,构造。

\(k\ 个 \(x\ 的异或和等于 \(a_i\ 的异或和。满足必要条件后,我们尝试划分序列。

\(k\ 相同,而其他数的异或和一定为 \(0\

    最大值大于等于 \(k\ 一定有解,我们可以把多出来的序列和多余的数全部扔进一个序列里,不会改变异或和。

  1. \(k\ 个一定无解,因为已经是能得到的最大值了。

\([1,n]\ 中:

    如果有 \(x\ 那就单独分一组。
  1. 对于 \(i\,如果 \(x \oplus i \leq n\,那就 \(i, x \oplus i\ 两个数分一组。

证明:

\(x\,那么我们一定要保证每个序列都有奇数个数,满足在 \(x\ 的最高位 \(1\ 处也是 \(1\

    \([1,n]\ 中有 \(m\ 个数满足在 \(x\ 的最高位 \(1\ 处也是 \(1\,那我们至多可以分 \(m\ 个序列。

  1. \(m\ 个数中任意一个数 \(i\\(i \oplus x\ 一定小于 \(i\,所以一定能找到数 \(i \oplus x\ 与其对应。同时,根据异或运算的等式性质,可以断定 \(i,i \oplus x\ 是唯一确定的一对,不会出现一个数被多个数对应,所以我们至少可以分 \(m\ 个序列。

\(i,i \oplus x\ ( \(x\ 可以直接安排进一个序列)的方式分出最多的序列,共 \(m\ 个。

时间复杂度 \(O(n\

\(O(n\

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve( {
    int n, k, x;
    cin >> n >> k >> x;
    int xsum = 0;
    for (int i = 1;i <= n;i++ xsum ^= i;
    if (xsum != x * (k & 1 return false;
    vector<char> vis(n + 1;
    vector<vector<int>> v;
    for (int i = 1;i <= n;i++ {
        if (vis[i] || (x ^ i > n continue;
        if (i == x v.push_back({ i };
        else v.push_back({ i,x ^ i };
        vis[i] = vis[i ^ x] = 1;
    }
    if (v.size( < k return false;
    cout << "YES" << '\n';
    for (int i = 0;i < k - 1;i++ {
        cout << v[i].size( << ' ';
        for (auto val : v[i] cout << val << ' ';
        cout << '\n';
    }
    vector<int> r;
    for (int i = k - 1;i < v.size(;i++ for (auto val : v[i] r.push_back(val;
    for (int i = 1;i <= n;i++ if (!vis[i] r.push_back(i;
    cout << r.size( << ' ';
    for (auto val : r cout << val << ' ';
    cout << '\n';
    return true;
}

int main( {
    std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
    int t = 1;
    cin >> t;
    while (t-- {
        if (!solve( cout << "NO" << '\n';
    }
    return 0;
}

编程笔记 » TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes) A-E

赞同 (29) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽