CF# 681 Div.2 部分

越来越菜

D. Extreme Subtraction

题意：

现在你有一个长为$n$的数组，现有两操作：1.从前往后数$k$个元素，使他们减一。2.从后往前数$k$个元素，使他们减一$(1\le k\le n)$。这两种操作可以做无限次，问最后能否将这个数组所有元素变成$0$。单次时间复杂度为$O(n)$。

题解：

首先我们明确一点，就是肯定是前面不够的用后面来补，则我们只要每次判断前面还差多少，和后面能提供多少就行了。

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(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'
typedef long long ll;


int a[30005];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    _for(int,i,0,n)cin>>a[i];
    if(n==1||n==2)cout<<"YES\n";
    else{
      int f=1;
      ll su=max(0ll,1ll*a[1]-a[0]);
      _for(int,i,2,n){
        if(su>a[i]){
          f=0;
          break;
        }
        ll pre=max(0ll,a[i-1]-su);
        su=max(su,a[i]-pre);
      }
      cout<<(f?"YES\n":"NO\n");
    }
  }
  return 0;
}

E. Long Permutation

题意：
你现在有一个长为$n(2\le n\le2e5)$的数组，初始元素为$\{1,2,3,4,5,\dots,n\}$，现在有如下操作：

1 l r,输出这个数组$l\sim r$的和。

2 x，这个数组变成他往下数$x(1\le x\le1e5)$个的排列。

一共有$q(1\le q\le2e5)$次操作。

(往下的排列即在全排列中字典序比他大$x$的排列。)

题解：

首先我们先观察数据范围，则可知道，最多求的向下的排列数为$2e10$个，而$15!>2e10$，那么每次操作$2$我们只需要对数组的最后$15$位数进行求排列数即可，可以用逆康托展开来进行处理；而操作$1$只在$15$位数之前的可用等差数列求和，之后的遍历一遍即可。单次的时间复杂度为$O(15q)$。

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 EB emplace_back
#define ER erase
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define _rfor(type,i,a,b) for(type i = (a);i>(b);--i)
#define endl '\n'
typedef long long ll;

const int N=20;
ll fac[N],a[200005];
void decantor(ll x,int n){
  vector<int>v;
  _for(int,i,max(1,n-14),n+1)v.EB(i);
  _rfor(int,i,min(n,15),0){
    int t=x/fac[i-1];
    x%=fac[i-1];
    a[n-i+1]=v[t];
    v.ER(v.begin()+t);
  }
}
signed main() {
  FIO;
  fac[0]=1;
  _for(int,i,1,N)fac[i]=fac[i-1]*i;
  int n,q;cin>>n>>q;
  _for(int,i,1,n+1)a[i]=i;
  ll cur=0;
  while(q--){
    int op,x;cin>>op>>x;
    if(op==1){
      ll ans=0;
      int y;cin>>y;
      if(y<max(1,n-15))ans=1ll*y*(y+1)/2-1ll*x*(x-1)/2;
      else{
        if(n-15>=0)ans=max(0ll,1ll*(n-15)*(n-14)/2-1ll*x*(x-1)/2);
        _for(int,i,max(x,n-14),y+1)ans+=a[i];
      }
      cout<<ans<<endl;
    }else{
      cur+=x;
      decantor(cur,n);
    }
  }
  return 0;
}

F. Identify the Operations

题意：

现在有一个长为$n$的数组$a$，有一个长为$k$数组$b(1\le k<n\le2e5)$，两个数组中的元素都没有重复，且$a$为一个排列，现在你可以选择$a$数组里的一个数并将这个数删除，选定他的左或者右的数并放进一个暂时数组$t$的末尾，然后后面的数向前补齐空位，问有多少种方法能得到$b$数组。

题解：

我们首先看$a$数组里的数。

①$a_i$是$b$数组里的一个数，且左右都是，并且在$b$中的位置在$a_i$的后面，则方案数为$0$。

②$a_i$是$b$数组里的一个数，但左右只有一个是$b$数组里的一个数，则删除那个不是的即可，方案数为$1$。

③$a_i$是$b$数组里的一个数，且左右都不是$b$数组里的数，则删除左右都可，方案数为$2$。

然后我们在操作的时候，改变的只是每个数下标的位置，并不影响他们的顺序，则答案就是所有的方案数相乘。

ps:我吐了，用jio排的版吧这个出题人。

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(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'


int a[200005],b[200005];
map<int,int>mp;
map<int,bool>vis;
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    mp.clear(),vis.clear();
    int n,k;cin>>n>>k;
    _for(int,i,0,n){cin>>a[i];mp[a[i]]=i;}
    _for(int,i,0,k){cin>>b[i];vis[b[i]]=1;}
    int ans=1;
    _for(int,i,0,k){
      int pos=mp[b[i]],t=0;
      vis[b[i]]=0;
      if(pos-1>=0&&!vis[a[pos-1]])++t;
      if(pos+1<n&&!vis[a[pos+1]])++t;
      ans*=t,ans%=MOD;
      if(!ans)break;
    }
    cout<<ans<<endl;
  }
  return 0;
}

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