#194 sequence(搜索+动态规划+主席树)

  考虑按顺序暴搜子序列。如果序列中的数两两不同,显然每次给上一个找到的子序列添上后缀最小值,即为下一个要找的子序列。如果不能再加了就回溯继续考虑后缀次小、第三小……值,直到找到k个子序列。

  有重复的数后,考虑后缀k小值只取第一次出现的位置,并在每找到一个子序列后就统计其出现次数。显然这样就能找到所有要找的子序列,因为序列末端选择位置更靠前,后面的选择更多。

  求一个序列在另一个序列里的出现次数显然可以dp,即设f[i][j]为第一个序列的i位置和第二个序列的j位置匹配的方案数。当然答案序列可能很长,dp数组可能开不下,不过注意到有ai<=30的部分分,可以猜想这个部分的答案序列长度不会很长,先考虑拿部分分。

  每找到一个序列就暴力dp即为O(n2k)。注意到dp时可以直接继承上层dfs的dp数组,于是复杂度O(nk)。这里的k一般来说并不能跑满,实际上是本质不同的答案中出现的子序列个数。但是很容易卡满,比如放99970个30,最后将1到30倒序加入序列,这样每个答案序列都是不同的,就被卡成暴力了。

  但上面这个hack数据有比较特殊的地方,即存在于答案中的数字基本上出现次数很少。注意到我们之前的dp实际上可以将做一次的复杂度优化到序列最后一个数的出现次数(*log)。并且dp时可以直接从搜到的位置开始。这样上面的数据就hack不掉了。同时如果要接着hack这个做法,使dp部分运算次数增加,本质不同的答案子序列数量又会减少。这样这个做法就根本卡不掉并且跑得飞快了,复杂度O(玄学)。

  但实际上可以冷静分析一下复杂度,如果某次dp时该数dp值不为0的位置个数为x(显然因为是从搜到的位置开始的,dp值均>0),我们至少就找到了x个答案中的子序列。所以这一部分复杂度其实是O(k)(*log)的。大概就是所谓卡常卡着卡着发现复杂度对了?

  还剩下一点问题,就是上面的dp数组开不下,以及要找后缀k小值。第一个问题直接对dp数组开vector,显然空间是线性的。第二个是主席树板子题。总复杂度O(klogn)。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;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;
}
int n,m,V,a[N],root[N],nxt[N],p[N],seed,P,tot,cnt;
vector<int> pos[N],f[N];
struct data{int l,r,x,pos;
}tree[N<<6];
void ins(int &k,int l,int r,int x,int p)
{
tree[++cnt]=tree[k];k=cnt;
if (l==r) {tree[k].x=1,tree[k].pos=p;return;}
int mid=l+r>>1;
if (x<=mid) ins(tree[k].l,l,mid,x,p);
else ins(tree[k].r,mid+1,r,x,p);
tree[k].x=tree[tree[k].l].x+tree[tree[k].r].x;
}
int query(int k,int l,int r,int x)
{
if (l==r) return tree[k].pos;
int mid=l+r>>1;
if (x<=tree[tree[k].l].x) return query(tree[k].l,l,mid,x);
else return query(tree[k].r,mid+1,r,x-tree[tree[k].l].x);
}
int findnxt(int k,int x){return query(root[k+1],0,V,x);}
int findpre(int x,int k){return lower_bound(pos[x].begin(),pos[x].end(),k)-pos[x].begin()-1;}
void dfs(int k,int cur,int h)
{
int last=0;
while (tot<m&&k<n)
{
last++;int u=findnxt(k,last);
if (u>n) break;
int H=(1ll*h*seed+a[u])%P;
f[cur+1].clear();pos[cur+1].clear();
for (int i=u,cnt=0;i<=n;i=nxt[i],cnt++)
{
pos[cur+1].push_back(i);
if (i!=u) f[cur+1].push_back(f[cur+1][cnt-1]);
else f[cur+1].push_back(0);
int x=findpre(cur,i);
if (x>=0) f[cur+1][cnt]+=f[cur][x];
f[cur+1][cnt]=min(f[cur+1][cnt],m-tot);
}
int v=f[cur+1][f[cur+1].size()-1];
for (int i=1;i<=v;i++) printf("%d\n",H);
tot+=v;
dfs(u,cur+1,H);
}
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=read(),m=read(),seed=read(),P=read();
for (int i=1;i<=n;i++) V=max(V,a[i]=read());
V++;a[n+1]=V;
root[n+2]=0;
for (int i=n+1;i>=1;i--)
{
root[i]=root[i+1];
ins(root[i],0,V,a[i],i);
}
nxt[n+1]=n+1;for (int i=0;i<=V;i++) p[i]=n+1;
for (int i=n;i>=0;i--) nxt[i]=p[a[i]],p[a[i]]=i;
f[0].push_back(1);pos[0].push_back(0);
dfs(0,0,0);
return 0;
}

  

上一篇:ubuntu 设置IP,设置网关


下一篇:也谈Promise