奶龙王
Yiwu High School
2026.5.23
由于一些原因，模拟赛结束后2个月内，请不要在公共可见的区域发表模拟赛的题目、题解或者代码。
题意
求字典序最小的满足以下条件的正整数序列：
- 所有数互不相同且异或和为 0；
- 符合 ( m ) 个给定的形如 ( a_x \neq y ) 的限制。
[
\sum n \leq 3 \times 10^5,\quad \sum m \leq 6 \times 10^5
]
先说不带限制的情况
结论 1
当前 ( n-2 ) 个位置确定时，有解当且仅当前 ( n-2 ) 个数的异或和不为 0。
证明：
- 若异或和为 0，则后两个数必须相等，违反互不相同限制，无解。
- 若异或和为 ( s \neq 0 )，取一个之前未出现过的二进制位 ( 2^t )，令后两个数分别为 ( 2^t \oplus s ) 和 ( 2^t )，则满足条件。
结论 2
无论前 ( n-3 ) 个数是多少，总是有解。
证明：
取一个之前未出现过的二进制位 ( 2^t )，令倒数第三个数为 ( 2^t )，则前 ( n-2 ) 个数的异或和非 0，由结论 1 知有解。
因此我们可以得到的构造策略是
- 对于 ( i \leq n-3 )，令 ( a_i = i )。
- 最后三个数根据结论 2 的证明，存在数值大小为 ( O(n) ) 的解，从前往后暴力贪心即可。
时间复杂度： ( O(n) )
考虑怎么加上限制，其实贪心就可以了
对于前 ( n-3 ) 个位置，依次考虑每个位置 ( i )，设之前未出现过的最小的数为 ( x )，从 ( x ) 开始枚举。
用 \(set\) 存储每个位置的禁止数，快速判断是否能放。
时间复杂度均摊 ( O(|S_i| + 1) )，总枚举量为 ( O(n + m) )。
最后三个位置也类似暴力枚举，判断最后一个数是否符合限制。
总时间复杂度：
- 使用
set：( O((n+m)\log(n+m)) ) - 使用
unordered_set：( O(n+m) )
代码很短
#include<bits/stdc++.h>
#define int long long
#define rep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define per(i, r, l) for(int i = (r); i >= (l); -- i)using namespace std;/*4
3 0
4 0
3 1
1 1
4 2
1 1
2 14 2
1 1
2 1*/
const int N = 3e5 + 10;
set<int> s[N];
unordered_map<int, int> mp;
int n, a[N], b[N], m;
bool check(int x, int y) {return s[x].find(y) != s[x].end();
}
void solve() {cin >> n >> m;mp.clear();rep(i, 1, n) s[i].clear();rep(i, 1, m) {cin >> a[i] >> b[i];s[a[i]].insert(b[i]);}// a1 a2 a3 ... an-3, x, y, zint now = 1, sum = 0;rep(i, 1, n - 3) {while(mp[now]) ++ now;int ans = now;while(check(i, ans) || mp[ans]) ++ ans;cout << ans << ' ';mp[ans] = 1;sum ^= ans;}int x = 1;while(check(n - 2, x) || mp[x] == 1 || (sum ^ x) == 0) ++ x;cout << x << ' ';sum ^= x, mp[x] = 1;int y = 1;while(1) {int z = sum ^ y;if(check(n - 1, y) || check(n, z) || y == z || mp[y] || mp[z] || y <= 0 || z <= 0) {++ y;} else {cout << y << ' ' << z << '\n';return ;}}
}
signed main() {freopen("array.in", "r", stdin);freopen("array.out", "w", stdout);ios :: sync_with_stdio(0);cin.tie(0); cout.tie(0);int T = 1;cin >> T;while(T -- ) solve();return 0;
}