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

本文主要是介绍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\leq3000$ ，匹配形式以邻接矩阵给出，并保证有 $\frac{n*(n-1)}{2}$ 个匹配。

思路

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

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

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

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

#include <bits/stdc++.h>
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;
}

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 <bits/stdc++.h>
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;
}