a经过一系列变换成为b需要的次数
简单的模拟
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) ll a, b; ll cnt; void solve() { cin >> a >> b; cnt = 0; while (a < b) { a *= 2; cnt++; } while (a > b && a % 2 == 0) { a /= 2; cnt++; } if (a != b) puts("-1"); else if (cnt % 3 == 0) cout << cnt / 3 << endl; else cout << cnt / 3 + 1 << endl; } int main() { int t = 1; cin >> t; while (t--) { solve(); } }
找到最小的k使 {s⊕k|s∈S}=S
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) ll n, s[1100]; ll cnt[1100], tmp[1100]; void solve() { cin >> n; memset(cnt, 0, sizeof(cnt)); rep(i, 1, n) { cin >> s[i]; cnt[s[i]]++; } rep(k, 1, 1023) { int flag = 1; rep(i, 0, 1023) tmp[i] = cnt[i]; rep(i, 1, n) { tmp[s[i] ^ k]--; if (tmp[s[i] ^ k] < 0) { flag = 0; break; } } if (flag) { cout << k << endl; return; } } puts("-1"); } int main() { int t = 1; cin >> t; while (t--) { solve(); } }
很明显答案是单调的,一位一位的拆减就可以了
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) ll n; ll a[70], b[70]; ll ans; void solve() { for (ll i = 1, j = 1; j <= 1e18; i++, j *= 2) { a[i] = j; b[i] = b[i - 1] * 2 + 1; } cin >> n; ans = 0; for (int i = 60; i; i--) if (n >= a[i]) { n -= a[i]; ans += b[i]; } cout << ans << endl; } int main() { int t = 1; cin >> t; while (t--) { solve(); } }
Codeforces Round #647 (Div. 2) - Thanks, Algo Muse!
原文:https://www.cnblogs.com/likunhong/p/13124016.html