P8468 [Aya Round 1 C] 文文的构造游戏

题目描述

对于一个长度为 $l$ 的数列 $p$，定义 $S(p)$ 为所有元素的异或和，其中 $\oplus$ 指按位异或运算。

给定整数 $s,m$，判断能否构造一个长度为 $n$（$n$ 值自定）的数列 $a$，满足：

  • $1 \le n \le m$。
  • $1 \le a_i \le s$。
  • $S(a)=0$。
  • $a_1+a_2+\cdots+a_n=s$。

试构造任意一组合法解或报告无解。

做法

构造题一般代码都是非常简单的，基本都是可以在 $O(1)$ 的情况下找寻答案的

所以我们要通过找寻反例情况造案例去寻找答案。反例情况很有可能出现在极端情况身上。因为不会有题目让你找出的几百的规律找规律。并且答案很容易拥有非常普遍的情况

以本题为例子：题目要求我们找寻异或和为 0 的情况, 根据异或性质，如果出现偶数类的和异或在一起,异或和为0;而考虑最一般的情况，那肯定是异$ s/2+s/2==s$ 的情况。

然后考虑极端情况，一种是无法凑出偶数的情况，那就是奇数。但是根据异或和的性质，肯定有一个1无法消。与m为1的情况。就一个数也无法消掉，故而答案得出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std ;
using ll = long long ; 
const int N = 2e5 + 10 ; 
void solve(){
	ll s , m ; cin >> s >> m ;
	if(s&1 || m == 1 ){
		cout << -1 << '\n' ;  
	}else{
		
		cout << 2 <<' ' << s/2 << ' ' << s /2 <<'\n' ; //枚举其中情况 ，然后找寻规律； 
	}
}                             
	int main(){
	ios::sync_with_stdio(false),cin.tie(0)  ;
    int t = 1;	
	cin >> t;
    while (t--) {
        solve();
    } 
    return 0; 
}