各种各样模拟赛的心得

No.1 2025.8.26 小模拟赛

共四道题，四个小时，OI赛制，难易程度大致为提高组（实际上没有提高组的天地差大）

赛时记录

T1：原题为ABC395_D，是道黄题，很简单，我的思路就是将复杂的所有鸽子换巢操作转变为简单的换两个巢的编号（不难想出来吧），简单地解决。具体来说：

操作 $1$ ：直接将鸽子 $x$ 所属的巢赋值成 $y$ 即可。
操作 $2$ ：新设置一个数组 $b$ 维护每个巢如今实际的位置序列，将巢 $x$ 和巢 $y$ 的如今实际的位置交换即可（即 swap(b[x],b[y]) ），所以实际上操作 $1$ 应将鸽子 $x$ 所属的巢赋值成 $b_y$ 。
操作 $3$ ：再维护一下每个巢所在的位置，这样就可以直接输出。

详情见代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000005],b[1000005],c[1000005],n,q;
int main()
{
	cin>>n>>q;
	for(ll i=1;i<=n;i++) a[i]=b[i]=c[i]=i;
	for(ll i=1;i<=q;i++)
	{
		ll opt;
		cin>>opt;
		if(opt==1) //操作 1
		{
			ll x,y;
			cin>>x>>y;
			a[x]=b[y];
		}
		else if(opt==2) //操作 2
		{
			ll x,y;
			cin>>x>>y;
			swap(c[b[x]],c[b[y]]); //记得改变一下巢的位置
			swap(b[x],b[y]);
		}
		else //操作 3
		{
			ll x;
			cin>>x;
			cout<<c[a[x]]<<endl;//输出鸽子 x 所在巢穴的实际位置
		}
	}
}

T1 用了 30 min 成功切掉了。

之后去看 T2（原题为CF1801B），发现没啥思路。倒是想到按其中一个来排序去dp一下，但发现往后就不太会做了，耗时 30 min+ 。

然后就去看 T3（原题为CF1801C）了，想了大概 30 min+ 有了一个大致的思路（当时认为非常对）：把每一个串对整个答案的贡献拆出来（例如 4 9 4 6 8 对答案的贡献就是 4 9），然后按结尾数字排个序，之后就可以进行组装了，按照顺序组装，在组装的时候进行二分（我以为是单调的），找到最大的能替换掉前面的部分时对答案贡献最大的位置。反正比较复杂，结果写代码的时候就直接崩了，写到最后都没调出来。。。T4（原题为CF1801D）看都没看。。。

临近比赛结束的时候花了 3 min 左右打了个 T2 的暴力，不用动脑子的暴搜。

反正这场比赛打的也是很拉垮，总分：

100+2+0+0=102 pts

。。。总之还是时间安排的不太对，自信认为能切掉 T3 ，结果不如打个暴力。

赛后题解

No.2 2025.8.27 NOIP模拟赛

共四道题，四个半小时（实际上只有四个小时），OI赛制，难易程度大致为NOIP（够难）

赛时记录

T1 想了将近 30 min 还没有想出正解的明确思路，就意识到这场比赛不像昨天那样有水题给你白嫖分了（哭），于是乎开始想特殊性质，我觉得保证所有

v_i

均相等是比较好做的，大体来说把逃离分成由

v_i

均相等到下一次

v_i

均相等这样的好几个块，在哪一个块逃不出去的计算是很简单的（当时还想了好长时间），然后在这个块内二分，找到并输出。代码的细节挺多的，耗费了挺长时间，大约耗时 100 min 。

写完 T1 就马不停蹄去看 T2 了，看了几分钟感觉

t=0

的情况很好处理然后就花了不到 30 min 写完了，然后去看 T3 了。

T3 刚开始还以为很简单（但为什么会有有

10^5

个键的乌蒙地插而且lost一个直接失败的），但仔细想了想好像不能贪心，应该要做个挺复杂的dp，也不太会，于是就打了个简单的特殊性质，每次按键都是两个两个出现时直接判断左手去第一个按键，右手去第二个按键与左手去第二个按键，右手去第一个按键那种最省距离就行了。耗时 30 min 。

之后瞟了一眼 T4 ，很讨厌这种无从下手的这种题！而且感觉暴力也不好打，果断回去打 T2 正解去了。T2 我想的是可以在快跳到块的末尾时判断一下是否需要多耗一步跳到块的末尾还是可以直接继续跳，但我忘了有可能一跳跳过好几个块。。。于是就这么delightly completely 寄掉了，但感觉应该有一个特殊性质可能能过。耗时 40 min+ 。

之后又不太放心 T3 ，又花了 10 min 左右打了个很草的暴搜，又写了个 T1 的暴力，和我原来的代码对拍居然排出来了点问题。

然后就摆烂了 10 min 左右（实际上在检查文件操作之类的）就交卷了，预计分数：

[0,60] + [50,60] + [20,28] + 0 = [70,148] pts

实际分数：

40+44+20+0=104 pts

怎么说呢…… T1 莫名挂了一点点分，应该是特殊性质挂的（代码细节太多没想着必须拿满）， T2 我也不是很清楚哪里写挂了，T3 的暴搜我居然没写对（我成彩笔了），总之也就还行。

当然挂分也很有可能和评测机有关，后面的比赛深深地印证了这一点。

（据说lyhr大佬 T3 用 crazy 的数据结构没卡常打正解打了 60pts，恐怖如斯）

赛后题解

不想写了，直接搬过来了。

t1:

t2:

t3:

t4:

No.3 2025.8.29 CSP-S 模拟赛

共四道题，四个小时，OI赛制，难易程度低于提高组（差不多是个入门组）

赛时记录

由于昨天的比赛真的挺难的，可能产生了一些畏惧心理，所以这场比赛本来没想着打多少分。

但是！T1 都没打算好好想思路，结果不到 10 min 就想出来正解了把我惊到了，代码也是 30 min 不到就写完了，那么来说一下思路吧：

最早：很自然就能想到从根节点一路走到该点，直接一条链下来肯定是最早遍历到该点的，即为该节点的深度 $dep[x]$ 。
最晚：最晚肯定是其他所有能走到的点全部被走过了一遍，所以除了自己的子树不能在自己之前被遍历到，其他点均可以，即为 $n-siz[x]$ ，也就是总点数减去子树大小，需不需要加一具体看写法。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,head[2000005],tail[2000005],nxt[2000005],siz[1000005],dep[1000005],tot,lastn;
void add(ll x,ll y)
{
	tail[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs(ll x,ll fa)
{
	siz[x]=1;
	for(ll i=head[x];i;i=nxt[i])
	{
		ll v=tail[i];
		if(v==fa) continue;
		dep[v]=dep[x]+1;
		dfs(v,x);
		siz[x]+=siz[v];
	}
}
int main()
{
	//freopen("TechTree.in","r",stdin);
	//freopen("TechTree.out","w",stdout);
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(ll i=1;i<=2*lastn;i++)
		{
			head[i]=tail[i]=nxt[i]=siz[i]=dep[i]=0;
		}
		tot=0;
		for(ll i=1;i<n;i++) 
		{
			ll x,y;
			cin>>x>>y;
			add(x,y);
			add(y,x);
		}
		dep[1]=1;
		dfs(1,0);
		for(ll i=1;i<=n;i++)
		{
			cout<<dep[i]<<" "<<n-siz[i]+1<<endl;
		}
		lastn=n;
	}
}

这里面的

lastn

是防止

t

过大导致多次清空超时的（其实有更优的写法）。

然后看 T2 ，很自然就能想到分讨，没花多长时间，正解放后面。

T3 看了一眼发现有树状数组差不多忘干净了，于是去看 T4 。T4 是一道很有趣的题，一看这种字符串题就要用哈希，那么就很容易就想出来

O(n^5)

的做法，之后发现可以只枚举头和尾的长度，其他的段的范围其实就都能算出来，时间复杂度

O(n^2)

。以为就这么切掉了，但发现题目中说的是整个串的所有子串，还得枚举串的头和尾，于是时间复杂度就飙升到

O(n^4)

了（其实

50pts

还是挺值的），耗时 120 min 左右。

我觉得我 T4 的代码有点参考价值，摆在这儿吧：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll t,a[30005],mul[30005];
string s;
ll getnum(ll l,ll r)//hash!
{
	return (((a[r]-(a[l-1]*mul[r-l+1]%mod)))%mod+mod)%mod;
}
int main()
{
	cin>>t;
	while(t--)
	{
		ll sum=0;
		cin>>s;
		s=' '+s;
		mul[0]=1;
		ll n=s.size()-1;
		for(ll i=1;i<=n;i++)//hash!
		{
			a[i]=(a[i-1]*113+s[i])%mod;
			mul[i]=mul[i-1]*113%mod;
			//cout<<a[i]<<" "<<mul[i]<<endl;
		}
		for(ll x=1;x<=n-5;x++)//枚举子串左端点
		{
			for(ll y=x+5;y<=n;y++)//枚举子串右端点
			{
				ll len=y-x+1;//子串长度
				for(ll i=1;i<=(len+2)/3;i++)//枚举第一段长度
				{
					for(ll j=1;j<=(len+1)/2;j++)//枚举最后一段长度
					{
						if(i*3+j*2+1>len) continue;
						if(getnum(x,x+i-1)==getnum(x+i,x+2*i-1)&&getnum(x,x+i-1)==getnum(y-j-i+1,y-j)&&getnum(x+2*i,x+2*i+j-1)==getnum(y-j+1,y))//是否符合条件
						{
//							cout<<x<<" "<<y<<" "<<i<<" "<<j<<endl;
//							cout<<x<<" "<<x+i-1<<" ";
//							for(ll k=x;k<=x+i-1;k++) cout<<s[k];
//							cout<<endl<<x+i<<" "<<x+2*i-1<<" "; 
//							for(ll k=x+i;k<=x+2*i-1;k++) cout<<s[k];
//							cout<<endl<<y-i-j+1<<" "<<y-j<<" ";
//							for(ll k=y-i-j+1;k<=y-j;k++) cout<<s[k];
//							cout<<endl<<x+2*i<<" "<<x+2*i+j-1<<" ";
//							for(ll k=x+2*i;k<=x+2*i+j-1;k++) cout<<s[k];
//							cout<<endl<<y-j+1<<" "<<y<<" ";
//							for(ll k=y-j+1;k<=y;k++) cout<<s[k];
//							cout<<endl<<endl;
							sum++;
						}
					}
				}
			}
		}
		cout<<sum<<endl;
	}
}

（写的有点丑就是了）

扭回头来看 T3 ，仔细一想想出一个看起来挺正确的贪心，就是现在需要改这个位置就改，用题目提供的函数去把之后要改的位置都改了，反正零零碎碎想了 60 min 。后来又加了道 T5 ，看了看没啥思路，打暴力也不好打，也就没写。

然后在最后 10 min 的时候对拍 T2 拍出来错了！有被吓到，但好在惊险改对了。

最终总分：

50+90+100+50=290 pts

。

令人难绷的是，后来我把我 T1 T2 的代码交到洛谷上过了，推断是评测机太慢的问题，但 T3 到洛谷上挂了，说是评测机数据过水了。

(惊爆：lyhr大佬除后加的 T5 外 AK 虐全场！！！)

赛后题解

T2：很容易想到分成正正，负负，正负和有0的情况分讨（下面的情况不想证明，感性理解一下）。

正正：当且仅当1乘任何正数时满足要求，但是1乘1的情况需要单独拉出来考虑，防止算重。根据乘法原理，设1的数量为 $x$ ，非1的正数数量为 $y$ ，则正正的情况为 $x \times y + \operatorname{C}_x^2 = x \times y + \frac{x \times (x-1)}{2}$ 种。
负负：容易得到均不符合。
正负：容易得到均符合，乘法原理求得即可。
有0：当另一个数为正数时符合，乘法原理求得即可。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,a[1000005];
int main()
{
	//freopen("Buff.in","r",stdin);
	//freopen("Buff.out","w",stdout);
	cin>>t;
	while(t--)
	{
		cin>>n;
		ll sum1=0,sum0=0,sumneg=0,sumpos=0,sum1up=0;
		for(ll i=1;i<=n;i++)
		{
			cin>>a[i];
			if(a[i]==1) sum1++;
			if(a[i]>0) sumpos++;
			if(a[i]==0) sum0++;
			if(a[i]<0) sumneg++;
			if(a[i]>1) sum1up++;
		}
		if(n==1)
		{
			cout<<0<<endl;
			continue;
		}
		cout<<sum1*sum1up+(sum1*(sum1-1))/2+sumpos*sumneg+sum0*sumpos<<endl;
	}
}

很简单。

No.4 2025.8.31 NOIP模拟第二场

共四道题，四个小时，OI赛制，难易程度大致于提高和NOIP之间

赛时记录

历史总是惊人的相似！

T1 看起来挺难，实际上并非难想，很简单的一道贪心。大致思路为：首先按照

a_i

从小到大排序，如果发现有一个数可以通过交换所有的值为此数的

a_i

和与之对应的

b_i

来达成序列

a

中没有此数（当然如果本身就不在序列

a

中也符合），那么此数就为

\operatorname{mex}(a)

的最小值。方案数就为所有

b_i \ne \operatorname{mex}(a)

且

a_i \ne \operatorname{mex}(a)

的

i

换或者不换，即

2^c

，

c

即为满足上述条件的

i

的数量。非常的简单！

放一下code：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,num,sum=1,flag1;
struct node
{
	ll a,b;
}arr[100005];
bool cmp(node x,node y)
{
	return x.a<y.a;
}
int main()
{
	//freopen("mex.in","r",stdin);
	//freopen("mex.out","w",stdout);
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>arr[i].a;
	for(ll i=1;i<=n;i++) cin>>arr[i].b;
	sort(arr+1,arr+n+1,cmp);
	arr[0].a=-1;
	for(ll i=1;i<=n;)
	{
		if(arr[1].a>0)
		{
			num=0;
			break;
		}
		if(arr[i].a-arr[i-1].a>1)
		{
			num=arr[i-1].a+1;
			break;
		}
		bool flag=0;
		while(i<=n)
		{
			if(arr[i].b==arr[i].a) flag=1;
			i++;
			if(arr[i].a!=arr[i-1].a) break;
		}
		if(!flag)
		{
			num=arr[i-1].a;
			break; 
		}
		if(i>n) flag1=1;
	}
	if(flag1==1&&num==0) num=arr[n].a+1;
	for(ll i=1;i<=n;i++)
	{
		if(arr[i].a!=num&&arr[i].b!=num)
		{
			sum=sum*2%mod;
		}
	}
	cout<<num<<" "<<sum;
}

然后翻了一遍 T2 T3 T4，没有一道打暴力性价比高的题，于是乎开始考虑正解。感觉 T2 是道挺套路的题（暑假的时候好像做过类似的），于是愉悦地开始写代码！

然后！如出一辙的事便发生了：思路总体正确，非常有信心，结果将近 180 min 没打出正解！就因为一个类似于树形背包的东西真的不知道怎么写了，就崩掉了，最后 10 min T4 打了个暴力，T3 瞎骗分，总分不忍直视：

100+0+0+4=104pts

。。。QWQ

只能说还是太自信了，渺茫的希望还想去奋力争取，结果发现性价比为0，但说实话，这场比赛部分分这么少，冲正解的思路也不见得大错特错。我只能说我真没招了，真到穷途末路了。

【LGR-250】洛谷 NOIP 2025 模拟赛

时隔多年，我终于回来了！备考CSP-S期间打的模拟赛实际上很多，但是没啥时间写总结~~其实是我懒得写~~所以没更新。

从文化课回归OI的第一场模拟赛！（其实昨天晚上刚回归）

8:30

比赛开始，先看 T1。

各种各样模拟赛的心得

文章操作

No.1 2025.8.26 小模拟赛

赛时记录

赛后题解

No.2 2025.8.27 NOIP模拟赛

赛时记录

赛后题解

No.3 2025.8.29 CSP-S 模拟赛

赛时记录

赛后题解

No.4 2025.8.31 NOIP模拟第二场

赛时记录

【LGR-250】洛谷 NOIP 2025 模拟赛

相关推荐

评论

各种各样模拟赛的心得