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

太菜了,太菜了。

A. Odd Divisor

题意

给出一个整数,如果这个数有除了1以外的奇数因子,输出yes,否则no。

题解

打出小于2^{14}的2的幂即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll nums[49]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312};
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    set<ll> s;
    for(ll i=0;i<48;i++) {
        ll j=nums[i];
        s.insert(j);
    }
    cin>>_;
    while(_--){
        ll a;
        cin>>a;
        if(s.count(a)==1)cout<<"NO"<<endl;
        else  cout<<"YES"<<endl;
    }

}

B. New Year’s Number

题意

给出一个数,如果能被n个2020和m个2021相加得到,输出yes,否则no。

题解

入门dp,首先将num[2020]和num[2021]标记为1,然后遍历,如果遇到标记为1的就把num[i+2020]和num[i+2021]标记为1。注意数组开成bool型以免超内存。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    bool num[1003000];
    memset(num,0,sizeof(num));
    num[2020]=1;
    num[2021]=1;
    for(int i=2020;i<1000008;i++){
        if(num[i]==1){
            num[i+2020]=1;
            num[i+2021]=1;
        }
    }
    cin>>_;
    while(_--){
        ll a;
        cin>>a;
        if(num[a]==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

}

C. Ball in Berland

题意

这题当时读了半个多小时才读懂,就是有n个男孩和b个女孩,同时在舞会上有k对组合方式,从中找出两对,问有多少种方式。

题解

按照男孩排序(比赛时的样例是有问题的,题中没有提示有序,但最初样例都是有序的,后来hack了一组无序样例),求出编号为i的男孩可以对应多少个女孩的后缀和、编号为i的女孩对应多少个男孩。然后遍历,当遍历到某一对的时候,总数+=男孩的后缀和-女孩对应男孩的数量+1,同时要该女孩对应男孩的数量–。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
struct node{
    int a;
    int b;
    bool operator < (node nod){
        if(a!=nod.a)
            return a < nod.a;
        return b < nod.b;
    }

};
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int a,b,k,s;
        cin>>a>>b>>k;
        vector<node> n1;
        map<int,int> s1;
        map<int,int> s2;
        for(int i=0;i<k;i++){
            cin>>s;
            node nod;
            nod.a=s;
            n1.push_back(nod);
            s1[s]++;
        }
        for(int i=0;i<k;i++){
            cin>>s;
            n1[i].b=s;
            s2[s]++;

        }
        sort(n1.begin(),n1.end());
        ll re=0;
        int nums[a+1];
        memset(nums,0,sizeof(nums));
        int last=n1.back().a,num=0;
        for(int i=n1.size()-1;i>=0;i--){
            if(n1[i].a!=last){
                nums[n1[i].a]=num;
                last=n1[i].a;
            }
            num++;
        }
        nums[0]=num;
        for(int i=0;i<k;i++){
                //cout<<nums[n1[i]]<<" "<<s2[n2[i]]<<endl;
            re+=nums[n1[i].a]-s2[n1[i].b]+1;
            s2[n1[i].b]--;
            //cout<<re<<endl;
        }
        cout<<re<<endl;
    }

}

D. Cleaning the Phone

题意

需要清理手机中m的内存,同时重要度的和最小,求最小的重要度。

题解

开始一看像背包,不过数据范围太大,背包一定会TLE。因为只有1和2两种状态,所以是贪心。
当然我们不能直接去贪,因为要考虑不少条件,比如我的第一版代码:
(在加了不少条件之后WA在test2的第1609个样例上)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
bool cmp(int a,int b){return a>b;}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n,m,s;
        cin>>n>>m;
        vector<int> num;
        vector<int> num1;
        vector<int> num2;
        ll sum=0;
        for(int i=0;i<n;i++){
            cin>>s;
            num.push_back(s);
            sum+=s;
        }
        for(int i=0;i<n;i++){
            cin>>s;
            if(s==1) num1.push_back(num[i]);
            else num2.push_back(num[i]);
        }
        if(sum<m){
            cout<<-1<<endl;
            continue;
        }
        sort(num1.begin(),num1.end(),cmp);
        sort(num2.begin(),num2.end(),cmp);
        ll re=0,mem=0;
        int i=0,j=0;
        while(mem<m){
            if(j==num2.size()){
                mem+=num1[i];
                re+=1;
                i++;
                continue;
            }
            if(i==num1.size()){
                mem+=num2[j];
                re+=2;
                j++;
                continue;
            }
            if(mem+num1[i]>=m){
                re+=1;
                break;
            }
            if(mem+num2[j]>=m){
                re+=2;
                break;
            }
            if(i==num1.size()-1){
                mem+=num2[j];
                re+=2;
                j++;
                continue;
            }
            if(j==num2.size()-1){
                mem+=num1[i];
                re+=1;
                i++;
                continue;
            }
            if(num1[i]+num[i+1]<=num2[j]){
                mem+=num2[j];
                re+=2;
                j++;
            }
            else{
                mem+=num1[i];
                re+=1;
                i++;
            }
            //cout<<re<<"re"<<endl;
        }
        cout<<re<<endl;
    }

}

后来参考了tourist的做法,这是一种很巧妙的贪心。
统计出重要度为2的总和,然后逐渐减少,O(n)时间复杂度下就能找到最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
bool cmp(int a,int b){return a>b;}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n,m,s;
        cin>>n>>m;
        vector<int> num;
        vector<int> num1;
        vector<int> num2;
        ll sum=0,sum2=0;
        for(int i=0;i<n;i++){
            cin>>s;
            num.push_back(s);
            sum+=s;
        }
        for(int i=0;i<n;i++){
            cin>>s;
            if(s==1) num1.push_back(num[i]);
            else {
                num2.push_back(num[i]);
                sum2+=num[i];
            }
        }
        if(sum<m){
            cout<<-1<<endl;
            continue;
        }
        sort(num1.begin(),num1.end(),cmp);
        sort(num2.begin(),num2.end(),cmp);
        ll re=lmax,mem=0;
        int j=0;
        for(int i=num2.size();i>=0;i--){
            while(j<num1.size()&&sum2<m){
                sum2+=num1[j];
                j++;
            }
            if(sum2>=m){
                re=min(re,2*i+j);
            }
            if(i>0){
                sum2-=num2[i-1];
            }
            //cout<<re<<endl;
        }
        cout<<re<<endl;
    }

}

这题另外还有二分做法。

E. Advertising Agency

题意

每个物品都有不同的收益,求拿k件物品的最大收益的方案总数。

题解

首先按照收益为n的物品个数分组,然后贪心一波,贪到再加一组中的n个就够了的时候,求组合。
求组合的时候用卢卡斯定理模板。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll fpow(ll a,ll n,ll mod)
{
    ll res = 1;
    while(n)
    {
        if(n & 1)
        {
            res = res % mod * a % mod;
        }
        a = a % mod * a % mod;
        n >>= 1;
    }
    return res;
}
ll inv(ll x, ll p)
{
    return fpow(x, p - 2, p);
}
ll C(ll n, ll m, ll p)
{
    if(m > n)return 0;
    ll up = 1, down = 1;
    for(int i = n - m + 1; i <= n; i++)up = up * i % p;
    for(int i = 1; i <= m; i++)down = down * i % p;
    return up * inv(down, p) % p;
}
ll Lucas(ll n, ll m, ll p)
{
    if(m == 0)return 1;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n,k,s;
        cin>>n>>k;
        map<ll,ll> m;
        for(int i=0;i<n;i++){
            cin>>s;
            m[s]++;
        }
        ll num=0;
        for(map<ll,ll>::reverse_iterator rit=m.rbegin();rit!=m.rend();rit++) {
            if(k>(*rit).second) k-=(*rit).second;
            else {
                num=(*rit).second;
                break;
            }
        }
        cout<<Lucas(num,k,1000000007)<<endl;

    }

}

题目来源于https://codeforces.com/contest/1475

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
上一篇
下一篇