文章目录
- A. Odd Divisor(思维)
- B. New Year's Number(暴力+思维)
- C. Ball in Berland(思维)
- D. Cleaning the Phone（前缀+二分）
- E. Advertising Agency(组合数学)
A. Odd Divisor(思维)
题意
给你一个n，如果n有一个奇数因子就输出YES，否则输出NO
解题思路
我们从n开始判断当前是否是奇数，如果是，则直接输出YES，否则就一直右移一位直到n为1，然后输出NO
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool 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");
}
else
puts("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 long
int 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");
else
puts("YES");
}
return 0;
}
C. Ball in Berland(思维)
题意
输入一个a，b，k分别表示男生的数量和女生的数量，以及k个组合，问你从中取出两组，且同一个人不能在两组有多少中组合方式
解题思路
利用两个数组记录男女在组合中出现的次数，再遍历一遍所有组合，用总人数减去当前组的人物编号总共出现的次数，即冲突的组数，最后要加上自己。结果要开long long存储。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const 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 long
const 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;
}