模拟赛、闲话

咱又去翻找头图了

膜你赛

rand 找题了。

多米诺骨牌覆盖

题目

有一个 $m$ 行 $n$ 列的矩形方格棋盘，用 $1 \times 2$ 的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法。

思路

非常典的题目，不难设计状压。

但其实这题还可以轮廓线哈哈，这是 szlxq 告诉我的，因为你轮廓线上放的话和当前竖放的可以合并，不放和被竖放的可以合并。

这是直接状压

cpp

signed main(){
    int m,n;cin>>n>>m;
    int S=1<<n;
    rep(s,0,S-1){
        int res=0;
        bool flag=1;
        rep(j,0,n-1){
            if((s>>j)&1){
                if(res&1){
                    flag=0;
                    break;
                }
                res=0;
            }else res++;
        }
        if(res){
            if(res&1){
                flag=0;
            }
        }
        v[s]=flag;
    }
    dp[0][0]=1;
    rep(i,1,m){
        rep(s1,0,S-1){
            if(!dp[i-1][s1])continue;
            rep(s2,0,S-1){
                if(s1&s2)continue;
                int fvv=s1|s2;
                if(!v[fvv])continue;
                (dp[i][s2]+=dp[i-1][s1])%=mod;
            }
        }
    }
    cout<<dp[m][0]<<'\n';
    return 0;
}

Jeff and Removing Periods

题目

给定一个序列，每次询问一个区间，一次操作可以删去区间内下标呈等差数列且数值相同的元素，对剩下的元素你可以任意排列。

思路

显然相同的数值排序在一起是最优秀的，所以答案就是 区间内不同的数的个数 + [是否存在一个数初始下标呈等差数列]。

对于后半部分，你先预处理出当前下标能保持下标呈等差数列到的最做位置，设其为 $f_{i}$ ，再设当前数的前一个相同的数的下标为 $p r e_{i}$ ，若 $p r e_{f_{i}} \geq l$ 则显然当前数不合法。

然后就可以莫队直接做了。

在线的话就类似 HH 的项链 再上可持久化就好了。

这是在线

cpp

int cg(int p,int l,int r,int w,int val){
    int dir=++tot;T[dir]=T[p];
    if(l==r){
        T[dir].val=val;
        return dir;
    }
    int mid=l+r>>1;
    if(w<=mid)T[dir].ls=cg(T[dir].ls,l,mid,w,val);
    else T[dir].rs=cg(T[dir].rs,mid+1,r,w,val);
    T[dir].val=T[T[dir].ls].val+T[T[dir].rs].val;
    return dir;
}
int qry(int p,int l,int r,int L,int R){
    int res=0,mid=l+r>>1;
    if(L<=l&&r<=R){
        return T[p].val;
    }
    if(L<=mid)res+=qry(T[p].ls,l,mid,L,R);
    if(mid<R)res+=qry(T[p].rs,mid+1,r,L,R);
    return res;
}
struct SGT{
    int ls,rs,minn;
    SGT(){
        minn=0x7fffffff;
    }
}P[N*65];
int thoth;
int change(int p,int l,int r,int w,int val){
    int dir=++thoth;P[dir]=P[p];
    if(l==r){
        P[dir].minn=val;
        return dir;
    }
    int mid=l+r>>1;
    if(w<=mid)P[dir].ls=change(P[dir].ls,l,mid,w,val);
    else P[dir].rs=change(P[dir].rs,mid+1,r,w,val);
    P[dir].minn=min(P[P[dir].ls].minn,P[P[dir].rs].minn);
    return dir;
}
int query(int p,int l,int r,int L,int R){
    int res=0x7fffffff,mid=l+r>>1;
    if(L<=l&&r<=R)return P[p].minn;
    if(L<=mid)res=min(res,query(P[p].ls,l,mid,L,R));
    if(mid<R)res=min(res,query(P[p].rs,mid+1,r,L,R));
    return res;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    int m;cin>>m;
    int tt;cin>>tt;
    rep(i,1,n)cin>>a[i];
    rep(i,0,100000)t[i]=-1;
    rep(i,1,n){
        pre[i]=t[a[i]];
        t[a[i]]=i;
        if(pre[i]==-1){
            sl[i]=i;
        }else if(pre[pre[i]]==-1||(i-pre[i]!=pre[i]-pre[pre[i]])){
            sl[i]=pre[i];
        }else{
            sl[i]=sl[pre[i]];
        }
    }
    rep(i,0,100000)t[i]=0x7fffffff;
    drep(i,n,1){
        suf[i]=t[a[i]];
        t[a[i]]=i;
        if(suf[i]==0x7fffffff){
            sr[i]=i;
        }else if(suf[suf[i]]==0x7fffffff||(i-suf[i]!=suf[i]-suf[suf[i]])){
            sr[i]=suf[i];
        }else{
            sr[i]=sr[suf[i]];
        }
    }
    rep(i,0,100000)t[i]=0;
    rep(i,1,n){
        rt[i]=cg(rt[i-1],0,n,t[a[i]],0);
        rt[i]=cg(rt[i],0,n,i,1);
        root[i]=change(root[i-1],0,n,t[a[i]],0x7fffffff);
        root[i]=change(root[i],0,n,i,pre[sl[i]]); // *
        t[a[i]]=i;
    }
    int lastans=0;
    while(m--){
        int l,r;cin>>l>>r;
        l=(l^(lastans*tt))%n+1;
        r=(r^(lastans*tt))%n+1;
        if(l>r)swap(l,r);
        int ans=qry(rt[r],0,n,l,r);
        if(query(root[r],0,n,l,r)<l)cout<<(lastans=ans)<<'\n';
        else cout<<(lastans=ans+1)<<'\n';

    }
    return 0;
}

MegaFactorial

好题待补

Intervals

题目

给定 $n$ 个闭区间 $[a_{i}, b_{i}]$ 和 $n$ 个整数 $c_{i}$ 。你需要构造一个整数集合 $Z$ ，使得对于任意 $i \in [1, n]$ ， $Z$ 中满足 $a_{i} \leq x \leq b_{i}$ 的整数 $x$ 不少于 $c_{i}$ 个，求这样的整数集合 $Z$ 最少包含多少个数。

简而言之就是，从 $0 \sim 5 \times 10^{4}$ 中选出尽量少的整数，使每个区间 $[a_{i}, b_{i}]$ 内都有至少 $c_{i}$ 个数被选出。

思路

其实出题人想让我们设计差分约束系统，但是，其实还是比较麻烦的，你要在前缀和上搞。

其实先做右端点排序贪心，你维护一棵线段树，在线段树上二分先进右子树，设计一下 $t a g$ 怎么打就好了，还是比较好写的。

cpp

struct Query{
    int a,b,c;
    bool operator<(const Query X)const{
        if(b==X.b)return a<X.a;
        return b<X.b;
    }
}q[N];
int val[N<<2],tag[N<<2];
int red(int p,int l,int r,int nd){
    int ad=val[p];
    int lft=nd-(r-l+1-val[p]);
    val[p]=min(val[p]+nd,r-l+1);
    ad=val[p]-ad;
    tag[p]+=ad;
    return max(0,lft);
}
void pushdown(int p,int l,int r){
    if(tag[p]){
        int mid=l+r>>1;
        int lftr=red(rs,mid+1,r,tag[p]);
        red(ls,l,mid,lftr);
        tag[p]=0;
    }
}
int cg(int p,int l,int r,int L,int R,int nd){
    if(nd==0)return 0;
    if(L<=l&&r<=R){
        return red(p,l,r,nd);
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    int res=nd;
    if(mid<R)res=cg(rs,mid+1,r,L,R,res);
    if(L<=mid)res=cg(ls,l,mid,L,R,res);
    val[p]=val[ls]+val[rs];
    return res;
}
int qry(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return val[p];
    pushdown(p,l,r);
    int mid=l+r>>1;
    int res=0;
    if(L<=mid)res+=qry(ls,l,mid,L,R);
    if(mid<R)res+=qry(rs,mid+1,r,L,R);
    return res;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    rep(i,1,n){
        cin>>q[i].a>>q[i].b>>q[i].c;
    }
    sort(q+1,q+n+1);
    rep(i,1,n){
        int tmp=qry(1,0,5e4,q[i].a,q[i].b);
        if(tmp>=q[i].c)continue;
        tmp=q[i].c-tmp;
        cg(1,0,5e4,q[i].a,q[i].b,tmp);
    }
    cout<<val[1]<<'\n';
    return 0;
}

刻痕

题目

给你一个 $n \times m$ 的网格，要你选定两个不同的 $1 \times k$ 或 $k \times 1$ 的矩形且不相交，给定能选的和不能选的网格，求方案数。

思路

正难则反算相交的。

一横一竖的就是类似种花。然后对于同向的你去考虑钦定枚举相交的左（上）端点，你对于左（上）边在枚举点左（上）边长度为 $0$ 的时候特殊考虑，否则不会重。

cpp

rep(i,1,n) rep(j,1,m) cin>>c[i][j];
rep(i,1,n) rep(j,1,m) if(c[i][j]=='1')u[i][j]=u[i-1][j]+1,l[i][j]=l[i][j-1]+1;
drep(i,n,1)drep(j,m,1)if(c[i][j]=='1')d[i][j]=d[i+1][j]+1,r[i][j]=r[i][j+1]+1;
__int128_t res=0,ans=0;
__int128_t wtfn4=0;
memset(vis,0,sizeof vis);
res=0,cnt1=0;
rep(i,1,n){
    rep(j,1,m){
        if(c[i][j]=='1'){
            res+=(__int128_t)((l[i][j]-1)*r[i][j]*(r[i][j]-1))*2+(__int128_t)(r[i][j]-1)*(r[i][j]-1);
            vis[i][j]=1;
            if(!vis[i][j-1]){
                len1[++cnt1]=l[i][j]+r[i][j]-1;
                wtfn4+=(__int128_t)len1[cnt1]*(len1[cnt1]-1)/2;
            }
        }
    }
}
rep(i,1,cnt1){
    ans+=(__int128_t)(len1[i]*(len1[i]-1)/2)*wtfn4;
}
ans-=res;
memset(vis,0,sizeof vis);
res=0,cnt2=0;
wtfn4=0;
rep(i,1,n){
    rep(j,1,m){
        if(c[i][j]=='1'){
            res+=(__int128_t)((u[i][j]-1)*d[i][j]*(d[i][j]-1))*2+(__int128_t)(d[i][j]-1)*(d[i][j]-1);
            vis[i][j]=1;
            if(!vis[i-1][j]){
                len2[++cnt2]=u[i][j]+d[i][j]-1;
                wtfn4+=(__int128_t)len2[cnt2]*(len2[cnt2]-1)/2;
            }
        }
    }
}
rep(i,1,cnt2){
    ans+=(__int128_t)(len2[i]*(len2[i]-1)/2)*wtfn4;
}
ans-=res;
res=0;
__int128_t res1=0,res2=0;
rep(i,1,cnt1)res1+=(__int128_t)len1[i]*(len1[i]-1)/2+len1[i];
rep(i,1,cnt2)res2+=(__int128_t)len2[i]*(len2[i]-1)/2+len2[i];
rep(i,1,n){
    rep(j,1,m){
        if(c[i][j]=='1'){
            __int128_t tmp1=(__int128_t)l[i][j]*r[i][j],tmp2=(__int128_t)u[i][j]*d[i][j];
            res+=tmp1*tmp2;
        }
    }
}
int cnt=0;
rep(i,1,n){
    rep(j,1,m){
        if(c[i][j]=='1'){
            ++cnt;
        }
    }
}
ans+=(res1*res2*2-res*2-1ll*cnt*(cnt-1));
write(ans);
puts("");

闲话

whk

困难困难困难困难困难困难困难困难困难困难困难困难

坐牢坐牢坐牢坐牢坐牢坐牢坐牢坐牢坐牢坐牢坐牢坐牢

音乐

周次

额额但是周次真的很好看。二刷到 232 话了，web 版最新是 391 话。（二刷就是在读新一话的时候容易把二刷时候的心情带入哈哈）。实体书出了 7 卷,但我现在还只有 3 卷。

就这样吧。

模拟赛、闲话https://blog.acerkaio.top/posts/2025/syproblem

作者Shawn

发布于1天前

更新于1天前

许可协议 CC BY-NC-SA 4.0

署名-非商业性使用-相同方式共享 4.0 国际

题解模拟赛闲话

反馈与投诉

膜你赛 ​

多米诺骨牌覆盖 ​

题目 ​

思路 ​

Jeff and Removing Periods ​

题目 ​

思路 ​

MegaFactorial ​

Intervals ​

题目 ​

思路 ​

刻痕 ​

题目 ​

思路 ​

闲话 ​

whk ​

音乐 ​

周次 ​

膜你赛

多米诺骨牌覆盖

题目

思路

Jeff and Removing Periods

题目

思路

MegaFactorial

Intervals

题目

思路

刻痕

题目

思路

闲话

whk

音乐

周次