Codeforces Round 891 (Div. 3)
A - Array Coloring
思路：需要两部分的奇偶相同，判断奇数的个数是否为偶数即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int c(int a,int b){
if(b>a)return 0;
int res=1;
for(int i=1,j=a;i<=b;++i,--j){
res=res*j%mod;
res=res*ksm(i,mod-2)%mod;
}
return res;
}
int Lucas(int a,int b){
if(a<mod&&b<mod)return c(a,b);
return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){
}
void solve(){
int n;cin>>n;
vector<int>ve(n);
int cnt=0;
for(int i=0;i<n;++i){
cin>>ve[i];
if(ve[i]%2)cnt++;
}
if(cnt%2==0)cout<<"YES\n";
else cout<<"NO\n";
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
init();
cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
B - Maximum Rounding
思路：找到第一个大于4的数，给前面最后一个小于4的数加一，之后的数全为0
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int c(int a,int b){
if(b>a)return 0;
int res=1;
for(int i=1,j=a;i<=b;++i,--j){
res=res*j%mod;
res=res*ksm(i,mod-2)%mod;
}
return res;
}
int Lucas(int a,int b){
if(a<mod&&b<mod)return c(a,b);
return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){
}
void solve(){
string s;
cin>>s;
for(int i=0;i<s.size();++i){
if(s[i]>='5'){
while(i>0&&s[i-1]>='4')i--;
for(int j=i;j<s.size();++j)s[j]='0';
if(i)s[i-1]++;
else s.insert(s.begin(),'1');
break;
}
}
cout<<s<<'\n';
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
init();
cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
C - Assembly via Minimums
思路1：对于原数组a，将其从小到大排序后，可以发现b数组中出现a的个数为 （n-1）~1；那么将b从小到大排序后，按个数取依次放到a中去
思路2：按从大到小统计所有的b及其出现的个数，枚举去重后的所有b，cnti为bi的个数，pre表示a中大于bi的个数，令a中bi的个数为x，那么会有pre*x+x*（x-1）/2个bi在b中，可以二分找到满足条件的x。
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353,M=44750;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
void solve(){
int n,m;cin>>n;
m=n*(n-1)/2;
vector<int>ve(m);
for(int i=0;i<m;++i)cin>>ve[i];
sort(ve.begin(),ve.end());
for(int i=1,j=0;i<=n;++i){
cout<<ve[j]<<' ';
j+=n-i;
j=min(j,m-1);
}
cout<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
View Code1
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int c(int a,int b){
if(b>a)return 0;
int res=1;
for(int i=1,j=a;i<=b;++i,--j){
res=res*j%mod;
res=res*ksm(i,mod-2)%mod;
}
return res;
}
int Lucas(int a,int b){
if(a<mod&&b<mod)return c(a,b);
return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){
}
map<int,int>mp;
void solve(){
int n;cin>>n;
mp.clear();
for(int i=0,u;i<(n*(n-1)/2);++i){
cin>>u;
mp[u]++;
}
vector<PII>g(mp.size());
int idx=mp.size()-1;
for(auto v:mp)g[idx--]={v.first,v.second};
vector<int>ans(mp.size(),0);
for(int i=0,pre=0;i<mp.size();++i){
int c=g[i].second;
int l=1,r=1e3,x;
while(l<=r){
int mid=l+r>>1;
if((pre*mid+mid*(mid-1)/2)>=c)r=mid-1,x=mid;
else l=mid+1;
}
ans[i]=x;
pre+=x;
}
for(int i=0;i<mp.size();++i){
while(ans[i]--)cout<<g[i].first<<' ';
}cout<<'\n';
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
init();
cin>>t;
while(t--){
solve();
}
return 0;
}
View Code2
D - Strong Vertices
思路：找出等于最大值的
E - Power of Points
思路：对于每个s，求的是所有x到s的距离和，二分找到s的位置，前缀和求大于和小于等于s的值，对s求距离即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int c(int a,int b){
if(b>a)return 0;
int res=1;
for(int i=1,j=a;i<=b;++i,--j){
res=res*j%mod;
res=res*ksm(i,mod-2)%mod;
}
return res;
}
int Lucas(int a,int b){
if(a<mod&&b<mod)return c(a,b);
return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){
}
void solve(){
int n;cin>>n;
vector<PII>ve(n+1);
vector<int>sum(n+1,0),ans(n+1);
for(int i=1;i<=n;++i)cin>>ve[i].first,ve[i].second=i;
sort(ve.begin()+1,ve.end());
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+ve[i].first;
for(int i=1;i<=n;++i){
int p= lower_bound(ve.begin()+1,ve.end(),ve[i])-ve.begin();
int l=sum[p],r=sum[n]-sum[p],cl=p,cr=n-p;
int s=0;
if(cl>0)s+=abs(ve[i].first*cl-l)+cl;
if(cr>0)s+=abs(r-ve[i].first*cr)+cr;
ans[ve[i].second]=s;
}
for(int i=1;i<=n;++i)cout<<ans[i]<<' ';cout<<'\n';
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
init();
cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
F - Sum and Product
思路：由a+b=x，ab=y，可以得出b2-xb+y=0，解方程即可
标签：891,typedef,return,int,res,Codeforces,long,Div,define From： https://www.cnblogs.com/bible-/p/17615167.html