CF1313D

发表于 | 阅读数

给$n$个区间$[l_i,r_i]$。若选择区间$[l_i,r_i]$，区间上的值$+1$,问求使$[1,n]$点值为奇数的个数最大，最大个数是多少，$1$个点最多被覆盖$k$次。$(n\leq 10^5,l,r\leq 10^9,k\leq 8)$

这题关键点在$k$。显然$2^k*n$复杂度可以接受。由于$l,r$大，把一个点覆盖$k$次，转换为离散化，一个区间最多覆盖$k$次。

$dp[i][j]$表示到$[i]$这个区间，且区间的状态为$j=10101001$,二进制每一位表示他是否含有覆盖自己的区间中的第$k$个。

举个例子$[2,3)$,题目给出$[3,7),[1,5],[2,4),[2,6)…$如果选择$2,4$原区间，$j=101$

如何转移?

$seg[i]=[l[i],l[i+1]],len(seg)=li[i+1]-li[i]$

找到都覆盖$seg[i]$与$seg[i-1]$的原区间。若$dp[i-1][st1]$($st1$含有这些区间),就可以转移到$dp[i][st2]$（$st2$也含有这些区间)。

过于唠口,所以借助$tmp[st]=max(tmp[st],dp[i-1][st1])(st1这个状态的区间里含有st)$,然后让其映射到$st2$上。

  • $pre[]$存的是共有的原区间，再$seg[i-1]$所有覆盖它的第几位。
  • $now[]$存的是共有的原区间，再$now[i-1]$所有覆盖它的第几位。
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int M = 8;
const int mod = 1e9 + 7;
int li[N], l[N], r[N], num, n;
int dp[N][1 << M], st[1 << M];
vector<int> seg[N];
int m, k;
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &l[i], &r[i]);
        r[i]++;
        li[++num] = l[i];
        li[++num] = r[i];
    }
    sort(1 + li, 1 + li + num);
    num = unique(1 + li, 1 + li + num) - li - 1;
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(li + 1, li + 1 + num, l[i]) - li;
        r[i] = lower_bound(li + 1, li + 1 + num, r[i]) - li;
        for (int j = l[i]; j < r[i]; j++)
            seg[j].push_back(i);
    }
    int ans = 0;
    for (int i = 1; i < num; i++)
    {
        memset(st, 0, sizeof(st));
        vector<int> pre, now;
        int len = li[i + 1] - li[i];
        for (int t = 0; t < seg[i - 1].size(); t++)
            for (int k = 0; k < seg[i].size(); k++)
                if (seg[i - 1][t] == seg[i][k])
                    pre.push_back(t), now.push_back(k);
        int pst = 1 << seg[i - 1].size(), nst = 1 << seg[i].size();
        for (int s = 0; s < pst; s++)
        {
            int ss = 0;
            for (int j = 0; j < pre.size(); j++)
                ss |= (s >> pre[j] & 1) << j; //s这个状态里是否含有pre[j]
            st[ss] = max(st[ss], dp[i - 1][s]);
        }
        for (int s = 0; s < nst; s++)
        {
            int ss = 0;
            for (int j = 0; j < now.size(); j++)
                ss |= (s >> now[j] & 1) << j; //s这个状态里是否含有now[j]
            dp[i][s] = max(dp[i][s], st[ss] + (__builtin_popcount(s) & 1) * len);
            ans = max(dp[i][s], ans);//__builtin_popcount(s) 判断二进制有几个1
        }
    }

    printf("%d\n", ans);
}