Logo kal0rona的博客

博客

「FZOI」Round #30 - (ICPC) 公告

2020-05-01 00:54:54 By kal0rona

经历了漫长的疫情封锁,我们终于会在 5 月份摆脱 COVID-19 的影响回到学校。回到学校前,是否竞赛手感下降、智力下降甚至颜值下降?本次的「FZOI」Round #30 - (ICPC) 就是给各大即将返校的选手准备的训练赛。

本次比赛的题目来自于组题人 @kal0rona 在各大 OJ 上刷到的一些比较适合恢复手感的题目,平均难度在 NOIp 提高组或 Codeforces Div.2 难度之上,但是峰值难度低于 Codeforces Div.2。

本次比赛分成两个 Episode,开始时间分别为 5 月 2 日和 5 月 3 日的下午 14:00 至 17:00。赛后将会提供视频讲解。

为了更好的让选手从这次比赛中得到恢复和训练,本次的比赛允许三人进行组队、并且提前准备模版,但仍然要遵守 ICPC 赛制的纪律。FZOI 成员中被发现任何学术作弊的行为都将会得到严厉的惩罚。

希望这次大家玩得开心。

上下界网络流 - 学习笔记

2020-04-23 10:04:10 By kal0rona

标定

考虑每条边的流量范围:$b(u, v) \leq f(u, v) \leq c(u, v)$。

无源汇上下界可行流

首先我们给这条边标入最大限制 $c(u, v) - b(u, v)$,并默认认为该边已经流入了 $b(u, v)$ 的流量,然后我们可以给每个点设置一个 $M_i$ 来进行流量搜集。

如果:

  • $M_i = 0$,那没啥问题。
  • $M_i > 0$,说明下界要求流入的流量更多,所以我们从附加源点 $S$ 连到此点。
  • $M_i < 0$,同理,说明下界要求流出的流量更多,所以我们专门开辟一个通道为此点流出至附加汇点 $T$。

代码:

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

using namespace std;

const int MAX_N = 220, MAX_E = 20400;

int n, m, head[MAX_N], current, di[MAX_N], start_pos, end_pos, dep[MAX_N], cur[MAX_N], idx[MAX_E], lowers[MAX_E];

struct edge
{
    int to, nxt, weight;
    bool tag;
} edges[MAX_E << 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 addtube(int src, int dst, int weight)
{
    addpath(src, dst, weight);
    addpath(dst, src, 0);
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(start_pos), dep[start_pos] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dep[edges[i].to] == 0 && edges[i].weight > 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[end_pos] != 0;
}

int dfs(int u, int flow)
{
    if (flow == 0 || u == end_pos)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0)
            if (int di = dfs(edges[i].to, min(flow, edges[i].weight)))
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
    return 0;
}

int dinic()
{
    int ret = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(head));
        while (int di = dfs(start_pos, 0x3f3f3f3f))
            ret += di;
    }
    return ret;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m), start_pos = n + 1, end_pos = n + 2;
    for (int i = 1, u, v, lower, upper; i <= m; i++)
    {
        scanf("%d%d%d%d", &u, &v, &lower, &upper);
        idx[i] = current, addtube(u, v, upper - lower), di[u] -= lower, di[v] += lower, lowers[i] = lower;
    }
    for (int i = 1; i <= n; i++)
        if (di[i] < 0)
            addtube(i, end_pos, -di[i]);
        else if (di[i] > 0)
            addtube(start_pos, i, di[i]);
    dinic();
    bool flag = true;
    for (int i = head[start_pos]; i != -1; i = edges[i].nxt)
        flag &= (edges[i].weight == 0);
    if (flag)
    {
        puts("YES");
        for (int i = 1; i <= m; i++)
            printf("%d\n", edges[idx[i] ^ 1].weight + lowers[i]);
    }
    else
        puts("NO");
    return 0;
}

有源汇上下界可行流

把有源汇上下界网络 $G$ 中的 $T$ 向 $S$ 连接一条无限大的渠道,转换为无源汇上下界可行进行求解。

addtube(end_pos, start_pos, 0x3f3f3f3f);

有源汇上下界最大流

其实有两种方法:

  • 第一种:这个方法比较好理解,但是时间复杂度会比较大,大概是 $\Theta(\text{dinic}(n) \log_2 n)$。我们可以二分这个最大流,然后从 $T$ 到 $S$ 连一条下界为 $mid$、上界无穷大的的边,在有可行流的情况下保持最大流。
  • 先按照「有源汇上下界可行流」的方法进行转换,先找一遍附加源点到附加汇点最大流,然后不管附加源点汇点,在原网络的参与网络上找 $S \to T$ 的最大流。不管附加源汇点其实可以直接把最后的那条 $T \to S$ 的边修改成 $0$ 边进行锁死,然后重新设置源汇点即可。复杂度为 $\Theta(\text{dinic}(n))$这个不是很好理解,可以看代码吧:
// LOJ116.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 330, MAX_E = 1e5 + 200, INF = 0x3f3f3f3f;

typedef long long ll;

int n, m, gS, gT, start_pos, end_pos, head[MAX_N], current, dep[MAX_N], cur[MAX_N], di[MAX_N];

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

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

void addtube(int src, int dst, int weight)
{
    addpath(src, dst, weight);
    addpath(dst, src, 0);
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(start_pos), dep[start_pos] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dep[edges[i].to] == 0 && edges[i].weight > 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[end_pos] != 0;
}

int dfs(int u, int flow)
{
    if (u == end_pos || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
            if (int di = dfs(edges[i].to, min(flow, edges[i].weight)))
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
    return 0;
}

ll dinic()
{
    ll ret = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(cur));
        while (int di = dfs(start_pos, 0x3f3f3f3f))
            ret += di;
    }
    return ret;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &gS, &gT);
    start_pos = n + 1, end_pos = n + 2;
    for (int i = 1, u, v, lower, upper; i <= m; i++)
    {
        scanf("%d%d%d%d", &u, &v, &lower, &upper);
        addtube(u, v, upper - lower);
        di[u] -= lower, di[v] += lower;
    }
    for (int i = 1; i <= n; i++)
        if (di[i] < 0)
            addtube(i, end_pos, -di[i]);
        else
            addtube(start_pos, i, di[i]);
    addtube(gT, gS, INF);
    ll ret = dinic();
    bool flag = true;
    for (int i = head[start_pos]; i != -1; i = edges[i].nxt)
        flag &= edges[i].weight == 0;
    if (flag == false)
        puts("please go home to sleep"), exit(0);
    ret = edges[current - 1].weight;
    start_pos = gS, end_pos = gT;
    edges[current - 1].weight = edges[current - 2].weight = 0;
    ret += dinic(), printf("%lld\n", ret);
    return 0;
}

有源汇上下界最小流

这个就很学玄学了。首先还是有两种解法:

  • 二分出流量,然后建图的时候限制下即可。
  • 先按照「有源汇上下界可行流」的方法进行转换,先找一遍附加源点到附加汇点最大流,然后不管附加源点汇点,在原网络的参与网络上找 $T \to S$ 的最大流(注意这个关系变了)。不管附加源汇点其实可以直接把最后的那条 $T \to S$ 的边修改成 $0$ 边进行锁死,然后重新设置源汇点即可。复杂度为 $\Theta(\text{dinic}(n))$这个不是很好理解,可以看代码吧:
// LOJ117.cpp
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

int n, m, gS, gT, start_pos, end_pos, head[MAX_N], current, dep[MAX_N], cur[MAX_N], di[MAX_N];

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

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

void addtube(int src, int dst, int weight)
{
    addpath(src, dst, weight);
    addpath(dst, src, 0);
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(start_pos), dep[start_pos] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dep[edges[i].to] == 0 && edges[i].weight > 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[end_pos] != 0;
}

int dfs(int u, int flow)
{
    if (u == end_pos || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
            if (int di = dfs(edges[i].to, min(flow, edges[i].weight)))
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
    return 0;
}

ll dinic()
{
    ll ret = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(cur));
        while (int di = dfs(start_pos, 0x3f3f3f3f))
            ret += di;
    }
    return ret;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &gS, &gT);
    start_pos = n + 1, end_pos = n + 2;
    for (int i = 1, u, v, lower, upper; i <= m; i++)
    {
        scanf("%d%d%d%d", &u, &v, &lower, &upper);
        addtube(u, v, upper - lower);
        di[u] -= lower, di[v] += lower;
    }
    for (int i = 1; i <= n; i++)
        if (di[i] < 0)
            addtube(i, end_pos, -di[i]);
        else
            addtube(start_pos, i, di[i]);
    addtube(gT, gS, INF);
    ll ret = dinic();
    bool flag = true;
    for (int i = head[start_pos]; i != -1; i = edges[i].nxt)
        flag &= edges[i].weight == 0;
    if (flag == false)
        puts("please go home to sleep"), exit(0);
    ret = edges[current - 1].weight;
    start_pos = gT, end_pos = gS;
    edges[current - 1].weight = edges[current - 2].weight = 0;
    ret -= dinic(), printf("%lld\n", ret);
    return 0;
}

「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;
}
kal0rona Avatar