欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

相关标签: C++ acm cf