Codeforces Hello 2018 [ABC]

A - Modular Exponentiation

思路：如果n>31,输出m;m<=31，直接取模

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(void)
{
    ll n,m,ans=1;
    cin >>n >>m;
    if(n>32)    cout << m <<endl;
    else
    {
        for(int i=1;i<=n;i++)
            ans*=2;
        cout << m%ans << endl;
    }
}

B - Christmas Spruce

思路：模拟

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> vec[1005];

int main(void)
{
    int n;
    cin >>n;
    for(int i=2;i<=n;i++)
    {
        int p;
        scanf("%d",&p);
        vec[p].push_back(i);
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        int cntleaf=0;
        if(vec[i].size()!=0)
        {
            for(int j=0;j<vec[i].size();j++)
            {
                if(vec[vec[i][j]].size()==0) cntleaf++;
            }
            if(cntleaf<3)
            {
                flag=false;
                break;
            }
        }
    }
    if(flag)    cout <<"Yes"<<endl;
    else    cout<<"No"<<endl;
}

C - Party Lemonade
思路：二分最小值。check当前的money是不是能够购买L升以上的饮料

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N=30+5;
ll cost[MAX_N];
ll n,l;

bool check(ll money)
{
    //cout <<"money="<<money << endl;
    ll liter=0;
    for(int i=n;i>=1;i--)
    {
        if(money>=cost[i])
        {
            ll p=money/cost[i];
            if(p>=l)    return true; //限制p的范围小于l,否则会爆LL
            liter+=p*(1<<(i-1));
            //cout <<" p="<<p<<" i="<<i<<" liter="<<liter<<endl;
            money-=p*cost[i];
        }
    }
    //cout << endl;
    return liter >=l ;
}

int main(void)
{
    cin >>n >>l;
    for(int i=1;i<=n;i++)
        cin >> cost[i];
    for(int i=2;i<=n;i++)
        cost[i]=min(cost[i],cost[i-1]*2);//cost[i]为1~i中，相同  体积2^(i-1)  价格最低的饮料
    ll l=1,r=1e18,mid;
    ll ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))  ans=mid,r=mid-1;
        else    l=mid+1;
    }
    cout << ans << endl;
}

D:Too Easy Problems

思路：二分最大值。check假设得到X分，判断是不是满足该情况。如果当前得x分，而实际上>=x，x可变大。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N=2e5+50;
int n,t;
vector <int> aaa;

struct node
{
    int a,t,id;
}p[MAX_N];

bool cmp(node a,node b)
{
    return a.t<b.t;
}

bool check(int x)
{
    aaa.clear();
    int cnt=0;
    int tottime=0;
    //cout <<"x=" <<x <<endl;
    for(int i=1;i<=n;i++)
    {
        if(tottime+p[i].t<=t && p[i].a>=x)
        {
            aaa.push_back(p[i].id);
           // cout <<"id="<<p[i].id<<endl;
            tottime+=p[i].t;
            cnt++;
        }
    }
    return cnt>=x;
}

int main(void)
{
    cin >>n >>t;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i].a,&p[i].t);
        p[i].id=i;
    }
    sort(p+1,p+1+n,cmp);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d %d %d\n",p[i].a,p[i].t,p[i].id);
    }*/
    int l=0,r=n,mid;
    int ans;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))  ans=mid,l=mid+1;
        else    r=mid-1;
        //printf("check(%d)=%d\n",mid,check(mid));
    }
    cout << ans << endl << ans << endl;
    check(ans); //注意再check一次，使得aaa中的元素是答案，而不是其他值check的值。
    for(int i=0;i<ans;i++)   cout <<aaa[i]<<" ";
    cout << endl;
}

总结：最值问题，考虑二分+贪心。即对特定的解是否满足题目的约束条件[贪心]