Skip to content

2020 牛客国庆集训派对 Day8

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K
6/11 O - - O O O O - - O -
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

Problem A. Easy Chess

Solved By Dup4. 02:36(+2)

题意

给出一个 8 \cdot 8 的棋盘，要求给出 a_1 到 h_8 的长度为 n 的路径。

思路

分类讨论一下，然后绕来绕去。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n;
char f[10];

void run() {
    rd(n);
    for (int i = 0; i < 8; ++i) f[i + 1] = 'a' + i;
    vector<pII> vec;
    if (n <= 50) {
        vec.push_back(pII(1, 1));
        int x = 1, y = 1;
        for (int i = 1; i <= n - 2; ++i) {
            if (x & 1) {
                ++y;
                if (y == 8) {
                    ++x;
                    --y;
                }
            } else {
                --y;
                if (y == 0) {
                    ++x;
                    ++y;
                }
            }
            vec.push_back(pII(x, y));
        }
        //	if (x == 8) --x;
        vec.push_back(pII(x, 8));
        vec.push_back(pII(8, 8));
    } else {
        for (int i = 1; i <= 6; ++i) {
            if (i & 1) {
                for (int j = 1; j <= 8; ++j) vec.push_back(pII(i, j));
            } else {
                for (int j = 8; j >= 1; --j) vec.push_back(pII(i, j));
            }
        }
        if (n == 51) {
            vec.push_back(pII(8, 1));
            vec.push_back(pII(8, 2));
            vec.push_back(pII(8, 3));
            vec.push_back(pII(8, 8));
        } else {
            n -= 49;
            vec.push_back(pII(7, 1));
            vec.push_back(pII(7, 8));
            if (n - 2 >= 6) {
                n -= 6;
                for (int i = 7; i >= 2; --i) {
                    vec.push_back(pII(7, i));
                }
                n -= 1;
                vec.push_back(pII(8, 2));
                if (n > 1) {
                    n -= 1;
                    vec.push_back(pII(8, 1));
                }
                for (int i = 1, j = 3; i < n; ++i, ++j) vec.push_back(pII(8, j));
                vec.push_back(pII(8, 8));
            } else {
                int i = 7;
                for (int j = n - 2; j; --i, --j) {
                    vec.push_back(pII(7, i));
                }
                vec.push_back(pII(8, i + 1));
                vec.push_back(pII(8, 8));
            }
        }
    }
    //	dbg(SZ(vec));
    for (int i = 0; i < SZ(vec); ++i) {
        cout << f[vec[i].fi] << vec[i].se << " \n"[i == SZ(vec) - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem B. Cactus Jubilee

Upsolved By -.

题意

思路

Problem C. Distance on Triangulation

Upsolved By -.

题意

思路

Problem D. PACM Team

Solved By Dup4. 01:37(+1)

题意

给出 n 个队伍，每个队伍有四种属性 p_i, a_i, c_i, m_i，选取一支队伍能够获得 g_i 点利益。 现在选出若干支队伍，并且要求 \sum p_i \leq P, \sum a_i \leq A, \sum c_i \leq C, \sum m_i \leq M, 并且利益最大。

1 \leq n, p_i, a_i, c_i, m_i, P, A, C, M \leq 36。

思路

分成两段枚举，每段 18 个，然后拼接。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e2 + 10;
int n, P, A, C, M;
int f[2][40][40][40][40], g[2][40][40][40][40];

struct E {
    int p, a, c, m, g;
    E() {}
    void scan() {
        rd(p, a, c, m, g);
    }
} e[N];

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) e[i].scan();
    rd(P, A, C, M);
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    pII ran[2] = {pII(1, min(18, n)), pII(19, n)};
    for (int o = 0; o < 2; ++o) {
        int l = ran[o].fi, r = ran[o].se;
        if (l > r)
            continue;
        for (int S = 1; S < 1 << 18; ++S) {
            int _P = 0, _A = 0, _C = 0, _M = 0, _G = 0;
            for (int i = 0; i < r - l + 1; ++i) {
                if ((S >> i) & 1) {
                    int _i = l + i;
                    _P += e[_i].p;
                    _A += e[_i].a;
                    _C += e[_i].c;
                    _M += e[_i].m;
                    _G += e[_i].g;
                }
            }
            if (_P <= P && _A <= A && _C <= C && _M <= M) {
                if (_G > f[o][_P][_A][_C][_M]) {
                    f[o][_P][_A][_C][_M] = _G;
                    g[o][_P][_A][_C][_M] = S;
                }
            }
        }
        for (int i = 0; i <= 36; ++i) {
            for (int j = 0; j <= 36; ++j) {
                for (int k = 0; k <= 36; ++k) {
                    for (int l = 0; l <= 36; ++l) {
                        if (i && f[o][i - 1][j][k][l] > f[o][i][j][k][l]) {
                            f[o][i][j][k][l] = f[o][i - 1][j][k][l];
                            g[o][i][j][k][l] = g[o][i - 1][j][k][l];
                        }
                        if (j && f[o][i][j - 1][k][l] > f[o][i][j][k][l]) {
                            f[o][i][j][k][l] = f[o][i][j - 1][k][l];
                            g[o][i][j][k][l] = g[o][i][j - 1][k][l];
                        }
                        if (k && f[o][i][j][k - 1][l] > f[o][i][j][k][l]) {
                            f[o][i][j][k][l] = f[o][i][j][k - 1][l];
                            g[o][i][j][k][l] = g[o][i][j][k - 1][l];
                        }
                        if (l && f[o][i][j][k][l - 1] > f[o][i][j][k][l]) {
                            f[o][i][j][k][l] = f[o][i][j][k][l - 1];
                            g[o][i][j][k][l] = g[o][i][j][k][l - 1];
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    int S[2] = {0, 0};
    for (int i = 0; i <= 36; ++i) {
        for (int j = 0; j <= 36; ++j) {
            for (int k = 0; k <= 36; ++k) {
                for (int o = 0; o <= 36; ++o) {
                    int _i = P - i, _j = A - j, _k = C - k, _o = M - o;
                    if (_i >= 0 && _j >= 0 && _k >= 0 && _o >= 0 && f[0][i][j][k][o] + f[1][_i][_j][_k][_o] > res) {
                        res = f[0][i][j][k][o] + f[1][_i][_j][_k][_o];
                        S[0] = g[0][i][j][k][o];
                        S[1] = g[1][_i][_j][_k][_o];
                    }
                }
            }
        }
    }
    vector<int> res_vec;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 18; ++j) {
            if ((S[i] >> j) & 1) {
                res_vec.push_back(j + ran[i].fi - 1);
            }
        }
    }
    pt(SZ(res_vec));
    pt(res_vec);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem E. Easy Problemset

Solved By Dup4. 00:55(+)

题意

给出一些策略，然后选出若干个题目，求总的 hardness。

思路

签到。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n, need;
vector<vector<int>> vec;

void run() {
    rd(n, need);
    vec.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        vec[i].resize(nextInt());
        for (auto &it : vec[i]) rd(it);
    }
    int res = 0, pos = 0;
    while (need) {
        for (int i = 1; need && i <= n; ++i) {
            int x = 0;
            if (pos < SZ(vec[i])) {
                x = vec[i][pos];
            } else {
                x = 50;
            }
            if (x >= res || x == 50) {
                --need;
                res += x;
            }
        }
        ++pos;
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem F. Landscape Improved

Solved By Dup4. 03:21(+)

题意

给出 n 个矩形，宽度为一个单位宽度，高度为 h_i，现在能够增加某个矩形的高度，能增加第 i 个矩形的高度至 x，当且仅当第 i - 1 个矩形和第 i + 1 个矩形的高度大于等于 x - 1。 现在给出 m 个砖块，问最高的矩形最多能增加到多高？

思路

  • 二分答案。
  • 考虑对于当前第 i 个矩形，如果想让它成为最大高度，假设为 x，那么第 i + 1 个矩形高度应该大于等于 x - 1，第 i + 2 个矩形高度应该大于等于 x - 2。
  • 对于第 i + 1 个矩形，如果想让它成为最大高度，假设为 x，那么要第 i + 2 个矩形高度应该大于等于 x - 1，第 i + 3 个矩形高度应该大于等于 x - 3。
  • 我们发现，最高矩形右移的过程中，右边那部分矩形所需的高度也在递增，可以线性维护。
  • 对于左边的矩形，因为是递减的，好像不太好处理，我们将数组反转，它就变成了右边，处理两遍，然后合并计算即可。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
constexpr ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n;
ll has, f[N], g[N], a[N];

bool ok(ll x) {
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    ll use = 0;
    int r = 2;
    for (int i = 2; i < n; ++i) {
        use += r - i;
        while (r < n && a[r + 1] < x - (r + 1 - i)) {
            use += x - (r + 1 - i) - a[r + 1];
            ++r;
        }
        if (r == n && a[r] < x - (r - i))
            f[i] = INFLL;
        else {
            f[i] = use;
        }
        use -= (x - 1) - a[i + 1];
    }
    int l = n - 1;
    use = 0;
    for (int i = n - 1; i > 1; --i) {
        use += i - l;
        while (l > 1 && a[l - 1] < x - (i - l + 1)) {
            use += x - (i - l + 1) - a[l - 1];
            --l;
        }
        if (l == 1 && a[l] < x - (i - l))
            g[i] = INFLL;
        else
            g[i] = use;
        use -= (x - 1) - a[i - 1];
    }
    //	if (x == 5) {
    //		for (int i = 2; i < n; ++i)
    //			dbg(i, f[i], g[i]);
    //	}
    for (int i = 2; i < n; ++i) {
        if (x - a[i] + f[i] + g[i] <= has)
            return true;
    }
    return false;
}

void run() {
    rd(n, has);
    for (int i = 1; i <= n; ++i) rd(a[i]);
    ll l = *max_element(a + 1, a + 1 + n) + 1, r = 2e9, res = l - 1;
    while (r - l >= 0) {
        ll mid = (l + r) >> 1;
        //	dbg(mid);
        if (ok(mid)) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem G. Shuffle Cards

Solved By Dup4. 00:04(+)

题意

给出一个全排列，然后 m 次操作，每次将一段区间的数提取到开头。

思路

其实就是数组的剪切与合并，用传统的 Treap 能做，也能 pb_ds 搞一搞。

Code 
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N = 1e5 + 10;
rope<int> ro;
int n, q, a[N];

int main() {
    while (scanf("%d%d", &n, &q) != EOF) {
        for (int i = 1; i <= n; ++i) a[i] = i;
        ro.append(a + 1, n);
        for (int i = 1, p, s; i <= q; ++i) {
            scanf("%d%d", &p, &s);
            ro = ro.substr(p - 1, s) + ro.substr(0, p - 1) + ro.substr(p + s - 1, n - p - s + 1);
        }
        for (int i = 0; i < n; ++i) printf("%d%c", ro[i], " \n"[i == n - 1]);
    }
    return 0;
}

Problem H. Damage Assessment

Upsolved By -.

题意

思路

Problem I. Filter

Upsolved By -.

题意

思路

Problem J. Diff-prime Pairs

Solved By Dup4. 00:13(+)

题意

给出 n, 求有多少对 (i, j) 满足 1 \leq i, j \leq n 并且 \displaystyle \frac{i}{\gcd(i, j)} 与 \displaystyle \frac{j}{\gcd(i, j)} 互质。

思路

答案就是：

\sum\limits_{i = 1}^n \sum\limits_{j = 1}^{\frac{n}{i}} [j \; is \; prime]
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e7 + 10;
int n, f[N];

int pri[N], check[N];
void sieve() {
    memset(check, 0, sizeof check);
    *pri = 0;
    for (int i = 2; i < N; ++i) {
        if (!check[i]) {
            pri[++*pri] = i;
        }
        for (int j = 1; j <= *pri; ++j) {
            if (1ll * i * pri[j] >= N)
                break;
            check[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
    f[1] = 0;
    for (int i = 2; i < N; ++i) f[i] = f[i - 1] + (check[i] == 0);
}

ll calc(int n) {
    return 1ll * n * (n - 1) / 2;
}

void run() {
    rd(n);
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        res += calc(f[n / i]) * 2;
    }
    pt(res);
}

int main() {
    sieve();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem K. Improvements

Upsolved By -.

题意

思路

Last update: March 23, 2022
Created: March 23, 2022
Back to top