CodeTonRound8-BC1C2补题

B-Bessie and MEX

思路:顺,逆填都可以.见代码注释

void solve(){           //补B--不用str.find来维护,这个是o(n)的。用set的count() or find()来维护，这两个都是o(logn)的
    int n;cin>>n;
//    // 顺着填：填的数字=MEX.find('0')-ai or 填了MEX[MEX.find('0')]='1',之后MEX.find('0')-刚才填的位置--这样虽然是对的，但是实现容易超时
//    //顺着填：x>=0,那么pi即为当前mex;如果x<0,那么pi=mex-x;
//    // 因为x>=0,即NewMex-CurMex>=0,那么mex一定是增加的,那pi只能填当前mex;
//    // 如果x<0,那么NewMex不能增加,那只能保持不变,那pi只能是mex-x;
    set<int> st;
    int mex=0;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        while(st.find(mex)!=st.end()) mex++;
        if(x>=0){
            cout<<mex<<" ";
            st.insert(mex);
        }
        else{
            cout<<mex-x<<" ";
            st.insert(mex-x);
        }
    }
    cout<<endl;
}

void solve(){           //补B
    //倒着填：因为填了最后一个之后，mex必然为n，那么最后一个pi就是n-arr[n];那么填n-1个时,因为只有pn还没出现过，那么此时mex为pn
    //但是遇到负数时填的数字会更大，mex不会改变，那么只有当mex-ai更小才更新mex
    //我们知道最后一个位置的MEX是n,那么n−pn=an,我们可以得出 pn=n−an
    //现在知道了pn,那么可以确定前n-1个数字的MEX.跟求出pn是一样的.一直这样计算下去即可.
    int n; cin>>n;
    int arr[200005];
    for(int i=1;i<=n;i++) cin>>arr[i];
    int cur=n-arr[n];
    stack<int> stk;
    stk.emplace(cur);
    for(int i=n-1;i>=1;i--){
        stk.emplace(cur-arr[i]);
        cur=min(cur,cur-arr[i]);
    }
    while(stk.size()){
        cout<<stk.top()<<" ";
        stk.pop();
    }
    cout<<endl;
}

C1-Bessie's Birthday Cake (Easy Version)

思路:见代码注释.

void solve(){           //补C1    新
    int n,x,y; cin>>n>>x>>y;
    int ans=x-2;            //!!显然!!任意x个点内部可以构成x-2个三角形.对于外部点三角形,也是显然，只有两个点距离恰好为2点时候可以构成外部一个三角形
    int arr[200005];
    for(int i=1;i<=x;i++) cin>>arr[i];
    sort(arr+1,arr+x+1);
    for(int i=2;i<=x;i++){
        if(arr[i]-arr[i-1]==2) ans++;
    }
    if(arr[1]+n-arr[x]==2) ans++;  //特判一下环的最后一个和第一个
    cout<<ans<<endl;
}

C2-Bessie's Birthday Cake (Hard Version)

思路:见代码注释

void solve(){           //补C2   !贪心! 重重贪心,先是贪偶数，再是贪从小的先拿
    int n,x,y; cin>>n>>x>>y;
    int ans=x-2;
    int arr[200005];
    for(int i=1;i<=x;i++) cin>>arr[i];
    sort(arr+1,arr+x+1);
    arr[x+1]=arr[1]+n;
    //priority_queue<int> pq;      //不能单调从大到小排。因为偶的是比奇的更有价值的，所以应该优先考虑偶的区间，还有y剩余的话，再考虑奇的区间(贪心)
    priority_queue<int,vector<int>,greater<int>> pqodd,pqeven;   //小根堆,优先拿小的
    for(int i=1;i<=x;i++){
        if(arr[i+1]-arr[i]==2) ans++;
        if(arr[i+1]-arr[i]>2&&(arr[i+1]-arr[i])%2==0) pqeven.emplace(arr[i+1]-arr[i]);
        if(arr[i+1]-arr[i]>2&&(arr[i+1]-arr[i])%2!=0) pqodd.emplace(arr[i+1]-arr[i]);
    }
    while(pqeven.size()&&y){
        //先贪心地跑偶的,因为得到相同的三角形个数,偶的可以花费更少y.
        // 先拿小的,是因为小的更值当;如果先拿大的,可能因为y不够,导致贪心没有贪到
        int cur=pqeven.top();
        pqeven.pop();
        if(cur%2==0&&y>=cur/2-1){
            y-=cur/2-1,ans+=cur/2-1,ans+=cur/2;
        }
        else if(cur%2==0&&y<cur/2-1){
            ans+=y,ans+=y,y=0;
        }
        else if(cur%2!=0&&y>=cur/2){
            y-=cur/2,ans+=cur/2,ans+=cur/2;
        }
        else if(cur%2!=0&&y<cur/2){
            ans+=y,ans+=y,y=0;
        }
    }
    while(pqodd.size()&&y){
        int cur=pqodd.top();
        pqodd.pop();
        if(cur%2==0&&y>=cur/2-1){
            y-=cur/2-1,ans+=cur/2-1,ans+=cur/2;
        }
        else if(cur%2==0&&y<cur/2-1){
            ans+=y,ans+=y,y=0;
        }
        else if(cur%2!=0&&y>=cur/2){
            y-=cur/2,ans+=cur/2,ans+=cur/2;
        }
        else if(cur%2!=0&&y<cur/2){
            ans+=y,ans+=y,y=0;
        }
    }
    cout<<ans<<endl;
}

总结:这场只写出来AB题，B题因为用str.find()来维护,被hack了。所以只有A题，一场扣了100多分..再接再厉吧。