首页 > 其他分享 >8.1 NOIP 模拟赛总结

8.1 NOIP 模拟赛总结

时间:2024-08-02 17:50:27浏览次数:16  
标签:8.1 发现 NOIP 可以 然后 往外拓 模拟

8.1 NOIP 模拟赛总结

T1

给你一个含有 \(n\) 个问号的形如 max(?,max(?,min(?,?))) 的表达式,将 \(1...n\) 填入 \(n\) 个问号中,求表达式一共有多少种可能的答案。

首先写的 \(10\ pts\) 的全排列,然后想了一会想不出来,就直接扬了。

直接是二叉树,很神奇。

T2

首先想暴力。

发现每回选一个点往外拓,然后比他小的直接吃掉。

然后发现直接暴力的话还要考虑返回,很麻烦。

过了 \(10\ min\) 发现可以用优先队列保证不用返回。

写完就交上去了。

然后发现两个规律:

  • 如果这个点可以统一,那么和它相连的点中比他大的点也可以统一,然后就可以一步一步往外拓。

  • 如果这个点不可以统一,那么和它相连的点中比他小的点也可以统一,然后就可以一步一步往外拓。

  • 考后发现:在这个点拓展的路径上也满足这个规律。

然后加上这个规律交上去,赛后发现过不去;

然后怕暴力写挂就码了个 \(Subtask\ 2\) 。

\(Subtask\ 2\)

就是优化枚举顺序加个并查集。

关于 \(\texttt {ZXK}\) 看到排序和并查集想到重构树这件事……(呜呜呜,我为什么没想到 \(QwQ\))

Kruskal I love You

T3

只看有一组的情况,胡推了个 \(5\ pts\) 柿子。

T4

没看……懂……

标签:8.1,发现,NOIP,可以,然后,往外拓,模拟
From: https://www.cnblogs.com/whrwlx/p/18339291

相关文章

  • 洛谷 P1080 [NOIP2012 提高组] 国王游戏
    一道非常有挑战性的题目(~太难了~)。这题我们可以用贪心来做。思路:首先我们定义一个结构体struct,里面放的是每个人左手和右手的数字。接着我们需要一种排列方式,使得获得奖赏最多的大臣,所获奖赏尽可能的少;这句话听起来是不是听绕口?意思就是说得到奖赏数量最多,但加起来的总奖赏......
  • Day 26 - 模拟赛
    热门景点(hot)题目描述输入格式输出格式\(\text{input1}\)10517409488246628223678\(\text{output1}\)YNYNY数据范围#include<iostream>#include<cstdio>#include<ctime>usingnamespacestd;#defineMAXN5000005intread......
  • SPONGE常用教程:蛋白+配体模拟3
    前序课程1前序课程2目录应用场景简述;-[Done]DSDP:蛋白-配体对接;-[Done]XPONGE:蛋白-配体建模,加溶剂;-[Done]SPONGE:能量极小化-NVT-NPT-正式模拟;-[Done]XPONGE:数据简单后处理。5.XPONGE:数据简单后处理经过1ns的SPONGE分子动力学模拟,得到了轨迹文件"mdcrd.dat......
  • P1006 [NOIP2008 提高组] 传纸条(线性 dp)
    link真的,第一次听懂了闫氏dp分析法,从集合的角度分析首先,两条路径,很朴素的状态表示就是定义\(f[x_1,y_1,x_2,y_2]\)来表示两条路径分别走到当前点的最大值但是,这样状态数量就达到了6.25e7,有点极限tip:动态规划的时间复杂度一般可以表示为状态数量与状态计算量的乘积注意......
  • [20240802]NOIP比赛总结
    比赛链接比昨天好多了,谢天谢地。好消息:明天放假。坏消息:后天开学。好消息:没暑假作业。坏消息:拉了一堆课。赛时先写了T1暴力,然后一眼觉得正解是二进制位运算,所以先跑了。T2题目给出了正解,照着打,过了50pts,然后简单一想,过掉了。T3写了暴力,先跑。T4写了暴力,然后开始推性质......
  • 2024.8.1 总结(集训)
    今天和昨天都是学图论。wwlw给我们讲了Tarjan求强连通分量、(有向图)缩点、欧拉路径和欧拉回路、2-SAT和某个奇妙的容斥DP题。感觉有收获,但是没有理解透。感觉lr好强啊,好多题好像都有思路。xwb也好强啊,在洛谷团队里的图论题单里rank1,1200分。我今天的主要问题还是理解......
  • 2024.8.1随笔
    前言今天下午最后的时间不想写题了,于是就准备拿来随便写写什么。上午讲的是一些图论中常见的考点的应用(大概),题目难度都在蓝到紫,感觉也不是完全不可做,或多或少都能有一些想法,有时能想到点子上,但也常常乱整。今天讲了有关连通分量、欧拉路、2-sat等知识的题,其中2-sat我全部遗......
  • 8.1 星露谷真好玩
    在体验星露谷物语的过程中,我体会到规划对于农场发展的重要性。刚开始时,由于缺乏经验,农场布局常常不尽如人意,不仅浪费空间还影响效率。然而,随着对游戏的摸索和熟悉,我可以更合理的安排作物种植区域、动物棚舍以及设施的位置,使农场运作更加高效有序。这一过程让我联想到项目管理和......
  • 洛谷 P1052 [NOIP2005 提高组] 过河
    原题https://www.luogu.com.cn/problem/P1052题目描述在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:1,⋯,L......
  • 2024.8.1 test
    A\(n\)个点的完全图,\(i\toj(i<j)\)的边权是\(u_j-u_i\),问最小生成树。\(n\le3e5\)。考虑boruvka算法。boruvka算法是重复以下过程,直到只有一个连通块。找到所有连通块的连向外面的最小边,并把这些边加入最小生成树。不难发现这是最多做\(\logn\)次的。我们现在考虑......