Educational CF 95 Div. 2

学习新的trick，从我做起

C.Mortal Kombat Tower

题意：

你和你的朋友去爬塔，塔上共有$n$只怪物，他们的等级只有$0,1$，$0$表示容易$1$表示较难，你和你的朋友每回合都可以选择打一只或者打两只，你的朋友如果打$1$的话，需要用掉$1cost$，需要按顺序打完所有怪物才能爬完，问最少的$cost$是多少。

题解（贪心）：

看见一很好的想法，第一只怪物无论如何都是你的朋友先手，然后我们考虑之后的$1$的怪物，不难发现，无论如何我们都可以构造出一种方案，使碰到的第一只$1$都是你起手，然后我们看如果只有一只或两只连在一起，则都是你解决，三只就需要你朋友出手，更多的话，就会成一个循环，设有$k$只$1$连在一起，总共要的$cost$就是$\lfloor\frac{3}{k}\rfloor$，然后看看有几段，加起来即可，单次询问时间复杂度为$O(n)$。

题解（dp）：

咕咕咕

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'


int a[200005];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    _for(i,0,n)cin>>a[i];
    int ans=a[0]==1;
    for(int i=1;i<n;++i){
      if(!a[i])continue;
      int j=i;
      while(j<n&&a[j])++j;
      ans+=(j-i)/3;
      i=j-1;
    }
    cout<<ans<<endl;
  }
  return 0;
}

D.Trash Problem

题意：

现在有一个$x$轴，初始在上面有$n$堆垃圾，现在有以下询问：

$0\ x$删除坐标为$x$的垃圾，保证存在

$1 x$在坐标$x$上添加一堆垃圾，保证添加之前，该位置没有垃圾

现你可以对一堆垃圾做$x+1$或$x-1$的操作，问最少需要多少次操作能合并成最多只有两堆垃圾。

先输出初始的最少量操作数，然后每次询问完都需要输出最少操作数。

题解：

不难看出需要的操作数是最大的$x$-最小的$x$-相邻的垃圾间最远的距离。

这里我们可以用一个$set$维护垃圾，$multiset$维护最远距离，这里用到了$c++11$的新函数，$next(it),prev(it)$，用途分别是查当前迭代器位置的前一个和后一个。

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define IN insert
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;


set<int>st;
multiset<int>ans;
signed main() {
  FIO;
  int n,q;cin>>n>>q;
  _for(i,0,n){
    int x;cin>>x;
    st.IN(x);
  }
  set<int>::iterator it;
  multiset<int>::iterator itt;
  if(st.size()>=2){
    for(it=st.begin();it!=st.end();++it){
      if(it!=st.begin())ans.IN(*it-*prev(it));
    }
  }
  if(st.size()<=2)cout<<"0\n";
  else cout<<*st.rbegin()-*st.begin()-*ans.rbegin()<<endl;
  while(q--){
    int ch,x;cin>>ch>>x;
    if(ch){
      st.IN(x);
      it=st.find(x);
      if(st.size()>1){
        if(it!=st.begin()&&next(it)!=st.end()){
          itt=ans.find(*next(it)-*prev(it));ans.erase(itt);
          ans.IN(*next(it)-*it),ans.IN(*it-*prev(it));
        }else if(it!=st.begin())ans.IN(*it-*prev(it));
        else ans.IN(*next(it)-*it);
      }
    }else{
      it=st.find(x);
      if(st.size()==1)st.erase(x);
      else{
          if(it!=st.begin()&&next(it)!=st.end()){
          itt=ans.find(*next(it)-*it),ans.erase(itt);
          itt=ans.find(*it-*prev(it)),ans.erase(itt);
          ans.IN(*next(it)-*prev(it));
        }else if(it!=st.begin())itt=ans.find(*it-*prev(it)),ans.erase(itt);
        else itt=ans.find(*next(it)-*it),ans.erase(itt);
        st.erase(x);
      }
    }
    if(st.size()<=2)cout<<"0\n";
    else cout<<*st.rbegin()-*st.begin()-*ans.rbegin()<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/29/Educational-CF-95-Div-2/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！