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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596549.html