noip模拟50[丧]

noip模拟50 solutions

队奶奶暴力打满(即使是暴力也比我的暴力高明),拿到rank1,220pts,而我只有可怜的60pts

好丧啊,连续两次都在中游,考场上脑子就像浆糊一样,啥也想不到

还有一个就是懒,暴力懒得打,算算复杂度,知道不可能拿到更多的分就不打有优化的暴力

可是有时候出题人就很SB,数据做的非常水,导致我想到的可以卡掉优化暴力的数据是没有的

然后稍微优化一下就可以AC,我却懒得做了。

总之我出现了一个新的问题,太懒了,以至于该拿到的分根本拿不到

所以以后要注意打暴力。。。。。

T1 第零题

仍然是暴力出奇迹的一道玄学题,不是做法玄学,而是数据玄学

我一开始认为是树剖+神奇线段树,然后想了半天如何处理边界问题

开场想暴力的时候想到了要处理向上的第一个复活的地方,但是我没有想到倍增,就差一点点

我知道一定会有一个结论来方便我处理从上向下的链

也就是题解里的神秘的观察:从上到下和从下到上是一样的

我确实是想到了,而且也尝试证明了,没有证出来,所以没有敢用

然后我想要一个一个复活点的跳,但是想了想没有啥用,因为特殊构造一定可以卡掉

最后直接弃掉了这个题,40pts就走人了。

刚才的神秘观察:对于一条链,如果体力都是满的从两边开始走,那么复活的次数是一样的

这个在沈队爷的提醒之下,应用了调整法

我们将从s到t的路径记录下来成为一个序列,这样我们按照题目说的走一遍。

我们可以对于每一个复活区间删掉左端点,那么区间就会一点一点的向后平移

这样复活的次数是一定的,所以我们就可以以lca为中心,两侧的向两侧移动,让中间空出来

这样我们就可以直接从s和t开始向上倍增,最后看看剩下的那一段是否大于k,大于的话就+1

AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=2e5+5;
int n,k,q;
int to[N*2],nxt[N*2],c[N*2],head[N],rp;
void add_edg(int x,int y,int z){
    to[++rp]=y;
    c[rp]=z;
    nxt[rp]=head[x];
    head[x]=rp;
}
int siz[N],son[N],dep[N],fa[N],top[N];
int dfn[N],idf[N],cnt;
int sum[N],val[N];
void dfs_fi(int x){
    siz[x]=1;son[x]=0;
    for(re i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa[x])continue;
        dep[y]=dep[x]+1;
        fa[y]=x;
        val[y]=c[i];
        dfs_fi(y);
        siz[x]+=siz[y];
        if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
    }
}
int st[N][21],ji[N],cj;
int find(int x){
    int l=0,r=x-1,mid;
    while(l<r){
        mid=l+r+1>>1;
        if(sum[ji[x]]-sum[ji[mid]]<k)r=mid-1;
        else l=mid;
    }
    return ji[l];
}
void dfs_se(int x,int f){
    top[x]=f;dfn[x]=++cnt;idf[cnt]=x;
    cj++;ji[cj]=x;
    sum[x]=sum[ji[cj-1]]+val[x];
    st[x][0]=find(cj);
    for(re i=1;i<=20;i++)st[x][i]=st[st[x][i-1]][i-1];
    if(son[x])dfs_se(son[x],f);
    for(re i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs_se(y,y);
    }
    cj--;
}
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(re i=1;i<n;i++){
        int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
        add_edg(x,y,z);add_edg(y,x,z);
    }
    dep[0]=0;dep[1]=1;
    dfs_fi(1);dfs_se(1,1);
    scanf("%lld",&q);
    while(q--){
        int x,y,ans=0;
        scanf("%lld%lld",&x,&y);
        int lca=LCA(x,y);
        //cout<<lca<<endl;
        for(re i=20;i>=0;i--){
            if(dep[st[x][i]]>=dep[lca])x=st[x][i],ans+=pow(2,i);
            if(dep[st[y][i]]>=dep[lca])y=st[y][i],ans+=pow(2,i);
        }
        if(sum[x]-sum[lca]+sum[y]-sum[lca]>=k)ans++;
        printf("%lld\n",ans);
    }
}

T2 第负一题

这个题是真的难,我考场上一直在枚举左端点,然后找到不同起点的dp数组的关系

甚至还想用矩阵快速幂直接找答案,后来发现好像这个矩阵并不符合乘法分配律

所以我又弃掉了这个题,然而此时已经过去了两个半小时。。。。

正解是分治,就是通过分治跨越当前分治中心的贡献

对题解进行阐述,官方的确实说的不是人话。。。。

设f[i][1/0]表示,在分治中心(就是mid)的左侧走到的i节点的最大值(就是i~mid这个区间)0表示不选mid,1就是选mid

设g[i][1/0]表示,右侧走到i节点的最大值(就是mid+1~r这个区间),0/1意义同上

这时候就明朗了,我们的答案就是要求跨过中心的所有区间的和。

也就是左右两侧任选节点求和,答案就是

\[\displaystyle\sum^{mid}_{i=l}\sum^{r}_{j=mid+1}max(f[i][0]+g[j][1],f[i][1]+g[j][0],f[i][0]+g[j][0]) \]

你会发现后面的式子好麻烦,所以我们直接换掉它,

\(cf[i]=max(f[i][1]-f[i][0],0),cg[i]=max(g[i][1]-g[i][0],0)\)

这样的话,上面的就可以化简成

\[\displaystyle\sum^{mid}_{i=l}\sum^{r}_{j=mid+1}(f[i][0]+g[j][0]+max(cf[i],cg[j])) \]

那就好说了,拆开来看,前面的两项可以直接\(\mathcal{O(n)}\)

后面的max可以直接对cf,cg进行排序,直接单调指针扫一遍就好了

AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=2e5+5;
const int mod=998244353;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,a[N],ans;
int f[N][2],g[N][2];
int cf[N],cg[N];
int dp[N][2];
void get(int l,int r){
    if(l==r){
        ans=(ans+a[l])%mod;
        //cout<<l<<" "<<ans<<endl;
        return ;
    }
    int mid=l+r>>1;
    get(l,mid);get(mid+1,r);
    for(re i=l;i<=r;i++)dp[i][0]=dp[i][1]=0;
    dp[mid][0]=0;dp[mid][1]=-inf;f[mid][0]=0;
    for(re i=mid-1;i>=l;i--)dp[i][0]=max(dp[i+1][0],dp[i+1][1]),dp[i][1]=dp[i+1][0]+a[i],f[i][0]=max(dp[i][0],dp[i][1]);
    dp[mid+1][0]=0;dp[mid][1]=-inf;g[mid+1][0]=0;
    for(re i=mid+2;i<=r;i++)dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+a[i],g[i][0]=max(dp[i][0],dp[i][1]);
    for(re i=l;i<=r;i++)dp[i][0]=dp[i][1]=0;
    dp[mid][0]=-inf;dp[mid][1]=a[mid];f[mid][1]=a[mid];
    for(re i=mid-1;i>=l;i--)dp[i][0]=max(dp[i+1][0],dp[i+1][1]),dp[i][1]=dp[i+1][0]+a[i],f[i][1]=max(dp[i][0],dp[i][1]);
    dp[mid+1][0]=-inf;dp[mid+1][1]=a[mid+1];g[mid+1][1]=a[mid+1];
    for(re i=mid+2;i<=r;i++)dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+a[i],g[i][1]=max(dp[i][0],dp[i][1]);
    for(re i=l;i<=mid;i++)cf[i]=max(f[i][1]-f[i][0],0ll),ans=(ans+f[i][0]*(r-mid))%mod;
    for(re i=mid+1;i<=r;i++)cg[i]=max(g[i][1]-g[i][0],0ll),ans=(ans+g[i][0]*(mid-l+1))%mod;
    sort(cf+l,cf+mid+1);sort(cg+mid+1,cg+r+1);
    int il=l,ir=mid;
    while(il<=mid){
        while(cg[ir+1]<=cf[il]&&ir<r)ir++,ans=(ans+cg[ir]*(il-l))%mod;
        ans=(ans+cf[il]*(ir-mid))%mod;il++;
    }
    while(ir<r){ir++;ans=(ans+cg[ir]*(mid-l+1))%mod;}
    //cout<<ans<<endl;
    return ;
}
signed main(){
    scanf("%lld",&n);
    for(re i=1;i<=n;i++)scanf("%lld",&a[i]);
    get(1,n);
    printf("%lld",ans);
}

T3 第负二题

所以这个题我是\(\mathcal{O(n^2)}\)水过去的

就直接枚举删第几次,然后去枚举每一行怎么删

AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=5e6+5;
const int mod=998244353;
int n,L,X,Y,l[N],r[N],ql[N],qr[N];
typedef unsigned long long u64;
u64 A,B;
u64 xorshift128p(u64 &A, u64 &B) { 
    u64 T=A,S=B;
    A=S;
    T^=T<<23;
    T^=T>>17;
    T^=S^(S>>26);
    B=T;
    return T+S;
}
void gen(int n,int L,int X,int Y,u64 A,u64 B,int l[],int r[]){ 
    for(int i=1;i<=n;i++){
        l[i]=xorshift128p(A,B)%L+X;
        r[i]=xorshift128p(A,B)%L+Y;
        if(l[i]>r[i])swap(l[i],r[i]);
    }
}
int f[N],ans,nxt[N],head=1,pre[N];
int ksm(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=ret*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ret;
}
bool vis[N];
signed main(){
    scanf("%lld%lld%lld%lld%llu%llu",&n,&L,&X,&Y,&A,&B);
    gen(n,L,X,Y,A,B,l,r);
    for(re i=1;i<n;i++)nxt[i]=i+1,pre[i+1]=i;
    for(re i=1;i<=n;i++){
        if(!nxt[1])break;
        for(re j=head;j;j=nxt[j]){
            ql[j]=l[j]+1;qr[j]=r[j]-1;
            ql[j]=max(ql[j],max(l[j-1],l[j+1]));
            qr[j]=min(qr[j],min(r[j-1],r[j+1]));
            //cout<<j<<" "<<ql[j]<<" "<<qr[j]<<endl;
        }
        for(re j=head;j;j=nxt[j]){
            l[j]=ql[j],r[j]=qr[j];
            if(qr[j]<ql[j]){
                f[j]=i,vis[j]=true;
                if(j!=head)nxt[pre[j]]=nxt[j],pre[nxt[j]]=pre[j];
                else head=nxt[j];
                //cout<<j<<" "<<f[j]<<endl;
            }
        }
        //cout<<head<<endl;
    }
    for(re i=1;i<=n;i++)ans=(ans+ksm(3,i-1)*f[i]%mod)%mod;//cout<<f[i]<<endl;
    printf("%lld",ans);
}

noip模拟50[丧]

上一篇:Python网络请求库httpx详解


下一篇:百度未整理获取LG函数