Kalorona

Codeforces Round #511 (Div. 1) – 解题报告

A – Enlarge GCD

大概可以想到，先把所有的数除掉一个 GCD 之后再来计算出现次数最多的素因子。我们用埃筛筛一下每个数的最小素因子，然后暴力除做标记即可。

// CF1034A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200, MAX_P = 1.5e7 + 200;

int n, ai[MAX_N], primes[MAX_P], ptot, gloabl_gcd, cnt[MAX_P], sfactor[MAX_P];
bool vis[MAX_P];

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    // sieve process;
    for (int i = 2; i < MAX_P; i++)
    {
        if (!vis[i])
            primes[++ptot] = i;
        for (int j = 1; j <= ptot && 1LL * primes[j] * i < MAX_P; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = 2; i < MAX_P; i++)
        sfactor[i] = i;
    for (int i = 2; i < MAX_P; i++)
        if (!vis[i])
            for (int j = (i << 1); j < MAX_P; j += i)
                if (sfactor[j] == j)
                    sfactor[j] = i;
    // read;
    scanf("%d%d", &n, &gloabl_gcd), ai[1] = gloabl_gcd;
    for (int i = 2; i <= n; i++)
        scanf("%d", &ai[i]), gloabl_gcd = gcd(gloabl_gcd, ai[i]);
    for (int i = 1; i <= n; i++)
        ai[i] /= gloabl_gcd;
    for (int i = 1; i <= n; i++)
    {
        int curt = ai[i];
        while (curt != 1)
        {
            int x = sfactor[curt];
            cnt[x]++;
            while (sfactor[curt] == x)
                curt /= sfactor[curt];
        }
    }
    int ans = n;
    for (int i = 1; i < MAX_P; i++)
        ans = min(ans, n - cnt[i]);
    if (ans == n)
        puts("-1");
    else
        printf("%d\n", ans);
    return 0;
}

B – Little C Loves 3 II

打表题吧，先用网络流打个表然后找到规律即可。

// CF1034B.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m;

int main()
{
    scanf("%lld%lld", &n, &m);
    if (n > m)
        swap(n, m);
    long long ans = 0;
    if (n == 1)
        ans = 6LL * ll(m / 6) + 2LL * max(m % 6 - 3, 0LL);
    else if (n == 2)
    {
        if (m == 2)
            ans = 0;
        else if (m == 3)
            ans = 4;
        else if (m == 7)
            ans = 12;
        else
            ans = m * n;
    }
    else
        ans = 1LL * n * m;
    printf("%lld\t", ans ^ (ans & 1LL));
    return 0;
}

C – Region Seperation

啊这题好难。

首先考虑分成二级的情况，列出几个已知的东西：

  • 二级的和 \(L_2\) 一定为 \(S_1\) 的一个约数。
  • 假设要剥离出 \(\frac{S_1}{k}\) 大小的块，那么我们就可以自底向上的去做，然后记录下与 \(S_1\) 的 gcd。考虑每一个 \(d = \gcd\) 出现了 \(d\) 次，那么在模意义下可以直接相减 \(k\) 次获得至少 \(k\) 组个为 \(0\) 的差。这个跟某个背包题的贪心结论很相似。
  • 最后用埃筛式的 DP 来统计所有的答案即可。
// CF1034C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, mod = 1e9 + 7;
typedef long long ll;

int n, fa[MAX_N], dp[MAX_N];
ll sum[MAX_N], cnt[MAX_N];

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &sum[i]);
    for (int i = 2; i <= n; i++)
        scanf("%d", &fa[i]);
    for (int i = n; i >= 1; i--)
        if (fa[i])
            sum[fa[i]] += sum[i];
    for (int i = n; i >= 1; i--)
    {
        sum[i] = sum[1] / gcd(sum[1], sum[i]);
        if (sum[i] <= n)
            cnt[sum[i]]++;
    }
    for (int i = n; i >= 1; i--)
        for (int j = (i << 1); j <= n; j += i)
            cnt[j] += cnt[i];
    dp[1] = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (cnt[i] == i)
        {
            ans = (0LL + ans + dp[i]) % mod;
            for (int j = i << 1; j <= n; j += i)
                dp[j] = (0LL + dp[j] + dp[i]) % mod;
        }
    printf("%d\n", ans);
    return 0;
}

D – Intervals of Intervals

先来一个二分答案，找出第 \(k\) 大的集合大小。我们可以用 ODT 的方式来处理线段和。

二分答案之后，我们可以使用这个答案来作为 two-pointers 的条件，然后就可以算个数和长度和。最后答案会多出一点，我们只需要用被计算的线段的个数减掉要求的线段个数，再乘上第 \(k\) 大的集合大小即可算完。

// CF1034D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200, INF = 0x3f3f3f3f;

typedef pair<int, int> pii;
typedef long long ll;

int n, limit, li[MAX_N], ri[MAX_N], len[MAX_N];

struct node
{
    int l, r, timestamp;
    bool operator<(const node &rhs) const { return l < rhs.l || (l == rhs.l && r < rhs.r); }
};

multiset<node> ms;
vector<pii> info[MAX_N];

bool check(int mid)
{
    int acc = 0;
    ll cnt = 0;
    for (int i = 1, ptr = 1; i <= n; i++)
    {
        len[i] = ri[i] - li[i] + 1, acc += len[i];
        for (auto &x : info[i])
        {
            len[x.second] -= x.first;
            // coming later;
            if (x.second >= ptr)
                acc -= x.first;
        }
        while (acc >= mid)
            acc -= len[ptr], ptr++;
        cnt += ptr - 1;
    }
    return cnt >= limit;
}

void calc(int max_len)
{
    int acc = 0;
    ll ans = 0, len_acc = 0, len_cnt = 0;
    for (int i = 1, ptr = 1; i <= n; i++)
    {
        len[i] = ri[i] - li[i] + 1, acc += len[i];
        for (auto &x : info[i])
        {
            len[x.second] -= x.first;
            // coming later;
            if (x.second >= ptr)
                acc -= x.first;
            if (x.second > 0 && x.second < ptr)
                len_acc -= 1LL * x.second * x.first;
        }
        while (acc >= max_len)
            acc -= len[ptr], len_acc += 1LL * ptr * len[ptr], ptr++;
        ans += len_acc + 1LL * acc * (ptr - 1), len_cnt += (ptr - 1);
    }
    printf("%lld\n", ans - 1LL * (len_cnt - limit) * max_len);
}

int main()
{
    scanf("%d%d", &n, &limit);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &li[i], &ri[i]), ri[i]--;
    // ODT-like initialize;
    ms.insert(node{0, INF, 0});
    for (int i = 1; i <= n; i++)
    {
        auto it = --ms.lower_bound(node{li[i], INF, 0});
        if (it->r >= ri[i])
        {
            // covered;
            info[i].push_back(make_pair(ri[i] - li[i] + 1, it->timestamp));
            if (it->l < li[i])
                ms.insert(node{it->l, li[i] - 1, it->timestamp});
            if (it->r > ri[i])
                ms.insert(node{ri[i] + 1, it->r, it->timestamp});
            ms.erase(it), ms.insert(node{li[i], ri[i], i});
        }
        else
        {
            // intersect;
            info[i].push_back(make_pair(it->r - li[i] + 1, it->timestamp));
            if (it->l < li[i])
                ms.insert(node{it->l, li[i] - 1, it->timestamp});
            ms.erase(it++);
            if (it->r < li[i])
                it++;
            while (it->r < ri[i])
                info[i].push_back(make_pair(it->r - it->l + 1, it->timestamp)), ms.erase(it++);
            info[i].push_back(make_pair(ri[i] - it->l + 1, it->timestamp));
            if (it->r > ri[i])
                ms.insert(node{ri[i] + 1, it->r, it->timestamp});
            ms.erase(it), ms.insert(node{li[i], ri[i], i});
        }
    }
    int l = 0, r = 1e9, res;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1, res = mid;
        else
            r = mid - 1;
    }
    calc(res);
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *