[C++知识库]【CodeForces】Codeforces Round #774 (Div. 2)【A-C】

A. Square Counting

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5+10;

int a[maxn];

int main(void){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif 
    int t;
    cin >> t;
    while(t--){
        ll n,s;
        cin >> n >> s;
        cout<<(s/n)/n<<endl;
    }
    return 0;
}

B. Quality vs Quantity

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5+10;

ll a[maxn];

int main(void){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a+1,a+1+n);
        ll dif = a[n]-a[1]-a[2];
        int l = 2;
        int r = n; 
        bool flag = 0;
        while(l < r){
            if(dif > 0){
                flag = 1;
                break;
            }
            dif += a[--r]-a[++l];
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

C. Factorials and Powers of Two

题解：满足1e12以内的阶乘最大到14。对于任意的一个n，二进制枚举，剩下的用2的幂次来凑。

AC代码

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5+10;

ll a[maxn];

int main(void){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif 
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        ll fac[15];
        fac[0] = 1;
        for(int i = 1; i <= 14; i++) fac[i] = fac[i-1]*i;
        int ans = 100;
        for(int i = 0; i < (1 << 15); i++){
            bitset<15> b(i);
            ll t = n;
            for(int j = 0; j < 15; j++) t -= b[j]*fac[j];
            if(t >= 0){
                bitset<64> b1(t);
                ans = min(ans, (int)(b.count()+b1.count()));
                //ans = min<int>(ans, __builtin_popcount(i) + __builtin_popcountll(t));
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}