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