A.

首先，后面三种是没用的。
然后，通过dp，会发现如下递推式： \(dp[i]=dp[i-2]+dp[i-4]+\sum_{k\geq 0}2*dp[i-4-2*k]\)
打表，得答案是斐波那契数的平方。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long D;
const int mod=1000000007;
int Plus(int x,int y){return (x+=y)>=mod?x-mod:x;}
void PlusEqual(int &x,int y){if((x+=y)>=mod)x-=mod;}
int mul(long long x,int y){return x*y%mod;}
struct matrix{
    int a[2][2];
    matrix(){memset(a,0,sizeof(a));}
    friend matrix operator*(const matrix &A,const matrix &B){
        matrix RET;
        for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)PlusEqual(RET.a[i][j],mul(A.a[i][k],B.a[k][j]));
        return RET;
    }
    friend matrix operator^(matrix A,D B){
        matrix RET;
        RET.a[0][0]=RET.a[1][1]=1;
        while(B){
            if(B&1)RET=RET*A;
            A=A*A;
            B>>=1;
        }
        return RET;
    }
};
int main(){
    matrix S,A,B;
    A.a[0][0]=A.a[1][0]=1;
    S.a[0][0]=S.a[0][1]=S.a[1][0]=1;
    D n;
    while(~scanf("%lld",&n)){
        if(n&1){puts("0");continue;}
        B=(S^((n>>1)-1))*A;
        printf("%d\n",mul(B.a[0][0],B.a[0][0]));
    }
    return 0;
}

B.

答案
\(=\sum \lfloor \frac{y}{a_i} \rfloor +y\%a_i\)
\(=\sum (y+\lfloor \frac{y}{a_i} \rfloor *(1-a_i))\)

80 pts

整除分块+树状数组。 \(O(\sqrt{n}\log n)\)

100 pts

考虑分块替换树状数组，做到 \(O(\sqrt{n})\) 修改， \(O(1)\) 查询。
维护一个块与块的前缀和，一个每个块内的后缀和，答案减一减就能得到。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long D;
const int maxn=100003,maxv=200003,sqmaxv=450,N=200000,sq=447;
int n,Q,a[maxn],bl[maxv];
D sum1[sqmaxv],sum2[maxv];
void build(){
    for(int i=1;i<=N;i++)bl[i]=(i-1)/sq+1;
}
void add(int pos,int k){
    for(int i=bl[pos];i<=bl[N];i++){
        sum1[i]+=k;
    }
    for(int i=(bl[pos]-1)*sq+1;i<pos;i++){
        sum2[i]+=k;
    }
}
D query(int pos){
    return sum1[bl[pos]]-sum2[pos];
}
int main(){
    scanf("%d%d",&n,&Q);
    build();
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        add(a[i],1-a[i]);
    }
    while(Q--){
        int mo,x,y;
        scanf("%d%d",&mo,&x);
        if(mo==1){
            scanf("%d",&y);
            add(a[x],a[x]-1);
            a[x]=y;
            add(y,1-y);
        }
        else{
            D ans=1ll*x*n,now,last=0;
            for(int i=1,j=1;i<=x;i=j+1){
                j=x/(x/i);
                now=query(j);
                ans+=x/i*(now-last);
                last=now;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

C.

60 pts

考虑对每行维护两个指针 \(L_i,R_i\) ，每次询问时先算出最小答案，然后找哪行哪列可以得到最小答案。

100 pts

设询问值为 \(m\) ，通过一番推导我们可以算出第 \(i\) 行的答案（的2倍）：
\(2*ans=\begin{cases} m^2+(2|i-mid|+2mid-1-2L_i)m, & L_i\text{ is better} \\ m^2+(2|i-mid|-2mid-1+2R_i)m, & R_i\text{ is better} \end{cases}\)
然后我们发现这是一个在 \(m>0\) 时单调递增的二次函数，且一次项系数越小答案越优，因此只需开一个堆维护一次项系数。
然而，对于一些区间，可能 \(L_i<m\) 或 \(n+1-R_i<m\) ，这些区间是不合法的，因此我们开一个线段树维护最值，每个叶子都是一个堆，区间查询，就没问题了。
时间复杂度 \(O(n\log k)\) 。细节较多。

Code 1

#include<bits/stdc++.h>
using namespace std;
typedef long long D;
const D maxn=300003,INF=0x3f3f3f3f3f3f3f3fll;
D n,Q,L[maxn],R[maxn],LL,RR;
bool fl[maxn];
D f(D i,D l,D r){
    if(!fl[i]){
        D m=r-l+1,mm=((m-1)>>1);
        RR=((n+1)>>1)+mm;
        LL=((n+1)>>1)-(m>>1);
        return abs(((n+1)>>1)-i)*(RR-LL+1)+mm*(mm+1)+(m&1?0:(m>>1));
    }
    if(l<1||r>n)return INF;
    LL=l,RR=r;
    return abs(((n+1)>>1)-i)*(RR-LL+1)+abs(((n+1)>>1)*(RR-LL+1)-((LL+RR)*(RR-LL+1)>>1));
}
int main(){
    scanf("%lld%lld",&Q,&n);
    while(Q--){
        D m,ans=INF,ans0=0,ans1=0;
        scanf("%lld",&m);
        for(D i=1;i<=n;i++){
            D f1=f(i,L[i]-m+1,L[i]),f2=f(i,R[i],R[i]+m-1);
            ans=min(ans,min(f1,f2));
        }
        if(ans==INF){
            puts("-1");
            continue;
        }
        for(D i=1;i<=n;i++){
            if(f(i,L[i]-m+1,L[i])==ans){
                ans0=i;
                ans1=LL;
                L[i]=LL-1;
                if(!fl[i])R[i]=RR+1;
                break;
            }
            else if(f(i,R[i],R[i]+m-1)==ans){
                ans0=i;
                ans1=LL;
                R[i]=RR+1;
                if(!fl[i])L[i]=LL-1;
                break;
            }
        }
        fl[ans0]=1;
        printf("%lld %lld %lld\n",ans0,ans1,ans1+m-1);
    }
    return 0;
}

Code 2

#include<bits/stdc++.h>
using namespace std;
typedef long long D;
const int maxn=300003,INF=0x3f3f3f3f;
const D INFll=0x3f3f3f3f3f3f3f3fll;
int n,MID,Q,L[maxn],R[maxn],q[maxn],val[maxn],num[maxn<<2];
struct comp{bool operator()(int x,int y){return val[x]!=val[y]?val[x]>val[y]:x>y;}};
priority_queue<int,vector<int>,comp> st[maxn];
void update(int i){
    if(L[i]<1&&R[i]>n)val[i]=INF;
    else val[i]=2*abs(i-MID)-1+(R[i]>n||MID-L[i]<=R[i]-MID?2*(MID-L[i]):2*(R[i]-MID));
}
int d(int i){
    return MID-L[i]<=R[i]-MID?L[i]:n+1-R[i];
}
int MIN(int x,int y){
    return val[x]!=val[y]?(val[x]<val[y]?x:y):(x<y?x:y);
}
void add(int p,int l,int r,int pos,bool isadd){
    if(l==r){
        if(isadd)st[l].push(pos);
        else st[l].pop();
        num[p]=(st[l].empty()?0:st[l].top());
        return;
    }
    int mid=(l+r)>>1;
    if(d(pos)<=mid)add(p<<1,l,mid,pos,isadd);
    else add(p<<1|1,mid+1,r,pos,isadd);
    num[p]=MIN(num[p<<1],num[p<<1|1]);
}
int query(int p,int l,int r,int seg_l,int seg_r){
    if(seg_l<=l&&r<=seg_r)return num[p];
    int mid=(l+r)>>1;
    if(seg_l<=mid&&seg_r>mid)return MIN(query(p<<1,l,mid,seg_l,seg_r),query(p<<1|1,mid+1,r,seg_l,seg_r));
    else if(seg_l<=mid)return query(p<<1,l,mid,seg_l,seg_r);
    else return query(p<<1|1,mid+1,r,seg_l,seg_r);
}
int main(){
    scanf("%d%d",&Q,&n);
    MID=(n+1)/2;
    int qq=1;
    for(int i=1;i<=n;i++)q[i]=(i&1?MID+(i>>1):MID-(i>>1));
    for(int i=0;i<=n;i++)val[i]=INF;
    while(Q--){
        int m;
        scanf("%d",&m);
        int p=query(1,1,n,m,n),pp=q[qq];
        int RR=MID+(m-1)/2,LL=RR-m+1,ans0=0,ans1=0;
        D ansp,anspp;
        if(val[p]>=INF)ansp=INFll;
        else ansp=1ll*m*m+1ll*val[p]*m;
        if(qq>n)anspp=INFll;
        else anspp=2*(1ll*abs(MID-pp)*(RR-LL+1)+1ll*((m-1)/2)*((m-1)/2+1)+(m&1?0:m/2));
        if(ansp==INFll&&anspp==INFll){puts("-1");continue;}
        if(p)add(1,1,n,p,0);
        if(anspp<ansp||(anspp==ansp&&pp<p)){
            qq++;
            ans0=pp;
            ans1=LL;
            L[pp]=LL-1;
            R[pp]=RR+1;
            update(pp);
            add(1,1,n,pp,1);
            if(p)add(1,1,n,p,1);
        }
        else{
            ans0=p;
            if(MID-L[p]<=R[p]-MID)ans1=L[p]-m+1,L[p]-=m;
            else ans1=R[p],R[p]+=m;
            update(p);
            add(1,1,n,p,1);
        }
        printf("%d %d %d\n",ans0,ans1,ans1+m-1);
    }
    return 0;
}

20191008

原文：https://www.cnblogs.com/BlogOfchc1234567890/p/11636169.html