专栏文章

2023 ICPC Asia Regional - Seoul

SStеlІаwіnD心華
个人记录参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minrunlo
此快照首次捕获于
2025/12/02 07:19
3 个月前
此快照最后确认于
2025/12/02 07:19
3 个月前
查看原文

A Apricot Seeds

https://www.luogu.com.cn/problem/solution/P14085
跪着抄题解吧（

B Black Box

Coconut 是小于 nn 的，所以后面的交换操作是假的。接下来的操作就是前面的 while，翻译一下就是说每次插入一个数然后指针往后挪 aia_i 个。树状数组维护这个过程即可。
CPP
int a[200010],b[200010];
int tree[200010],n;
int lowbit(int x){return x&(-x);}
void add(int x,int k){while(x<=n)tree[x]+=k,x+=lowbit(x);}
int query(int x,int ans=0){while(x)ans+=tree[x],x-=lowbit(x);return ans;}
int main(){
  ios::sync_with_stdio(0);
  cin>>n;
  for(int i=0;i<n;++i)cin>>a[i];
  swap(a[0],a[a[n-1]%(n-1)]);
//  for(int i=0;i<n;++i)cout<<a[i]<<' ';
//  cout<<'\n';
  b[0]=a[0];
  set<int>S;
  for(int i=1;i<n;++i)add(i,1);
  int las=0;
  for(int i=1;i<n;++i){
    int X=query(las);
    int now=(a[i-1]+X-1)%(n-i)+1;
    int l=0,r=n-1;
//    cout<<now<<'\n';
    while(l<r){
      int mid=l+r>>1;
      int Y=query(mid);
//      cout<<mid<<' '<<Y<<' '<<*S.upper_bound(mid)<<'\n';
      if(Y<now)l=mid+1;
      else r=mid;
    }
    las=l;
    add(las,-1);
    b[las]=a[i];
//    cout<<"put:"<<las<<endl;
  }
  for(int i=0;i<n;++i)cout<<b[i]<<'\n';
}

C Farm

每次取最高的没有覆盖的关键点，以这个关键点取一个最大的矩形即可。代码巨难写，不建议做此题。
CPP
int L[400010],R[400010];
std::map<int,int>mp;
struct point{
  pii X,Y;
}P[400010];
struct line{
  int x,sy,ey;
}l[400010];
pii pst[400010];
int X[400010],Y[400010];
int a[400010],F[400010];
int cntx,cnty;
struct sgt{
  int tree[2000010];
  void pushdown(int p){
    if(tree[p]){
      tree[p<<1]=tree[p<<1|1]=tree[p];
      tree[p]=0;
    }
  }
  void modify(int p,int l,int r,int x,int y,int k){
    debug("modify %lld %lld %lld %lld %lld %lld\n",p,l,r,x,y,k);
    // fflush(stdout);
    if(l>=x&&r<=y)return(void)(tree[p]=k);
    pushdown(p);int mid=l+r>>1;
    if(mid>=x)modify(p<<1,l,mid,x,y,k);
    if(mid<y)modify(p<<1|1,mid+1,r,x,y,k);
  }
  int query(int p,int l,int r,int x){
    debug("query %lld %lld %lld %lld %lld\n",p,l,r,x,tree[p]);
    // fflush(stdout);
    if(tree[p])return tree[p];
    if(l==r)return 0;
    pushdown(p);int mid=l+r>>1;
    if(mid>=x)return query(p<<1,l,mid,x);
    else return query(p<<1|1,mid+1,r,x);
  }
}T;
void solve(){
  int m,n;read(m),read(n);
  rep(i,1,m){
    read(a[i]);
    if(i%2)X[++cntx]=a[i];
    else a[i]=a[i]*2,Y[++cnty]=a[i];
  }
  rep(i,1,m/2)l[i]={a[i*2-1],a[i*2-2],a[i*2]};
  rep(i,1,m/2)if(l[i].sy<l[i].ey)F[i]=1;else F[i]=0;
  rep(i,1,m/2)if(l[i].sy>l[i].ey)std::swap(l[i].sy,l[i].ey);
  rep(i,1,n)read(pst[i].first),read(pst[i].second),pst[i].second=std::max(pst[i].second,1ll)*2-1;
  rep(i,1,n)X[++cntx]=pst[i].first,Y[++cnty]=pst[i].second;
  // edebug("#");
  std::sort(X+1,X+cntx+1);cntx=std::unique(X+1,X+cntx+1)-X-1;
  std::sort(Y+1,Y+cnty+1);cnty=std::unique(Y+1,Y+cnty+1)-Y-1;
  rep(i,1,m/2){
    l[i].x=std::lower_bound(X+1,X+cntx+1,l[i].x)-X;
    l[i].sy=std::lower_bound(Y+1,Y+cnty+1,l[i].sy)-Y;
    l[i].ey=std::lower_bound(Y+1,Y+cnty+1,l[i].ey)-Y;
  }
  rep(i,1,n){
    pst[i].first=std::lower_bound(X+1,X+cntx+1,pst[i].first)-X;
    pst[i].second=std::lower_bound(Y+1,Y+cnty+1,pst[i].second)-Y;
  }
  // rep(i,1,m/2)debug("%lld %lld %lld\n",l[i].x,l[i].sy,l[i].ey);
  // rep(i,1,n)debug("%lld %lld\n",pst[i].first,pst[i].second);
  // fflush(stdout);
  // edebug("$");
  // std::sort(l+1,l+m/2+1,[](line i,line j){return i.x<j.x;});
  std::sort(pst+1,pst+n+1);
  rep(i,1,m/2)debug("%lld %lld %lld\n",l[i].x,l[i].sy,l[i].ey);
  rep(i,1,n)debug("%lld %lld\n",pst[i].first,pst[i].second);
  // fflush(stdout);
  int curl=1,curr=1;
  while(curl<=m/2||curr<=n){
    debug("%lld %lld\n",curl,curr);
    // fflush(stdout);
    if(curl<=m/2&&(curr>n||l[curl].x<pst[curr].first||(l[curl].x==pst[curr].first&&F[curl]==1)))T.modify(1,1,cnty,l[curl].sy,l[curl].ey,l[curl].x),++curl;
    else L[curr]=T.query(1,1,cnty,pst[curr].second),++curr;
  }
  memset(T.tree,0,sizeof(T.tree));
  curl=m/2,curr=n;
  while(curl||curr){
    debug("%lld %lld\n",curl,curr);
    fflush(stdout);
    if(curl&&(!curr||l[curl].x>pst[curr].first||(l[curl].x==pst[curr].first&&F[curl]==0)))T.modify(1,1,cnty,l[curl].sy,l[curl].ey,l[curl].x),--curl;
    else R[curr]=T.query(1,1,cnty,pst[curr].second),--curr;
  }
  rep(i,1,n)debug("%lld %lld %lld %lld\n",pst[i].first,pst[i].second,L[i],R[i]);
  // fflush(stdout);
  edebug("&");
  rep(i,1,n)P[i]={std::make_pair(L[i],R[i]),pst[i]};
  int ans=0;memset(T.tree,0,sizeof(T.tree));
  std::sort(P+1,P+n+1,[](point i,point j){return i.Y.second>j.Y.second;});
  rep(i,1,n)if(!T.query(1,1,cntx,P[i].Y.first))++ans,T.modify(1,1,cntx,P[i].X.first,P[i].X.second,1);
  print(ans,'\n');
}

D Fraction

按题意模拟，注意约分。
CPP
struct Frac{
  int X,Y;
  Frac operator+(Frac b)const{
    int X2=b.X,Y2=b.Y;
    int G=__gcd(Y,Y2);
//    cout<<X<<' '<<Y<<' '<<X2<<' '<<Y2<<' '<<G<<endl;
    return{Y2/G*X+Y/G*X2,Y/G*Y2};
  }
  Frac operator/(Frac b)const{
    int X2=b.X,Y2=b.Y;
    // XY2 / YX2
    int G=__gcd(Y,Y2),G2=__gcd(X,X2);
//    cout<<X<<' '<<Y<<' '<<X2<<' '<<Y2<<' '<<G<<' '<<G2<<' '<<(X/G2)*(Y2/G)<<' '<<(Y/G)*(X2/G2)<<'\n';
    return{(X/G2)*(Y2/G),(Y/G)*(X2/G2)};
  }
};
void print(Frac X){
  int G=__gcd(X.X,X.Y);
  cout<<(long long)(X.X/G)<<' '<<(long long)(X.Y/G)<<'\n';
}
signed n;
Frac solve(){
  if(!n) {cout<<-1;exit(0);}
  char a; cin>>a; --n;
  Frac X,Y,Z;
  if(a=='('){
    X=solve();
    if(!n){cout<<-1;exit(0);}
    cin>>a; --n;
    if(a!=')'){cout<<-1;exit(0);}
  }
  else if(isdigit(a))X={a-'0',1};
  else{cout<<-1;exit(0);}
  if(!n) return X;
  cin>>a; --n;
  if(a=='('){
    Y=solve();
    if(!n){cout<<-1;exit(0);}
    cin>>a; --n;
    if(a!=')'){cout<<-1;exit(0);}
  }
  else if(isdigit(a))Y={a-'0',1};
  else{cout<<-1;exit(0);}
  if(!n){cout<<-1;exit(0);}
  cin>>a; --n;
  if(a=='('){
    Z=solve();
    if(!n){cout<<-1;exit(0);}
    cin>>a; --n;
    if(a!=')'){cout<<-1;exit(0);}
  }
  else if(isdigit(a))Z={a-'0',1};
  else{cout<<-1;exit(0);}
  Frac ans = (X+(Y/Z));
//  cout<<X.X<<' '<<X.Y<<'\n';
//  
//  cout<<Y.X<<' '<<Y.Y<<'\n';
//  
//  cout<<Z.X<<' '<<Z.Y<<'\n';
//  cout<<ans.X<<' '<<ans.Y<<'\n';
  return ans;
}
signed main(){
  cin>>n;
  Frac ans=solve();
  if(n){cout<<"-1";return 0;}
  print(ans);
//  cout<<(long long)ans.X<<' '<<(long long)ans.Y<<'\n';
}

E K-Lottery

把每个排列哈希一下，比如说 [1,2,3]→(123)x,[3,2,1]→(321)x[1,2,3]\to (123)_x,[3,2,1]\to(321)_x。那么问题就变成对于给出的数列求每一个长度为 kk 的窗口的答案。
这个哈希就相当于是求 ∑xk−ipi\sum x^{k-i}p_i。那么开一个线段树 SS 表示每一位上乘的 xx 幂次，开一个树状数组 TT 表示窗口内有多少个小于等于它的数，也就是 pip_i。
每次加入一个数的时候，树状数组要做一个区间加，线段树上每一位乘上 xx，然后把移出窗口的数字置 00，加入窗口的数字置 11，每次操作的同时更新前面那个求和即可。
代码常数巨大，不过出题人没卡自然溢出。
CPP
constexpr int base=10001;
std::map<unsigned int,int>mp;
// int pw[4000010],pw2[4000010];
struct sgt{
  unsigned int tree[4000010],lzy[4000010];
  sgt(){rep(i,0,4000000)lzy[i]=1;}
  void pushdown(int p){
    if(lzy[p]!=1){
      tree[p<<1]=tree[p<<1]*lzy[p];
      tree[p<<1|1]=tree[p<<1|1]*lzy[p];
      lzy[p<<1]=lzy[p<<1]*lzy[p];
      lzy[p<<1|1]=lzy[p<<1|1]*lzy[p];
      lzy[p]=1;
    }
  }
  void modify(int p,int l,int r,int x,int k){
    // debug("%lld %lld %lld %lld %lld\n",p,l,r,x,k);
    if(l==r)return(void)(tree[p]=k,lzy[p]=1);
    pushdown(p);
    int mid=l+r>>1;
    if(mid>=x)modify(p<<1,l,mid,x,k);
    else modify(p<<1|1,mid+1,r,x,k);
    tree[p]=(tree[p<<1]+tree[p<<1|1]);
    // debug("%lld %lld %lld %lld\n",p,l,r,tree[p]);
  }
  void modify(){lzy[1]=lzy[1]*base;tree[1]=tree[1]*base;}
  unsigned int query(int p,int l,int r,int x,int y){
    // debug("%lld %lld %lld %lld\n",p,l,r,tree[p]);
    if(x>y)return 0;
    if(l>=x&&r<=y)return tree[p];
    pushdown(p);
    int mid=l+r>>1,ans=0;
    if(mid>=x)ans+=query(p<<1,l,mid,x,y);
    if(mid<y)ans+=query(p<<1|1,mid+1,r,x,y);
    return ans;
  }
}T;
int a[1000010],b[1000010],S,n;
int X[1010][10010];
int tree[1000010];
int lowbit(int x){return x&(-x);}
void add(int x,int k){while(x<=n)tree[x]+=k,x+=lowbit(x);}
unsigned int query(int x,int ans=0){while(x)ans+=tree[x],x-=lowbit(x);return ans;}
void solve(){
  int k,m;read(k),read(m),read(n);
  // pw[0]=pw2[0]=1;rep(i,1,n)pw[i]=pw[i-1]*base%mod,pw2[i]=pw2[i-1]*base%mod2;
  rep(i,1,m){
    unsigned int sum=0;
    rep(j,1,k){
      read(X[i][j]);
      sum=(sum*base+X[i][j]);
    }
    assert(!mp.count(sum));
    mp[sum]=i;
    // debug("%lld\n",sum);
  }
  rep(i,1,n)read(a[i]),b[i]=a[i];
  std::sort(b+1,b+n+1);
  rep(i,1,n)a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;
  rep(i,1,n){
    T.modify();S=S*base;
    T.modify(1,1,n,a[i],1);S=(S+query(a[i]));
    add(a[i],1);
    S=(S+T.query(1,1,n,a[i],n));
    // debug("BIT:");rep(i,1,n)debug("%lld ",query(i));debug("\n");
    // debug("SEG:");rep(i,1,n)debug("%lld ",T.query(1,1,n,i,i));debug("\n");
    // debug("%lld %lld\n",a[i],S);
    if(i>=k){
      if(mp.count(S)){
        rep(i,1,k)print(X[mp[S]][i],' ');
        return;
      }
      S=S-T.query(1,1,n,a[i-k+1],a[i-k+1])*query(a[i-k+1]);
      T.modify(1,1,n,a[i-k+1],0);
      add(a[i-k+1],-1);
      S=S-T.query(1,1,n,a[i-k+1],n);
    }
    // debug("%lld\n",S);
  }
  puts("0");
}

F Lucky Draws

设 dpi,jdp_{i,j} 表示做到第 ii 位，选了 jj 个点的答案，那么有 dpi,j=ci+max⁡{dppre,j−1−S(pre,i)}dp_{i,j}=c_i+\max\{dp_{pre,j-1}-S(pre,i)\}，其中 cic_i 表示 ii 位置上的线段个数，S(j,i)S(j,i) 表示跨越 j∼ij\sim i 的区间个数。
线段树维护后面那个式子的最大值即可。
CPP
pair<int,int>a[10010];
struct sgt{
  vector<int>tree,lzy;
  void init(int n){
    tree.resize(n*4),lzy.resize(n*4);
  }
  void pushdown(int p){
    if(lzy[p]){
      tree[p<<1]+=lzy[p];
      tree[p<<1|1]+=lzy[p];
      lzy[p<<1]+=lzy[p];
      lzy[p<<1|1]+=lzy[p];
      lzy[p]=0;
    }
  }
  void modify(int p,int l,int r,int x,int k){
//    cout<<"Modify "<<p<<' '<<l<<' '<<r<<' '<<x<<' '<<k<<endl;
    if(l==r)return(void)(tree[p]=k);
    pushdown(p);
    int mid=l+r>>1;
    if(mid>=x)modify(p<<1,l,mid,x,k);
    else modify(p<<1|1,mid+1,r,x,k);
    tree[p]=max(tree[p<<1],tree[p<<1|1]);
  }
  void modify(int p,int l,int r,int x,int y,int k){
//    cout<<"Modify "<<p<<' '<<l<<' '<<r<<' '<<x<<' '<<y<<' '<<k<<endl;
    if(l>=x&&r<=y)return(void)(tree[p]+=k,lzy[p]+=k);
    pushdown(p);
    int mid=l+r>>1;
    if(mid>=x)modify(p<<1,l,mid,x,y,k);
    if(mid<y)modify(p<<1|1,mid+1,r,x,y,k);
    tree[p]=max(tree[p<<1],tree[p<<1|1]);
  }
  int query(int p,int l,int r,int x,int y){
//    cout<<"Query "<<p<<' '<<l<<' '<<r<<' '<<x<<' '<<y<<endl;
    if(l>=x&&r<=y)return tree[p];
    pushdown(p);
    int mid=l+r>>1,ans=0;
    if(mid>=x)ans=max(ans,query(p<<1,l,mid,x,y));
    if(mid<y)ans=max(ans,query(p<<1|1,mid+1,r,x,y));
    return ans;
  }
}T[10010];
int sum[30010];
vector<int>del[30010],dp[30010];
map<int,int>mp;
int main(){
  ios::sync_with_stdio(0);
  int n,k;cin>>n>>k;
  for(int i=1;i<=n;++i)cin>>a[i].first>>a[i].second;
  vector<int>A;
  for(int i=1;i<=n;++i)A.push_back(a[i].first),A.push_back(a[i].second);
  sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());
  int m=A.size();
  for(int i=0;i<m;++i)mp[A[i]]=i+1;
  for(int i=1;i<=n;++i)++sum[mp[a[i].first]],del[mp[a[i].second]].push_back(mp[a[i].first]);
  for(int i=0;i<=k;++i)T[i].init(m+1);
  for(int i=1;i<=m;++i)dp[i].resize(k+2);
//  cout<<"#"<<endl;
//  cout<<m<<endl;
//  for(int i=1;i<=m;++i){
//    for(int j:del[i])cout<<j<<' '<<i<<endl;
//  }
  int S=0;
  for(int i=1;i<=m;++i){
    S+=sum[i];
//    cout<<i<<' '<<S<<endl;
    for(int j=k-1;j>=0;--j)dp[i][j+1]=S+T[j].query(1,1,m,1,i);
    for(int j=k;j>0;--j)T[j].modify(1,1,m,i,dp[i][j]-S);
    S-=del[i].size();
    for(int j:del[i])for(int l=1;l<=k;++l)
      T[l].modify(1,1,m,j,i,1);
  }
  int ans=0;
  for(int i=1;i<=m;++i)for(int j=1;j<=k;++j)ans=max(ans,dp[i][j]);
  cout<<ans<<'\n';
}

G Magic Cards

哈希记录每个数字出现的位置。
看了题解，发现我唐了。因为他只有 100100 张卡，把它看做一个 100100 位二进制数就可以了。
CPP
map<pair<int,int>,vector<int>>mp;
int Hash[500010],Hash2[500010];
int pw[500010],pw2[500010];
map<int,int>m2;
signed main(){
  ios::sync_with_stdio(0);
  pw[0]=pw2[0]=1;
  int n,k,m,f;
  cin>>n>>k>>m>>f;
  for(int i=1;i<=k;++i){
    m2.clear();
    pw[i]=pw[i-1]*200%1000000009;
    pw2[i]=pw2[i-1]*300%993244853;
    for(int j=1;j<=m;++j){
      int x;cin>>x;
      if(m2[x])continue;
      m2[x]=1;
      Hash[x]=(Hash[x]+pw[i])%1000000009;
      Hash2[x]=(Hash2[x]+pw2[i])%993244853;
    }
  }
  for(int i=1;i<=n;++i)mp[{Hash[i],Hash2[i]}].push_back(i);
  for(int i=1;i<=f;++i){
    string s;cin>>s;
    int H1=0,H2=0;
    for(int j=1;j<=k;++j){
      if(s[j-1]=='Y'){
        H1=(H1+pw[j])%1000000009;
        H2=(H2+pw2[j])%993244853;
      }
    }
    if(mp[{H1,H2}].size()==1)cout<<mp[{H1,H2}][0]<<'\n';
    else cout<<"0\n";
  }
}

H M.S.I.S.

https://www.luogu.com.cn/article/iajjp9st
我看得懂，但我大受震撼。
显然每个位置至少可以取一个数。把取两个数的位置拿出来，那么它们必然两项全部单调递增。开树状数组维护这一部分额外的贡献即可。
CPP
int tree[50010];
int N=50000;
int lowbit(int x){return x&(-x);}
void modify(int x,int k){while(x<=N)tree[x]=max(tree[x],k),x+=lowbit(x);}
int query(int x,int ans=0){while(x)ans=max(ans,tree[x]),x-=lowbit(x);return ans;}
pair<int,int>a[10010];
int main(){
  ios::sync_with_stdio(0);
  int n;cin>>n;
  for(int i=1;i<=n;++i)cin>>a[i].first;
  for(int i=1;i<=n;++i)cin>>a[i].second;
  sort(a+1,a+n+1);
  int ans=0;
  for(int i=1;i<=n;++i)modify(a[i].second,min(a[i].first,a[i].second)+query(a[i].second));
  for(int i=1;i<=n;++i)ans+=max(a[i].first,a[i].second);
  cout<<ans+query(N)<<'\n';
}

I Product Delivery

就是求分成多少段连续不增子序列。
CPP
int main(){
  ios::sync_with_stdio(0);
  int n;cin>>n;
  int ans=1,las=0;
  for(int i=1;i<=n;++i){
    int l,r;cin>>l>>r;
    if(r<las)++ans,las=l;
    else las=max(las,l);
  }
  cout<<ans<<'\n';
}

J Special Numbers

数位 DP。dp[n][k]dp[n][k] 表示做到第 n 位，后面必须是 k 的倍数。不会写的建议重新学习数位 DP。
CPP
constexpr int mod=1e9+7;
int d[20],pw[22],k;
map<int,int>dp[22];
int dfs(int n,bool flag,bool F,int K){
//  cout<<n<<' '<<(int)flag<<' '<<(int)F<<' '<<K<<'\n';
  if(n==0){
    return K==1;
  }
  if(K==1&&!flag)return pw[n];
  if(!flag&&!F&&dp[n].count(K))return dp[n][K];
  int bound=9;if(flag)bound=d[n];
  int ans=0;
  for(int i=0;i<=bound;++i){
    int newK=K;
    if(i==0&&!F)newK=1;
    else if(i!=0)newK/=__gcd(i,K);
//    cout<<i<<' '<<K<<' '<<newK<<'\n';
    ans+=dfs(n-1,flag&&(i==bound),F&&(i==0),newK);
    ans%=mod;
//    cout<<"now:"<<n<<' '<<i<<' '<<ans<<'\n';
  }
//  cout<<"#"<<n<<' '<<K<<' '<<ans<<' '<<(int)flag<<' '<<(int)F<<'\n';
  if(!flag&&!F)dp[n][K]=ans;
  return ans;
}
int solve(__int128 X){
  for(int i=1;i<=20;++i)dp[i].clear();
  int n=0;
  while(X)d[++n]=X%10,X/=10;
  return dfs(n,1,1,k);
}
signed main(){
  ios::sync_with_stdio(0);
  string l,r;cin>>k>>l>>r;
  pw[0]=1;for(int i=1;i<=20;++i)pw[i]=pw[i-1]*10%mod;
  __int128 L=0,R=0;
  for(char c:l)L=(L*10+c-'0');
  for(char c:r)R=(R*10+c-'0');
//  cout<<solve(R)<<endl;cout<<solve(L-1)<<endl;
  cout<<(solve(R)-solve(L-1)+mod)%mod<<"\n";
}

K Tandem Copy

神秘题。还以为有什么高论，结果暴力跑的飞快。
首先把 T 里面相邻两个相等的字符删掉，然后如果倒数第三个等于最后一个就 pop 掉最后一个，第一个等于第三个也同理。
接下来对于 S 的每一个位置作为起点尝试匹配 T。需要注意的是，比如说 S=CABABC，T=CABABABABABABABC，那么 S 匹配完前两个 AB 以后发现不匹配了，是可以直接跳过中间连着的这一大堆 AB 的。
有一个特殊情况就是 S=AB，T=BA，这个东西特判一下就好了。
具体可以看代码。复杂度是平方的。
CPP
int id[20010],R[20010];
void solve(){
  std::string s,t;std::cin>>s>>t;
  std::string tt="";
  for(char c:t)if(tt.empty()||tt.back()!=c)tt+=c;
  int n=s.size(),cnt=tt.size();
  t=tt;
  while(cnt>=3&&t[cnt-1]==t[cnt-3])t.pop_back(),--cnt;
  while(cnt>=3&&t[0]==t[2]){rep(i,1,cnt-1)t[i-1]=t[i];--cnt;t.pop_back();}
  // std::cout<<t<<'\n';
  nrep(i,cnt-1,0){
    if(i<cnt-2&&i>0&&t[i]==t[i+2]&&t[i-1]==t[i+1])id[i]=id[i+2];
    else id[i]=i;
  }
  debug("%lld\n",cnt);
  rep(i,0,cnt-1)debug("%lld ",id[i]);
  debug("\n");
  rep(i,0,n-1)R[i]=n;
  rep(i,0,n-1){
    int flag=1,cur=0;
    rep(j,0,cnt-1){
      if(cur+i>=n){flag=-1;break;}
      if(s[cur+i]!=t[j]){
        if(j<=1||j==cnt-1||id[j-1]==j-1){flag=0;break;}
        else j=id[j-1];
      }
      else ++cur;
    }
    if(cnt==2&&s[i]==t[1]&&s[i+1]==t[0])flag=1,cur=2;
    if(flag==-1)break;
    if(!flag)continue;
    R[i]=i+cur-1;
  }
  rep(i,0,n-1)debug("%lld %lld\n",i,R[i]);
  int cur=n,ans=0;
  nrep(i,n-1,0){
    ckmin(cur,R[i]);
    ans+=n-cur;
    debug("%lld %lld\n",i,cur);
  }
  print(ans,'\n');
  // ans-=sum*(sum+1)/2;
  // print(ans,'\n');
}

L Walk Swapping

操作相当于拿着一个数然后随便挪。挪一圈相当于进行了一次循环位移。
所以可以枚举循环位移了多少次。位移完了以后一定形如两个串有一个共同前缀和一个共同后缀，中间剩的东西就形如把第一个数放到最后一位或者把最后一位放到第一位。先判断是否形如这个样子，再计算操作次数即可。
代码还没写。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...