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
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Codeforces Round #487 (Div. 2)
-
CodeForces 1324 - Codeforces Round #627 (Div. 3)
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #649 (Div. 2) C-Ehab and Prefix MEXs
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
Codeforces Round #610 (Div. 2)