Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 – Final) 解题报告

发布于 2020-11-05  132 次阅读

A

只需要构造 $2n+2,2n+4,...,4n$ 就可以了。算下来刚好 $n$ 个人。

<

pre class="lang:default decode:true ">#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (vec.begin())
#define veclast (vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("nnTime used: system("pause");
#endif
}
int n;
inline void solve()
{
cin >> n;
for (int i = 2 * n + 2, tot = 1; tot <= n; ++tot, i += 2)
{
cout << i << " ";
}
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf( while (Test--)
{
solve();
// if (Test)
// putchar('n');
}
TIME__END = clock();
program_end();
return 0;
}``

B

贪心。连续的 1 段可以看成一个，问题就在于是把这些 1 段串起来然后一起激活还是每一个 1 段单独激活。连起来的话那么就需要计算串起来所需要的花费，然后从左到右贪心就可以了。

#include 
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("nnTime used:
    system("pause");
#endif
}
ll n, a, b;
string s;
inline void solve()
{
    cin >> a >> b >> s;
    n = s.length();
    ll ans = 0, lst = -inf;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '1')
            ans += min(a, b * (i - lst - 1)), lst = i;
    }
    cout << ans << 'n';
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
C

将每道菜按照 $a$ 排序，一个显然的贪心就是对于一个特定的 $a_0$，所有 $ale a_0$ 的菜都只需要点外卖即可。剩下的就是 $sum b$，我们可以枚举每一个 $a$，之后可以 $mathcal{O}(1)$ 计算剩下需要自己去买的 $sum b$，所有的情况取最小值就是答案。

#include 
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("nnTime used:
    system("pause");
#endif
}
int n;
ll sumb;
struct dishes
{
    ll a, b;
    bool operator<(const dishes &x) const
    {
        return a < x.a;
    }
} d[N];
inline void solve()
{
    sumb = 0;
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    ll ans = sumb;
    sort(d + 1, d + n + 1);
    int i = 1;
    ll maxa = d[i].a;
    while (i <= n)
    {
        while (d[i].a == maxa)
        {
            sumb -= d[i].b;
            i++;
        }
        ans = min(ans, max(maxa, sumb));
        maxa = d[i].a;
    }
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
D

如果整个序列都是单调不增或者单调不减的，那么我们就一定能够只操作其中一边来使整个序列减到 0。比如说整个序列是单调不增的，那么我们只需要操作左边就可以。
接下来问题就在于中间不是单调的怎么办。实际上，假设我们最后得到的序列是单调不增的，那么操作右边只会改变交界处的单调性。途中要保证右边的数不能减到小于 0。这样，我们可以两边分别算一下就可以了。代码实现中记录一个增量 delta 即可。

#include 
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("nnTime used:
    system("pause");
#endif
}
int n;
int a[N];
inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    int delta = 0;
    bool solved = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] > a[i - 1])
            delta += a[i] - a[i - 1];
        if (a[i] - delta < 0)
        {
            solved = 0;
            break;
        }
    }
    if (solved)
        return printf("YESn"), void();
    delta = 0, solved = 1;
    reverse(a + 1, a + n + 1);
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] > a[i - 1])
            delta += a[i] - a[i - 1];
        if (a[i] - delta < 0)
        {
            solved = 0;
            break;
        }
    }
    if (solved)
        return printf("YESn"), void();
    puts("NO");
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
E

一共最多只会跳 2e10 次，算一下发现最多只会变最后 15 项。那么我们可以用康托展开逆变换求出每次操作最后 15 项变成的排列，再重新计算一下 sum 前缀和即可。

#include 
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("nnTime used:
    system("pause");
#endif
}
int n, q;
int a[N], b[20];
ll sum[N];
ll fac[20];
void work(int n, ll k)
{
    int p[20] = {0};
    for (int i = 1; i <= n; ++i)
        b[i] = 0, p[i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll t = k / fac[n - i];
        k
        for (int j = 1; j <= n; ++j)
        {
            if (!b[j] && !(t--))
            {
                b[j] = 1, p[i] = j;
                break;
            }
        }
    }
    int L = max(0, (::n) - 15);
    for (int i = L + 1; i <= (::n); ++i)
        sum[i] = sum[i - 1] + p[i - L] + L;
}
inline void solve()
{
    fac[0] = 1;
    for (int i = 1; i <= 15; ++i)
        fac[i] = fac[i - 1] * i;
    scanf(
    for (int i = 1; i <= n; ++i)
        a[i] = i;
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + i;
    ll k = 0;
    while (q--)
    {
        int op, x, l, r;
        scanf(
        if (op == 2)
        {
            scanf(
            k += x;
            work(min(n, 15), k);
        }
        else
        {
            scanf(
            ll ans = sum[r] - sum[l - 1];
            printf(
        }
    }
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
F

首先把所有需要被打进 b 的位置给标记一下，之后从头开始 check 相邻的位置。每次 check 就看当前这个 $b_i$ 相邻位置上没有被打进 b 的元素个数。因为删除一个相邻位置的数之后，$b_i$ 也被打进 b 了，由于题目保证打进 b 的元素互不相同，那么这个元素打进去之后就没用了，可以理解为极限一换一。于是只需要看相邻的数即可。

#include 
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("nnTime used:
    system("pause");
#endif
}
int n, k;
int a[N], b[N], pos[N], c[N];
inline void solve()
{
    ll ans = 1;
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= k; ++i)
        scanf(
    for (int i = 1; i <= k; ++i)
    {
        ll fac = 0;
        fac += ((pos[b[i]] > 1) && (c[pos[b[i]] - 1])) + ((pos[b[i]] < n) && (c[pos[b[i]] + 1]));
        c[pos[b[i]]] = 1;
        ans = (ans * fac)
    }
    cout << ans << 'n';
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}