2023牛客暑假多校第五场（补题向题解：C，E）

当时只做出来4个题，被两个学弟的队伍压了一题，可能是因为两个中等题都偏向构造和猜结论这种，我们队伍不太擅长，需要加强这方面的训练。

C Cheeeeen the Cute Cat（图论）

说实话不看题解，还是很难想到这么转化的，当时队友直接用正解过了这个题，tql
知识点：二分图匹配，哈密顿图，半哈密顿图，竞赛图

题意

给定一组二分图匹配在 $(1\sim n)$ 和 $(n+1\sim n+n)$ 之间，求最大匹配数，给定匹配满足不存在 $i-(i+n)$，以及若存在 $i-(j+n)$ 就一定不存在 $j-(i+n)$（关键）。$n\le 3000$，匹配形式以邻接矩阵给出，并保证有 $\frac{n\ast (n-1)}{2}$ 个匹配。

思路

直接用二分图匹配或者网络流来跑肯定不现实，时间复杂度不允许，考虑如何转化。

建图，将一个匹配 $i\to j+n$ 视作 $i\to j$ 有一条有向边，二分图匹配成功一对可以看做经过一条边，唯一匹配则要求点不能重复经过。
而题目给出图转换后满足无自环无重边，并且边数为 $\frac{n\ast (n-1)}{2}$。这说明转化后的图是竞赛图，而竞赛图的性质是一定存在一条哈密顿通路，即一定能不重复的经过 $n$ 个点走过 $n-1$ 条边，根据上述转化最少的匹配数也是 $n-1$.

而考虑到走出一个回路也是合法的匹配，则答案是否为 $n$ 则需要判定是否为哈密顿图（具有哈密顿回路），而竞赛图是否具有哈密顿回路则需要判断是否强连通，即判断是否所有强连通分量大小都 $>1$ 这样就可以形成若干哈密顿回路使得答案为 $n$.

具体如何实现，tarjan算法缩点计数即可。

代码

#include 
using namespace std;

const int N = 3010;
int n, dfn[N], low[N], vis[N], st[N], cnt, top;
vector<int> g[N];

int min_cnt = 1e9; // 最小的强连通分量的大小
void tarjan(int u){
    vis[u] = 1; st[top ++] = u;
    dfn[u] = low[u] = ++ cnt;

    for(auto v : g[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(dfn[u] == low[u]){
        int sum = 0;
        while(true){
            int x = st[-- top]; vis[x] = 0;
            sum ++;
            if(x == u) break;
        }
        min_cnt = min(min_cnt, sum);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            int x; cin >> x;
            if(x) g[i].push_back(j); // 建图
        }
    }

    for(int i = 1; i <= n; i ++){
        if(!dfn[i]) tarjan(i);
    }
    if(min_cnt < 2) cout << n - 1 << "\n";
    else cout << n << "\n";
    return 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

E Red and Blue and Green（构造，贪心）

当时摆烂，遇到构造就不想动脑子了，今天回过头重新写发现还是能不看题解写出来的，只是效率偏低。

题意

需要构造一个大小为 $n$ 的排列，使得满足 $m$ 个要求，$m$ 个要求以 $[l,r,w]$ 的形式给出，要求区间 $[l,r]$ 的逆序对数的奇偶为 $w$. 给定的 $m$ 个区间保证不重复，且任意两个区间都不相交（可能包含）。

思路

首先我们需要知道，对于一个排列的任意一个区间 $[l,r]$，任意交换两个位置 $x,y$ 上的数，只要满足 $x,y$ 不全包含在 $[l,r]$ 中，则不会改变区间$[l,r]$ 的逆序对。
题目既然只有不相交和包含关系，于是就可以建出一个树（有包含关系的区间为父子）递归解决子问题。例如 $1.[1,6],2.[2,4],3.[2,3]$，其中2为1的儿子，3为2的儿子，2是1的一级子区间，3是1的二级子区间。

递归到 $u$ 区间时，统计所有一级子区间 $v_i$ 的逆序对奇偶，假设已经满足了所有的子区间 $v_i$ 的要求，加起来以后若已经满足区间 $u$ 的要求则不作改变，否则只需要找到该区间 $u$ 中相邻两个数（不在同一个一级子区间 $v_i$ 中）交换，这样只会对 $u$ 这个区间逆序对改变 $1$，而不会影响到任何一个子区间的逆序对数。

而我们可以在开头就预处理这些信息，在解决子问题前就先交换。

注意无解的情况当且仅当 $[l,r,w]，l=r，w=1$.

具体实现看代码

代码

/* 
对于一个排列的任意一个区间[l, r]，任意交换两个数x, y, 只要满足x, y不全在[l, r] 中， 则不会改变区间[l, r]的逆序对
只有不相交和包含关系，于是建出一个树递归解决子问题
递归到u区间时，统计所有一级子区间的逆序对奇偶，若满足则不作改变，
否则只需要找到该区间相邻两个数（不在同一个一级子区间中）交换，这样只会对u这个区间逆序对改变1，而不会影响到任何一个子区间

而我们可以在开头就预处理这些信息，在解决子问题前就先交换
*/
#include 
using namespace std;

const int N = 1010;

struct seg{
    int l, r, w;
    bool operator < (const seg& A)const{
        return r - l + 1 > A.r - A.l + 1; // 按区间大小排序
    }
}s[N];

bool cmp(int A, int B){
    return s[A].l < s[B].l;
}

vector<int> g[N];
int p[N], sum[N], len[N], siz[N];
void dfs(int u, int w){
    if(sum[u] != w){ // 子区间满足的情况下，当前区间不满足，则需要只对当前区间改变不影响子区间，可以提前交换
        if(siz[u]){
            if(len[u] == s[u].r - s[u].l + 1) swap(p[s[g[u][0]].r], p[s[g[u][1]].l]); // 子区间已满则直接交换两个相邻子区间的相邻的数
            else if(s[g[u][0]].l == s[u].l) swap(p[s[g[u][0]].r], p[s[g[u][0]].r + 1]);
            else swap(p[s[g[u][0]].l], p[s[g[u][0]].l - 1]);
        }
        else swap(p[s[u].l], p[s[u].l + 1]);
    }
    for(auto v : g[u]){
        dfs(v, s[v].w);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= m; i ++){
        int l, r, w;
        cin >> l >> r >> w;
        if(l == r && w == 1){
        	cout << "-1\n";
        	return 0;
        }
        s[i] = {l, r, w};
    }

    sort(s + 1, s + 1 + m);
    for(int i = m; i >= 1; i --){
    	bool flag = 0;
        for(int j = i - 1; j >= 1; j --){
            if(s[j].l <= s[i].l && s[j].r >= s[i].r){ // 建树
                g[j].push_back(i); flag = 1;
                siz[j] ++;
                sum[j] ^= s[i].w; // 预处理一级子区间已经满足的情况下的当前区间的奇偶
                len[j] += s[i].r - s[i].l + 1;
                break;
            }
        }
        if(!flag) {
            g[0].push_back(i); // 虚构一个总区间 [1, n]
            sum[0] ^= s[i].w;
        }
    }

    for(int i = 1; i <= n; i ++) p[i] = i; // 先设定好初始逆序对为0的排列
    for(int i = 1; i <= m; i ++) sort(g[i].begin(), g[i].end(), cmp); // 同一级的子区间按左端点排序
    
    int st = (s[1].l == 1 && s[1].r == n) ? 1 : 0;
    s[0].w = sum[0];
    dfs(st, s[st].w);
    
    for(int i = 1; i <= n; i ++) cout << p[i] << " ";
    return 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

B Circle of Mistery（贪心，构造）

题意

$n$ 个点，点 $i$ 的权值为 $a_i$，要求构造一个长度为 $n$ 的排列 $p$，生成 $p_i$ 与 $i$ 连边的无向图，使得至少存在一个简单环使得环上点权和 $\ge k$. 同时要求构造的排列逆序对最小，输出最小的逆序对数，无解输出 $-1$. $1\le n\le 10^3,-1e6\le a_i,k\le 1e6$.

思路

考虑我们一定是选择一个区间，舍弃其中（可能为 $0$）一些数，使得成环后 $sum\ge k$.

1. 假设都是正数，不用舍弃那么最优构造将成环区间所有数右移一位即可，代价为区间长度 $-1$.
2. 考虑要舍弃一些负数，除了舍弃的数其他数按1.方法构造仍然最优，对于舍弃的数每个都会比原先多贡献 $1$ 的逆序对数。

于是我们的策略就是枚举区间的右端点，找到第一个满足区间正数之和 $\ge k$ 的左端点，将所有的负数当做舍弃的数。继续向左推进左端点，每增加一个数，从被舍弃的数中判断最多能取出多少的负数，使得代价减少，这些负数用动态开点权值线段树维护，并将负数离散化为对应正数 $-x\to x$，贪心的考虑每次取回最大的负数才能取回的更多，线段树中二分求解。

具体见代码

代码

#include 
using namespace std;

const int N = 1e3 + 10, MAX = 1e6;
int a[N];

struct node{
    int ls, rs, sum, val;
}tr[N * 40];

int tot, root;

void clear(){ // 清空
    for(int i = 1; i <= tot; i ++) tr[i] = {0, 0, 0, 0};
    tot = root = 0;
}
void update(int &p, int loc, int k, int l = 0, int r = MAX){ // 更新
    if(!p) p = ++ tot;
    tr[p].sum ++; // 更新负数的数量
    tr[p].val += k; // 更新负数的和
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(loc <= mid) update(tr[p].ls, loc, k, l, mid);
    else update(tr[p].rs, loc, k, mid + 1, r);
}

int get_sum(int p, int k, int l = 0, int r = MAX){ // 最多能取回和为k的负数
    if(!p || !k) return 0;
    if(l == r){
        if(tr[p].val >= k) return tr[p].sum;
        return 0;
    }
    int mid = (l + r) >> 1;
    if(tr[tr[p].ls].val < k) return get_sum(tr[p].ls, k, l, mid);
    else return tr[tr[p].ls].sum + get_sum(tr[p].rs, k - tr[tr[p].ls].val, mid + 1, r);
}

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    if(*max_element(a + 1, a + 1 + n) >= k){ // 自环即可
        cout << "0\n";
        return 0;
    }

    if(k <= 0){ // 全是负数
        cout << "-1\n";
        return 0;
    }

    int ans = MAX;
    for(int r = 1; r <= n; r ++){

        clear();
        
        int val = 0, res = MAX, sum = 0;
        for(int l = r; l >= 1; l --){
            if(a[l] >= 0) val += a[l], sum ++;
            else update(root, -a[l], a[l]);
            if(val >= k) res = min(res, r - l + (r - l + 1 - sum) - get_sum(root, -(val - k)));
        }
        ans = min(ans, res);
    }
    if(ans == MAX) cout << "-1\n";
    else cout << ans << "\n";
    return 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
66
67
68
69

I The Yakumo Family（DP，拆位，前缀和）

很妙的一个妙妙dp，看着别人看jiangly代码写出来的题解，再折磨补过这题的队友给我讲题，终于弄明白了一点，试图用自己语言解释一下。

题意

给定长度为 $n$ 的数组 $a$，设 $XOR[l,r]=a_l⨁a_{l+1}⨁\cdots ⨁a_{r-1}⨁a_r$. 求 ${\sum }_{1\le l_1\le r_1<l_2\le r_2<l_3\le r_3\le n}XOR[l_1,r_1]\ast XOR[l_2,r_2]\ast XOR[l_3,r_3]$.

思路

如题，是要找到所有可能的 $3$ 个不重叠的子数组的异或和之积的和。我们先考虑一个简化的问题，求一个子数组的所有可能异或和之和。

首先我们知道位运算的一个性质，对于二进制每一位是单独运算互不影响的，所以我们拆位来考虑。

我们首先枚举区间的右端点 $r$， 以二进制第 $k$ 位为例，如何算 $2^k$ 的贡献，一个暴力的方法就是枚举区间的左端点 $l$ 若是 $XOR[l,r]$ 二进制第 $k$ 位为 $1$ 就能算一次贡献 $1\ast 2^k$，如何优化这个过程？

考虑前缀和优化，设$pre[i]=XOR[1,i]$ 即前缀异或和，$sum[k][0/1]:$ 动态更新代表前 $i$ 个数中有多少个前缀异或和 $pre[l]$ 的二进制第 $k$ 位为 $0/1$. 那么当我们枚举右端点 $r$ 时，枚举到二进制第 $k$ 位的贡献有，若 $pre[i]$ 第 $k$ 位为 $p$，那么异或上 $pre[l]$ 第 $k$ 为 $!p$ 的前缀就能贡献 $2^k$，即 $ans+sum[k][!p]\ast 2^k$.

代码如下

for(int i = 1; i <= n; i ++){
    cin >> a[i];
    pre[i] = pre[i - 1] ^ a[i]; // 前缀异或和
}

int ans = 0;
for(int r = 1; r <= n; r ++){ // 枚举区间右端点
    for(int j = 0; j < 31; j ++){ // 枚举二进制各位的贡献
        ans += sum[j][!(pre[r] >> j & 1)] * (1 << j);
    }    
    for(int j = 0; j < 31; j ++){ // 动态更新
        sum[j][pre[r] >> j & 1] += 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

回到我们本次的问题，我们考虑分成 $2$ 个子数组如何解决，不知道是否有注意到在前文说贡献和代码中计算 $sum$ 的时候用的是 $1\ast 2^k$ 以及 $sum+=1$，我们此时将 $sum$ 的定义改成：动态更新前 $i$ 个数分出 $1$ 个子数组的异或和，那么此时 $sum$ 的贡献就不是数量了，而是前一段子数组的异或和，设 $XOR[l_2,r_2]=2^{p_1}+2^{p_2}+\cdots +2^{p^k}$，那么 $XOR[l_1,r_1]\ast XOR[l_2,r_2]$ 一样可以写成 $XOR[l_1,r_1]\ast (2^{p_1}+2^{p_2}+\cdots +2^{p^k})$ 拆位计算同样不影响结果。而 $XOR[l_1,r_1]$ 就是我们现在定义的 $sum$.

同理我们只需要再更改一次 $sum$ 的定义，将其变成前 $i$ 个数 分成 $j$ 段的异或和之积的和。就能处理 $3$ 段子数组甚至更多子数组的问题。

代码

#include 
using namespace std;

#define ll long long
const int N = 2e5 + 10, mod = 998244353;

int n, w[N], p[N];
ll f[4][N], sum[4][31][2]; 
// f:前i个数，分成不重合的j段 j段异或和之积的和
// sumjkp:动态更新，前 i 个数 分成 j - 1段 前缀二进制第k项为p的 异或和之积的和

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
        p[i] = p[i - 1] ^ w[i]; // 前缀异或和
    }

    for(int i = 0; i <= n; i ++) f[0][i] = 1;

    for(int i = 1; i <= 3; i ++){ // 枚举这是第几次分段
        for(int r = 0; r <= n; r ++){ // 枚举第 i 段的右端点为 r
            for(int k = 0; k < 31; k ++){ // 拆位计算
                f[i][r] = (f[i][r] + sum[i][k][!(p[r] >> k & 1)] * (1LL << k) % mod) % mod;
            }
            for(int k = 0; k < 31; k ++){
                sum[i][k][p[r] >> k & 1] = (sum[i][k][p[r] >> k & 1] + f[i - 1][r]) % mod; // 将前i-1段异或和之积的结果累加进来
            }
        }
        for(int j = 1; j <= n; j ++){
            f[i][j] = (f[i][j] + f[i][j - 1]) % mod; // 所有子数组，就要求右端点任意，所以累加
        }
    }
    cout << f[3][n] << "\n";
    return 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