Codeforces Round #697 (Div. 3)A~E题解

发布于 2021-02-01  3 次阅读

A. Odd Divisor

题意：

给你一个数字n，求该数是否存在一个为奇数的约数。

思路：

本身为奇数则自身就是奇数的约数，为偶数时不断的除2直到出现奇数即可，若最终除到1，则不存在。

AC Code：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
ll n;
void solve(){
   cin>>n;
   while(!(n&1)){
      n/=2;
   }
   if(n==1) cout<<"NO"<<endl;
   else     cout<<"YES"<<endl;
   return ;
}
signed main(){
   int T;
   cin>>T;
   while(T--) solve();
   return 0;
}

B. New Year's Number

题意：

给你一个数字n，判断n是否能由非负整数个2020和2021组成

思路：

用n对2020取余判断需要多少个2020，余数用2021去填充，所以只需判断n对2020的需求个数是否不小于n对2020的余数个数

AC Code：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
void solve(){
	cin>>n;
	if(n/2020 >= n%2020) cout<<"YES"<<endl;
	else 	cout<<"NO"<<endl;
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

C. Ball in Berland

题意：

共有a个男生和b个女生，以及k对（x，y）关系表示男生x和女生y可以为舞伴，你需要从k对关系中找出两队的舞伴且满足两队中无相同的男女生
问能找出多少队

思路：

一个简单的数学思维题
首先，将一个人看作一个点，记录有多少人可以与这个人成为舞伴
然后，枚举跳舞的组，比如枚举第一组的时候，显然满足的队的数量为总数k减去与男生x+女生y一起跳舞的情况-1，最后算出来的数量除2，因为枚举的时候组相互之间会枚举两次。

AC Code：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int a, b, k;
int w[2][N],m[2][N]; //0为组编号，1为配对数量
void solve(){
    cin>>a>>b>>k;
    memset(m,0,sizeof(m));
    memset(w,0,sizeof(w));
    for(int i=1; i<=k; i++){
        cin>>m[0][i];
        m[1][m[0][i]]++;
    }
    for(int i=1; i<=k; i++){
        cin>>w[0][i];
        w[1][w[0][i]]++;
    }
    ll ans=0;
    for(int i=1; i<=k; i++){
        ans+=k-m[1][m[0][i]]-w[1][w[0][i]]+1;
    }
    cout<<ans/2<<endl;
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D. Cleaning the Phone

题意：

给你n个数，每个数有一个对应的权值，求从n个数中选择任意个数使得其和不小于m，并且权值和最小

思路：

显然我们选择权值小且数值尽可能大的数最优
又因为每个数对应的权值只有1和2，所以应该优先选择权值为1的数，再考虑权值为2的数
所以我们可以用两个数组分别装不同的权值，枚举在权值为1的数组中取的个数，在算出在权值为2的数组中应取的个数，对于权值为2的数组应该先用前缀和维护，再用二分求
注意点：int会爆

AC Code：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, m;
int a1[N], k1, a2[N], k2, pre2[N], tmp[N];
bool cmp(int x, int y){return x>y;}
void solve(){
	k1=k2=0;
	cin>>n>>m;
	for(int i=1; i<=n; i++) cin>>tmp[i];
	int x;
	for(int i=1; i<=n; i++){
		cin>>x;
		if(x==1) 	a1[++k1]=tmp[i];
		else 		a2[++k2]=tmp[i];
	}
	sort(a1+1, a1+1+k1,cmp);
	sort(a2+1, a2+1+k2,cmp);
	for(int i=1; i<=k2; i++) pre2[i]=pre2[i-1]+a2[i];
	int ans=INF, sum1=0;
	for(int i=1; i<=k1; i++){
		sum1+=a1[i];
		if(sum1>=m){ans=mymin(ans,i); break;}
		int idx2=lower_bound(pre2+1,pre2+k2+1,m-sum1)-pre2;
		if(idx2!=k2+1) ans=mymin(ans,i+idx2*2);
	} 
	int idx2=lower_bound(pre2+1,pre2+k2+1,m)-pre2;
	if(idx2!=k2+1) 	ans=mymin(ans,idx2*2);
	if(ans==INF) cout<<"-1"<<endl;
	else 		cout<<ans<<endl;
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

E. Advertising Agency

题意：

从n个数中选出k个数，使得其和最大，求可以选择的方案数

思路：

显然应该考虑从n中选择尽可能大的数
显然不同的方案由最小的数可以选择的情况而定
所以需要求出选择的最小的数字的总个数sum和被选中的个数ans，答案即为

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
#include<map>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=1009;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, k, a[N];
map<ll,ll>mp;
ll f[N];
void init(){
	f[0]=1;
	for(int i=1; i<=1000; i++) f[i]=f[i-1]*i%M;
}
ll quick_pow(ll a, ll b)
{ 
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % M;
		a = a * a % M;
		b >>= 1;
	}
	return res;
}
ll c(int n, int m){
	if(n<m) return 0;
	return f[n]*quick_pow(f[m]*f[n-m]%M,M-2)%M;
}

void solve(){
	mp.clear();
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		mp[a[i]]++;
	} 
	sort(a+1,a+n+1);
	ll kk=a[n-k+1];
	ll ansk=0;
	for(int i=n-k+1; i<=n && a[i]==kk; i++) ansk++;
	cout<<c(mp[kk],ansk)<<endl;
	return ;
}
signed main(){
	init();
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}
赏

平平无奇的在校大学生