Codeforces Round #538 (Div. 2) 题解

Author Avatar
Sakits 2月 11, 2019

题解

  居然过了所有pt…(还没测完不敢立flag)
  人生中第二次 AK div2…

A. Got Any Grapes?

  贪就完事儿了

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 500010, inf = 1e9 + 233;

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

int main()
{
    int x, y, z, a, b, c;
    read(x); read(y); read(z);
    read(a); read(b); read(c);
    a -= x;
    if (a < 0) return puts("NO"), 0;
    if (y <= a) a -= y;
    else
    {
        b -= y - a;
        a = 0;
    }
    if (b < 0) return puts("NO"), 0;
    if (a + b + c < z) return puts("NO"), 0;
    puts("YES");
}

B. Yet Another Array Partitioning Task

  这题一眼看过去怎么觉得这么难…
  后来发现最大的 m×km \times k 个数一定可以构造出方案取到,就是每一次取到恰好 mm 个在这些数里的数就可以划分为一段了。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 500010, inf = 1e9 + 233;
struct poi{int w, pos;}q[maxn];
int n, m, k;
int a[maxn];
bool v[maxn];

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

bool operator < (poi a, poi b) {return a.w > b.w;}

int main()
{
    read(n); read(m); read(k);
    for (int i = 1; i <= n; i++) read(a[i]), q[i].w = a[i], q[i].pos = i;
    
    sort(q + 1, q + 1 + n);

    ll ans = 0;
    for (int i = 1; i <= m * k; i++) ans += q[i].w, v[q[i].pos] = 1;

    printf("%lld\n", ans);
    
    int now = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        now += v[i];
        if (now == m) printf("%d ", i), now = 0, cnt++;
        if (cnt == k - 1) return 0;
    }
}

C. Trailing Loves (or L’oeufs?)

  经典题改版,就是把 bb 分解质因数,然后对每个质因子看看 n!n! 能除几次,最小值就是答案了。
  要注意不要乘爆了…for循环的时候我写了个long double判了一下

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
#define int long long
using namespace std;
const int maxn = 500010, inf = 1e9 + 233;
int n, b;

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

signed main()
{
    read(n); read(b);

    int ans = 1e18;
    for (int i = 2; i * i <= b; i++)
    if (b % i == 0)
    {
        int cnt = 0, sum = 0;
        while (b % i == 0) cnt++, b /= i;
        for (int j = i; j <= n; j *= i) 
        {
            sum += n / j;
            if ((long double)j * i - n > (1e-9)) break;
        }
        ans = min(ans, sum / cnt);

        // printf("%lld %lld %lld\n", i, sum, cnt);
    }

    if (b != 1)
    {
        int sum = 0;
        for (int j = b; j <= n; j *= b) 
        {
            sum += n / j;
            if ((long double)j * b - n > (1e-9)) break;
        }
        ans = min(ans, sum);
    }

    printf("%lld\n", ans);
}

D. Flood Fill

  区间 DP,比赛的时候貌似脑抽写的很奇怪
  fl,rf_{l,r} 表示区间 [l,r][l,r] 内的改成同种颜色的代价,每次要么左端点改,要么右端点改,如果左右端点的颜色一样,那就改中间的就完事了。
  放个脑抽了的代码,反正相信大部分人都会做…

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 5010, inf = 1e9 + 233;
int n;
int a[maxn], f[maxn][maxn], findl[maxn], findr[maxn];

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

int main()
{
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);

    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][i] = 0;

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == a[i - 1]) findr[i] = findr[i - 1];
        else findr[i] = i;
    }

    for (int i = n; i; i--)
    {
        if (a[i] == a[i + 1]) findl[i] = findl[i + 1];
        else findl[i] = i;
    }

    for (int l = n - 1; l; l--)
    {
        for (int r = l + 1; r <= n; r++)
        {
            if (a[l] != a[r]) 
            {
                if (findl[l] + 1 != findr[r]) f[l][r] = min(f[findl[l] + 1][r], f[l][findr[r] - 1]) + 1;
                else f[l][r] = 1;
            }
            else
            {
                if (findl[l] < findr[r]) f[l][r] = f[findl[l] + 1][findr[r] - 1] + 1;
                else f[l][r] = 0;
            }
        }
    }

    printf("%d\n", f[1][n]);
}

E. Arithmetic Progression

  为什么又是二分交互题…(大雾
  先二分出最大值,然后随机询问一些位置,查出它和前驱后继的差,跟答案取 gcd\gcd,感觉应该 log\log 次就可以得到答案了…
  因为其实数字个数并不多,n2n^2 暴力就行了没必要写个set

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1000010, inf = 1e9 + 233;
set<int>s;
vector<int>v;
int n, x, y, cnt;

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

inline bool check(int p)
{
    cnt--;

    printf("> %d\n", p);
    fflush(stdout);

    bool flag = 0;
    read(flag);

    return !flag;
}

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

int main()
{
    srand(time(0));

    read(n);
    
    int l = 0, r = 1e9; cnt = 60;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    s.insert(l);
    int ans = 0;

    for (int i = 1; i <= n; i++) v.push_back(i);

    for (int i = 1; i <= cnt && i <= n; i++)
    {
        int x = (1ll * rand() * rand()) % v.size();

        printf("? %d\n", v[x]);
        fflush(stdout);
        read(y);

        v[x] = v.back(); v.pop_back();

        auto it = s.lower_bound(y);
        if (it != s.end()) ans = gcd(ans, (*it) - y);
        if (it != s.begin())
        {
            it--;
            ans = gcd(ans, y - (*it));
        }

        s.insert(y);
    }

    printf("! %d %d\n", l - (n - 1) * ans, ans);
    fflush(stdout);
}

F. Please, another Queries on Array?

  因为值域只有 300300,所以考虑把 300300 内的质数全部搞出来,φ(x)\varphi(x) 其实就是每个 xx 的质因子 pp 贡献 p1p\frac{p - 1}{p},所以线段树上维护每个区间的积和出现的质数状态,因为只有 6262 个,压成一个 unsigned long long 即可。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;
const int maxn = 500010, inf = 1e9 + 233, mod = 1e9 + 7;
struct sgt{int sum, delta; ull tag, st;}tr[maxn << 2];
int n, Q, x, y, z, l, r, cnt;
int pri[maxn], a[maxn];
char s[maxn];

template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

inline int power(int a, int b)
{
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}

inline void addone(int x, int delta, ull st, int len)
{
    // printf("addone:%d %d\n", delta, len);
    tr[x].sum = 1ll * tr[x].sum * power(delta, len) % mod;
    tr[x].delta = 1ll * tr[x].delta * delta % mod;
    tr[x].st |= st;
    tr[x].tag |= st;
}

inline void up(int x)
{
    tr[x].sum = 1ll * tr[x << 1].sum * tr[x << 1 | 1].sum % mod;
    tr[x].st = tr[x << 1].st | tr[x << 1 | 1].st;
}

inline void down(int x, int l, int r)
{
    if (tr[x].tag)
    {
        int mid = (l + r) >> 1;
        addone(x << 1, tr[x].delta, tr[x].tag, mid - l + 1);
        addone(x << 1 | 1, tr[x].delta, tr[x].tag, r - mid);
    }

    tr[x].tag = 0;
    tr[x].delta = 1;
}

void build(int x, int l, int r)
{
    tr[x].delta = 1;
    if (l == r)
    {
        tr[x].sum = a[l];
        

        for (int i = 0; i < cnt; i++)
            if (a[l] % pri[i] == 0) tr[x].st |= 1ull << i;

        return;
    }

    int mid = (l + r) >> 1;
    build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r);
    up(x);
}

void update(int x, int l, int r, int cl, int cr, int delta, ull st)
{
    if (cl <= l && r <= cr)
    {
        addone(x, delta, st, r - l + 1);
        return;
    }

    down(x, l, r);
    int mid = (l + r) >> 1;
    if (cl <= mid) update(x << 1, l, mid, cl, cr, delta, st);
    if (cr > mid) update(x << 1 | 1, mid + 1, r, cl, cr, delta, st);
    up(x);
    // printf("l:%d r:%d tr[x].sum:%d %d %d\n", l, r, tr[x].sum, tr[x << 1].sum, tr[x << 1 | 1].sum);
}

sgt operator + (sgt a, sgt b)
{
    if (a.sum == -1) return b;
    sgt c;
    c.sum = 1ll * a.sum * b.sum % mod;
    c.st = a.st | b.st;
    return c;
}

sgt query(int x, int l, int r, int cl, int cr)
{
    if (cl <= l && r <= cr) return tr[x];

    down(x, l, r);
    int mid = (l + r) >> 1; sgt ans = (sgt){-1};
    if (cl <= mid) ans = query(x << 1, l, mid, cl, cr);
    if (cr > mid) ans = ans + query(x << 1 | 1, mid + 1, r, cl, cr);
    // printf("l:%d r:%d cl:%d cr:%d ans.sum:%d ans.st:%llu\n", l, r, cl, cr, ans.sum, ans.st);
    return ans;
}

int main()
{
    for (int i = 2; i <= 300; i++)
    {
        bool flag = 1;
        for (int j = 2; j < i; j++)
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        if (flag) pri[cnt++] = i;
    }

    // printf("%d\n", cnt);
    // for (int i = 0; i < cnt; i++) printf("%d ", pri[i]);
        // puts("");

    read(n); read(Q);
    for (int i = 1; i <= n; i++) read(a[i]);

    build(1, 1, n);
    
    while (Q--)
    {
        scanf("%s", s + 1);
        if (s[1] == 'M') 
        {
            read(x), read(y), read(z);

            ull st = 0;
            for (int i = 0; i < cnt; i++)
                if (z % pri[i] == 0) st |= 1ull << i;

            // printf("st:%llu\n", st);

            // printf("qwqtr[1].sum:%d\n", tr[1].sum);
            update(1, 1, n, x, y, z, st);
            // printf("qaqtr[1].sum:%d\n", tr[1].sum);
        }
        else
        {
            read(l); read(r);
            sgt ans = query(1, 1, n, l, r);
                
            // printf("pre:%d %d %llu\n", tr[1].sum, ans.sum, ans.st);

            for (int i = 0; i < cnt; i++)
                if ((ans.st >> i) & 1)
                    ans.sum = 1ll * ans.sum * power(pri[i], mod - 2) % mod * (pri[i] - 1) % mod;
            
            printf("%d\n", ans.sum);
        }
    }
}