300iq Contest 3
B. Best Tree
首先n==2使只有一对;
n!=2时,如果1的个数比别的个数多,即别的点都和1匹配
如果1个个数比别的个数少,所有点即可俩俩匹配,
#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 998244353; const int maxn = 1e6 + 10; void solve() { int n,x; cin>>n; int none=0; for (int i = 1; i <=n; ++i) { cin>>x; if(x!=1) none++; } if(n==2) cout<<1<<endl; else cout<<min(n/2,none)<<endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; cin >> _; while (_--) solve(); return 0; }
I. Ignore Submasks
俩个数&只要一个数的2进制的某一个1为0即可使&的结果不一样
遍历数组,记录使用过的二进制位置即可
#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 998244353; const int maxn = 1e6 + 10; int a[105]; int vis[70]; int fastpow(int a, int n) { if (n < 0) return 0; int res = 1, temp = a; while (n) { if (n & 1) res = res * temp % mod; temp = temp * temp % mod; n >>= 1; } return res % mod; } void solve() { memset(vis, 0, sizeof(vis)); int n, k, kk = 0, sum = 0; cin >> n >> k; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) { int x = a[i]; int aa = 0; for (int j = 0; j < k; ++j) { if (vis[j] == 1)continue; if (x & (1ll << j)) { aa++; vis[j] = 1; kk++; } } int b = k - kk; sum = (sum + (fastpow(2, aa) - 1) * fastpow(2, b) % mod * i % mod) % mod; } cout << sum % mod << endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; // cin >> _; while (_--) solve(); return 0; }
c/c++开发分享300iq Contest 3地址:https://blog.csdn.net/weixin_45436102/article/details/110644888
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596508.html