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;
}