JZP系列[未完待续]

目标JZPKIL/STR/FAR/LCM/TAB/EXT/GYZ
切完这些我就去版切sgu!
@Leo Jacob告诉我spoj上还有JZPSTA/LIT/LIT2/CIR/FOR

JZPLCM

7k+的题解讲得很详细了
我怕拆出来的数太多,就把每个数的2/3/5/7都消掉,用线段树维护区间最大值,然后再按题解的方法搞的TAT……这样一个数最多拆出8个数……
写的时候被各种奇怪错误屠……冬天手冷了的缘故?

update

感谢maoxiao大神指出我原本代码的一个错误……
gyz居然也会有数据弱的情况出现= =

JZPLCM.cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 200000
#define MN 2000000
int prime[N],pnum,n,P[N],ans[N],q;
int ql,qr,start[N],end[N],a[N],A[MN],w[MN],tot,mi[N][4];
struct node{
    node*c[2];
    int w[4];
}Ss[N*2],*root,*stp=Ss;
#define mid ((l+r)>>1)
node* build(int l,int r)
{
    node*x=stp++;
    if(l==r)
        copy(mi[l],mi[l]+4,x->w);
    else{
        x->c[0]=build(l,mid);
        x->c[1]=build(mid+1,r);
        for(int i=0;i<4;i++)
            x->w[i]=max(x->c[0]->w[i],x->c[1]->w[i]);   
    }
    return x;
}node query(node*o,int l,int r)
{
    if(l>=ql&&r<=qr)
        return *o;
    else if(l>qr||r<ql)
    {
        node h;
        for(int i=0;i<4;i++)h.w[i]=0;
        return h;
    }
    node x,y=query(o->c[0],l,mid),z=query(o->c[1],mid+1,r);
    x.c[0]=&y;x.c[1]=&z;
    for(int i=0;i<4;i++)
        x.w[i]=max(x.c[0]->w[i],x.c[1]->w[i]);
    return x;
}
const int MOD=7+(int)1e9;
int mypow(int x,int y)
{
    int res=1;
    for(;y;y>>=1)
    {
        if((y&1)==1)res=(long long)res*x%MOD;
        x=(long long)x*x%MOD;
    }return res;
}struct Query{
    int l,r,id;
    bool operator<(const Query&rhs)const{
        return l<rhs.l;
    }
}Q[N];
int last[MN];
#include<map>
map<int,int>S;
int inv(int x)
{
    return mypow(x,MOD-2);
}
int BIT[MN];
void modify(int x,int w)
{
    for(;x<=tot;x+=(x&(-x)))
        BIT[x]=(long long)BIT[x]*w%MOD;
}int Pi(int x)
{
    int an=1;
    for(;x;x-=(x&(-x)))
        an=(long long)an*BIT[x]%MOD;
    return an;
}
void solve()
{
    sort(Q+1,Q+1+q);
    if(!tot)return;
    for(int i=tot;i>=1;i--)
    {
        if(S.find(A[i])==S.end())
            last[i]=tot+1;
        else last[i]=S[A[i]];
        S[A[i]]=i;
    }
    int now=1;
    fill(BIT,BIT+tot+1,1);
    for(map<int,int>::iterator it=S.begin();it!=S.end();it++)
        modify(it->second,w[it->second]);
    for(int i=1;i<=q;)
    {
        if(Q[i].l==now){
            for(;Q[i].l==now&&i<=q;i++)
                if(Q[i].r>=Q[i].l)
                    ans[Q[i].id]=(long long)ans[Q[i].id]*Pi(Q[i].r)%MOD;
        }
        if(last[now]<=tot)
            modify(last[now],w[now]);
        modify(now,inv(w[now]));
        now++;
    }
}
int main(){
    //freopen("JZPLCM.in","r",stdin);

    //freopen("JZPLCM.out","w",stdout);

    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=2;i<N;i++)
        if(!P[i]){
            prime[pnum++]=i;
            for(int j=i+i;j<N;j+=i)
                P[j]=1;
        }
    for(int i=1;i<=n;i++)
    {
        start[i]=tot+1;
        while(a[i]%2==0)mi[i][0]++,a[i]/=2;
        while(a[i]%3==0)mi[i][1]++,a[i]/=3;
        while(a[i]%5==0)mi[i][2]++,a[i]/=5;
        while(a[i]%7==0)mi[i][3]++,a[i]/=7;
        for(int j=0;j<pnum;j++)
            if(prime[j]*prime[j]>a[i])break;
            else if(a[i]%prime[j]==0)
            {
                int now=1;
                while(a[i]%prime[j]==0)
                {
                    now*=prime[j];
                    tot++;
                    A[tot]=now;
                    w[tot]=prime[j];
                    a[i]/=prime[j];
                }
            }
        if(a[i]>1)
            tot++,A[tot]=a[i],w[tot]=a[i];
        end[i]=tot;
    }
    root=build(1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&ql,&qr);
        Q[i].id=i;
        node o=query(root,1,n);
        ans[i]=1;
        for(int j=0;j<4;j++)
            ans[i]=(long long)ans[i]*mypow(prime[j],o.w[j])%MOD;
        Q[i].l=start[ql],Q[i].r=end[qr];
    }solve();
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
}

JZPFAR

不会证明复杂度…… 既然7k+说是那么就是吧……
写了个指针版本的kd tree= =本来以为速度很颓……结果似乎还能看?
群众喜闻乐见的0分风格分
fenggefen.bmp

JZPFAR.cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
bool flag;
#define N 400010
struct point
{
    int x,y,id;
    bool operator<(const point&rhs)const{
        if(flag)return x<rhs.x;
        else return y<rhs.y;
    }
}P[N];
struct heap{
    long long Dis;
    int id;
    bool operator<(const heap&rhs)const{
        return Dis>rhs.Dis||(Dis==rhs.Dis&&id<rhs.id);
    }
};
#define mid ((l+r)>>1)
struct Node{
    point P;
    int a,b,c,d;
    Node*ch[2];
    void maintain()
    {
        a=c=P.x;b=d=P.y;
        if(ch[0])
        {
            a=min(ch[0]->a,a);c=max(ch[0]->c,c);
            b=min(ch[0]->b,b);d=max(ch[0]->d,d);
        }if(ch[1])
        {
            a=min(ch[1]->a,a);c=max(ch[1]->c,c);
            b=min(ch[1]->b,b);d=max(ch[1]->d,d);
        }
    }long long calc(point tmp)
    {
        int z=max(abs(tmp.x-a),abs(tmp.x-c)),h=max(abs(tmp.y-b),abs(tmp.y-d));
        return (long long)z*z+(long long)h*h;
    }
}SS[N],*stp=SS,*root;
Node*build(int l,int r,bool now)
{
    if(l>r)return NULL;
    Node*o=stp++;
    flag=now;
    nth_element(P+l,P+mid,P+r+1);
    o->P=P[mid];
    o->ch[0]=build(l,mid-1,now^1);
    o->ch[1]=build(mid+1,r,now^1);
    o->maintain();
    return o;
}
int n,m,q;
priority_queue<heap>Q;
long long len(point x,point y)
{
    return (long long)(x.x-y.x)*(x.x-y.x)+(long long)(y.y-x.y)*(y.y-x.y);
}
void query(Node*o,point&P,bool now)
{
    if(!o)return;
    heap temp=(heap){len(P,o->P),o->P.id};
    if(Q.size()<m)Q.push(temp);
    else if(temp<Q.top())Q.pop(),Q.push(temp);
    flag=now;
    Node*left=o->ch[0],*right=o->ch[1];
    if(P<o->P)swap(left,right);
    if(left&&(Q.size()<m||left->calc(P)>=Q.top().Dis))
        query(left,P,now^1);
    if(right&&(Q.size()<m||right->calc(P)>=Q.top().Dis))
        query(right,P,now^1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&P[i].x,&P[i].y),P[i].id=i;
    root=build(1,n,0);
    scanf("%d",&q);
    while(q--)
    {
        point Z;
        scanf("%d%d%d",&Z.x,&Z.y,&m);
        while(!Q.empty())Q.pop();
        query(root,Z,0);
        printf("%d\n",Q.top().id);
    }
}

JZPEXT

做这题请先把cf这题过掉……cf55D
然后这题就是加强版+卡常数版+卡代码长度版……
为什么傻逼的总是我!!!
为什么!!

JZPEXT.cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
int n=0,t,h[3000],D[20],len;LL f[19][252][55],l,r;short M[253][10],mu[253][10],i,j,lc[3000][10];
LL F(short i,short m,short L,bool e){if(i==-1)return !(m%L);if(!e&&~f[i][m][h[L]])return f[i][m][h[L]];int E=e?D[i]:9;LL r=0;for(int d=0;d<=E;d++)r+=F(i-1,i==0?mu[m][d]:M[m][d],lc[L][d],e&&d==E);return e?r:(f[i][m][h[L]]=r);}inline LL s(LL x){len=0;while(x)D[len++]=x%10,x/=10;return F(len-1,0,1,1);}
inline LL read(){LL tmp=0;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar());for(;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';return tmp;}
void print(LL x){putchar(x>=10?(print(x/10),x%10+'0'):x+'0');}
int main(){memset(f,-1,sizeof f);for(i=0;i<=252;i++)for(j=0;j<10;j++)mu[i][j]=i*10+j,M[i][j]=mu[i][j]%252;for(i=0;i<=2520;i++){if(i>0&&2520%i==0)h[i]=n++;for(j=0;j<10;j++)lc[i][j]=j?i*j/__gcd(i,j):i;}t=read();while(t--)l=read(),r=read(),print(s(r)-s(l-1)),puts("");}

其实我交上去的代码还是有一点缩进的……但是为了美观这里一点缩进都没有了

JZPGYZ

题目描述点赞233
总之这题是在SAM,ACM不普及时候出的……现在看来挺水的……
这题离线后……对于第i个模板搞出它包含哪些询问,这个做法显然
我用acm水过去的……

JZPGYZ.cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char s[210005],st[366666];
int n,m,tot=0,h=0,t=1;
struct node{
    int mk,cnt;
    node*f,*c[128];
}RR[400000],*stp=RR,*root,*rd[360000],*Q[366666];
int main(){
    root=stp++;root->f=root;
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=n;i++)
        while((s[tot++]=getchar())!='\n');
    for(int j=1;j<=m;j++)
    {
        scanf("%s",st);
        int l=strlen(st);
        node*now=root;
        for(int i=0;i<l;i++)
            if(!now->c[st[i]])
                now->c[st[i]]=stp++,now=now->c[st[i]];
            else now=now->c[st[i]];
        rd[j]=now;
    }
    Q[h]=root;
    for(;h<t;)
    {
        node*now=Q[h++];
        for(int i=0;i<128;i++)
            if(now->c[i])
            {
                node *x=now->f;
                while(x!=root&&!x->c[i])x=x->f;
                if(x->c[i]&&x->c[i]!=now->c[i])
                    now->c[i]->f=x->c[i];
                else now->c[i]->f=root;
                Q[t++]=now->c[i];
            }
    }tot=0;
    for(int i=1;i<=n;i++)
    {
        node*now=root;
        while(s[tot]!='\n')
        {
            while(now!=root&&!now->c[s[tot]])now=now->f;
            if(now->c[s[tot]])now=now->c[s[tot]];
            for(node*x=now;x!=root;x=x->f)
                if(x->mk!=i)
                    x->mk=i,x->cnt++;
            tot++;
        }tot++;
    }for(int i=1;i<=m;i++)
        printf("%d\n",rd[i]->cnt);
}

JZPCIR

打表找规律
发现递推式后上矩阵乘法即可
你问我规律?oeis召唤术
推导的话……太神不会
spoj真是一个磨练人意志的题库……
我的矩阵乘法取模次数太多导致tle了好久……
代码风格很丑……因为懒得写个struct matrix了……

JZPCIR.cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MOD=9+(int)1e9;
int a[7][7],ans[9],an[7][7],c[7][7];
typedef long long LL;
int solve(long long n)
{
    if(n<=8)
        return ans[n];
    memset(a,0,sizeof(a));
    n-=8;
    a[1][1]=a[1][2]=1;
    a[1][5]=a[1][6]=-1;
    for(int i=2;i<=5;i++)
        a[i][i-1]=1;
    a[6][6]=1;
    memset(an,0,sizeof(an));
    for(int i=1;i<=6;i++)
        an[i][i]=1;
    for(;n;n>>=1)
    {
        if(n&1)
        {
            for(int i=1;i<=6;i++)
                for(int j=1;j<=6;j++)
                    for(int k=1;k<=6;k++)
                        c[i][j]=(c[i][j]+(LL)an[i][k]*a[k][j])%MOD;
            for(int i=1;i<=6;i++)
                for(int j=1;j<=6;j++)
                    an[i][j]=c[i][j],c[i][j]=0;
        }
        for(int i=1;i<=6;i++)
            for(int j=1;j<=6;j++)
                for(int k=1;k<=6;k++)
                    c[i][j]=(c[i][j]+(LL)a[i][k]*a[k][j])%MOD;
        for(int i=1;i<=6;i++)
            for(int j=1;j<=6;j++)
                a[i][j]=c[i][j],c[i][j]=0;
    }int tmp=0;
    for(int i=1;i<=5;i++)
        tmp+=(LL)ans[9-i]*an[1][i]%MOD,tmp%=MOD;
    tmp+=2*an[1][6]%MOD;tmp%=MOD;
    return (tmp+MOD)%MOD;
}
long long n;
int T;
int main(){
    ans[1]=2;ans[2]=2;
    ans[3]=8;ans[4]=9;
    ans[5]=12;ans[6]=16;
    ans[7]=23;ans[8]=29;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        printf("%d\n",solve(n));
    }
}

JZPFOR

标题里面出现了Formula 这个单词……有没有想到连通性状压dp?(逻辑呢)
因为……保证x坐标相同的点最多有8个……所以按x坐标排序……
做连通性状压dp就可以了……

代码不想写(:з」∠)

JZPKIL

数论推导=-=其实也没有啥亮点……以前初学mobius反演的时候觉得很神的东西现在看来也就这样……
知道伯努利数之后就直接上吧……
7k+的题解不知道为啥扯了好久奇怪的东西……好像是在介绍伯努利数……没仔细看
总之推导也就五六行……算不上复杂……(我跳步比较多?)
唯一的亮点就是卡常数吧……
所幸没有被卡得太厉害……
在bzoj上以40s水过去了TAT
代码就不发了

JZPSTR

块状链表,每个块弄个sam,然后处理出hash,跨块的用hash乱搞,不跨的用sam乱搞就可以了……
看到标程的长度……没敢去写……


暂时就到这里吧……讨厌卡常数的题目……做不下去了……以后再把剩下的弄掉……

Comments

comments powered by Disqus