300iq Contest 3
程序员文章站
2022-06-26 14:49:11
300iq Contest 3B. Best Tree首先n==2使只有一对;n!=2时,如果1的个数比别的个数多,即别的点都和1匹配如果1个个数比别的个数少,所有点即可俩俩匹配,#include #define int long longusing namespace std;const int mod = 998244353;const int maxn = 1e6 + 10;void solve() { int n,x;...
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;
}
本文地址:https://blog.csdn.net/weixin_45436102/article/details/110644888
上一篇: mysql索引失效的几种情况分析