首页 > 其他分享 >10.5 模拟赛(NOIP十三连测 #11)

10.5 模拟赛(NOIP十三连测 #11)

时间:2024-10-05 17:34:16浏览次数:15  
标签:11 大样 10.5 NOIP 连测 DP 模拟

2024--梦熊&太戈--NOIP十三连测 #11【订正】 - 比赛 - 梦熊联盟 (mna.wang)

复盘

赢麻了(?)

老师说照着 \(300\) 分打。

顺序开题。T1 读懂题后模拟了一下样例,发现答案就是 $n - $ 连通块???快速写完了代码发现大样例全过了。此时 8:05。

T2。一眼 DP。但是 \(n \le 10^6\) 所以放弃了。先写了 \(n^2\) 的 \(30\) 分 DP。猜测正解是贪心,但其实不是。

有两个特殊性质。用暴力程序模拟了一下也做出来了。

T3。没有思路。

T4。暴力是最短路,但是只会这 \(20\) 分。

尝试做特殊性质。打表发现找规律未果遂放弃。其实不用找规律直接做也不难。

T2 还剩 30 分不重要了。所以做 T3。

发现有 \(48\) 的暴力分,不是很难。冲正解。

发现一个美妙的性质。模拟了一会大样例(很强对吧),但是还找不到一个通用的方法。

但是直接爆搜加上剪枝可能会跑的特别快,起码 \(48\) 分能拿到。于是爆搜启动。

写了 1e4514min 终于过大样例了。但是跑了 50s。

卡常。发现是备份用时太长了。换了一种备份方法。

跑大样例。0.8s????

哦 WA 了。调了 1e4514min 后过了。还是 0.8s。

非常非常好的爆搜,是我的大脑旋转。这样应该能拿 \([64,100]\) 分。

调完还剩 10min。检查。

最后一分没挂!\(100+70+64+20=254\)。其实 T4 还有 \(10\) 分是不难的,但光想偷懒打表找规律了。

总结

好的:

  • 爆搜没写挂。

差的:

  • 不要偷懒。

知识点

  • T1:并查集。
  • T2:DP。
  • T3:性质。

题解

A.

B.

C.

标签:11,大样,10.5,NOIP,连测,DP,模拟
From: https://www.cnblogs.com/2huk/p/18448149

相关文章

  • NOIP 前 dp 做题小记
    NOIP前dp做题小记[BJOI2019]排兵布阵设\(f(i,j)\)表示在前\(i\)个城堡中总共派遣\(j\)个士兵时,可以获得的最大分数。初始化:\(\forall0\lej\lem\),\(f(0,j)=0\)答案统计:\(ans=f(n,m)\)转移:\(f(i,j)=\max_{0\lek\lej}f(i-1,j-k)+g(i,k)......
  • Leetcode 1011. 在 D 天内送达包裹的能力
    1.题目基本信息1.1.题目描述传送带上的包裹必须在days天内从一个港口运送到另一个港口。传送带上的第i个包裹的重量为weights[i]。每一天,我们都会按给出重量(weights)的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在days天内将传送带上的所......
  • P9611 题解
    题目大意从题目可知,本题要求求出\(l\simr\)的因子个数和。题目分析我们可以将这个问题分解为两个问题,变成求\(1\simr\)的因子个数和减去\(1\siml-1\)的因子个数和,然后我们考虑如何求\(1\simn\)的因子个数和首先,如果正着做很难的话,我们可以考虑反着做。对于一个数\(......