codeforces 732套题题解

Codeforces Round #377 (Div. 2)

CF #377

这是原来的比赛：打CF打得多了之后，发现CF上分的秘诀有三个：

手速+暴力+模拟

DIV2场的AB基本送分题，C和D一般都是用简单的STL来维护几个数学值，然后用数学结论或者公式什么的搞一搞

然后E题呢，给足够的时间推推过程，其实是有可能做的

这场的6个题在补题之后写了5个

A. Buy a Shovel

这个题有个小小的坑点：注意多了一个单位价值为c的硬币：所以还有可能价值对10取余为c（当然这个坑点在样例中已经有了）

    while(scanf("%d%d",&a,&b)!=EOF){
        for(int ans=1;ans<=10;ans++){
            int sum=a*ans;
            if (sum%10==0||sum%10==b){
                printf("%d\n",ans);
                break;
            }
        }
    }

那么：添加数的方案很简单：如果连续两个数的和小于K了，那么在后面那个数上补足（因为这个可以影响到第三个数）

代码：

    while(scanf("%d%d",&n,&k)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        tot=0;
        for(int i=2;i<=n;i++)
            if (a[i]+a[i-1]>=k) continue;
            else{
                add=k-a[i]-a[i-1];
                tot+=add;
                a[i]+=add;
            }
        printf("%d\n",tot);
        for(int i=1;i<=n;i++)
            printf("%d%c",a[i],i==n?'\n':' ');
    }

这个题是个很好的题：怎么去理解这个题的意思

早上出发晚上吃饭吃完后回来……等等，这样可以列出七种情况，枚举一下就好

#include<bits/stdc++.h>
using namespace std;

#define LL __int64
LL a,b,c;
const LL INF=1e19;

LL calc(LL x,LL y,LL z){
    LL Max=max(x,max(y,z));
    return 3*Max-(x+y+z);
}

int main(){
    while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF){
        LL ans=INF;
        ans=min(ans,calc(a,b,c));
        ans=min(ans,calc(a+1,b,c));
        ans=min(ans,calc(a,b+1,c));
        ans=min(ans,calc(a,b,c+1));
        if (a>0)
            ans=min(ans,calc(a-1,b,c));
        if (b>0)
            ans=min(ans,calc(a,b-1,c));
        if (c>0)
            ans=min(ans,calc(a,b,c-1));
        cout<<ans<<endl;
    }
    return 0;
}

经典的二分好题：判断连续K天是不是可行（这个复杂度是log（n））

因为第i科要在数组中的值为i的天数的时候考试，那么直接暴力一发即可（这个复杂度是O（n））

所以乘起来时间是够的

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+50;
int n,m;
int a[maxn];
int b[maxn];

struct node{
    int Time;
    int sub;
}c[maxn];

int cmp(node x,node y){
    return x.Time<y.Time;
}

bool calc(int x){
    int lefttime=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=x;i++)
        if (a[i]){
            c[a[i]].sub=a[i];
            c[a[i]].Time=i;
        }
    for(int i=1;i<=m;i++)
        if (!c[i].Time) return false;
    sort(c+1,c+m+1,cmp);
    //for(int i=1;i<=m;i++)
    //    printf("%d %d%c",c[i].sub,c[i].Time,i==m?'\n':' ');
    for(int i=1;i<=m;i++){
        lefttime+=c[i].Time-c[i-1].Time-1;
        if (lefttime<b[c[i].sub]) return false;
        lefttime-=b[c[i].sub];
    }
    return true;
}

int main(){
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=m;i++) scanf("%d",&b[i]);
        int L,R,mid,ans=-1;
        if (!calc(n)){
            printf("%d\n",ans);
            continue;
        }
        L=1;R=n-1;ans=n;
        while(L<=R){
            mid=(L+R)>>1;
            if (calc(mid)){
                ans=mid;
                R=mid-1;
            }
            else L=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
} 

读题读完之后就是个暴力题，但是怎么暴力：有技巧

把每个火箭的值放进去查询，如果有，那么匹配，如果没有，就不断的（+1）/2，直到匹配或者到1为止

所以要用到STL的multiset来搞

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+50;
int a[maxn],b[maxn];
int n,m;
multiset<pair<int,int> > p;
multiset<pair<int,int> > s;
multiset<pair<int,int> >::iterator it;
multiset<pair<int,int> >::iterator iter;
int main(){
    cin>>n>>m;
    int x;
    for(int i=1;i<=n;i++){
        cin>>x;
        p.insert(make_pair(x,i));
    }
    for(int i=1;i<=m;i++){
        cin>>x;
        s.insert(make_pair(x,i));
    }
    for(it=s.begin();it!=s.end();++it){
        int value=it->first;
        int index=it->second;
        int tmp=0;
        while(1){
            iter=p.lower_bound(make_pair(value,-1));
            if (iter!=p.end()&&(iter->first)==value){
                a[index]=tmp;
                b[iter->second]=index;
                p.erase(iter);
                break;
            }
            if (value==1) break;
            value=(value+1)/2;
            tmp++;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if (b[i]) ans++;
    cout<<ans<<" ";
    ans=0;
    for(int i=1;i<=m;i++)
        ans+=a[i];
    cout<<ans<<endl;
    for(int i=1;i<=m;i++)
        printf("%d%c",a[i],i==m?'\n':' ');
    for(int i=1;i<=n;i++)
        printf("%d%c",b[i],i==n?'\n':' ');
    return 0;
}