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題沒寫出來, 后續會補充詳細的解題思路

感謝大家的點贊和關注，你們的支持是我創作的動力！

?