A. Odd Divisor(思维)

题意

给你一个n，如果n有一个奇数因子就输出YES，否则输出NO

解题思路

我们从n开始判断当前是否是奇数，如果是，则直接输出YES，否则就一直右移一位直到n为1，然后输出NO

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long longbool f(ll n) {while(n != 1) {if(n%2 == 1)return true;n >>= 1;}return false;
}int main()
{ll n,x,t;scanf("%lld",&t);while(t--) {scanf("%lld",&n);if(f(n)) {puts("YES");}elseputs("NO");}return 0;
}

B. New Year’s Number(暴力+思维)

题意

给你一个n问你是否能用一定数量的2020和2021凑齐n(刚好等于)

解题思路

1.看一眼数据n的范围为[1,1e6]，直接暴力二重循环跑500就行

2.我们可以先计算n对2020的余数a以及n对2020的商b，如果a <=b则输出YES，否则输出NO

Code

暴力

#include<bits/stdc++.h>
using namespace std;
#define ll long longint main()
{int n,x,t;scanf("%d",&t);while(t--) {scanf("%d",&n);bool fg = false;for(int i = 0;i <= 500; ++i) {for(int j = 0;j <= 500; ++j) {if(i*2020+j*2021 == n) {fg = true;goto out;}}}out:if(fg) {puts("YES");}else {puts("NO");}}return 0;
}

公式

#include<bits/stdc++.h>
using namespace std;
int main()
{int t,n;cin>>t;while(t--) {cin>>n;int a = n % 2020;int b = n / 2020;if(a > b) puts("NO");elseputs("YES");}return 0;
}

C. Ball in Berland(思维)

题意

输入一个a，b，k分别表示男生的数量和女生的数量，以及k个组合，问你从中取出两组，且同一个人不能在两组有多少中组合方式

解题思路

利用两个数组记录男女在组合中出现的次数，再遍历一遍所有组合，用总人数减去当前组的人物编号总共出现的次数，即冲突的组数，最后要加上自己。结果要开long long存储。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int N = 200005;int a[N],b[N];
int fa[N],fb[N];int main()
{int t,A,B,k,temp;scanf("%d",&t);while(t--) {scanf("%d%d%d",&A,&B,&k);memset(fa,0,sizeof fa);memset(fb,0,sizeof fb);ll l = 0,r = 0;for(int i = 0;i < k; ++i) {scanf("%d",&a[i]);fa[a[i]]++;}for(int i = 0;i < k; ++i) {scanf("%d",&b[i]);fb[b[i]]++;}ll ans = 0;for(int i = 0;i < k; ++i) {ans += k - fa[a[i]] - fb[b[i]] + 1;}printf("%lld\n",ans/2);}return 0;
}

D. Cleaning the Phone（前缀+二分）

题意

从n个软件中选取清理内存超过m且价值最小的方法，输出花费的最小价值，如果都不满足就输出-1

解题思路

可能一眼看上去像贪心or背包，但是看看数据就会发现都不是，我的做法是前缀+二分，我们分别统计消耗价值为1的application以及消耗价值为2的application，然后对这两个数组排序，遍历其中一个数组用二分枚举另一个数组（这里注意使用longlong类型防止溢出）

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int N = 200005;
ll n,m;
ll a[N],b,pre1[N],pre2[N];vector<ll> b1,b2;bool cmp(ll a,ll b) {return a > b;
}int main()
{int t;scanf("%d",&t);while(t--) {memset(pre1,0,sizeof pre1);memset(pre2,0,sizeof pre2);b1.clear();b2.clear();scanf("%lld%lld",&n,&m);ll sum = 0,ans = 0;for(int i =  0;i < n; ++i) {scanf("%lld",&a[i]);sum += a[i];}for(int i =  0;i < n; ++i) {scanf("%lld",&b);ans += b;if(b == 1) {b1.push_back(a[i]);}else {b2.push_back(a[i]);}}if(sum < m) {puts("-1");}else if(sum == m) {printf("%lld\n",ans);}else {ans = 0x3f3f3f3f3f3f3f3f;int len1 = b1.size(), len2 = b2.size();sort(b1.begin(),b1.end(),cmp);sort(b2.begin(),b2.end(),cmp);for(int i = 0;i < len1; ++i) {pre1[i + 1] = pre1[i] + b1[i];}for(int i = 0;i < len2; ++i) {pre2[i + 1] = pre2[i] + b2[i];}for(int i = 0;i <= len1; ++i) {int l = -1,r = len2+1;while(l + 1 < r) {int mid = l + r >> 1;if(pre1[i] + pre2[mid] <= m - 1) {l = mid;}else {r = mid;}}int loc = r;loc = min(loc,len2);loc = max(0,loc);if(pre1[i] + pre2[loc] >= m)ans = min(ans,loc * 2LL + i);}printf("%lld\n",ans);}}return 0;
}

E. Advertising Agency(组合数学)

题意

玛莎有n个博客，她需要k个价值总和最大的博客，输出方案数

解题思路

我们先对n个博客从大到小排序，然后找到第k大的博客的价值，然后判断相同价值的博客数量m，以及从k+1开始和第k大博客价值相等的数量p，方案数为C(p,m) m>=p

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
const int N = 1005;int a[N],t,n,k;bool cmp(int a,int b) {return a > b;
}ll qpow(ll a,ll b,ll c) {ll ans = 1;while(b) {if(b & 1) ans = (ans * a) % c;b >>= 1;a = (a * a) % c;}return ans;
}ll inv(ll x,ll c) {return qpow(x,c-2,c);
}ll C(ll a,ll b, ll c) {ll ans = 1;for(int i = 1;i <= b; ++i) {ans = ans * (a-i+1) % mod;ans =  ans * inv(i,c) % mod;}return ans;
}int main()
{scanf("%d",&t);while(t--) {scanf("%d%d",&n,&k);for(int i = 0;i < n; ++i) {scanf("%d",&a[i]);}sort(a,a+n,cmp);int kk = 0,m = 0;for(int i = k;i < n; ++i)if(a[i] == a[k-1]) kk++;for(int i = 0;i < n; ++i)if(a[i] == a[k-1]) m++;printf("%lld\n",C(m,kk,mod));}return 0;
}