A.小苯的xor构造

题目描述

小红喜欢整数 k，他想让小苯构造两个不相等的非负整数，使得两数的异或和等于 k。

请你帮帮小苯。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int k;cin>>k;cout<<0<<" "<<k<<'\n';
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

B. 小苯的权值计算

题目描述

小苯通过如下步骤计算一个长度为 n 的数组 {a1,a2,…,an}的权值：

计算所有相邻元素的异或和，形成一个长度为 n−1 的新数组 {b1,b2,…,bn−1}。

定义数组 a 的权值为数组 b 的最大公因数。

小红构造了一个长度为 n 且元素均为正整数的数组 {a1,a2,…,an}，他想让小苯计算这个数组的权值。

请你帮帮小苯。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];int g=0;for(int i=0;i<n-1;i++){int x=a[i]^a[i+1];g=gcd(g,x);}cout<<g<<'\n';
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

C.小苯的01矩阵构造

题目描述

小苯想要构造一个 n 行 n 列、仅由 0 和 1 组成的矩阵，满足：
∙其每行的全部元素的按位异或异或和之和 sumr、每列的全部元素的按位异或异或和之和 sumc 相加恰好为 k
请你帮帮小苯。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n,k;cin>>n>>k;if(k%2==1){cout<<-1<<'\n';return;}int m=k/2;if(m>n){cout<<-1<<'\n';return;}vector<string> ans(n,string(n,'0'));for(int i=0;i<m;i++){ans[i][i]='1';}for(int i=0;i<n;i++){cout<<ans[i]<<'\n';}
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

D.小苯的重排构造

题目描述

小苯拿到了一个长为 n、仅由整数 1 或 2 组成的数组 a={a1,a2,…,an}。
现在小红想要让小苯将其重排得到数组 a′={a1′,a2′,…,an′}，使得 ∑i=1n−1gcd⁡(ai′,ai+1′)=k。
请你帮帮小苯。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n;ll k;cin>>n>>k;vector<int> a(n);int t1=0,t2=0;for(int i=0;i<n;i++){cin>>a[i];if(a[i]==1) t1++;else t2++;}                int m1 = t2 == 0 ? 0 : t2 - 1;int m2 = max(0,(t2-1)-t1);          ll ne=k-n+1; if(ne < 0 || ne > m1 || ne < m2) {cout << -1 << '\n';return;} int r = t2 == 0 ? 0 : (t2 - 1) - ne; vector<int> res;if (t2 == 0) {res.assign(t1, 1);} else {for (int i = 0; i < t2; i++) {res.push_back(2);if (i < r) {res.push_back(1);}}for (int i = 0; i < t1 - r; i++) res.push_back(1);} for (int i=0;i<n;i++) {if(i) cout<<' ';cout<<res[i];}cout<<'\n';     
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

E.小苯的xor图

小苯拿到了一个由 n 个顶点、m 条无向边组成的简单连通图，每个顶点都有一个权值。

他定义一条长度为 2 的简单路径的权值为这条路径所连接的三个顶点的权值的异或和。

小苯想知道，这张图中所有长度为 2 的简单路径的权值之和为多少。由于答案可能很大，请将答案对 998 244 353998 取模后输出。

请你帮帮小苯。

需要注意的是，无向图中 (u - v - w)视为同一条长度为 2 的简单路径；等价于对每个中心点 v 统计其邻居无序对 {u,w}

【名词解释】

简单路径[1]：在图上由若干顶点构成的序列，序列中顶点互不重复，且相邻顶点有边相连；路径长度为其中边的数量。

异或和[2]：两个数进行按位异或运算的结果。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
using pii=pair<int,int>;
int p[31];
void x(){p[0]=1;for(int i=1;i<31;i++){p[i]=(p[i-1]*2LL)%MOD;}
}
void solve() {int n,m;cin>>n>>m;vector<int> a(n),d(n);for(int i=0;i<n;i++) cin>>a[i];vector<pii> g;for(int i=0;i<m;i++){int u,v; cin>>u>>v;u--; v--;g.emplace_back(u,v);d[u]++; d[v]++;}x();ll ans=0;vector<int> t(n,0);for(int i=0;i<31;i++){fill(t.begin(), t.end(), 0);for(auto [u,v]:g){if((a[u]>>i)&1) t[v]++;if((a[v]>>i)&1) t[u]++;}ll res=0;for(int j=0;j<n;j++){ll d_=d[j];if(d_<2) continue;ll sum=d_*(d_-1)/2;ll x=t[j]*(d_-t[j]);if(((a[j]>>i)&1)==0){res+=x;}else{res+=(sum-x);}}res%=MOD;ans=(ans+res*p[i])%MOD;}cout<<ans%MOD<<'\n';
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

F.小苯的前缀gcd构造

题目描述

对于一个长度为 n 的数组 {a1,a2,…,an}，小苯先定义 f(i)=gcd⁡(a1,a2,…,ai)，基于此，再定义数组的权值为：

现在，小红想让小苯构造一个长为 n 且所有元素都在 [1,m]之内的数组，满足其权值恰好为 x。
请你帮帮小苯。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 50;bool f[N + 1][N + 1][N * N + 1];
int pre[N + 1][N + 1][N * N + 1];vector<int> ds[N + 1];void solve() {int n, m, x;cin >> n >> m >> x;for (int j = 1; j <= m; j++) {if (f[n][j][x]) {for (int _ =  n; _ >= 1; _--) {cout << j << " \n"[_ == 1];int oj = j;j = pre[_][j][x];x -= oj;}return;}}cout << "-1\n";
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for (int i = 1; i <= N; i++) {ds[i].push_back(0);for (int j = i; j <= N; j += i) {ds[j].push_back(i);}}f[0][0][0] = true;for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {for (auto k : ds[j]) {for (int s = j; s <= N * N; s++) {if (f[i - 1][k][s - j]) {f[i][j][s] = true;pre[i][j][s] = k;}}}}}int tt = 1;cin >> tt;while (tt--) solve();return 0;
}

注：赛时F题没写出来, 后续会补充详细的解题思路

感谢大家的点赞和关注，你们的支持是我创作的动力！