A. Odd Divisor(思维)

题意

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

解题思路

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

Code

#include
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
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
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
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
using namespace std;
#define ll long long

const int N = 200005;
ll n,m;
ll a[N],b,pre1[N],pre2[N];

vector 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
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;
}

本当の声を響かせてよ