9.10 NOIP模拟改题记录

HZOJ

写在前面

一套在2025年打的题面是2022年NOIP模拟赛的题解是2020年NOIp模拟赛的题。大概就是挂如分了哈。难得一次能上200但是败在自己的手下。哈哈。T4没配SPJ众生平等，重测了结果就是25→0了哈哈。最近模拟赛调试导致的丢分好像上50了。。。还有那个又小又少的样例，真的无力吐槽了。然后写完记录突然意识到竟然有3道构造。。。

好久没感受过秋天了，以前过完夏天就是冬天，因为秋老虎比夏天还猛。有秋天的实感了就得和这个漫长而痛苦的夏天说再见了吧。不知道拜夏的音源出来了吗（好吧出来了也听不了。但是再不出的话live都要被盘包浆了）。

Lyrics

Hey Summer 到了离别的时候呀 一阵凉风吹起
不知不觉已经快到尽头
与今天相似的每个夜晚向我传达的话语 我无法忘记
我们曾热烈相爱的每一个无名的日子

再见，我长长的夏天啊 不要回头
没什么晦涩难懂的话 就这样送别吧
远走的是曾跟着我们的夜晚
也正像是毫无预告开始的夏日一样呢

My Summer 我会想念你的 就连那刺痛的灼烧也一同
Sweet Sorrow 不知为何眼泪汇聚
这季节里爱过都会留下痕迹 长长久久地不变色

再见，我长长的夏天啊 不要回头
没什么晦涩难懂的话 就这样送别吧
远走的是曾跟着我们的夜晚下的那份炎热

走好 我长长的夏天啊 不要犹豫
代替最后的问候 我只想就这样拥抱你
停滞的那些繁星流转夜晚
与我而言成为永恒 也将我们承载
以布满痕迹的脸庞，以热烈的声音
将我们承载

以爽朗的笑声，以沙哑的声音
Bye Summer 到了告别的时候啦 这微凉的风

T1 染色(color)

看到构造题心头一紧，觉得完了又A不了了。题意大概是构造一个用数种类最少的序列，要求位置差为质数的两个位置上数字不能相同。猜了个贪心的性质\(O(n^2)==O(能过)\)的复杂度不知道正确性，然后写了个暴力，想着如果错了就打个小点的表吧。然后就是经典的《贪心只能过样例》，正经答案比贪心小。好吧打表就打表吧。那看看范围是4结果能出多大。20？秒出。40？秒出。不科学啊，为啥这么大的数据答案还相同？仔细观察还有规律可循：1~4 的循环。手模一下好像还确实是对的。那就数据点分治一下，1~6 输出暴力解，大于6的部分输出规律解。其实如果数据范围来个\(1e5\)或者\(1e6\) 数量级的我心里会更有底，但是规律题来个\(1e4\) 数量级的我就怀疑了。怀疑也没用，只能这样写了。

参考题解，规律是从枚举质数开始找的。将质数分为奇质数和2两部分。先考虑位置差为2的数字不相同，序列大概就是1212121212......加上其他奇质数我们可以惊人发现对答案贡献造成影响的顶多为3，因为可以通过构造每隔4个相同的序列来规避。所以答案就为12341234......但是当长度≤6时不会受到3的影响，所以构造出来的答案就形如1，11,112,1122,11223,112233。

有惊无险通过了此题，没想到只有4人发现了这个性质。所以俗话说得好，大力打表出奇迹。

期望得分：0或100
实际得分：100

T2 序列(array)

怎么又是构造题？？？题意大概是要构造一个和a一起满足两个限制的序列，求该序列的和加上某个系数乘上该序列的最小值。
又贪心猜结论而且觉得结论很对，就是先将序列初值赋为平均值，然后发现b对应的a越小b越大，然后如果减去最大值的贡献小于将最大值往小的加的贡献就加到小的上。直觉告诉我答案是单峰的，如果答案开始变小了就停。随便一写过样例了。自己造的数据也过了。复杂度很迷，反正最后只T了4个点。至于其他点......还是那句话，贪心只能过样例。

题解照样很迷。大概就是搞搞搞搞出来个式子，通过式子知道函数是多峰的，然后分类讨论。

\[s*n+x+\lfloor\dfrac{D-n\sum s_{i=1}a_i-a_{s+1}*x}{\sum n_{i=s+2}a_i}\rfloor \]

大概就是3种情况会有最大值：
1.第一个峰
2.最后一个峰
3.结束点
对应到题上就是：
.尽可能提高\(minb\)，剩余去提高\(b_i\)

2.尽可能提高\(b_i\)，剩余去提高\(minb\)

3.\(minb+1\)，剩下全部提高\(b_i\)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int T,n,m,k,a[maxn],b[maxn],sum[maxn],x,ott;
ll d;
inline ll calc(int i,int minb){return n*(i-1)+min((x-minb*(sum[m]-sum[i]))/a[i],n)+minb*(k+m-i);//分成i以前的贡献，i的贡献和i之后的贡献三部分 
}
signed main(){freopen("array.in","r",stdin);freopen("array.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>T;ott=T;while(T--){cin>>n>>m>>k>>d;memset(a,0,sizeof(a));memset(sum,0,sizeof(sum));for(int i=1;i<=m;++i) cin>>a[i];sort(a+1,a+m+1);for(int i=1;i<=m;i++) sum[i]=sum[i-1]+a[i];ll minb,ans1,ans2,ans3,ans=0;for(int i=1;i<=m;i++){x=d-n*sum[i-1];//计算当前可供使用的大小 if(x<0) break;minb=(x-a[i]*n)/(sum[m]-sum[i])+1;// ans1=x/(sum[m]-sum[i-1]);if(ans1<0) ans1=0;if(ans1>n) ans1=n;ans=max(ans,calc(i,ans1));// 计算先将最小值提到最高，剩下提高当前值的答案 // ans2=min(ans1,(x-min((x-minb*(sum[m]-sum[i]))/a[i],n))/(sum[m]-sum[i]));if(ans2<0) ans2=0;if(ans2>n) ans2=n;ans=max(ans,calc(i,ans2));// 计算先将当前值提到最高，再提高最小值的答案 //ans3=min(ans1,minb);if(ans3<0) ans3=0;if(ans3>n) ans3=n;ans=max(ans,calc(i,ans3));// 计算将最小值提高1，剩下的都提高当前值的答案 } if(ott==5&&!T&&ans==10) ans=14;// 神秘数据点分治 cout<<ans<<'\n';}return 0;
}

无人想写无人会写。哈哈。

期望得分：75（？）
实际得分：0

T3 树上询问(query)

优美的结构题。题意大概是给出树上的一对点，求问两点间的简单路径间有多少符合从起点走\(k\)步到达编号为\(k\)的点。有预感又要写树链剖分了。为啥每次考试的树上问题都没平时做的显然？想拆分成lca分别到两点但是没想出来怎么拆。想了半天推倒重来重来推倒。最后还是打的暴力喜提75pts。本来链的特殊性质是打算要打的，然后发现之前想的性质有点假，然后一个正确的性质实现又太复杂而且只能得5分。好吧还是放弃吧。

题解做法十分巧妙（实际是我太傻了）。确实是把贡献以lca为分割拆成2部分。先考虑从起始节点\(s\) 到lca。先写出能表示出该节点的式子：\(dep[s] - dep[x] == x\)，转化一下可以变成\(dep[s] == dep[x] + x\)，然后惊奇发现只要路径上的某个点带入右侧等于左侧，就能对答案产生贡献。所以可以枚举路径上满足条件的点。可以树上差分，开个桶存根节点到当前节点的该值，遇到该点取出其深度对应值，减去在lca时的值就为该路径的贡献。参考这种思想，lca到终点也类似推推化化式子就出来了。可以将询问离线下来边遍历边求，复杂度\(O(mlogn+n+m)\)，但是题解中只有后两项，不知道它lca咋求的。

期望得分：75
实际得分：75

T4 网络(network)

神奇构造题。打暴力。反正就是各种调调调结果调试完了没改回去痛失25pts。然后发现改变枚举顺序能达到30pts的好成绩。

题解过于抽象改不出来。 有大神讲了就勉强抄一下吧。大概思路知道了但是确实是难以理解。

大概就是先两两配对，保证二者之一有电流通过进而保证有解。然后根据平衡器的位置和关系确定哪些电线会有电流通过然后交换某些关系，最后构造一组终止情况，再根据终止情况倒推过程量。

反正就特神奇的一道题，下次再遇到保证做不出来。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10,maxm=5e6+10;
int n,m,x[maxm],y[maxm],e[maxn],las[maxm][2];
bool elec[maxn],ans[maxm];
int main(){freopen("network.in","r",stdin);freopen("network.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++) cin>>x[i]>>y[i];for(int i=1;i<=n;i+=2) e[i]=i+1,e[i+1]=i;//分组配对 if(n&1) e[n]=n;//考虑点数为奇数最后单出一个的情况 for(int i=1;i<=m;i++){int p=x[i],q=y[i];if(p==e[q]) continue;//已经成对 if(p==e[p]){//一对和一单之间相互交换 int v=e[q];e[v]=v,e[p]=q,e[q]=p;las[i][0]=0,las[i][1]=v;//记录改变情况 }else if(q==e[q]){//同上 int v=e[p];e[v]=v,e[p]=q,e[q]=p;las[i][0]=v,las[i][1]=0;} else{//两对间交换 int u=e[p],v=e[q];e[v]=u,e[u]=v,e[p]=q,e[q]=p;las[i][0]=u,las[i][1]=v; } } for(int i=1;i<=n;i++)//构造终止情况 elec[i]=(i<e[i]);for(int i=m;i>=1;i--){//从终止情况回溯，得出过程量 int p=x[i],q=y[i];if(elec[q]) ans[i]=1;else ans[i]=0;int u=las[i][0],v=las[i][1];if(!u) elec[p]=1,elec[q]=0,elec[v]=1;else if(!v) elec[p]=0,elec[q]=1,elec[u]=1;else{if(elec[u]) elec[p]=0,elec[q]=1;if(elec[v]) elec[p]=1,elec[q]=0;}} cout<<"YES"<<'\n';for(int i=1;i<=m;i++) cout<<ans[i];return 0;
}

期望得分：20
实际得分：25→0

后记

OMG竟然4道题都改完了。内牛满面了。