模拟赛好题分享

亚洲卷王 AK IOI

2026-10-25 20:29:39

发布于：北京

1阅读

0回复

0点赞

RT，挑了一些近期我打的模拟赛里的好题分享一下。

难度：CSP-S（少许题目超纲）

会持续更新。

题目 1

定义 $\text{tree}(x)$ 是 $x-\text{fib}$ 树：

若 $x=0$ ，则为空树；

若 $x=1$ ，则为只有一个节点的树；

若 $x>1$ ，则为一个节点下连接两个儿子：左儿子是 $\text{tree}(x-1)$ ，右儿子是 $\text{tree}(x-2)$ 。

现在 A 和 B 在玩游戏，A 先手。每个人可以选择一个子树删除，删掉根节点的人输。

求 $\text{tree}(n)$ 里有多少个 A 的必胜点。

$1\leq n\leq 10^4$ 。

我们先考虑建出整棵树之后怎么做。删子树不好考虑，改成删子树根节点连向父亲的边，无法操作者输。考虑 SG 函数，令 $sg(u)$ 表示将以 $u$ 为根节点的子树中的边全部删除的 SG 值。

如果 $u$ 是叶子，则 $sg(u)=0$ ，代表这个点先手必输。

如果 $u$ 有且只有一个儿子 $v$ ，则有 $sg(u)=sg(v)+1$ 。按照定义，这相当于在 $v$ 这 $sg(v)$ 个石子上增加了一个石子 $v\rightarrow u$ 。

如果 $u$ 有多个儿子，按照定理， $sg(u)=\bigoplus_{v \in \operatorname{son}(u)} (sg(v)+1)$ 。其中 $+1$ 是 $v\rightarrow u$ 的边。

这可能不太容易理解，画个图：

    u                   
   / \       /            \
  o   o =   o      xor     o
 / \       / \
o   o     o  o

这样我们只能通过 $sg(1)$ 求出开始是否必胜，所以我们还得枚举第一步的决策，判断删除第一步的子树后对手是否必败。时间复杂度 $O(m^2)$ ，其中 $m$ 是树的点数。大概是 $1.618^n$ 的级别。

发现题目给出的树比较特殊，或许可以利用斐波那契的性质递推一下。设 $f_{i,j}$ 表示在 $\operatorname{tree}(i)$ 中，删除一个子树（不是根）使得 $sg(1)=j$ 的方案数。我们需要求 $f_{n,0}$ 。

为了转移，我们还需要设一个 $g_{i}$ 表示 $\operatorname{tree}(i)$ 中的 $sg(1)$ 。

那么有转移：

$f_{i,j}=f_{i-1,j\oplus (g_{i-2}+1)-1}+f_{i-2,j\oplus (g_{i-1}+1)-1} \\ g_{i}=(g_{i-1}+1)\oplus (g_{i-2}+1)$

我们会发现 $f$ 的转移过程中下标可能变成负数，这意味着，在 $sg(1)=j$ 的情况下，这个儿子不存在，也就是说我们把 $i$ 与这个儿子间的边删除了。所以遇到非法情况，我们需要让 $f_{i,j}\gets f_{i,j}+1$ 。

根据 $sg$ 的边界，有 $f,g$ 的边界：

$f_{2,0}=1 \\ g_1=0 \\ g_2=1$

发现 $sg(n)=O(n)$ ，时间复杂度 $O(n^2)$ 。

难度：紫。

Code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+4,MOD=998244353;
int n,m=1;
int f[MAXN][MAXN],g[MAXN];
int main(){
	cin>>n;
	f[2][0]=g[2]=1;
    for(int i=3;i<=n;i++){
        g[i]=g[i-1]+1^g[i-2]+1;
        m=max(g[i],m);
    }
	for(int i=3;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j^g[i-2]+1) f[i][j]=(f[i][j]+f[i-1][(j^g[i-2]+1)-1])%MOD;
			else f[i][j]=(f[i][j]+1)%MOD;
			if(j^g[i-1]+1) f[i][j]=(f[i][j]+f[i-2][(j^g[i-1]+1)-1])%MOD;
			else f[i][j]=(f[i][j]+1)%MOD;
		}
	}
	cout<<f[n][0];
    return 0;
}

题目 2

给定一个 $n\times m$ 的 $01$ 矩阵，设两点的距离为它们的欧几里得距离的平方。你需要对于每一个点 $(x,y)$ ，求出上、下、左、右（允许同行同列）的 $1$ 点中离它最近的那个的距离。不存在则定义为 $10^9$ 。

输出量较大，设 $(x,y)$ 上方的最近 $1$ 点距离为 $up_{x,y}$ ，求 $\bigoplus_{x,y} up_{x,y}$ 。另外三个同理。

$1\leq n,m\leq 4000$ 。

$O(n^4)$ 毫无意义，直接来考虑三次方做法。

四个方向本质相同，我们只讨论 $up$ 。设 $s_j$ 表示第 $j$ 列上，最靠下的 $1$ 点的位置。我们按照 $i=1,2,\dots,n$ 的顺序处理每一行，若 $a_{i,j}=1$ ，则更新 $s_j\gets 1$ 。那么 $(i,j)$ 的答案即为 $\min_{k=1}^m ((i-s_k)^2+(j-k)^2)$ 。时间复杂度 $O(n^3)$ 。

考虑推一下式子：

$up_{i,j}=\min((i-s_k)^2+(j-k)^2)=\min((i-s_k)^2+j^2-2kj+k^2)=j^2+\min(-2kj+k^2+(i-s_k)^2)$

设 $j$ 是自变量，则要求的式子形如 $\min(kx+b)$ ，斜率优化。发现斜率是 $-2k$ ，单调递减；查询的是 $j=1,2,\dots,m$ ，单调递增；所以可以单调队列维护下凸包。时间复杂度 $O(nm)$ 。

难度：蓝。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=4e3+5;
struct dque{
    ll l,r;
    ll dq[MAXN];
    dque(){
        l=1,r=0;
        memset(dq,0,sizeof(dq));
    }
    bool empty(){return l>r;}
    ll size(){return r-l+1;}
    ll front(){return dq[l];}
    ll ffront(){return dq[l+1];}
    ll back(){return dq[r];}
    ll bback(){return dq[r-1];}
    void pushback(const ll &x){
        dq[++r]=x;
        return;
    }
    void popback(){
        r--;
        return;
    }
    void popfront(){
        l++;
        return;
    }
};
ll n,m,k,u,d,l,r;
ll a[MAXN][MAXN],s[MAXN],y[MAXN],x[MAXN],res[MAXN];
dque dq;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin>>a[i][j];
    //处理up
    memset(s,0,sizeof(s));
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++) if(a[i][j]) s[j]=i;//更新每一列最下面的点
        dq=dque();
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for(ll j=1;j<=m;j++){
            x[j]=j;
            y[j]=j*j+(i-s[j])*(i-s[j]);
        }
        for(ll j=1;j<=m;j++){//加直线
            if(s[j]==0) continue;
            while(dq.size()>1&&(y[j]-y[dq.back()])*(x[dq.back()]-x[dq.bback()])<=(y[dq.back()]-y[dq.bback()])*(x[j]-x[dq.back()])) dq.popback();
            dq.pushback(j);
        }
        for(ll j=1;j<=m;j++){
            k=j<<1;
            while(dq.size()>1&&y[dq.front()]-k*x[dq.front()]>y[dq.ffront()]-k*x[dq.ffront()]) dq.popfront();
            if(!dq.empty()) res[j]=j*j+y[dq.front()]-k*x[dq.front()];
            else res[j]=1e9;
            u^=res[j];
        }
    }
    //处理down
    memset(s,0,sizeof(s));
    for(ll i=n;i;i--){
        for(ll j=1;j<=m;j++) if(a[i][j]) s[j]=i;//更新每一列最上面的点
        dq=dque();
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for(ll j=1;j<=m;j++){
            x[j]=j;
            y[j]=j*j+(i-s[j])*(i-s[j]);
        }
        for(ll j=1;j<=m;j++){//加直线
            if(s[j]==0) continue;
            while(dq.size()>1&&(y[j]-y[dq.back()])*(x[dq.back()]-x[dq.bback()])<=(y[dq.back()]-y[dq.bback()])*(x[j]-x[dq.back()])) dq.popback();
            dq.pushback(j);
        }
        for(ll j=1;j<=m;j++){
            k=j<<1;
            while(dq.size()>1&&y[dq.front()]-k*x[dq.front()]>y[dq.ffront()]-k*x[dq.ffront()]) dq.popfront();
            if(!dq.empty()) res[j]=j*j+y[dq.front()]-k*x[dq.front()];
            else res[j]=1e9;
            d^=res[j];
        }
    }
    //处理left
    memset(s,0,sizeof(s));
    for(ll i=1;i<=m;i++){
        for(ll j=1;j<=n;j++) if(a[j][i]) s[j]=i;//更新每一行最右面的点
        dq=dque();
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for(ll j=1;j<=n;j++){
            x[j]=j;
            y[j]=j*j+(i-s[j])*(i-s[j]);
        }
        for(ll j=1;j<=n;j++){//加直线
            if(s[j]==0) continue;
            while(dq.size()>1&&(y[j]-y[dq.back()])*(x[dq.back()]-x[dq.bback()])<=(y[dq.back()]-y[dq.bback()])*(x[j]-x[dq.back()])) dq.popback();
            dq.pushback(j);
        }
        for(ll j=1;j<=n;j++){
            k=j<<1;
            while(dq.size()>1&&y[dq.front()]-k*x[dq.front()]>y[dq.ffront()]-k*x[dq.ffront()]) dq.popfront();
            if(!dq.empty()) res[j]=j*j+y[dq.front()]-k*x[dq.front()];
            else res[j]=1e9;
            l^=res[j];
        }
    }
    //处理right
    memset(s,0,sizeof(s));
    for(ll i=m;i;i--){
        for(ll j=1;j<=n;j++) if(a[j][i]) s[j]=i;//更新每一行最左面的点
        dq=dque();
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for(ll j=1;j<=n;j++){
            x[j]=j;
            y[j]=j*j+(i-s[j])*(i-s[j]);
        }
        for(ll j=1;j<=n;j++){//加直线
            if(s[j]==0) continue;
            while(dq.size()>1&&(y[j]-y[dq.back()])*(x[dq.back()]-x[dq.bback()])<=(y[dq.back()]-y[dq.bback()])*(x[j]-x[dq.back()])) dq.popback();
            dq.pushback(j);
        }
        for(ll j=1;j<=n;j++){
            k=j<<1;
            while(dq.size()>1&&y[dq.front()]-k*x[dq.front()]>y[dq.ffront()]-k*x[dq.ffront()]) dq.popfront();
            if(!dq.empty()) res[j]=j*j+y[dq.front()]-k*x[dq.front()];
            else res[j]=1e9;
            r^=res[j];
        }
    }
    cout<<u<<' '<<d<<' '<<l<<' '<<r;
    return 0;
}

题目 3

给定 $n$ 个点 $m$ 条边的带边权有向图，每个点有开放时间，若当前时间 $T$ 满足： $l_i\leq T\bmod t_i\leq r_i$ ，则可以从此点出发到其它点。你有两种状态：停止状态和移动状态，初始你是停止状态。如果你处于停止状态的时候想移动，必须额外消耗 $k$ 时间变成移动状态。移动之后如果你能不停歇地继续移动，则可以不切换为停止状态。

注意，如果在时间 $T$ ，点 $i$ 开启了，并且你处于停止状态，那么无论 $T+k$ 时间时点 $i$ 是否开启，你都可以通过。也就是说，能否通过一个点取决于你准备移动地那一刻。

求 $1$ 到所有点的最短路。

$2\leq n,m\leq 5\times 10^3$ ， $0\leq k\leq 10^3$ ， $1\leq w\leq 10^3$ ， $2\leq t_i\leq 10$ ， $0\leq l_i\leq r_i<t_i$ ，没有重边自环。

首先经过 $\operatorname{LCM}(t)$ 的时间，所有点的开放状态会回归初始，而 $t$ 很小，可以计算出这个循环时间为 $2520$ 。

建立分层图，设 $dist_{u,T,0/1}$ 表示到达点 $u$ ，此时时间为 $T$ （满足 $0\leq T<2520$ ），状态为停止还是移动的最短路。朴素实现复杂度大概是 $O(mT\log mT)$ 。不可通过。

发现 $k,w$ 也很小，且 $k+w<2520$ ，说明经过一条边之后，循环次数只会 $+0$ 或 $+1$ 。这令我们想到 01bfs。设 $dist_{u,T,0/1}$ 表示最小经过循环次数，使用 01bfs 跑即可。答案为 $\min_i(2520\times \min(dist_{u,i,0},dist_{u,i,1})+i)$ 。

时间复杂度： $O(mT)$ 。

难度：青。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXT=2520;
struct node{
    int u,tm,s,d;
    node(const int &A=0,const int &B=0,const int &C=0,const int &D=0):u(A),tm(B),s(C),d(D){}
};
struct graph{
    int nxt,to,w;
    graph(const int &A=0,const int &B=0,const int &C=0):nxt(A),to(B),w(C){}
};
int n,m,k,u,v,w,ans,tot=1;
int hd[5005],l[5005],r[5005],t[5005],dist[5005][MAXT][2];
graph edge[5005];
deque<node> dq;
void add(const int &u,const int &v,const int &w){
    edge[++tot]=graph(hd[u],v,w);
    hd[u]=tot;
    return;
}
void dij(){
    node u,v;
    memset(dist,0x3f,sizeof(dist));
    dist[1][0][0]=0;
    dq.push_back(node(1,0,0,0));
    while(!dq.empty()){
        u=dq.front();
        dq.pop_front();
        if(u.s==0){
            v=node(u.u,u.tm+1,0,u.d);
            if(v.tm>=MAXT){
                v.tm-=MAXT;
                v.d++;
            }
            if(v.d<dist[v.u][v.tm][v.s]){
                dist[v.u][v.tm][v.s]=v.d;
                if(v.d==u.d) dq.push_front(v);
                else dq.push_back(v);
            }
        }
        if(u.tm%t[u.u]<l[u.u]||u.tm%t[u.u]>r[u.u]) continue;
        for(int i=hd[u.u];i;i=edge[i].nxt){
            v.u=edge[i].to;
            v.tm=u.tm+edge[i].w;
            if(u.s==0) v.tm+=k;
            v.d=u.d;
            v.s=0;
            if(v.tm>=MAXT){
                v.tm-=MAXT;
                v.d++;
            }
            if(v.d<dist[v.u][v.tm][v.s]){
                dist[v.u][v.tm][v.s]=v.d;
                if(v.d==u.d) dq.push_front(v);
                else dq.push_back(v);
            }
            v.s=1;
            if(v.d<dist[v.u][v.tm][v.s]){
                dist[v.u][v.tm][v.s]=v.d;
                if(v.d==u.d) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i]>>t[i];
    dij();
    for(int i=1;i<=n;i++){
        ans=1e18;
        for(int j=0;j<MAXT;j++) ans=min({(dist[i][j][0]>=1e9?(int)1e9:dist[i][j][0])*MAXT+j,(dist[i][j][1]>=1e9?(int)1e9:dist[i][j][1])*MAXT+j,ans});
        cout<<ans<<' ';
    }
    return 0;
}

题目 4

给定 $n$ 个居民，编号 $1,2,\dots,n$ ，再给定 $n$ 个礼物，编号 $m+1,m+2,\dots,m+n$ 。居民 $i$ 只喜欢要 $i$ 的倍数的礼物。求有几种分配方案使得每个人都恰好有 $1$ 个礼物。

$1\leq n\leq 10^9$ ， $1\leq m\leq 20$ 。

假设 $n\leq m$ ，状压就行。我们只考虑 $n>m$ 的做法。

假设居民 $i$ 拿到了 $j$ 。如果 $i=j$ ，那么无事发生；如果 $i<j$ ，那么我们接着考虑 $j$ 怎么办。 $j$ 肯定还得拿一个 $k$ ， $k$ 也得接着拿，以此类推，最终拿到哪里呢？拿到一个 $>n$ 的数截止。

我们发现 $[m+1,n]$ 里面的居民可以无事发生，所以先不管；但是 $[1,m]$ 的居民只能拿其他人的。对于 $1\leq i\leq m$ ，假设他拿了 $a_1$ ，则有 $i\mid a_1$ ；接着，有 $a_1\mid a_2$ 。因此，设最后 $j>n$ ，有 $i\mid a_1\mid a_2\mid \dots\mid j$ 。我们思考这个的方案数怎么求。

设这个倍数的过程，每次乘上了 $t$ ，则有：

$j=it_1t_2\dots t_K\\ \prod t=\frac{j}{i}$

同时满足 $t_k>1$ 。

我们来求这个的方案数，直接枚举因数再记忆化搜索就可以，时间复杂度 $O(玄学)$ 。设分解 $x=\frac{j}{i}$ 的方案数为 $F(x)$ 。

此时可能会有一个问题，就是两条不同的倍数链会不会相交在某一个点？假设这个点是 $t$ ，显然：

$\begin{cases} m+1\leq t\leq n\\ t\mid j_1\\ t\mid j_2\\ \end{cases}\\ \therefore t\mid (j_1-j_2)\\ \because j_1-j_2<m\\ \therefore t<m$

所以不会相交。

然后我们发现，这个链的第一个数是 $[1,m]$ ，但是第二个数应该是 $[m+1,n]$ 的，所以还需要特意枚举一下每条链的第二个数。应该有 $t_1>\frac{m}{i}$ 。

那么，我们设 $f(i,j)$ 表示，当第一个数是 $i$ ，最后一个是 $j$ 的时候的方案数，容易得到：

$f(i,j)=F(\frac{j}{i})-\sum_{2\leq k\leq \frac{m}{i},k\mid \frac{j}{i}} F(\frac{\frac{j}{i}}{k})$

时间复杂度是 $O(m^2\log m\cdot 玄学)$

然后我们就可以考虑状压求解总方案了。设 $dp_{s}$ 表示，将 $[1,\operatorname{popcount}(s)]$ 的数作为起点， $n+\{s\}$ 集合作为终点的分配方案数。有 $dp_{0}=1$ 。

然后我们考虑转移进来下一个终点 $i$ 。设 $t=\operatorname{popcount}(s)$ ，有：

$dp_{s|2^i}\gets dp_{s,i}f(t+1,n+i)$

时间复杂度： $O(2^mm+m^2\log{m}\cdot 玄学)=O(能过)$ 。

难度：紫。

Code:

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int n,m,t;
int f[21][21],dp[1<<20];
map<int,int> vis;
void solve1(){
    dp[0]=1;
    for(int s=0;s<1<<n;s++){
        t=__builtin_popcount(s);
        for(int i=0;i<n;i++){
            if(s>>i&1) continue;
            if((m+i+1)%(t+1)) continue;
            dp[s|1<<i]=(dp[s|1<<i]+dp[s])%MOD;
        }
    }
    cout<<dp[(1<<n)-1];
    return;
}
int dfs(const int &x){
    if(vis.count(x)) return vis[x];
    int res=1;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            res=(res+dfs(x/i))%MOD;
            if(i*i<x) res=(res+dfs(i))%MOD;
        }
    }
    return vis[x]=res;
}
void solve2(){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){//begin:i end:n+j
            if((n+j)%i) continue;
            f[i][j]=dfs((n+j)/i);
            for(int k=2;k<=m/i;k++){
                if((n+j)/i%k) continue;
                f[i][j]=(f[i][j]-dfs((n+j)/i/k)+MOD)%MOD;
            }
        }
    }
    dp[0]=1;
    for(int s=0;s<1<<m;s++){
        t=__builtin_popcount(s);
        for(int i=0;i<m;i++){
            if(s>>i&1) continue;
            dp[s|1<<i]=(dp[s|1<<i]+1ll*dp[s]*f[t+1][i+1])%MOD;
        }
    }
    cout<<dp[(1<<m)-1];
    return;
}
int main(){
    cin>>n>>m;
    if(n<=m) solve1();
    else solve2();
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

题目 1

题目 2

题目 3

题目 4

热门讨论