CF1313D Happy New Year 题解

题意：

做圣诞老人是一件很难的事。有时你不得不面对困难的情况。

今天圣诞老人在度假的时候，有 $m$ 个孩子排在他面前。我们把他们从 $1$ 到 $m$ 编上号。圣诞老人知道 $n$ 个咒语。每个咒语给编号从 $L_i$ 到 $R_i$ 的每个孩子一颗糖果。

题目保证如果将全部的咒语都用一次，每个孩子至多收到 $k$ 颗糖果。

如果一个孩子得到的糖果量是偶数（可能为零），那么他（或她）会很伤心。不过，其他孩子（收到奇数个糖果的孩子）会很高兴。

请问圣诞老人最多能使多少个孩子快乐。

输入格式：

The first line contains three integers of $n$ , $m$ , and $k$ ( $1 \leq n \leq 100\,000, 1 \leq m \leq 10^9, 1 \leq k \leq 8$ ) — the number of spells, the number of children and the upper limit on the number of candy a child can get if all spells are used, respectively.

This is followed by $n$ lines, each containing integers $L_i$ and $R_i$ ( $1 \leq L_i \leq R_i \leq m$ ) — the parameters of the $i$ spell.

输出格式：

Print a single integer — the maximum number of children that Santa can make happy.

题目保证了每个点至多有 $k \le 8$ 条线段覆盖，如果仅仅看到字面意思确实很难解题。

实际上这句话告诉我们，所有的线段都可以无重叠的划分到 $k\le 8$ 个轨道（集合）内，如下图（搬的）

每条线段在哪个轨道可以预处理出来

for(auto a : vec)
{
    if(a.op) { // 左端点
        for(int i = 0; i < 8; i++)
            if(!used[i]) { used[i] = true; ID[a.id] = i; break; }
    }else used[ID[a.id]] = false;
}

于是我们实际上可以用状压dp，即考虑每个点的第 $i$ 条轨道是否存在线段。细节详见代码。

时间复杂度 $\mathcal{O}(n2^k)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

struct node { int x, id, op; };
bool operator<(node a, node b) {
    return a.x == b.x ? a.op < b.op : a.x < b.x;
}
vector<node> vec;
int n, m, k, ID[N], f[505]; bool used[8]; 
bool check(int x) { return __builtin_popcountll(x) & 1; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    memset(f, 0xc0, sizeof(f)); f[0] = 0;
    for(int i = 1, l, r; i <= n; i++)
    {
        cin >> l >> r;
        vec.push_back({l, i, 1}); vec.push_back({r + 1, i, 0});
    }
    sort(vec.begin(), vec.end());
    for(auto a : vec)
    {
        if(a.op) {
            for(int i = 0; i < 8; i++)
                if(!used[i]) { used[i] = true; ID[a.id] = i; break; }
        }else used[ID[a.id]] = false;
    }
    for(int i = 0; i < vec.size(); i++)
    {
        int id = ID[vec[i].id];
        if(vec[i].op)
        {
            for(int S = (1 << 8) - 1; ~S; S--)
            {
                int v = (i + 1 < vec.size() ? (vec[i + 1].x - vec[i].x) : 0);
                if(!check(S)) v = 0;
                if((S >> id) & 1) f[S] = f[S ^ (1 << id)] + v;
                else f[S] = f[S] + v;
            }
        }else
        {
            for(int S = 0; S < (1 << 8); S++)
            {
                if(((S >> id) & 1) == 0)
                {
                    int v = (i + 1 < vec.size() ? (vec[i + 1].x - vec[i].x) : 0);
                    if(check(S)) { up(f[S], f[S ^ (1 << id)]), f[S] += v; }
                    else { up(f[S], f[S ^ (1 << id)]); }
                }else { f[S] = -INF; }
            }
        }
    }
    cout << f[0] << '\n';
    return 0;
}