主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
联合省选 2025 游记
最后更新于 2025-07-31 11:35:44
作者
Miku_QwQ
分类
生活·游记
复制 Markdown
查看原文
删除文章
更新内容
## Day 0 从合肥坐火车到芜湖。 试机是 NOIWC2025。 ## Day 1 >我常常追忆过去。 > >生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲,揉捻成天上朵朵白云。 > >云朵之间亦有分别:积云厚重,而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀,而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦,太过清楚则无法愉悦自己的幻想,过分模糊却又坠入虚无。只有薄雾间的山水,面纱下的女子,那恰到好处的朦胧,才能满足我对美的苛求。 > >追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友,推倒又重建的街道,种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来,我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间,在一个场景前驻足,在岁月的朦胧里瞭望过去的自己,感受尽可能多的甜蜜。美好的时光曾流过我的身体,我便心满意足。 > >过去已经凝固,我带着回忆向前,只是时常疏于保管,回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。 > >我该在哪里停留?我问我自己。 进考场。 压缩包密码是 `keeP*drEAm&iNg`,含义明显。 开题。T1 看起来是妙妙数学题,T2 像是图论和 ds 的杂交产物,T3 一眼不可做题。好像药丸怎么办? 重新读 T1,发现原题与性质 A 几乎相同,启示我们使用离散化。于是我们只需要尝试判断 $x$ 是否可能成为中位数即可。 我们发现,如果令小于 $x$ 的数有 $cnt_l$ 个,等于 $x$ 的数有 $cnt_x$ 个,大于 $x$ 的数有 $cnt_r$ 个,那么 $x$ 为中位数的充要条件就是 $cnt_l+cnt_x \geq cnt_r$ 且 $cnt_r+cnt_x>cnt_l$。 整理一下,可以得到 $cnt_r-cnt_l \in (-cnt_x,cnt_x]$,然而这个条件貌似不是特别好看。 我们给出第二种形式:$0 \in [cnt_l-cnt_x-cnt_r+1,cnt_l+cnt_x-cnt_r]$。 此时我们发现,令 $L=cnt_l-cnt_x-cnt_r+1,R=cnt_l+cnt_x-cnt_r$,则只需要让 $0 \in [L,R]$。 那么,对于 $a \in [l_1,r_1]$ 且 $b \in [l_2,r_2]$ 的条件,产生的贡献如下: - 若 $a<x$,则 $L \leftarrow L+b$,$R \leftarrow R+b$。 - 若 $a=x$,则 $L \leftarrow L-b$,$R \leftarrow R+b$。 - 若 $a>x$,则 $L \leftarrow L-b$,$R \leftarrow R-b$。 通过分类讨论,不难看出若存在 $a=x$,则一定让 $a=x$,$b=r_2$,此时一定不劣。若无论如何 $a \not=x$,则产生的贡献是 __几乎__ 确定的,因为此时只能取左边或右边。 然后你发现新的形式很不好做的样子,所以回到原来的形式:$cnt_r-cnt_l \in (-cnt_x,cnt_x]$。此时 $cnt_x$ 应该是确定的。然后我们发现区间具有连续的性质,所以可以求出 $cnt_r-cnt_l$ 的取值范围,判断两个区间的交是否存在即可。 这是高贵的考场代码。 ```cpp #include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct Node{ int l1,r1,l2,r2; }a[200010]; int n,tot,tmp[400010],len[400010]; long long cnt_x[400010],cnt_l_min[400010],cnt_l_max[400010],cnt_r_min[400010],cnt_r_max[400010]; int main(){ freopen("lucky.in","r",stdin); freopen("lucky.out","w",stdout); int Case_id,Case_num; scanf("%d %d",&Case_id,&Case_num); while(Case_num--){ tot=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d %d %d %d",&a[i].l1,&a[i].r1,&a[i].l2,&a[i].r2); tmp[++tot]=a[i].l2; tmp[++tot]=a[i].r2+1; } sort(tmp+1,tmp+tot+1); tot=unique(tmp+1,tmp+tot+1)-(tmp+1); int cnt=tot-1; for(int i=1;i<=cnt;i++){ len[i]=tmp[i+1]-tmp[i]; } for(int i=0;i<=cnt+1;i++){ cnt_x[i]=0; cnt_l_min[i]=cnt_l_max[i]=cnt_r_min[i]=cnt_r_max[i]=0; } for(int i=1;i<=n;i++){ int L=lower_bound(tmp+1,tmp+tot+1,a[i].l2)-tmp; int R=lower_bound(tmp+1,tmp+tot+1,a[i].r2+1)-tmp-1; cnt_x[L]+=a[i].r1; cnt_x[R+1]-=a[i].r1; if(L>1){ cnt_r_min[L-1]+=a[i].l1; cnt_r_max[L-1]+=a[i].r1; } if(R<cnt){ cnt_l_min[R+1]+=a[i].l1; cnt_l_max[R+1]+=a[i].r1; } } for(int i=1;i<=cnt;i++){ cnt_x[i]+=cnt_x[i-1]; } for(int i=1;i<=cnt;i++){ cnt_l_min[i]+=cnt_l_min[i-1]; cnt_l_max[i]+=cnt_l_max[i-1]; } for(int i=cnt;i>=1;i--){ cnt_r_min[i]+=cnt_r_min[i+1]; cnt_r_max[i]+=cnt_r_max[i+1]; } int ans=0; for(int i=1;i<=cnt;i++){ long long L=-cnt_x[i]+1,R=cnt_x[i]; if(L<=R){ long long minn=cnt_r_min[i]-cnt_l_max[i],maxn=cnt_r_max[i]-cnt_l_min[i]; if(minn<=R && maxn>=L){ ans+=len[i]; } } } printf("%d\n",ans); } return 0; } ``` 然后是 T2,先被这个题目背景震撼了几分钟。 看到这个时空限制就感觉是一个特技卡常数题,貌似是一个 bitset 或者一个分块的复杂度。然而想了半天都没有任何结果。 先打暴力。前 $20\%$ 是 easy 的,接下来就是优化算法。 __第一次失误:当你发现一道题目看起来没有思路,不妨先看一看其他题,不要想着做出来这一题。__ 于是很长时间过去,分数仍然停留在这里。 看 T3。题目在说什么!我怎么不知道! 红温了,手搓一下样例,好像有点思路!我会树了! __第二次失误:当你发现一道题目你已经会了一档分,不妨看看别的分能不能轻松拿到。__ 于是打了一个树。还有八分钟,时间快到了,来不及打 T3 暴搜了。检查一下文件,没问题就撤了。 估分:100+20+24=144,测了一下民间数据好像没有什么问题。 然后中午出去吃饭,一拍脑袋:欸我不是会 T3 的森林了吗?如果不在 T2 上花那么长时间,能把森林和暴搜打完,不就 100+20+52=172 了吗? 输麻了。 ## Day 2 >希望大家一直记得我。 > >“希望大家永远忘了我。” 进考场。 压缩包密码是 `ReM#Ain(LoVinG`。含义明显。 开题。T1 看起来是道结论题,T2 看起来很不可做,T3 看起来很不可做。
正在渲染内容...
点赞
2
收藏
0