P6360 [CEOI2018] Lottery 题解

· · 题解

P6360 [CEOI2018] Lottery 题解

集训时讲了这道题，来写一下题解当笔记。

思路

注意到这些区间有一个这样的性质：设 x,y 对应的距离为 f(x,y)，假设 f(x,y) 已知，则我们可以 O(1) 计算得到 f(x+1,y+1)，有 f(x+1,y+1)=f(x,y)-[a_x \not=a_y]+[a_{x+l}\not=a_{y+l}]。

于是我们有这样的策略，先暴力算出所有的 f(1,j)，时间复杂度 O(n^2)，然后推出所有的 f(x,y) 时间复杂度为 O(n^2)，最后统计的时候开数组记得把询问离散化，空间复杂度为 O(qn)，时间复杂度 O(n^2)。

代码

代码很短，重在思考（比赛时没有想到 10^4 能用 O(n^2) 屮过去）。

#include <iostream>
#include <algorithm>
#define ll int
using namespace std;
const ll N=10002;
const ll Q=102;
inline ll read(){
  register ll f=1,x=0;
  register char c=getchar();
  while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
  return x*f;
}
ll n,l,A[N],q,ans[N][Q];
ll chg[N],ask[N],lis[N];
int main(){
    n=read(),l=read();
    for(ll i=1;i<=n;i++) A[i]=read();
    q=read();
    for(ll i=1;i<=q;i++){
        ask[i]=read();
        lis[i]=ask[i];
    }
    sort(lis+1,lis+1+q);
    ll nq=unique(lis+1,lis+1+q)-lis-1;
    ll tp=1;
    for(ll i=1;i<=n;i++){
        while(tp<=nq&&i>lis[tp]) tp++;
        chg[i]=tp;
    }
    for(ll i=2;i+l-1<=n;i++){
        ll d=0;
        for(ll j=0;j<l;j++) if(A[1+j]!=A[i+j]) d++;
        ans[1][chg[d]]++,ans[i][chg[d]]++;
        for(ll j=1;j+i<=n-l+1;j++){
            d=d-(A[j]!=A[i+j-1])+(A[j+l]!=A[i+j-1+l]);
            ans[1+j][chg[d]]++,ans[i+j][chg[d]]++;
        }
    }
    for(ll i=1;i<=n-l+1;i++)
        for(ll j=1;j<=nq;j++) ans[i][j]+=ans[i][j-1];
    for(ll i=1;i<=q;i++){
        for(ll j=1;j<=n-l+1;j++) printf("%d ",ans[j][chg[ask[i]]]);
        printf("\n");
    }
    return 0;
}