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;
}
Comments | NOTHING