Codeforces Round #815 (Div. 2）

Codeforces Round #815 (Div. 2)

传送门 ：Codeforces Round #815 (Div. 2)

之前都是108键的键盘，最近在家用的68，两三天了还是非常不顺手，觉得打字聊天还好，打代码的话没快捷键debug多少有点难受（而且用惯了静电容之后真的会觉得黄轴很重（什

大概是一些，为了监督自己补题写的blog

D2. Xor-Subsequence (hard version)

prob：

给一个长度为n的数列，下标从0开始，要求满足$a[i]⨁j<a[j]⨁i$ 的最长子序列 ,$n\le 3e5,a[i]\le 1e9$

ideas:

$a[i]⨁j<a[j]⨁i$

考虑拆位，将式子转化一下，即这个式子的前k个二进制位（从高位）相等，第k+1位不等，且$a[i]⨁j$ 的k + 1位小于 $a[j]⨁i$ 的k+1位

前面相等的部分（前k位）拎出来，得到$a[i]⨁j=a[j]⨁i$

两边同时$⨁i⨁j$ 得到：$a[i]⨁i=a[j]⨁j$

这样i、j就各自在一边了，但注意这个式子是等号，不等号的时候并不适用，也就是说当考虑完了前k位来到第k+1位的时候，我们还是需要分类讨论所有情况，使得 $a[i]⨁j<a[j]⨁i$ 对于第k+1位成立

列出所有情况，其中满足条件的情况为，$a[i]⨁j=0,a[j]⨁i=1$（为了简单，将x这个数的第k+1位为1表示为x=1）, 更具体地，四种情况为：
$$\begin{gathered} a[i]=0,j=0,a[j]=1,i=0 \\ a[i]=0,j=0,a[j]=0,i=1 \\ a[i]=1,j=1,a[j]=1,i=0 \\ a[i]=1,j=1,a[j]=0,i=1 \end{gathered}$$
前面相等的部分我们考虑在01tire树上每次插入$a[i]⨁i$ 实现，对于第k+1位分讨dp

$a[i],a[j],i,j$ 这四个数中我们当前已知的是 $a[j]$ 和 j

参考博客：https://www.cnblogs.com/xhy666/p/16607009.html

当时盯了很久的代码，关于更新时候的u、v问题，大概是当取当前max的时候是根据a[i], 而a[i] 与j同号，所以是v，更新dp值的时候是根据a[j]， 所以是u

因为知道 a[j] , j 其实四个数都知道了，感觉只要不把a[i] 和 i 合起来，跟一个a[i]或者跟i记录都是可以的，

insert可以直接insert，不用分讨（

code：

#include 

using namespace std;

const int N = 3e5 + 10;
int a[N];
int dp[N * 50][2];
int tire[N * 50][2];

int idx = 0;

void insert(int x) {
    int p = 0;
    for (int i = 31; i >= 0; --i) {
        int u = (x >> i) & 1;
        if (!tire[p][u]) tire[p][u] = ++idx;
        p = tire[p][u];
    }
}

int getMx(int x, int y) {
    int p = 0, mx = 0;
    for (int i = 31; i >= 0; --i) {
        int u = (x >> i) & 1, v = (y >> i) & 1;
        int q = tire[p][!(u ^ v)];
        p = tire[p][u ^ v];
        mx = max(mx, dp[q][v]);
        if (!p) break;
    }
    return mx + 1;
}

void update(int x, int y, int mx) {
    int p = 0;
    for (int i = 31; i >= 0; --i) {
        int u = (x >> i) & 1, v = (y >> i) & 1;
        p = tire[p][u ^ v];
        dp[p][u] = max(dp[p][u], mx);
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int _;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            int mx = getMx(a[i], i);
            ans = max(ans, mx);
            insert(a[i] ^ i);
            update(a[i], i, mx);
        }
        cout << ans << endl;

        for (int i = 0; i <= n * 40; ++i) {
            tire[i][0] = tire[i][1] = dp[i][0] = dp[i][1] = 0;
        }
        idx = 0;
    }
}
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

E. Misha and Paintings

prob： 给一个$n\times n$ 的矩阵，需要用若干次操作将它变成只有k种不同的数字，操作是每次选择一个正方形的区域，将区域内完全替换成一种数字，问最少的操作数

ideas： 记当前所有出现的颜色数为cnt，当cnt

当cnt>k的时候，可以构造，一个方块A（选择的正方形区域）的左上角为$(1,1)$，右下角为$(n-1,n-1)$，另一个方块B的左上角随意，右下角为$(n,n)$ ，可以保证一定有解，则最少的操作数不超过2

证明两个方块内一定有解：

如图，考虑将cnt删成k，当lenB（方块B的边长）不断扩展（增加1）的时候，与方块A不相交部分的两个角即为可操作空间，每次根据1.这两个数字是否为该数字最后一次出现 2.这两个数字与方块A、B填的数字是否相同，会有0~2的删除数字的贡献，加上可以更改AB填充的数字，是可以做到范围内全覆盖

这题就变成判0,1是否可行，不可行则为2

考虑记录每种数字出现的位置（能覆盖它的方块的位置），$n^3$枚举单个方块位置，判断是否合法

二维差分维护

wa30+ 调过再发代码