Logo kal0rona的博客

博客

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

2020-02-25 17:38:00 By kal0rona

A - 幼儿园

这道题的来源是 CF Div.2 D,只有 20 多个人过了。我在比赛的时候差点把这题写出来,然后因为一些玄学错误彻底 GG。

无疑,这是正常比赛中最难的题。但是这道题并不难想:我们可以把多个线段的端点提取出来,然后做一次「线段剖分」。如下图所示:

线段剖分

由于 $m \leq 10^9$,所以我们我们可以离散化之后进行剖分。接下来就是状压 DP 的部分了。由于全部放置之后并不会超过 $k \leq 8$,所以我们可以枚举线段,从上一条线段的覆盖状态进行转移。

线段剖分的具体实现可以用类似差分的方法:给每个位置开一个 Vector,剖分的时候可以在离散化之后的 $[L_i, R_i]$ 上,给 $L_i$ 位置插一个 pair(i, 1),给 $R_i + 1$ 的位置插一个 pair(i, -1)。剖分之后做前缀和即可。

剖分做完了之后,我们就可以进行状态压缩。我们把每个位置中存好的线段 vector 叫做 segover[]。我们枚举到从 $i$ 开始,那么范围用离散化数组表示就是 $[vec[i], vec[i + 1])$。我们把线段上方覆盖的线段进行标号,再用一个 map 维护上一根线段上方覆盖的线段的标号。这里如果我们要知道某条线段在上一个区间中的编号就可以用 map 很快维护了。之后,枚举一个 preStat,也就是上一个区间的覆盖情况。如果 preStat 要求我们选一根这两个区间上方都存在的线段,那么就把其加入「必选」集合中;如果 preStat 中并没有选某根两个区间上方都存在的线段,那么就把其加入「必不选」集合中。最后,把这个必不选集合取反,得到本区间状态的全集。我们可以枚举这个全集的子集,同时保证包含「必选」集合,我们便可以进行转移了。

代码有点复杂,搞清楚了就不难了:

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

using namespace std;

const int MAX_N = 2e5 + 200;

typedef pair<int, int> pii;

int n, m, limit, dp[MAX_N][(1 << 8)];
vector<int> vec;
pii segs[MAX_N];
vector<pii> overlay[MAX_N];
vector<int> segover[MAX_N];
set<pii> st;

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

int getlen(int x) { return segs[x].second - segs[x].first; }

int main()
{
    scanf("%d%d%d", &n, &m, &limit);
    // input;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &segs[i].first, &segs[i].second);
        vec.push_back(segs[i].first);
        vec.push_back(segs[i].second + 1);
        st.insert(segs[i]);
    }
    // make elements and segments unique;
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    int seg_siz = vec.size();
    set<pii>::iterator it = st.begin();
    n = st.size();
    for (int i = 1; i <= n; i++)
        segs[i] = *it, it++;
    // make the diff;
    for (int i = 1; i <= n; i++)
    {
        int l = ripe(segs[i].first), r = ripe(segs[i].second + 1);
        overlay[l].push_back(make_pair(i, 1));
        overlay[r].push_back(make_pair(i, -1));
    }
    // make the sum;
    for (int i = 1; i <= seg_siz; i++)
    {
        segover[i] = segover[i - 1];
        for (auto pr : overlay[i])
            if (pr.second == -1)
            {
                for (vector<int>::iterator it = segover[i].begin(); it != segover[i].end(); it++)
                    if (*it == pr.first)
                    {
                        segover[i].erase(it);
                        break;
                    }
            }
            else
                segover[i].push_back(pr.first);
    }
    // start to dp;
    int ans = 0;
    for (int i = 1; i < seg_siz; i++)
    {
        unordered_map<int, int> idx;
        // rearrange;
        for (int j = 0, siz = segover[i].size(); j < siz; j++)
            idx[segover[i][j]] = j;
        // enumerating the previous stat;
        int pre_siz = segover[i - 1].size();
        for (int pre_stat = 0; pre_stat < (1 << pre_siz); pre_stat++)
        {
            int current_stat = (1 << segover[i].size()) - 1;
            int compulsory = 0;
            // convert the previous id in current id system;
            for (int j = 0; j < pre_siz; j++)
                if (((~pre_stat) & (1 << j)) && idx.count(segover[i - 1][j]))
                    current_stat ^= (1 << idx[segover[i - 1][j]]);
                else if ((pre_stat & (1 << j) && idx.count(segover[i - 1][j])))
                    compulsory ^= (1 << idx[segover[i - 1][j]]);
            // enumerate the subset;
            for (int stat = current_stat;; stat = (stat - 1) & current_stat)
                if ((stat & compulsory) == compulsory)
                {
                    int const_term = vec[i] - vec[i - 1];
                    dp[i][stat] = max(dp[i - 1][pre_stat] + const_term * (__builtin_popcount(stat) & 1), dp[i][stat]);
                    if (i == seg_siz - 1)
                        ans = max(ans, dp[i][stat]);
                    if (stat == 0)
                        break;
                }
                else if (stat == 0)
                    break;
        }
    }
    // output;
    printf("%d\n", ans);
    return 0;
}

B - 床单上的矩阵

这道题比较简单,就是把按位考虑和单调栈混在一起做而已。

我们按位考虑:假设当前我们要算 $2^b$ 的答案,我们可以把这个矩阵变成一个 01 矩阵。我们如果要算 AND,其实就是要算出有多少个子矩阵中不包含 0;要算出 OR,其实就是要算出有多少个子矩阵包括至少一个 0。

那么,我们可以先来枚举一个矩阵的右下角 $(i, j)$。以下面这个矩阵为例:

0 1 1 0 1
0 0 1 1 1
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0

先来算 AND。欲算出多少个子矩阵不包含 0,我们不妨先枚举一个 $i$,在第 $i$ 行的视角来进行检视。假设 $i = 3$ 时,枚举到 $j = 5$。我们可以把可以作为左上角的点给独立出来:

0 0 0 0 1
0 0 1 1 1
1 1 1 1 1

发现其实这个左上角的合法范围就是前 $j$ 个、高度不下降的竖直长方体所组成的一段面积。这就跟单调栈有关了,算一下就完事了。

那么,如果我们要算 OR,算所有至少包含一个 0 的矩阵:其实可以做个容斥,用所有子矩阵个数减去不包含 0 的矩阵个数。不包含 0 的矩阵个数跟上面差不多,随便做做就完事了。

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

using namespace std;

const int MAX_N = 1010, mod = 1e9 + 7;

int n, mat[32][MAX_N][MAX_N], ans1, ans2, tmp[32][MAX_N][MAX_N], stk[MAX_N], wi[MAX_N];

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

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

int main()
{
    n = read();

    for (int i = 1; i <= n; i++)
        for (int j = 1, val; j <= n; j++)
        {
            val = read();
            for (int b = 0; b <= 30; b++)
                mat[b][i][j] = (val >> b) & 1;
        }
    int submat = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            submat = (0LL + submat + 1LL * i * j % mod) % mod;
    // or;
    for (int b = 0; b <= 30; b++)
    {
        int acc = 0;
        for (int i = 1; i <= n; i++)
        {
            int tail = 0, S = 0;
            for (int j = 1; j <= n; j++)
            {
                if (mat[b][i][j] == 1)
                    tmp[b][i][j] = 0;
                else
                    tmp[b][i][j] = 1 + tmp[b][i - 1][j];
                int w = 0;
                while (tail && tmp[b][i][j] < stk[tail])
                    S = (0LL + S + mod - 1LL * wi[tail] * stk[tail] % mod) % mod, w += wi[tail], tail--;
                w++, stk[++tail] = tmp[b][i][j], wi[tail] = w, S = (0LL + S + 1LL * w * stk[tail] % mod) % mod;
                acc = (0LL + acc + S) % mod;
            }
        }
        ans2 = (0LL + ans2 + 1LL * (0LL + submat + mod - acc) % mod * (1 << b) % mod) % mod;
    }
    for (int b = 0; b <= 30; b++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                mat[b][i][j] = 1 - mat[b][i][j];
    memset(tmp, 0, sizeof(tmp));
    for (int b = 0; b <= 30; b++)
    {
        int acc = 0;
        for (int i = 1; i <= n; i++)
        {
            int tail = 0, S = 0;
            for (int j = 1; j <= n; j++)
            {
                if (mat[b][i][j] == 1)
                    tmp[b][i][j] = 0;
                else
                    tmp[b][i][j] = 1 + tmp[b][i - 1][j];
                int w = 0;
                while (tail && tmp[b][i][j] < stk[tail])
                    S = (0LL + S + mod - 1LL * wi[tail] * stk[tail] % mod) % mod, w += wi[tail], tail--;
                w++, stk[++tail] = tmp[b][i][j], wi[tail] = w, S = (0LL + S + 1LL * w * stk[tail] % mod) % mod;
                acc = (0LL + acc + S) % mod;
            }
        }
        ans1 = (0LL + ans1 + 1LL * acc % mod * (1 << b) % mod) % mod;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

C - 集合幸运数

调和级数进行枚举,然后记录上一个取的位置即可。

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

using namespace std;

const int MAX_N = 1e6 + 200;

int m, n, last[MAX_N];
vector<long long> ansBox;
bool tag[MAX_N], vis[MAX_N];

int main()
{
    scanf("%d", &m);
    for (int i = 1, val; i <= m; i++)
        scanf("%d", &val), tag[val] = true;
    long long idx = 0;
    scanf("%d", &n);
    for (int i = 1, val, cnt; i <= n; i++)
    {
        scanf("%d", &val), cnt = 0;
        for (int j = last[val] + val; j < MAX_N && cnt < val; last[val] = j, j += val)
            if (!vis[j])
            {
                vis[j] = true, cnt++;
                if (tag[j])
                    ansBox.push_back(cnt + idx);
            }
        idx += val;
    }
    printf("%lld\n", ansBox.size());
    for (int i = 0, siz = ansBox.size(); i < siz; i++)
        printf("%lld\n", ansBox[i]);
    return 0;
}

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;
}

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

2019-12-15 21:25:42 By kal0rona

A - Genius ACM

个人认为这道题目作为一个小的贪心+模拟作为签到题不算过分。考虑把第一个连续的分数段作为金牌,之后一直取银牌直到大于金牌数量,最后能取多少取多少铜牌即可。

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

using namespace std;

const int MAX_N = 3e6 + 2000;

int T, n, pi[MAX_N], cnt;
pair<int, int> prs[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &pi[i]);
        if (pi[i] != pi[i - 1])
            prs[++cnt] = make_pair(pi[i], 0);
        prs[cnt].second++;
    }
    int gold = prs[1].second, silver = 0, bronze = 0, ptr = 2;
    while (silver <= gold && ptr <= cnt)
        silver += prs[ptr++].second;
    while (bronze <= gold && ptr <= cnt)
        bronze += prs[ptr++].second;
    while (gold + silver + bronze + prs[ptr].second <= (n >> 1) && ptr <= cnt)
        bronze += prs[ptr++].second;
    if (gold < silver && gold < silver && (gold + silver + bronze) <= (n >> 1))
        printf("%d %d %d\n", gold, silver, bronze);
    else
        puts("0 0 0");
    return 0;
}

B - 镜之边缘

一道比较基础的概率期望 DP。考虑设置状态$dp[i]$为从$1 \to i$的期望次数,那么很自然的有: $$ \begin{aligned} dp[i] &= dp[i - 1] \times p_i + 1 + (1 - p_i)(dp[i - 1] + 1 + dp[i]) \\ &= \frac{dp[i - 1] + 1}{p_i} \end{aligned} $$ 然而,这样直接做只能拿到$90$分。我们发现在$p_i \times 100 \in [0, 100]$之间,所以我们可以预处理$100$个逆元,并且加上一个快读即可。

// mirror.cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 7e7 + 200, mod = 998244353;

int n, pi[MAX_N], dp[MAX_N], inv[200];

inline char gc()
{
    static const int IN_LEN = 1 << 21 | 1;
    static char buf[IN_LEN], *s, *t;
    return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
}
int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = gc();
    return x * f;
}
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;
}
int main()
{
    const int inv100 = quick_pow(100, mod - 2);
    n = read();
    for (register int i = 1; i <= n; i++)
        pi[i] = read();
    for (register int i = 1; i <= 100; i++)
        inv[i] = quick_pow(1LL * i * inv100 % mod, mod - 2);
    for (register int i = 1; i <= n; i++)
        dp[i] = 1LL * ((1LL * dp[i - 1] + 1) % mod) * inv[pi[i]] % mod;
    printf("%d\n", dp[n]);
    return 0;
}

C - 接水果

在讲题的时候并没有讲清楚,所以在这里我会写一个比较长的题解。

首先,对于每一个询问,我们都要确定一个问题:哪些设定路径会覆盖询问路径?我们把这颗树的 DFS 求出,记录子树的 DFS 序范围在 $[L[u], R[u]]$ 之间。询问路径 $(x, y)$ 有两种情况:

  • LCA 为 $x$ 或 $y$。
  • LCA 为其他点,记为 $w$。

第一种情况

考虑把设定路径设为 $(a, b), dfn[a] < dfn[b]$,我们把这个路径抽象成一个有序数对,只不过需要用 DFS 序进行表示:$(dfn[a], dfn[b])$。我们发现,满足覆盖的设定路径在这种情况下,一定满足:

  • $dfn[b] \in [L[y], R[y]]$。
  • $dfn[a] \in [1, L[x]] \cup (R[x], n]$。

如图所示就十分清晰:DFS 序的取值区间意味着是否在子树内。理解了这个之后就不难理解上面两则为什么是一定满足的了。

第二种情况

第二种情况更为简单,如图所示:

发现对于 $(a, b), dfn[a] < dfn[b]$,有:

  • $dfn[a] \in [L[x], R[x]]$。
  • $dfn[b] \in [L[y], R[y]]$。

这两种情况讨论之后,我们可以成功把这道题目转换成二位平面上的问题。

长方形问题

我们可以先对整个树进行一遍 DFS。结束之后,所有的设定路径就会分布在二维平面上。

我们再来思考每个询问的意义:在两个维度上限制 DFS 在某一个区间内。那么其实,第二种询问所对应的就是一块长方形区域,而第一种其实就是两块分开的长方形区域。我们需要一种技术,能让所有的长方形块中快速得到第$k$小的点(也就是设定路径)。

扫描线技术

详见:扫描线 - OI Wiki

整体二分

求第 $k$ 小是有二分性的:对于比当前$mid$小的,计入$cnt++$;而如果没有,那么则忽略。如果这个 $cnt \leq k$ ,那么说明 $mid$ 可以再大一点。假设我们硬是要在一个序列上做,那么复杂度是 $\Theta(n \log n)$ 的。然而,我们不能做 $q$ 次这样的操作,否则一定会超时。我们可以考虑把 $q$ 个问题一起进行二分:也就是整体二分。整体二分使用了分治的技巧,可以让最后的 $q$ 个询问都得到单独的处理。考虑把这 $q$ 个询问放入一个询问序列中 $\{opt_i\}$,设置函数 $solve(l, r, ql, qr)$:$l, r$ 指的是值域的二分范围,而 $ql, qr$ 则是需要处理的询问区间,初始的时候,参数设置为 $ql = 1, qr = q, l = 1, r = 10^9$。我们可以拿到一个 $mid$ ,这个时候整个询问序列中一定会分化出两种情况:一个是 $kth \leq mid$,还有一种是大于的。欲处理这两种二分方向,我们只能把这两种情况的询问分别取出,再重新分配给两个不同二分方向的子任务:左侧为小于的询问,而右侧为大于的询问,我们只需要开两个队列进行储存,并重新设置整个序列的顺序即可。

设置好了之后,我们就向下,让子问题继续解决被缩小的两个子问题。当触碰到边界时,那么我们发现$[ql, qr]$操作的答案全部为边界。

我们如何在整体二分时,把长方形放入扫描线中?很简单,只需要按 $x$ 进行排序即可,然后用树状数组维护即可。树状数组中维护的是当前平面上$y \in [lower, upper]$这一段上有多少个小于 $mid$ 的个数,以供询问时进行二分判断。

代码

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

using namespace std;

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

int n, p, q, head[MAX_N], current, dfn[MAX_N], low[MAX_N], fa[20][MAX_N], dep[MAX_N];
int qcnt, ptot, ans[MAX_N], nodes[MAX_N], vec[MAX_N], vcnt;

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

struct query
{
    int typ, x, lower, upper, k, val, id;
    bool operator<(const query &rhs) const { return x < rhs.x || (x == rhs.x && typ < rhs.typ); }
} queries[MAX_N], q1[MAX_N], q2[MAX_N];

inline char gc()
{
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}

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

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

void dfs(int u, int fat)
{
    fa[0][u] = fat, dep[u] = dep[fat] + 1, dfn[u] = ++ptot;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat)
            dfs(edges[i].to, u);
    low[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 getSon(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] + 1)
            x = fa[i][x];
    return x;
}

inline int lowbit(int x) { return x & (-x); }

inline void update(int qx, int d)
{
    for (; qx <= n; qx += lowbit(qx))
        nodes[qx] += d;
}

inline int querySum(int qx, int ret = 0)
{
    for (; qx != 0; qx -= lowbit(qx))
        ret += nodes[qx];
    return ret;
}

void solve(int l, int r, int ql, int qr)
{
    if (ql > qr)
        return;
    if (l == r)
    {
        for (int i = ql; i <= qr; i++)
            if (queries[i].typ == 1)
                ans[queries[i].id] = vec[l];
        return;
    }
    int mid = (l + r) >> 1, lcnt = 0, rcnt = 0;
    for (int i = ql; i <= qr; i++)
        if (queries[i].typ == 0)
            if (queries[i].k <= mid)
                update(queries[i].lower, queries[i].val), update(queries[i].upper + 1, -queries[i].val), q1[++lcnt] = queries[i];
            else
                q2[++rcnt] = queries[i];
        else
        {
            int ref_val = querySum(queries[i].lower);
            if (queries[i].k <= ref_val)
                q1[++lcnt] = queries[i];
            else
                q2[++rcnt] = queries[i], q2[rcnt].k -= ref_val;
        }
    for (int i = 1; i <= lcnt; i++)
        queries[ql + i - 1] = q1[i];
    for (int i = 1; i <= rcnt; i++)
        queries[ql + lcnt + i - 1] = q2[i];
    solve(l, mid, ql, ql + lcnt - 1), solve(mid + 1, r, ql + lcnt, qr);
}

int main()
{
    memset(head, -1, sizeof(head));
    n = read(), p = read(), q = read();
    for (int i = 1, u, v; i <= n - 1; i++)
        u = read(), v = read(), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    for (int i = 1; i <= 19; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    // to put rect above the axis;
    for (int id = 1; id <= p; id++)
    {
        int a = read(), b = read(), c = read();
        vec[++vcnt] = c;
        if (dfn[a] > dfn[b])
            swap(a, b);
        int lca = getLCA(a, b);
        if (lca == a)
        {
            int son = getSon(a, b);
            // the less at x-axis, bigger at y-axis;
            if (dfn[son] > 1)
            {
                queries[++qcnt] = query{0, 1, dfn[b], low[b], c, 1, 0};
                queries[++qcnt] = query{0, dfn[son], dfn[b], low[b], c, -1, 0};
            }
            if (low[son] < n)
            {
                queries[++qcnt] = query{0, dfn[b], low[son] + 1, n, c, 1, 0};
                queries[++qcnt] = query{0, low[b] + 1, low[son] + 1, n, c, -1, 0};
            }
        }
        else
        {
            queries[++qcnt] = query{0, dfn[a], dfn[b], low[b], c, 1, id};
            queries[++qcnt] = query{0, low[a] + 1, dfn[b], low[b], c, -1, id};
        }
    }
    sort(vec + 1, vec + vcnt + 1), vcnt = unique(vec + 1, vec + vcnt + 1) - (vec + 1);
    for (int i = 1; i <= qcnt; i++)
        queries[i].k = lower_bound(vec + 1, vec + 1 + vcnt, queries[i].k) - vec;
    for (int i = 1; i <= q; i++)
    {
        int x = read(), y = read(), k = read();
        if (dfn[x] > dfn[y])
            swap(x, y);
        queries[++qcnt] = query{1, dfn[x], dfn[y], 0, k, 0, i};
    }
    sort(queries + 1, queries + 1 + qcnt);
    solve(1, vcnt, 1, qcnt);
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

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

2019-12-10 12:34:39 By kal0rona

致歉

由于准备的比较仓促,所以这次周赛组题上出现了一些问题,并对受影响的选手表示道歉。

题解

A - 回旋旅行

显然是一个 Hamilton 路径,设置状态$dp[stat][j]$来进行转移即可。

B - 模拟赛水题

这道题的原题是 CF1257E。考虑对于当前三个序列的每一个序列都在值域上做一个前缀和,记为$prefix_1[i], prefix_2[i], prefix_3[i]$。考虑枚举值域上的两个断点$i, j$,那么操作次数则为:$prefix_1[n] - prefix_1[i] + prefix_3[j] + prefix_2[i] + prefix_2[n] - prefix_2[j]$。这样做$\Theta(n^2)$次,取最小值即可拿到答案,可以得到 60 分。

那么正解是啥?我们发现式子中有两项可以放在一起来算:$prefix_3[j] - prefix_2[j], i < j$。我们只要考虑让这个部分最小即可让当前选中$i$的决策下值最小。做个后缀最小值即可。

C - 彩灯

这道题的出题人为长沙市雅礼中学的 Wearry。以下是他的原题解:


子区间之间只有相互包含和不交的关系,因此它们的包含关系会构成一棵树。

首先考虑一个暴力的解法, 记 $f[i][j]$ 表示在 $i$ 为根的子树中点被覆盖的最多次数为 $j$ 的最优答案, 转移的时候首先将所有子树的答案直接合并,然后考虑点 $i$ 的贡献:

$$ f[i][j] = \max\{f[i][j], f[i][j-1] + a[i]\} $$

不难发现可以维护 $f[i]$ 的差分表, 则 $f[i]$ 的差分表一定单调, 则合并子树相当于将差分表对应相加, 点 $i$ 的贡献则相当于将 $a[i]$ 按照大小顺序插入差分表。

kal0rona 的 CSP-S2 模拟赛 #1 出题分析

2019-12-06 19:56:19 By kal0rona

Day 1

篮球 - Basketball

前 30% 的数据

直接枚举上场状态和中间断开的点,由于上场状态只有上场和不上场,所以总的复杂度是$\Theta(2^n n)$。

正解

我们发现球员的数位非常小,且上场球员也非常少。那么,我们可以考虑设计一个前缀异或和还有后缀与和,那么在相同的数字上相乘即可得到结果。$prefix[i][j]$表示前$i$个中,能凑成$j$的方案数,$suffix[i][j]$表示$[i, n]$中,能凑成$j$的方案数。相乘的时候要固定后缀部分一定要选当前球员,这样可以避免算重。

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

using namespace std;

const int MAX_N = 1030, mod = 1e9 + 7;

int prefix_xor[MAX_N][MAX_N], suffix_and[MAX_N][MAX_N];
int n, seq[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    for (int i = 1; i <= n; i++)
    {
        prefix_xor[i][seq[i]] = 1;
        for (int j = 0; j < 1024; j++)
            prefix_xor[i][j] = (1LL * prefix_xor[i][j] + 1LL * prefix_xor[i - 1][j ^ seq[i]]) % mod;
        for (int j = 0; j < 1024; j++)
            prefix_xor[i][j] = (1LL * prefix_xor[i - 1][j] + 1LL * prefix_xor[i][j]) % mod;
    }
    for (int i = n; i >= 1; i--)
    {
        suffix_and[i][seq[i]] = 1;
        for (int j = 0; j < 1024; j++)
            suffix_and[i][j & seq[i]] = (1LL * suffix_and[i][j & seq[i]] + 1LL * suffix_and[i + 1][j]) % mod;
        for (int j = 0; j < 1024; j++)
            suffix_and[i][j] = (1LL * suffix_and[i + 1][j] + 1LL * suffix_and[i][j]) % mod;
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < 1024; j++)
            ans = (1LL * ans + 1LL * prefix_xor[i - 1][j] * (1LL * suffix_and[i][j] - 1LL * suffix_and[i + 1][j] + 1LL * mod) % mod) % mod;
    printf("%d", ans);
    return 0;
}

旅行 - Travel

前 50% 的数据

直接跑最短路即可,时间复杂度视最短路算法而定。

正解

这是一道分层图最短路的裸题,由于数据非常大,所以这道题应该使用带堆优化的 Dijkstra 算法。分层图的模型来自于 2004 年肖天的国家集训队论文,具体了解可以上网搜索或者转至国家集训队的 GitHub 仓库

建图部分:我们把坐了$i$次火车作为一层($i \in [0, m_2]$),顶点$x$在第$i$层的节点编号为$x + n \times i$。首先把飞机的路径复制$m_2 + 1$层,然后再把火车路径$(u, v)$复制$m_2$层,在第$i$层为$(u + i \times n, v + (i + 1) \times n), i \in [0, m_2 - 1]$。合法的答案就在每一层的$n$号节点。所以,跑完最短路直接扫一遍$dist$数组即可。记得开 long long。

// travel.cpp
#include <bits/stdc++.h>
typedef long long ll;
#define pr pair<ll, int>

using namespace std;

const int MAX_N = 6e5 + 200;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int head[MAX_N], current, n, m1, m2;
ll dist[MAX_N];
bool vis[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N * 10];

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

void shortest_path(int src)
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pr> pq;
    pq.push(make_pair(0, src)), dist[src] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 1, u, v, w; i <= m1; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        for (int layer = 0; layer <= m2; layer++)
            addpath(u + layer * n, v + layer * n, w);
    }
    for (int i = 1, u, v; i <= m2; i++)
    {
        scanf("%d%d", &u, &v);
        for (int layer = 0; layer < m2; layer++)
            addpath(u + layer * n, v + (layer + 1) * n, 0);
    }
    shortest_path(1);
    for (int layer = 0; layer <= m2; layer++)
        if (dist[layer * n + n] < INF)
            printf("%d\n%lld", layer, dist[layer * n + n]), exit(0);
    puts("-1");
    return 0;
}

回文树 - Palindrome

前 40% 的数据

随便乱做,对于每一个作为根节点的节点,$\Theta(n^2)$时间枚举路径即可。总的时间复杂度为$\Theta(n^3)$。

前 60% 的数据

我们发现字符集数量很小,所以我们把每一个字符变成$2^i$作为边权,发现合法的路径其实就是路径上异或和为$0$或者为$2^i$的情况(奇数回文串的情况)。所以,可以直接在子树内用$\Theta(n)$的时间内进行记录,放到桶子里统计即可。

正解

考虑每一次在子树内枚举,损失了太多已知信息。我们考虑进行启发式合并,然后就可以优化到$\Theta(n \log n)$。具体也可以看这篇博客

// palindrome.cpp
// dsu on tree;
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5 + 200;

int head[MAX_N], current, n, fa[MAX_N], siz[MAX_N], lft[MAX_N], rig[MAX_N], ptot;
int son[MAX_N], dep[MAX_N], anti[MAX_N], book[1 << 23], answer[MAX_N], dist[MAX_N];
char opt[10];

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

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

void predfs(int u)
{
    lft[u] = ++ptot, siz[u] = 1, dep[u] = dep[fa[u]] + 1, anti[ptot] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        dist[edges[i].to] = dist[u] ^ edges[i].weight, predfs(edges[i].to), siz[u] += siz[edges[i].to];
        if (siz[son[u]] < siz[edges[i].to])
            son[u] = edges[i].to;
    }
    rig[u] = ptot;
}

void dfs(int u, bool save)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != son[u])
            dfs(edges[i].to, false), answer[u] = max(answer[u], answer[edges[i].to]);
    if (son[u] != 0)
        dfs(son[u], true), answer[u] = max(answer[u], answer[son[u]]);
    if (book[dist[u]] != 0)
        answer[u] = max(answer[u], book[dist[u]] - dep[u]);
    // iterate the mid char;
    for (int ch = 0; ch <= 21; ch++)
        if (book[dist[u] ^ (1 << ch)])
            answer[u] = max(answer[u], book[dist[u] ^ (1 << ch)] - dep[u]);
    book[dist[u]] = max(book[dist[u]], dep[u]);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != son[u])
        {
            for (int id = lft[edges[i].to]; id <= rig[edges[i].to]; id++)
            {
                int curt = anti[id];
                if (book[dist[curt]])
                    answer[u] = max(answer[u], dep[curt] + book[dist[curt]] - (dep[u] << 1));
                // iterate the mid char;
                for (int ch = 0; ch <= 21; ch++)
                    if (book[dist[curt] ^ (1 << ch)])
                        answer[u] = max(answer[u], book[dist[curt] ^ (1 << ch)] + dep[curt] - (dep[u] << 1));
            }
            for (int id = lft[edges[i].to]; id <= rig[edges[i].to]; id++)
                book[dist[anti[id]]] = max(book[dist[anti[id]]], dep[anti[id]]);
        }
    if (save == false)
        for (int id = lft[u]; id <= rig[u]; id++)
            book[dist[anti[id]]] = 0;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
        scanf("%d%s", &fa[i], opt + 1), addpath(fa[i], i, 1 << (opt[1] - 'a'));
    predfs(1), dfs(1, true);
    for (int i = 1; i <= n; i++)
        printf("%d ", answer[i]);
    return 0;
}

Day 2

太空 - Space

前 50% 的数据

直接$\Theta(n^2)$枚举点对,然后记录最小值。

正解

平面最近点对板子题,详细见:

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

using namespace std;

const int MAX_N = 1000001, INF = 0x3f3f3f3f;

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

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

double pow2(double bas) { return bas * bas; }

double getDist(point a, point b) { return sqrt(pow2(a.x - b.x) + pow2(a.y - b.y)); }

double solve(int l, int r)
{
    if (l == r)
        return INF;
    else if (l + 1 == r)
        return getDist(pts[l], pts[r]);
    int mid = (l + r) >> 1;
    double current_ans = min(solve(l, mid), solve(mid + 1, r));
    int tot = 0;
    for (int i = l; i <= r; i++)
        if (fabs(pts[i].x - pts[mid].x) <= current_ans)
            tmp[++tot] = pts[i];
    sort(tmp + 1, tmp + 1 + tot, compareByY);
    for (int i = 1; i <= tot; i++)
        for (int j = i + 1; j <= tot && fabs(tmp[i].y - tmp[j].y) < current_ans; j++)
            current_ans = min(current_ans, getDist(tmp[i], tmp[j]));
    return current_ans;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &pts[i].x, &pts[i].y);
    sort(pts + 1, pts + 1 + n);
    printf("%.4lf", solve(1, n));
    return 0;
}

原子理论 - Atom

前 20% 的数据

其实就是分解质因数,然后找到最大且不为自己的因数即可,时间复杂度为$\Theta(\sqrt{n})$

前 60% 的数据

可以用$\Theta(n \log n)$的时间求出这$n$个数字与$a_i$的$\gcd$,然后分解质因数找到最大不为自己的因数即可。时间复杂度为$\Theta(n \log n + n \sqrt{n})$。

正解

我们发现次大公约数肯定是$a_1$的因数之一,所以我们可以用$\Theta(\sqrt{a_1})$的时间把$a_1$分解并存下其因数,然后再将$a_i$除这些因数找到最大不为自己的因数。总的时间复杂度为$\Theta(\sqrt{a_1} + n \log n)$。

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

using namespace std;

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

const int MAX_N = 1e6 + 200;

ll n, ai[MAX_N], primes[MAX_N];

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    for (int i = 1; 1LL * i * i <= ai[1]; i++)
        if (ai[1] % i == 0)
        {
            primes[++primes[0]] = i;
            if (ai[1] / i != i)
                primes[++primes[0]] = ai[1] / i;
        }
    sort(primes + 1, primes + 1 + primes[0]);
    for (int i = 1; i <= n; i++)
    {
        bool flag = true;
        ll di = gcd(ai[1], ai[i]);
        for (int j = 1; j <= primes[0]; j++)
            if (di % primes[j] == 0 && di / primes[j] < di)
            {
                printf("%lld ", di / primes[j]);
                flag = false;
                break;
            }
        if (flag)
            printf("-1 ");
    }
    return 0;
}

韭菜国 - Winnie

有一个坑点:权贵的时间非常值钱,所以每一个权贵都期望他那$m$个时间单位刚好用尽。所以没有把 DP 赋值成负无穷的同学可能会错。

前 50% 的数据

直接上 01 背包即可,复杂度为$\Theta(nm)$。

正解

这道题其实就是 01 背包前 k 优解的板子题,看过背包九讲应该可以秒掉。

首先回忆 01 背包的 DP 递推式: $$ dp[j] = \max\{ dp[j], dp[j - weight_i] + value_i \} $$ 我们可以尝试加一维,记录为第$x$优解:$dp[x][j]$。如何从之前的更优解合并为次优解是这道题的难点。首先我们发现,对于每一个$j$,${ dp[1][j], dp[2][j], dp[3][j], \dots }$是单调下降的。那么,我们如果要合并出一个新的单调下降序列,我们就可以使用归并排序的合并方式:只不过不是在两个序列上,而是在两种决策中选择,我们可以把选择第$i$个的和不选择的答案虚拟成两个长度为$k$的序列,然后用归并的方式合并。

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

using namespace std;

const int MAX_N = 5050;

int dp[55][MAX_N], k, m, n, wi[MAX_N], vi[MAX_N], tmp[MAX_N];

int main()
{
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &wi[i], &vi[i]);
    memset(dp, 128, sizeof(dp));
    dp[1][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= wi[i]; j--)
        {
            int ptr1 = 1, ptr2 = 1, ptr = 0;
            while (ptr <= k)
                if (dp[ptr1][j] > dp[ptr2][j - wi[i]] + vi[i])
                    tmp[++ptr] = dp[ptr1++][j];
                else
                    tmp[++ptr] = dp[ptr2++][j - wi[i]] + vi[i];
            for (int pt = 1; pt <= k; pt++)
                dp[pt][j] = tmp[pt];
        }
    int ans = 0;
    for (int i = 1; i <= k; i++)
        ans += dp[i][m];
    printf("%d", ans);
    return 0;
}

总结 - Conclusion

对于新高一的选手来说,这一套卷子的暴力分非常足,有 240 分(30+50+0+50+60+50)的弱智分。而对于其他更熟练的选手,本套卷子更是提供了 440 分(30+100+60+100+100+50)的无脑暴力。对于新高一的选手,这套题考查的东西是暴力能力;对于熟练的选手而言,这道题就是在测稳定度还有基础能力,因为剩下的题几乎全是板子题。

祝大家 CSP-S 2019 取得好成绩。

出题人:江西师范大学附属中学 2021 级 17 班黄晨曦

共 9 篇博客