首页 > 其他分享 >NOIP2024 模拟赛 #12

NOIP2024 模拟赛 #12

时间:2024-11-01 17:35:58浏览次数:1  
标签:10 12 20 log DP 枚举 NOIP2024 做法 模拟

学长出的模拟赛,风格挺好。

赛时

8:00 T1 会了一个 \(O(n^2\log n)\) 的做法,先写一下,看看能不能过样例。

8:20 过了小样例,大样例跑得慢但是是对的。

8:40 发现一个好的做法,可以枚举 \(c_i\) 最小的那一天选了哪个,再枚举 \(k\) 天,这样纯枚举复杂度是 \(O(k)\) 的。但是有些细节不太好处理。

现在转化成了一个经典问题,很多次遇到了,但我还是不会。

欸,好像会了。时间复杂度 \(O(k\log n)\)。贪心不好写,枚举解决!

9:05 ok,大样例全过了。最慢的点 \(0.4\) s。

T2 怎么还有 SPJ,这么神秘。下发了 checker 但是不知道怎么用。

9:35 T3 会了 \(O(m^n)\) 的爆搜,有了 \(15\) pts。

完了,不会 \(2^n\) 做法。

T4 一次旅行不可能经过很多的点,这样很浪费。也不可能经过一个点,

T4 直接模拟旅行不太可做,可以将题意转化为分成若干个连通块,而这是树,转化为哪些条边需要断掉。这样可以 \(2^{n-1}\) 枚举,计算每个连通块的贡献。

也许可以树形 DP,设 \(dp_i\) 为断掉与父亲的边时 \(i\) 子树内的答案,但是我不会转移,唐完了。

10:25 T4 的 \(10\) pts 写完了。

一次旅行经过的点数不可能大于 \(3\),也就是每个连通块的大小小于等于 \(3\),也不可能是 \(1\)。

欸,结论假了,寄。

\(10\ 1\ 1\ 1\ 11\) 这样,\(5\) 个数全选上是最优的。

10:55 把链 \(O(n^2)\) 的性质写了。

11:30 T2 通过找大样例规律拿了输出方案数的 \(20\) pts。

又写了 \(n=1\) 的分。

想冲一下 \(n,m\le 4\),打算手玩。

玩得我头晕了,还有两种情况没写,不写了。

寄。

估分:\(100+28+15+20=163\)。

得分:\(100+28+15+20=183\),rank 2。

赛后

T1 怎么除了我 A 掉的做法都是一样的啊,我就这么独特(。

T2 可以手玩一下发现一下消除 \(3\) 行或 \(3\) 列,感觉如果不考虑证明该做法最优还是简单的,但是细节肯定不少。

T3 容斥 + DP,赛时没写出 \(O(n^4)\) 的做法,亏大了。

T4 树形 DP,朴素 \(O(n^3)\)。然后 \(O(n\log n\log V)\) 的做法是一个 dsu on tree 加权值线段树,挺对的。

\(O(n\log V)\) 的做法是线段树合并优化 DP,很可订正。

感觉把状态列出来,再加上朴素转移,很困难。之后还是比较简单的。

总结

要多玩样例,找找规律,发掘性质,多拿性质分,从性质中推出正解。

对于数学还是要加强。

标签:10,12,20,log,DP,枚举,NOIP2024,做法,模拟
From: https://www.cnblogs.com/zhujiangyuan/p/-/NOIP2024_12

相关文章

  • 11.01模拟赛
    T1把所有的薯片按热量排序,\(l,r\)表示选取的区间的左右端点,当区间中的种类数等于\(k\)时,这个区间合法,更新答案并\(l\)++,否则\(r\)++,直到\(r=n\),最后的话要看\(l\)能否往上加,开始没有写,所以最后一个大样例一直不过,调了20min左右。T2构造题,感觉很难啊,就想着先找最多数量......
  • 2023CSP-S 复赛模测(日记和×××) - 模拟赛记录
    Preface这套题说实话挺水的,它的水不仅仅是在数据上(实际得分比期望得分高了\(50+\)分),而且正解也神奇得不像个正解(全是各种分类讨论卡子任务的,感觉像是出题人水平不够一样)。日记和最短路(shortway)(话说最短路的英语不应该是shortestpath吗?)题目中给了一个DAG,然后要求用两种方......
  • 2024.10.7 模拟赛 多校3
    模拟赛水题场。T1colorful签。感觉题挺好,正难则反,找出四角都相同的。在这两排有6个四角相同的矩形对于两排来说,我们只需要记录相同的列的个数,然后能直接算出个数。发现桶排每次清空复杂度太高,考虑每次只开一排的桶,只会有\(n\)个。code#include<bits/stdc++.h>u......
  • 2024-11-1校内模拟赛总结
    前言:从下了早读一直打到吃午饭,\(4h\)左右的时间,\(IOI\)赛制,\(6\)道\(ABC203\)、\(204\)的\(CDE\)题,\(318\)分。赛时:T1:水,直接模拟即可。\(100\)分。T2:中位数二分答案,有点难,但之前写过,也是直接拿下了啊。100分。T3:也是模拟,但是我开\(map\)存的是\(pair<int,int>......
  • MindSponge分子动力学模拟——增强采样(2024.11)
    技术背景关于增强采样(EnhancedSampling)算法的具体原理,这里暂不做具体介绍,感兴趣的童鞋可以直接参考下这篇综述文章:Enhancedsamplinginmoleculardynamics。大致的作用就是,通过统计力学的方法,使得目标分子的CV(CollectiveVariables)具有一个尽可能大的采样子空间,并且可以将其还......
  • 快来了解三石峰新品N12振动信号采集卡
        本产品是三石峰科技的12通道智能数据采集器,以下简称SSF-Vib-N12。SSF-Vib-N12旨在帮助用户对工业生产中的设备健康状况进行监测与诊断,降低因设备故障对生产过程产生的影响。SSF-Vib-N12输入同时兼容IEPE、ICP传感器,使用16位分辨率ADC对12路信号同步采集,并且支......
  • Kafka python模拟整理
    模拟需要用到kafka的包,需要pip安装,但注意pipinstallkafka不适用于python3.x的某个版本以上,均已经换成kafka-python推荐使用版本2.0.2,目前稳定pip没有的问题如果是windows环境,可通过直接去官网下载python版本,指定版本会顺带安装pip如果是linux环境,有节点是不带pip的,可使用yu......
  • 【C++】string 类模拟实现:深入探索字符串操作原理
     快来参与讨论......
  • P11228 [CSP-J 2024] 地图探险 题解
    模拟第一眼,可能有人回想起dfs.但因为起点终点,并且走的步数都告诉你了,所以直接模拟就行.注意起始点也算被走过,所以可以用一个标记数组,判断当前格子有没有被走过.代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;int......
  • 笔试真题——机器人拧魔方模拟
    说明:根据遗留的记忆写出来了此篇文章,可能与原文解释有部分出入,但总体思路一致。题目说明:YYYYRRRRWWWWOOOOGGGGBBBBUUL'第一行为输入为对应F,R,B,L,U,D面的元素颜色第二行输入为翻转的标识符标识符有:F、F'、R、R'、B、B'、L、L'、U、U'、D、D'。分别为对应明的顺时针......