daily 3

今天三道双指针

CF 1324D

简单双指针，转化为$c[i]=a[i]-b[i]$即可

void solve(){
  int n;cin>>n;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  for(int i=1;i<=n;++i){
    int x;cin>>x;
    a[i]-=x;
  }
  sort(a.begin()+1,a.end());
  ll ans=0;
  for(int l=1,r=n;l<=n;++l){
    while(r>1&&a[l]+a[r]>0)--r;
    ans+=n-max(l,r);
  }
  cout<<ans<<'\n';
  return;
}

CF 1680C

我们需要尽可能地让删除的1和剩下的0相等，否则不管怎么样都会增大cost，那就双指针去搜就可以了

void solve(){
  string s;
  cin>>s;
  int n=s.size();
  int cnt_1=0;
  for(int i=0;i<s.size();++i){
    if(s[i]=='1')++cnt_1;
  }
  int ans=INT_MAX;
  int cnt_0=0;
  for(int l=0,r=-1;l<n;++l){
    while(r<n&&cnt_0<cnt_1){
        ++r;
        if(s[r]=='1'){
            cnt_1--;
        }else{
            cnt_0++;
        }
        ans=min(ans,max(cnt_0,cnt_1));
    }
    if(s[l]=='0'){
        --cnt_0;
    }else{
        ++cnt_1;
    }
    ans=min(ans,max(cnt_0,cnt_1));
  }
  cout<<ans<<'\n';
  return;
}

CF 386C
三指针的题
每次搜索对应unique为i的长度的最大和最小的r，然后更新答案

#define int ll
void solve(){
  string s;
  cin>>s;
  int n=s.size();
  s='0'+s;
  vector<ll>ans;
  auto calc=[&](int lim){
    int l=1,r1=0,r2=1,res=0;
    int now_cnt=0;
    vector<int>cnt(26);
    for(;l<=n;++l){
        while(r1<n&&now_cnt<lim){
            if(++cnt[s[++r1]-'a']==1){
                ++now_cnt;
            }
        }
        if(now_cnt<lim)break;
        r2=max(r1,r2);
        while(r2<=n&&cnt[s[r2]-'a'])++r2;
        res+=(r2-r1);
        if(--cnt[s[l]-'a']==0)--now_cnt;
    }
    if(res>0)ans.push_back(res);
  };
  for(int i=1;i<=26;++i){
    calc(i);
  }
  cout<<ans.size()<<'\n';
  for(int i=0;i<ans.size();++i){
    cout<<ans[i]<<'\n';
  }
  return;
}