NOIP2024游记

· · 生活·游记

这辈子最后一场NOIP，也是最认真准备的一场NOIP

Day 13

牛客周赛 C

题目大意：给定两个长度均为n的数组a,b，每次操作可以从a,b中各选择一个数删除，最后使得两个数组合并后得到的新数组c中没有重复元素，最小化操作数 (n \le 10^5)

题解：

算法：贪心，模拟

先分别对两个数组进行去重操作，分别独立计算各自的消除次数，计为ans1和ans2，得到两个无重集p,q，现在要消除p，q合体之后的新集合内的重复元素，当存在相同元素时，可以跟ans1和ans2中较少的部分一起消，若ans1 = ans2，则得进行额外的操作数，计为ans，由于有可能只存在奇数个相同元素，所以ans要加1再除2，最后的答案对于ans1+ans和ans2+ans取max即可

```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int n,ans1,ans2,ans; vector <int> p,q; map <int,int> cnt; int main(int argc,char *argv[]) { cin>>n; for(int i = 1,a;i <= n;++i) { cin>>a; if(!cnt[a]) p.push_back(a); else ans1++; cnt[a]++; } cnt.clear(); for(int i = 1,b;i <= n;++i) { cin>>b; if(!cnt[b]) q.push_back(b); else ans2++; cnt[b]++; } cnt.clear(); for(auto i:p) cnt[i]++; for(auto i:q) cnt[i]++; for(auto i:cnt) if(i.second == 2) { if(ans1 == ans2) {ans++;continue;} if(ans1 > ans2) swap(ans1,ans2); ans1++; } ans = (ans+1)/2; cout<<max(ans1+ans,ans2+ans); return 0; } ``` **Day12** ~~唐氏~~模拟赛 ![](https://cdn.luogu.com.cn/upload/image_hosting/vzcyb7iu.png) ~~致敬传奇唐氏比赛设置人Ding00sb~~ ~~数值最溢出的一集~~ 认真写点东西哈，唐氏zfl开的唐氏乐多赛制，错一次罚一分，脸都不要了。 S2吃满了3分罚时，脸都不要了，红题都不会写了 J4和J5卡了半天，模拟和深搜都不会写了，脸都不要了。 可恶的ding00sb 竟然一发罚时都没吃，最后考了6亿多分，实在是太厉害了。 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 感觉昨天晚上整个机房集体降智。 ~~致敬传奇大吼大叫人zzf~~ ~~厦外信竞队精神状态良好，感觉他们停课两周回来会变成山顶洞人~~ **Day11** 晚上又开了一场加拿大CCC的模拟赛，国外真的很喜欢写一些奇奇怪怪的要脑子的题目，这对于我这么根本没有脑子的人十分不友好。 求最短路用了dfs，结果T飞了，脸都不要了，赛后换成bfs一下就过了，真的是唐完了，太久没学了连dfs和bfs的区别都不清楚了/kk 6道橙红题写了2.5h 脸都不要了 被拉爆了 **Day10** **NOIP倒计时十天！** 今天决定彻底放弃whk，主要是太累了加上我作业没写好像听文科课也没什么用，于是就直接润了，感觉回去会被班主任骂死，算了不管了 早上的模拟赛垫底，脸都不要了，T3分讨Floyd和dij就可以拿到69分的高分，结果我分越交越少，唐。 下午的“基础题”也写的是依托，感觉自己要报废了 好消息是晚上的ACM赛制的模拟赛打的还行 ![](https://cdn.luogu.com.cn/upload/image_hosting/vrkk1r3o.png) 《厦外宇宙无敌暴龙赛》 不是厦外宇宙无敌暴暴龙战士选拔赛我不是很认可 B题逆天错误输出“N0”，喜欢我B题首A吗，那是罚时四发换来的/kk A题卡了非常久，后面才发现是没有一开始就判断奇偶，喜提6发罚时/kk H题成功证明了一个结论并且独立写了出来，爽，建议NOIP T1出H这种我能想到的题目。 还有一道魔改版的猪国杀，但是题目实际上跟猪国杀没有任何关系，直接输出4*n+m就行了，结果首A被zfl抢了，可恶 早上4道题一题都没订正，要完蛋了/kk 感觉我是打了一天的题目到晚上才找到题感，乐 **Day 9** 感觉自己码力好废 想死 下午突然就想到了昨晚模拟赛k题怎么写，昨晚打到最后唐了 真服了自己了 用for_each循环时候遇到了神奇问题 奇怪 晚上跟zxq大佬合作一起打了CCPC的重现赛，zxq实在是太厉害了 %%%%%%%%%%%%%%%%%%%。 模拟赛J题简单几何题 但我唐了连吃两发罚时，感谢xq大佬不杀之恩 [CCPC(新疆赛区)题解](https://uploadfiles.nowcoder.com/files/20241111/999991351_1731293331693/24-CCPC%E6%96%B0%E7%96%86%E7%9C%81%E8%B5%9B%E9%A2%98%E8%A7%A3.pdf) 订正昨天的简单题时候遇到了一道非常有意思的多栈维护问题。 ### **【题目描述】** 给定$n$个栈，初始都为空。 有$q$次操作，每次操作为以下三种之一： 1 push x y z：在编号为$z

的栈中加入x 个数字 y 。

2. pop x z：从第 z 个栈中弹出 x 个数，并输出最后一个数。保证操作合法。

3. put u v：依次把第 u 个栈中的数弹出并加入到第 v 个栈中。

请维护以上操作。

这道题对于每个操作维护一个Pair记录连续的数量和数字种类，然后每个Pair记录两个连接，一个往前一个往后，类似于双向链表的操作，对于每个put操作直接记录哪个连接是现在能用的即可。

Day8

破防了，多栈维护问题调了一个上午没调出来，想死

好的，下午还是调不出来，std写的跟大粪一样，无语凝噎

吃晚饭前终于调出来了 好耶

中午商赛说明会 一遇到商赛就会遇到远古情感问题 希望这次不会影响到我的NOIP

早上模拟赛直接下发std 笑不活了

感觉今天一整天状态都很不好 晚上牛客的小白月赛只打出来了A B cbh把F题写出来了 orz

今天因为情感问题状态好差 千万不要重蹈去年NOIP前的覆辙啊。

加油

晚上比赛的题解

Day7

今年早上的模拟赛简直是乱搞专题

T1是一道很典的LCS，但是题目叫做二分图匹配，然后数据范围是n \le 1e6 m \le 1e3

直接乱搞，前面小部分直接套LCS板子上去，后面的部分正着扫一遍再反着扫一遍取max，这样我们就得到了一个O(min(n,m))的逆天算法，然后直接A了，逆天数据

然后T2 cbh同学发现直接输出关键点间的最小值再加上30分的Floyd可以得到80分的高分，虽然正解也很好想，但是毕竟80分更有性价比。

T3打了半天的暴力一分没有，我大样例都过了，红温了，唐式模拟赛/kk

T4取随机数种子114515可以过掉第一个点，再加上我的乱搞可以拿到20分，无敌了

最后以180分收尾，被cbh210分偷榜了，可恶

中午玩小恐龙玩出了1584分的高分，好耶！

下午老师说早上的模拟赛的附加题是黄题，NOIP T1的难度，是怕我们T3T4都写不出来才加给我们的，都怪可恶的zfl签订了核不扩散条约，导致赛时错过了最简单的一道题（虽然我最后30分钟在T5拿了30分暴力）

然后下午和zxq看了好久的T5，最后经过老师的点拨才知道怎么写，NOIPT1难度的题都不会，可以回家种田了。

题目大意：给定一个数N和N3，请问有多少组小于P的非负整数a b c ，满足：

记 N0 = N^2+1

N1 = N0 \mod a N2 = N1+b N3 = N2 \mod c

其中，1 \le a,c \le P,0 \le b \le P,P \le 10^5

考虑枚举a 和 c，我们就可以得到一系列N1和N2的取值，由于b是非负数，所以每个大于N1的N2,都是一组可行解，二分即可。

时间复杂度 O(Plog_2P)

Day6

凌晨的cf打的令人崩溃，C之后全是数学题，根本不会写，只会写AB，可以回家种田了，晚上目睹了狼队4-1血洗富勒姆，狼也是终于崛起起来了，还目睹了tourist被周康阳偷榜，zky好闪，拜谢zky。

然后下午开始订正昨天的T5，结果写了半天调不出来，崩溃了，返校一问zxq也没调出来，那没事了。

晚上打了牛客周赛，算是一场信心赛吧。

但是我A先看错一次题目，把等差数列看成了等比数列，最逆天的是样例还过了。。。

然后B是纯纯唐式模拟，但是我打到一半思路乱了，A掉B的时候已经过去了18min

C就更逆天了，小学立体几何题，怒调半天，结果发现没有开long long，乐。切完C的时候已经过去1h了，时间都浪费在这里了。

D题一个唐式二进制枚举加深搜，没有一点难度，纯纯码量题，30minA掉。

这个时候只剩下30min了，此时zxq还没有调出来D，我看了一眼E决定直接打暴力，又过了10minzxq把D调出来了，然后直接20min写出来E题正解，tql，%%%

后面还打了F的暴力，结果F不给我暴力分，一怒之下怒了一下。

最后也是被zxq大佬拉爆了，orz

在机房启动了一把大金博，但是被三跑了/kk

要订正的：Day8订正T5、昨天的CF、牛客周赛

Day5

时间过得是真快啊，还有5天就要NOIP了

早上模拟赛1道数学3道数据结构，数据结构题是真的烂完了，根本没有独立调出来的实力，线段树根本不会打，可以回家种田了。

T1由于取模取少了，直接100 -> 30，怒拿80分，回家种田了。

下午说要有线段树专项练习，不知道能不能让我捡回来一点古早的知识记忆。

Day 4

二分答案板子

ll l = 0,r = n;
while(l < r)
{
  ll mid = l+r>>1;
  if(check(mid)) r = mid;
  else l = mid+1;
}
cout<<l;

或

ll l = 0,r = n+1;
while(l+1 < r)
{
  ll mid = l+r>>1;
  if(check(mid)) r = mid;
  else l = mid;
}
cout<<l+1;

二分找第一个小于等于x的数

int l = 0,r = n+1;
while(l+1 < r)
{
  int mid = l+r>>1;
  if(a[mid] <= x) l = mid;
  else r = mid; 
}   
cout<<l<<'\n';

早上模拟赛一道大模拟调了2h没调出来，后面才发现判非法输入的时候没判全，导致下面的查询也错了，结果我一以为大样例过不去是查询的问题，导致赛时没调出来，怒挂45分，真服了

Day3

有时候真的会被自己蠢笑

如果关掉流同步的话，就不要再用puts输出换行了！

优先用scanf和printf

喜欢我模拟赛T1 100 -> 70吗，就是因为我发现用puts输出会乱而直接把答案存在一个数组里面再输出然后就T飞了

T4也是纯唐，有个变量忘开long long了，我直接将它跟long long乘一块，精度直接爆炸

有空复习下板子

Day2

数组变量名不要用x0和y0

数组变量名不要用x0和y0

数组变量名不要用x0和y0

早上模拟赛: T3 100 -> 0

晚上老师发了一个《考前测试》，然后打开一看发现是《论持久战》？直接觉醒文科生人格，政治大题，启动！

虽然因为停课了两周知识点都忘得差不多了表述十分狗屎，致歉lsl

习近平总书记曾以《论持久战》为例,指出要“善于从战略上看问题、
想问题”。请根据材料谈谈《论持久战》对我们“看问题、想问题”有什么
启示。
5.1.不能主观、片面的看问题。世界是物质的，不随人的意志转移。世界的根本本质在于其物质性，物质是运动的，运动是有规律的，一切违背客观运动规律的事物终将消散。要坚持马克思唯物辩证主义，反对唯心主义，反对一切形式的有神论；2.对于事物的发展，起决定因素的是人。在客观规律面前，人不是无能为力的，我们可以发挥主观能动性，能动地认识世界，能动地改造世界。符合客观规律的实践将将主观见之于客观，推动事物的发展。3.矛盾就是对立统一。矛盾具有普遍性，事事有矛盾，时时有矛盾。矛盾具有同一性，矛盾双方在一定条件下可以相互转化。一切要以时间、地点、条件为转移。4.事物的性质由主要矛盾的主要方面组成。我们要坚持重点论和两点论的统一，既要看到事物的主要矛盾，又不能忽视事物的次要矛盾，既要抓住主流，又不能忽视支流。唯物论的两点论是有重点的两点论，而不是均衡论；重点论是有主次的重点论，而不是一点论。

考前两天在机房练习文化课，我们信竞队也是无敌了

马上NOIP了 但我还不想退役啊啊啊啊啊啊啊啊啊啊啊

Day1

尽人事 听天命 要来力

早上的《省选模拟赛》zxq大佬直接AK，我因为一些唐氏小错误挂成了70分，orz zxq大佬。

然后也是出征啦，跟zxq大佬在一个房间，orz，希望能rp++

感谢蔡老师的恩情指导

NOIP rp++