Posted in: QuestOJ 比赛题解

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

Written by kal0rona Leave a Comment on 「FZOI」OI 寒假赛 #12 Div.1 – 题解
内容纲要

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

Back to Top