Logo kal0rona的博客

博客

FZOI WC 2020 抢救计划

2020-01-20 14:05:50 By kal0rona

为了抢救各位被文化课耽误的信息学,kal0rona 出了一套抢救计划。

科技

数据结构

  1. 主席树
  2. 树链剖分
  3. 线段树的各种骚操作
  4. 分块
  5. 左偏树

图论

  1. 虚树
  2. 图连通性 Tarjan
  3. 网络流
  4. 点分治

数学

  1. gcd, lcm, Euler's function.
  2. 线性筛,数论函数
  3. 莫比乌斯反演
  4. 计数问题
  5. 高斯消元

离线

  1. CDQ 分治
  2. 整体二分

计算几何

  1. 扫描线
  2. 凸包

DP

  1. 概率期望 DP
  2. 矩阵快速幂优化

字符串

  1. AC 自动机
  2. Manacher

题单

Codeforces

CF1288D

CF1182E

CF1223D

CF1223C

CF1286C1

CF1264C

CF1168A

CF1009E

AtCoder

AtCoder Grand Contest 002E

AtCoder Grand Contest 001E

LibreOJ

LOJ6029

Universial OJ

UOJ228

Quest OJ

QOJ2030

QOJ2033

QOJ2044

QOJ2017

Sphere OJ

SP3267

Luogu

P4774

P2469

P4099

P2513

P2606

P4284

P2455

P3389

P4103

P3261

P4178

P2495

P3041

P2617

P3242

P3121

「FZOI」OI 寒假赛 #1 Div.1 - 题解

2020-01-17 11:41:56 By kal0rona

A - 资本家 kal0rona

我们可以考虑把每个员工的前缀收益放在折线图上进行考虑:一条折线从$(1, 0)$出发,在$(x, y)$向上走就是给第$x$个员工发钱,上升高度就是发钱数量。最后,把老板当作第$n + 1$个员工即可。可以发现,因为这个是前缀收益,所以最后我们会走到$(n + 1, m)$,我们只需要算从$(1, 0)$到$(n + 1, m)$的不降路径数即可,也就是${n + m \choose m}$。

对于前 40% 的分我们只需要暴力处理组合数即可,用递推式:${n \choose k} = {n - 1 \choose k} + {n - 1 \choose k - 1}$即可。那么对于前 60% 的分我们需要用 Lucas 定理进行处理,也就是: $$ {n \choose k} \bmod p = {\lfloor \frac{n}{p} \rfloor \choose \lfloor \frac{k}{p} \rfloor} \cdot {n \bmod p \choose k \bmod p} \bmod p $$ 发现 $p$ 很小,我们就可以直接处理 $p$ 以内的阶乘和逆元即可计算。

那么对于 80% 的分数,我们可以对不同的模数做两次,然后用 CRT 进行合并即可。那么对于全部分数,就需要一点技巧。我们仍然使用 CRT 进行合并,但是对于每一个质数幂来说计算方式有变化:

我们发现质数幂不能用正常的 Fermat Little Therom 来算,因为有些数字是没有逆元的。在模$p^c$意义下,如果$\gcd(x, p^c) \neq 1$,那么这样的$x$是没有逆元的。那我们如何来计算呢?首先,我们先把组合数写出来: $$ {n \choose k} \bmod p^c = \frac{n!}{(n - k)!k!} \bmod p^c = p^x \frac{f(n!)}{f[(n - k)!]f(k!)} \bmod p^c $$ 其中,我们可以把阶乘中的$p$的幂给提取出来,然后进行上下化简。对于分母,由于与$p$互质,所以可以直接用扩展欧几里得算法得出逆元。至于$p^x$,可以直接快速幂。然后上下式可以直接用类似 Lucas 定理的方式处理(在模意义下,阶乘是有循环率的,自己打个表康康即可)即可。处理时需要记录$p$的出现次数。

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

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, p, primes[MAX_N], cnt[MAX_N], ptot, cmod, pic[MAX_N], ai[MAX_N];

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y), t = x;
    x = y, y = t - (a / b) * y;
    return d;
}

int getInv(int a)
{
    int x, y;
    exgcd(a, cmod, x, y);
    return (x + cmod) % cmod;
}

int quick_pow(int bas, int tim)
{
    if (tim < 0)
        return quick_pow(getInv(bas), -tim);
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % cmod;
        bas = 1LL * bas * bas % cmod;
        tim >>= 1;
    }
    return ret;
}

int fac(int x, int mod)
{
    int ret = 1;
    for (int i = 1; i <= x; i++)
        if (i % mod != 0)
            ret = 1LL * ret * i % cmod;
    return ret;
}

int fac(int x, int mod, int &tot)
{
    // lucas;
    if (x < mod)
        return fac(x, mod);
    int seg = x / cmod, rem = x % cmod;
    int res = 1LL * quick_pow(fac(cmod - 1, mod), seg) * fac(rem, mod) % cmod;
    tot += x / mod;
    res = 1LL * res * fac(x / mod, mod, tot) % cmod;
    return res;
}

int binomial(int n_, int k_, int mod)
{
    int a = 0, b = 0, c = 0, res = 1;
    res = 1LL * res * fac(n_, mod, a) % cmod * getInv(fac(k_, mod, b)) % cmod * getInv(fac(n_ - k_, mod, c)) % cmod;
    return 1LL * res * quick_pow(mod, a - (b + c)) % cmod;
}

void factorize(int tmp)
{
    for (int i = 2; 1LL * i * i <= tmp; i++)
        if (tmp % i == 0)
        {
            primes[++ptot] = i;
            while (tmp % i == 0)
                cnt[ptot]++, tmp /= i;
        }
    if (tmp > 1)
        primes[++ptot] = tmp, cnt[ptot] = 1;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p), n += m;
    factorize(p);
    for (int i = 1; i <= ptot; i++)
    {
        cmod = 0x7fffffff, cmod = pic[i] = quick_pow(primes[i], cnt[i]);
        ai[i] = binomial(n, m, primes[i]);
    }
    cmod = 0x7fffffff;
    // begins to merge;
    for (int i = 2; i <= ptot; i++)
    {
        int x, y;
        exgcd(pic[i - 1], pic[i], x, y);
        pic[i] *= pic[i - 1];
        ai[i] = ((1LL * x * (ai[i] - ai[i - 1]) * pic[i - 1] % pic[i] + ai[i - 1]) % pic[i] + pic[i]) % pic[i];
    }
    printf("%d\n", ai[ptot]);
    return 0;
}

B - XOR-MIN-MAX

这道题很适合作为被 A 穿签到题,利用了分治的思想,很适合缺乏分治思维训练的选手。

我们可以设置任务$solve(dep, l, r)$为「确定最大值下标在$[l, r]$,正在处理第$dep$位」。具体如何理解呢?首先,显然高位的权要比低位的权要高,那么,如果这段区间中所有数的第$dep$位并不能被消成$0$,也就是这段区间内的数在第$dep$位存在$0, 1$两种情况,那么在$X_{dep}$中我们选$0, 1$都无法让最大值小于$2^{dep}$,那么我们可以分类讨论:把在$[l, r]$之间,$dep$这一位为$0, 1$的数字分类成集合$A, B$,然后把它们第$dep$位都赋为$1$。

如果$X$的第$dep$位为$0$,则最大值将会出现在集合$B$中,执行$solve(mid + 1, r, dep - 1)$;反过来同理。

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

using namespace std;

const int MAX_N = 1e5 + 200;

int n, ai[MAX_N], ans = 0x7fffffff, tmp[MAX_N];

void solve(int l, int r, int dep)
{
    if (l > r)
        return;
    if (dep == -1)
    {
        int max_val = 0;
        for (int i = l; i <= r; i++)
            max_val = max(max_val, ai[i]);
        ans = min(ans, max_val);
        return;
    }
    int lptr = l, rptr = r, cnt0 = 0, cnt1 = 0;
    for (int i = l; i <= r; i++)
        if (ai[i] & (1 << dep))
            tmp[rptr--] = ai[i], cnt1++;
        else
            tmp[lptr++] = ai[i], cnt0++;
    if (cnt1 == (r - l + 1))
        for (int i = l; i <= r; i++)
            ai[i] = (tmp[i] ^ (1 << dep));
    else if (cnt0 == (r - l + 1))
        for (int i = l; i <= r; i++)
            ai[i] = tmp[i];
    else
        for (int i = l; i <= r; i++)
            ai[i] = (tmp[i] | (1 << dep));
    solve(l, lptr - 1, dep - 1), solve(lptr, r, dep - 1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    solve(1, n, 29);
    printf("%d\n", ans);
    return 0;
}

C - 平面上的点

$\Theta(n^2)$暴力还是很好写的,先枚举水平线,然后再分上下讨论;讨论中,我们都要从左往右枚举,但是我们有两个指针$lptr, rptr$,我们可以在过程中维护在$[lptr, rptr]$之间的颜色数始终严格小于$k$,然后再用点个数更新答案。

那么正解就没这么好写了。我们考虑在$k$中枚举一个被排除的颜色,然后分情况讨论:

  • 按$x$排序,相邻点对做垂直线,两线之间的点个数可能成为答案。
  • 向上看,我们可以把点按$y$降序排序,然后让矩形的横线段$[l, r]$强行$\in x_i$,也就是置横线段为当前点之上。用 multiset 查询当前点前驱后继的$x$作为矩形的横线范围,然后把当前点的$y + 1$作为基准线,用主席树查询当前矩形内的点数。
  • 向下看类似。

详细见代码:

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

using namespace std;

const int MAX_N = 4e5 + 200;

int T, n, k, roots[MAX_N], yupper, gans;

struct point
{
    int x, y, c;
    bool operator<(const point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
} pts[MAX_N];

typedef multiset<point>::iterator mpit;

bool compareByY(const point &rhs1, const point &rhs2) { return rhs1.y < rhs2.y || (rhs1.y == rhs2.y && rhs1.x < rhs2.x); }

vector<point> ptByColor[MAX_N];
vector<int> mpx, mpy;

inline char nc()
{
    static char buf[10000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

namespace PST
{

struct node
{
    int lson, rson, val;
} nodes[MAX_N << 5];

int ptot;

int update(int qx, int l, int r, int pre)
{
    int p = ++ptot;
    nodes[p] = nodes[pre], nodes[p].val++;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid, nodes[pre].lson);
    else
        nodes[p].rson = update(qx, mid + 1, r, nodes[pre].rson);
    return p;
}

int query(int ql, int qr, int l, int r, int pre, int p)
{
    if (ql > qr)
        return 0;
    if (ql <= l && r <= qr)
        return nodes[p].val - nodes[pre].val;
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid)
        ret += query(ql, qr, l, mid, nodes[pre].lson, nodes[p].lson);
    if (mid < qr)
        ret += query(ql, qr, mid + 1, r, nodes[pre].rson, nodes[p].rson);
    return ret;
}

void init()
{
    ptot = 0;
    int last_ptr = 0;
    for (int i = 1, r = 0; i <= n; i = r + 1)
    {
        r = i, roots[pts[i].x] = update(pts[i].y, 1, yupper, last_ptr), last_ptr = roots[pts[i].x];
        while (r + 1 <= n && pts[r + 1].x == pts[i].x)
            r++, roots[pts[i].x] = update(pts[r].y, 1, yupper, last_ptr), last_ptr = roots[pts[i].x];
    }
}

} // namespace PST

int ripe(vector<int> &vec, int x) { return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1; }

void processCategory(int color)
{
    using namespace PST;
    if (ptByColor[color].empty())
        return (void)(gans = max(gans, n));
    sort(ptByColor[color].begin(), ptByColor[color].end());
    // horizontal intervals;
    gans = max(gans, query(1, yupper, 1, yupper, 0, roots[ptByColor[color].front().x - 1]));
    for (int i = 1, siz = ptByColor[color].size(); i < siz; i++)
    {
        point pt = ptByColor[color][i];
        gans = max(gans, query(1, yupper, 1, yupper, roots[ptByColor[color][i - 1].x], roots[pt.x - 1]));
        continue;
    }
    gans = max(gans, query(1, yupper, 1, yupper, roots[ptByColor[color].back().x], roots[mpx.size()]));
    // looking up;
    sort(ptByColor[color].begin(), ptByColor[color].end(), compareByY);
    multiset<point> ms;
    for (int siz = ptByColor[color].size(), i = siz - 1; i >= 0; i--)
    {
        mpit curt = ms.insert(ptByColor[color][i]);
        int baseLine = ptByColor[color][i].y + 1;
        int l, r;
        if (curt != ms.begin())
            curt--, l = curt->x, curt++;
        else
            l = 0;
        curt++;
        if (curt != ms.end())
            r = curt->x - 1;
        else
            r = mpx.size();
        curt--;
        gans = max(gans, query(baseLine, yupper, 1, yupper, roots[l], roots[r]));
    }
    ms.clear();
        // looking down;
    for (int siz = ptByColor[color].size(), i = 0; i < siz; i++)
    {
        mpit curt = ms.insert(ptByColor[color][i]);
        int baseLine = ptByColor[color][i].y - 1;
        int l, r;
        if (curt != ms.begin())
            curt--, l = curt->x, curt++;
        else
            l = 0;
        curt++;
        if (curt != ms.end())
            r = curt->x - 1;
        else
            r = mpx.size();
        curt--;
        gans = max(gans, query(1, baseLine, 1, yupper, roots[l], roots[r]));
    }
}

int main()
{
    T = read();
    while (T--)
    {
        n = read(), k = read();
        mpx.clear(), mpy.clear(), gans = 0;
        for (int i = 1; i <= n; i++)
        {
            pts[i].x = read(), pts[i].y = read(), pts[i].c = read();
            mpx.push_back(pts[i].x), mpy.push_back(pts[i].y);
        }
        sort(mpx.begin(), mpx.end()), mpx.erase(unique(mpx.begin(), mpx.end()), mpx.end());
        sort(mpy.begin(), mpy.end()), mpy.erase(unique(mpy.begin(), mpy.end()), mpy.end());
        yupper = mpy.size();
        for (int i = 1; i <= k; i++)
            ptByColor[i].clear();
        for (int i = 1; i <= n; i++)
        {
            pts[i].x = ripe(mpx, pts[i].x), pts[i].y = ripe(mpy, pts[i].y);
            ptByColor[pts[i].c].push_back(pts[i]);
        }
        sort(pts + 1, pts + 1 + n), PST::init();
        for (int i = 1; i <= k; i++)
            processCategory(i);
        printf("%d\n", gans);
    }
    return 0;
}

「FZOI」OI 周赛 #4 Div.1 - 题解

2020-01-04 18:17:51 By kal0rona

A - 对称的多边形

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

typedef long long ll;

using namespace std;

const int MAX_N = 4e5 + 200;

int T, n, xi[MAX_N], yi[MAX_N], len[MAX_N];
ll seq[MAX_N];

ll getDist(int x1, int y1, int x2, int y2)
{
    return ll(x1 - x2) * ll(x1 - x2) + ll(y1 - y2) * ll(y1 - y2);
}

ll getAngle(int orgx, int orgy, int x1, int y1, int x2, int y2)
{
    ll dx1 = x1 - orgx, dy1 = y1 - orgy;
    ll dx2 = x2 - orgx, dy2 = y2 - orgy;
    return dx1 * dy2 - dx2 * dy1;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(len, 0, sizeof(len));
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &xi[i], &yi[i]);
        // create new string for manacher;
        for (int i = 0; i < n; i++)
        {
            seq[(i << 1) | 1] = getDist(xi[i], yi[i], xi[(i + 1) % n], yi[(i + 1) % n]);
            seq[(i << 1)] = getAngle(xi[i], yi[i], xi[(i + n - 1) % n], yi[(i + n - 1) % n], xi[(i + 1) % n], yi[(i + 1) % n]);
        }
        int tot_len = n << 1;
        for (int i = 0; i < n; i++)
            seq[i + tot_len] = seq[i];
        tot_len <<= 1;
        int R = 0, ans = 0, mid = 0;
        for (int i = 0; i < tot_len; i++)
        {
            if (i < R)
                len[i] = min(R - i, len[mid * 2 - i]);
            else
                len[i] = 1;
            while (i - len[i] >= 0 && i + len[i] < tot_len && seq[i + len[i]] == seq[i - len[i]])
                len[i]++;
            if (i + len[i] > R)
                R = i + len[i], mid = i;
            if (len[i] >= n + 1)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B - 最小方差树

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 2020;

int fa[MAX_N], n, m;
double ans = (double)(0x3f3f3f3f);

struct edge
{
    int from, to, weight;
    double cmp;
    bool operator<(const edge &d) const { return cmp < d.cmp; }
} edges[MAX_N];

int find(int x) { return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }

void kruskal(double avg)
{
    double sqr = 0;
    double len = 0;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
        edges[i].cmp = 1.0 * (avg - 1.0 * edges[i].weight) * (avg - 1.0 * edges[i].weight);
    sort(edges + 1, edges + 1 + m);
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= m; i++)
    {
        int x = edges[i].from, y = edges[i].to;
        if (find(x) != find(y))
            fa[fa[x]] = fa[y], cnt++, len += edges[i].weight, q.push(i);
    }
    len /= (n - 1);
    while (!q.empty())
    {
        int u = q.front();
        sqr += (edges[u].weight - len) * (edges[u].weight - len);
        q.pop();
    }
    if (cnt == n - 1)
        ans = min(ans, sqrt(sqr / (n - 1)));
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &edges[i].from, &edges[i].to, &edges[i].weight);
    for (double avg = 0.25; avg <= 100; avg += 0.25)
        kruskal(avg);
    printf("%.4lf", ans);
    return 0;
}

C - 数列计数

为啥你们都写得那么复杂?其实发现容斥+DP就可以比较轻松的做出来了。我们发现先算和为$p$的倍数的任意方案数,然后再减去只用质数的方案数就是答案。

第一部分

第一部分的式子并不难,设置$dp[i][j]$为前$i$个数的和在模意义下为$j$的方案数,那么转移如下: $$ dp[i][j] = \sum_{k = 0}^{p - 1} dp[i - 1][(j - k) \bmod p] \times c_k $$ 其中$c_k$就是在$m$的值域内选模意义下为$k$的方案数。根据题意,$c_k$也比较显然: $$ c_k = \begin{cases} \lfloor \frac{m}{p} \rfloor, k = 0 \\ \lfloor \frac{m - k}{p} \rfloor + 1, k < m \\ 1, k = m \\ 0, k > m \end{cases} $$ 因为序列长度很长,那么我们可以考虑构建矩阵来优化之: $$ dp'[0][j] = \sum_{k = 0}^{p - 1} dp[0][j - k \bmod p] \times c_k \\ dp'[0][j] = \sum_{k = 0}^{p - 1} dp[0][k] \times c_{(j - k \bmod p)} $$ 再参考矩阵乘法的意义: $$ A[i][j] = \sum_{k = 0}^{p - 1} B[i][k] \times C[k][j] $$ 那么我们的矩阵其实就很好构造: $$ trans[k][j] = c_{(j - k \bmod p)} $$

第二部分

第二部分差不多,我们需要线性筛把$m$内的质数筛出来,然后在桶里计数:$bucket[i \bmod p]++$。之后在$trans$矩阵内减去这些质数的方案数,做一遍即可。

代码

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

using namespace std;

const int MAX_N = 110, MAX_M = 2e7 + 200, mod = 20170408;

int primes[MAX_M], tot, n, m, p, table[MAX_N];
bool vis[MAX_M];

struct matrix
{
    int mat[MAX_N][MAX_N];

    matrix() { memset(mat, 0, sizeof(mat)); }

    int *operator[](const int &rhs) { return mat[rhs]; }

    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        for (int i = 0; i < p; i++)
            for (int j = 0; j < p; j++)
                for (int k = 0; k < p; k++)
                    ret[i][j] = (1LL * ret[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }

    matrix operator^(const int &rhs)
    {
        int tim = rhs;
        matrix ret, bas = *this;
        for (int i = 0; i < p; i++)
            ret[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                ret = ret * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ret;
    }
} dp, trans;

void sieve()
{
    for (int i = 2; i <= m; i++)
    {
        if (!vis[i])
            primes[++tot] = i;
        for (int j = 1; j <= tot && 1LL * i * primes[j] <= m; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= tot; i++)
        table[primes[i] % p]++;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    sieve();
    for (int c = 0; c < p; c++)
        for (int b = 0; b < p; b++)
        {
            int delta = (c - b + p) % p;
            if (delta == 0)
                trans[b][c] = m / p;
            else if (delta < m)
                trans[b][c] = int((m - delta) / p) + 1;
            else if (delta == m)
                trans[b][c] = 1;
            else
                trans[b][c] = 0;
            trans[b][c] %= mod;
        }
    dp[0][0] = 1, dp = dp * (trans ^ n);
    int ans = dp[0][0];
    memset(dp.mat, 0, sizeof(dp.mat));
    memset(trans.mat, 0, sizeof(trans.mat));
    for (int c = 0; c < p; c++)
        for (int b = 0; b < p; b++)
        {
            int delta = (c - b + p) % p;
            if (delta == 0)
                trans[b][c] = m / p;
            else if (delta < m)
                trans[b][c] = int((m - delta) / p) + 1;
            else if (delta == m)
                trans[b][c] = 1;
            else
                trans[b][c] = 0;
            trans[b][c] = (trans[b][c] + mod - table[delta]) % mod;
        }
    dp[0][0] = 1, dp = dp * (trans ^ n);
    ans = (ans + mod - dp[0][0]) % mod;
    printf("%d\n", ans);
    return 0;
}

HNOI 2018 省队集训 Day 1 - 解题报告

2019-12-20 21:34:04 By kal0rona

A - Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 $1$ 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 $root$ 时,$u, v$ 之间的 $LCA$ 显然是 $lca(u, v), lca(root, u), lca(root, v)$ 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

// QOJ2030.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 3e5 + 200;

int n, q, seq[MAX_N], lft[MAX_N], rig[MAX_N], anti[MAX_N], root, fa[20][MAX_N], head[MAX_N], current;
int dep[MAX_N], ptot;

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

namespace SegmentTree
{

ll nodes[MAX_N << 2], tag[MAX_N << 2];
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(nodes[p] = seq[anti[l]]);
    build(l, mid, lson), build(mid + 1, r, rson);
    nodes[p] = nodes[lson] + nodes[rson];
}

void pushdown(int p, int l, int r)
{
    if (tag[p] != 0)
    {
        tag[lson] += tag[p], tag[rson] += tag[p];
        nodes[lson] += 1LL * tag[p] * (mid - l + 1), nodes[rson] += 1LL * tag[p] * (r - mid);
        tag[p] = 0;
    }
}

void update(int ql, int qr, int l, int r, int p, ll val)
{
    if (ql <= l && r <= qr)
    {
        nodes[p] += 1LL * (r - l + 1) * val, tag[p] += val;
        return;
    }
    pushdown(p, l, r);
    if (ql <= mid)
        update(ql, qr, l, mid, lson, val);
    if (mid < qr)
        update(ql, qr, mid + 1, r, rson, val);
    nodes[p] = nodes[lson] + nodes[rson];
}

ll query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return nodes[p];
    pushdown(p, l, r);
    ll ret = 0;
    if (ql <= mid)
        ret += query(ql, qr, l, mid, lson);
    if (mid < qr)
        ret += query(ql, qr, mid + 1, r, rson);
    return ret;
}

#undef mid
#undef rson
#undef lson

} // namespace SegmentTree

void dfs_init(int u, int fat)
{
    dep[u] = dep[fat] + 1, fa[0][u] = fat, lft[u] = ++ptot, anti[ptot] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat)
            dfs_init(edges[i].to, u);
    rig[u] = ptot;
}

int getLCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y])
            x = fa[i][x];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}

int main()
{
    memset(head, -1, sizeof(head)), root = 1;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs_init(1, 0), root = 1, SegmentTree::build(1, n, 1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    while (q--)
    {
        int opt, x, y, z;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
            root = x;
        else if (opt == 2)
        {
            scanf("%d%d", &y, &z);
            int lca = getLCA(x, y), lca1 = getLCA(root, x), lca2 = getLCA(root, y);
            int dlca = (dep[lca1] > dep[lca2] ? lca1 : lca2);
            if (dep[lca] > dep[dlca])
                dlca = lca;
            if (dlca == root)
                SegmentTree::update(1, n, 1, n, 1, z);
            else if (lft[dlca] <= lft[root] && rig[root] <= rig[dlca])
            {
                int u = root;
                for (int i = 19; i >= 0; i--)
                    if (dep[fa[i][u]] > dep[dlca])
                        u = fa[i][u];

                SegmentTree::update(1, n, 1, n, 1, z);
                SegmentTree::update(lft[u], rig[u], 1, n, 1, -z);
            }
            else
                SegmentTree::update(lft[lca], rig[lca], 1, n, 1, z);
        }
        else if (opt == 3)
        {
            // something different;
            // if there is an ancestor relationship;
            if (x == root)
                printf("%lld\n", SegmentTree::nodes[1]);
            else if (lft[x] <= lft[root] && lft[root] <= rig[x])
            {
                int u = root;
                for (int i = 19; i >= 0; i--)
                    if (dep[fa[i][u]] > dep[x])
                        u = fa[i][u];
                printf("%lld\n", SegmentTree::nodes[1] - SegmentTree::query(lft[u], rig[u], 1, n, 1));
            }
            else
                printf("%lld\n", SegmentTree::query(lft[x], rig[x], 1, n, 1));
        }
    }
    return 0;
}

B - Function

我们回顾一下式子: $$ f(x, y) = \begin{cases} A_y & x = 1 \\ f(x-1, y) + A_y & y = 1 \text{ and } x \neq 1 \\ \min \{ f(x-1, y-1), f(x-1, y) \} + A_y & \text{otherwise} \end{cases} $$ 我们可以近似地认为,这个式子的意义为在网格图上从 $(x, y)$ 走到 $(1, 1)$ 的最短距离。可以大概猜到一个结论:这样的路径一定是先走一段连续的左上角,再停在一个相对较小的权值上直走向上。那么,假设停止时,$y = i$,那么答案就是: $$ \text{设 } p[n] = \sum_{i = 1}^n A_i, ans = A_i(x - y + i) + p[y] - p[i] $$ 我们整理一下: $$ A_i(x - y) + A_i \cdot i + p[y] - p[i] $$ 我们可以把 $(x - y)$ 看做自变量,然后把这些直线丢入平面空间中。我们需要把询问离线排序,然后我们只需要保留最小的直线,也就是下凸包,这样可以让答案最小,用单调栈维护,并在栈上二分在其定义域中的直线并求值即可。

// QOJ2031.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 5e5 + 200;

int n, q, stk[MAX_N << 1], tail;
double pos[MAX_N << 1];
ll ai[MAX_N], prefix[MAX_N], constSuf[MAX_N], ans[MAX_N];

struct query
{
    int x, y, id;
    bool operator<(const query &rhs) const { return y < rhs.y; }
} queries[MAX_N];

double calc(int x, int y) { return double(constSuf[y] - constSuf[x]) / double(ai[x] - ai[y]); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &ai[i]), prefix[i] = prefix[i - 1] + ai[i];
        constSuf[i] = ai[i] * i - prefix[i];
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &queries[i].x, &queries[i].y), queries[i].id = i;
    sort(queries + 1, queries + 1 + q);
    int curt = 0;
    for (int i = 1; i <= q; i++)
    {
        int delta = queries[i].x - queries[i].y;
        while (curt + 1 <= queries[i].y)
        {
            curt++;
            while (tail > 0 && ai[stk[tail]] >= ai[curt])
                tail--;
            while (tail > 1 && calc(curt, stk[tail]) > calc(stk[tail], stk[tail - 1]))
                tail--;
            stk[++tail] = curt;
            if (tail > 1)
                pos[n - tail] = calc(curt, stk[tail - 1]);
        }
        int idx = n - (lower_bound(pos + n - tail, pos + n - 1, delta) - pos);
        ans[queries[i].id] = delta * ai[stk[idx]] + constSuf[stk[idx]] + prefix[curt];
    }
    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

C - Or

很显然的 DP 式子,设置 $dp[i][j]$ 为前 $i$ 个序列中已经选择了 $j$ 位 $1$ 的合法状态。正常的转移非常简单: $$ dp[i][j] = \sum_{c = 1}^j dp[i - 1][j - c] {j \choose c} 2^{j - c} $$ 其中,$c$ 为这次新增的 $1$ 的个数。这样的转移是 $\Theta(nk^2)$ 的。然而,我们发现这个式子的卷积形式非常明显: $$ \begin{aligned} dp[i][j] &= \sum_{c = 1}^j \frac{ dp[i - 1][j - c] 2^{j - c} } { (j - c)! } \cdot \frac{j!}{c!} \\ \frac{dp[i][j]}{j!} &= \sum_{c = 1}^j \frac{dp[i - 1][j - c] 2^{j - c}}{(j - c)!} \cdot \frac{1}{c!} \end{aligned} $$ 稍微设置一下: $$ \begin{aligned} A_i(x) &= \sum_{j = 0}^\infty \frac{dp[i][j]}{j!} x^j = \sum_{j = 0}^\infty x^j \sum_{c = 1}^j \frac{dp[i - 1][j - c]2^{j - c}}{(j - c)!} \cdot \frac{1}{c!} \\ F_i(x) &= \sum_{c = 0}^\infty \frac{dp[i - 1][c]2^c}{c!} x^c, G_i(x) = \sum_{c = 0}^\infty \frac{1}{c!} x^c \\ A_i(x) &= F_i(x)G_i(x) \end{aligned} $$ 调用 $n$ 次 NTT 即可算完。但是这样非常的缓慢,我们需要利用更多已有的信息。我们注意到: $$ \begin{aligned} A_i(2x) &= \sum_{c = 0}^\infty \frac{dp[i - 1][c]}{c!} (2x)^c = \sum_{c = 0}^\infty \frac{dp[i - 1][c]2^c}{c!} x^c \\ &= F_i(x) \end{aligned} $$ Splendid!调整一下: $$ A_i(x) = F_i(x)G_i(x) = A_i(2x)G_i(x) $$ 我们可以递归来算,这样复杂度就是 $\Theta(n \log n \log k)$ 的了。

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

using namespace std;

const int MAX_N = 1e5 + 200, mod = 998244353, G = 3;

int n, K, poly_bit, poly_siz, rev[MAX_N], fac[MAX_N], fac_inv[MAX_N], pow2[MAX_N];
int f[MAX_N], g[MAX_N];

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

const int Gi = quick_pow(G, mod - 2);

void ntt_initialize()
{
    for (int i = 0; i < poly_siz; i++)
        rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (poly_bit - 1)));
}

void ntt(int *arr, int dft)
{
    for (int i = 0; i < poly_siz; i++)
        if (i < rev[i])
            swap(arr[i], arr[rev[i]]);
    for (int step = 1; step < poly_siz; step <<= 1)
    {
        int omega_n = quick_pow((dft == 1 ? G : Gi), (mod - 1) / (step << 1));
        for (int j = 0; j < poly_siz; j += (step << 1))
        {
            int omega_nk = 1;
            for (int k = j; k < j + step; k++, omega_nk = 1LL * omega_nk * omega_n % mod)
            {
                int t = 1LL * arr[k + step] * omega_nk % mod;
                arr[k + step] = (0LL + arr[k] + mod - t) % mod;
                arr[k] = (1LL * arr[k] + t) % mod;
            }
        }
    }
    if (dft == -1)
    {
        int inv = quick_pow(poly_siz, mod - 2);
        for (int i = 0; i < poly_siz; i++)
            arr[i] = 1LL * arr[i] * inv % mod;
    }
}

void polyMultiply(int *A, int *B)
{
    ntt(A, 1), ntt(B, 1);
    for (int i = 0; i < poly_siz; i++)
        A[i] = 1LL * A[i] * B[i] % mod;
    ntt(A, -1);
    for (int i = 0; i < poly_siz; i++)
        B[i] = 0;
    for (int i = K + 1; i < poly_siz; i++)
        A[i] = 0;
}

void multiply(int *A, int coeff)
{
    for (int i = 0, acc = 1; i <= K; i++, acc = 1LL * acc * coeff % mod)
        A[i] = 1LL * A[i] * acc % mod;
}

void solve(int idx)
{
    if (idx == 0)
        return (void)(f[0] = 1);
    if (idx & 1)
    {
        solve(idx - 1), g[0] = 0;
        for (int i = 1; i <= K; i++)
            g[i] = fac_inv[i];
        multiply(g, quick_pow(2, idx - 1));
        polyMultiply(f, g);
    }
    else
    {
        solve(idx >> 1);
        for (int i = 0; i <= K; i++)
            g[i] = f[i];
        multiply(g, quick_pow(2, idx >> 1));
        polyMultiply(f, g);
    }
}

int main()
{
    scanf("%d%d", &n, &K);
    for (int i = fac[0] = 1; i <= K; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[K] = quick_pow(fac[K], mod - 2);
    for (int i = K - 1; i >= 0; i--)
        fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod;
    for (int i = pow2[0] = 1; i <= max(n, K); i++)
        pow2[i] = 2LL * pow2[i - 1] % mod;
    while ((1 << poly_bit) <= (K << 1))
        poly_bit++;
    poly_siz = (1 << poly_bit), ntt_initialize();
    solve(n);
    int ans = 0;
    for (int i = n; i <= K; i++)
        ans = (1LL * ans + 1LL * f[i] * fac[K] % mod * fac_inv[K - i] % mod) % mod;
    printf("%d\n", ans % mod);
    return 0;
}

总结

我认为这是一套比较好的入门省选训练题,不会过于毒瘤也不会过于偏向联赛,科技题也不会过于裸露,而签到题也很友好。

「FZOI」OI 周赛 #2 Div.2 - 题解

2019-12-15 22:05:43 By kal0rona

A - 维他柠檬茶

很傻逼,直接把所有剩余液体加起来,然后放入最大的和次大的杯子进行判断即可。

B - 毒瘤题

我们可以考虑从 $n \to 1$ 进行扫描,更新可以向左的最大距离。如果最大距离为 $0$ 时,则有人没看到毒瘤题,计入答案即可。

C - 笔记本等式

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXN=1000000+5;
const int MAXQ=100+5;

int n;
int cnt,cnta=1,cntb;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

struct Node{
    bool flag;//符号, true -> '+', false -> '-'
    int val;//绝对值
    inline Node(void){
        flag=false,val=0;
        return;
    }
    inline Node(reg bool a,reg int b){
        flag=a,val=b;
        return;
    }
};

Node a[MAXQ];

inline void Read(void){
    n=-1;//其实并不需要这一行
    a[1]=Node(true,0);//第一个是正的,绝对值不确定。
    static char ch;
    reg int i=1;
    cin>>ch;//吞掉开头的 '?'
    do{
        cin>>ch;//读入数学符号 '+', '-', '='
        if(ch=='+')
            ++cnta,a[++i]=Node(true,0);//正
        else if(ch=='-')
            ++cntb,a[++i]=Node(false,0);//负
        else if(ch=='='){
            cin>>n;
            break;
        }
        cin>>ch;
    }while(n==-1);
    cnt=cnta+cntb;//cnt -> Q
    return;
}

inline void Work(void){
    reg int Max=cnta*n-cntb,Min=-cntb*n+cnta;
    //Max 为最大,Min 为最小
    if(n<Min||n>Max){//不在值域之内
        puts("Impossible");
        return;
    }
    for(reg int i=1;i<=cnt;++i)
        a[i].val=a[i].flag?n:1;
    reg int temp=(Max-n)/(n-1),t2=(Max-n)%(n-1);
    //彻底更改 temp 个,小幅度修改第 temp+1 的值
    for(reg int i=1;i<=temp;++i)
        if(a[i].val==n)
            a[i].val=1;
        else
            a[i].val=n;
    if(a[temp+1].val==n)
        a[temp+1].val-=t2;
    if(a[temp+1].val==1)
        a[temp+1].val+=t2;
    //输出
    puts("Possible");
    for(reg int i=1;i<=cnt;++i)
        if(i==1)
            printf("%d",a[i].val);
        else
            printf(" %c %d",a[i].flag?'+':'-',a[i].val);
    printf(" = %d\n",n);
    return;
}

D - 序列

很有意思的一题。无解的情况非常显然:当这$n$个的$\gcd$不为$1$时,那么无解。如果这个序列本身就有$k$个$1$,那么答案就是$n - k$。剩余情况,最优策略一定是:一段区间$[l, r]$中,把$a_l$不停向右合并找出一个$1$,然后再把这个$1$扩散到剩下的$n - 1$个数中。最终,我们把问题转换为找到最小的一段区间满足 $[l, r], \gcd_{l \leq i \leq r}(a_i) = 1$。

正常的方式就是用 $\Theta(n^2)$ 的方式枚举并记录区间 $\gcd$,并更新答案取最小值。然而,我们发现这个问题有二分性:当右端点固定时,区间长度越大,$\gcd$ 为 $1$ 的可能性越大,且一定存在一个分界点,其右侧都为 $1$,其左侧都不为 $1$ 。我们要找出这个最小的区间长度,用二分答案的形式。

然而,我们需要一种方式快速算出区间的 $\gcd$。这个时候我们可以使用 ST 表来进行区间 $\gcd$ 的计算,然后配合上二分答案,答案就是 $n - 1 + len - 1$。时间复杂度为 $\Theta(n \log^2 n)$。

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

using namespace std;

const int MAX_N = 1e5 + 200;

int n, st[20][MAX_N], ans = 0x3f3f3f3f;

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

int query(int l, int r)
{
    int d = 0, pos = l;
    for (int i = 19; i >= 0; i--)
        if (pos + (1 << i) - 1 <= r)
            d = ((d == 0) ? st[i][pos] : gcd(d, st[i][pos])), pos += (1 << i);
    return d;
}

int main()
{
    scanf("%d", &n);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &st[0][i]);
        if (st[0][i] == 1)
            cnt++;
    }
    if (cnt > 0)
        printf("%d\n", n - cnt), exit(0);
    int combo = st[0][1];
    for (int i = 2; i <= n; i++)
        combo = gcd(combo, st[0][i]);
    if (combo != 1)
        puts("-1"), exit(0);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = gcd(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = i - 1, res = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (query(mid, i) != 1)
                r = mid - 1;
            else
                l = mid + 1, res = i - mid;
        }
        if (res != -1)
            ans = min(ans, res + n - 1);
    }
    printf("%d\n", ans);
    return 0;
}
kal0rona Avatar