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

Codeforces Round #678 (Div. 2)

程序员文章站 2022-07-05 09:36:57
Codeforces Round #678 (Div. 2)A. Reorder#include #define int long longusing namespace std;typedef long long ll;const int maxn = 2e5 + 5;const int N = (1 << 16) + 1;void solve() { int n,m; int sum=0; cin>&...

Codeforces Round #678 (Div. 2)

A. Reorder

#include <bits/stdc++.h>

#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int N = (1 << 16) + 1;

void solve() {
    int n,m;
    int sum=0;
    cin>>n>>m;
    for (int i = 1; i <=n; ++i) {
        int x;
        cin>>x;
        sum+=x;
    }
    cout<<(sum==m?"YES":"NO")<<"\n";
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

B. Prime Square

除一条对角线都填1,通过对角线的值来使行列变为质数

#include <bits/stdc++.h>

#define int long long
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int N = (1 << 16) + 1;

int flag[maxn],prime[maxn],pnum;

void getPrime(){
    pnum=0;
    for(int i=0;i<=maxn;i++) flag[i]=1;
    for (int i = 2; i <=maxn; ++i) {
        if(flag[i]==1) prime[pnum++]=i;
        for (int j = 0; j < pnum && prime[j]*i<=maxn; ++j) {
            flag[prime[j]*i]=0;
            if(i%prime[j]==0) break;
        }
    }
}

void solve() {
    int n;
    cin>>n;
    int x=n-1,y=0;
    while (flag[x]==0||flag[y]) x++,y++;
    for (int i = 1; i <=n; ++i) {
        for (int j = 1; j <=n; ++j) {
            if(i==j) cout<<y<<" ";
            else cout<<1<<" ";
        }
        cout<<"\n";
    }
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;getPrime();
    cin >> _;
    while (_--)
        solve();
    return 0;
}

可以填0,所以让每行每列都为2即可

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t,n,i,j;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                cout<<(i==j or i==j-1 or (i==n-1 and j==0))<<(j==n-1?'\n':' ');
    }
    return 0;
}

C. Binary Search

根据题目二分,在查询到pos之前的点对于x的值是大于还是小于便知道了,
然后组合数计算即可:C(l,x-1)*C(r,n-x)*A(l,l)*A(r,r)*A(n-l-r-1)

#include <bits/stdc++.h>

#define int long long
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int N = (1 << 16) + 1;
const int kk = 1e3 + 5;
vector<int> vv, uu;

int inv[kk], fact[kk], invfact[kk];

void getInv() {
    inv[1] = 1;
    for (int i = 2; i < kk; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

int init() {
    fact[0] = 1;
    invfact[0] = 1;
    for (int i = 1; i < kk; i++) {
        fact[i] = fact[i - 1] * i % mod;
        invfact[i] = invfact[i - 1] * inv[i] % mod;
    }
}

int getC(int m, int n) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invfact[m] % mod * invfact[n - m] % mod;
}

void solve() {
    vv.clear();
    uu.clear();
    int n, x, pos;
    cin >> n >> x >> pos;
    int left = 0, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (mid <= pos) {
            left = mid + 1;
            if (mid != pos) vv.push_back(mid);
        } else right = mid, uu.push_back(mid);
    }
    int l = vv.size();
    int r = uu.size();
    int res = getC(l, x - 1) * getC(r, n - x) % mod;
    int ans = fact[l] * fact[r] % mod * fact[n - l - r - 1] % mod;
    res = res * ans % mod;
    cout << res;
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    getInv();
    init();
//    cin >> _;
    while (_--)
        solve();
    return 0;
}

D. Bandit in a City

该节点的局部答案 = max(儿子的局部答案最大值, 总人数/叶子数(向上取整))

#include <bits/stdc++.h>

#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;

vector<int> vv[maxn];
int a[maxn];
int num[maxn];
int max_;

void dfs(int u) {
    if (vv[u].size() == 0) num[u] = 1;
    else num[u] = 0;
    for (auto x:vv[u]) {
        dfs(x);
        num[u] += num[x];
        a[u] += a[x];
    }
    max_ = max(max_, (a[u] + num[u] - 1) / num[u]);
}

void solve() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int x;
        cin >> x;
        vv[x].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    dfs(1);
    cout << max_;
}

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/110239489