c/c++语言开发共享Codeforces Round #678 (Div. 2)

Codeforces Round #678 (Div. 2)A. Reorder#include <bits/stdc++.h>#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; }  

c/c++开发分享Codeforces Round #678 (Div. 2)地址:https://blog.csdn.net/weixin_45436102/article/details/110239489

www.ctvol.com true Article c/c++语言开发共享Codeforces Round #678 (Div. 2)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/596549.html

(0)
上一篇 2021年5月8日 上午7:38
下一篇 2021年5月8日 上午7:42

精彩推荐