首页 > 其他分享 >20231013

20231013

时间:2023-10-13 19:25:34浏览次数:45  
标签:20231013 10 00 终点 25 线段 数据结构

20231013 NOIP#19(33daiOJ)总结

时间安排

7:25~8:00

看题,\(A\) 一点不会,\(B\) 会 \(15\) 分,\(C,D\) 各会一档。

7:50~8:00

写 \(D\) 的第一档。

8:00~8:10

写 \(B\) 的前两档。

8:10~8:40

写 \(C\) 的第一档。

8:40~9:00

想到写了 \(B\) 的 \(n^2\)。

9:00~10:25

会了 \(A\) 题,但是因为 \(upper_bound\) 学艺不精没过大样例,调了半天改了线段树二分。

10:25~11:00

\(C\) 题尝试拼包。

11:00~11:50

都写完了,试图切 \(B\) 失败。

总结反思

  • 考试捡有把握的写

题解

A.数据结构

找第一小于 \(x\) 的位置和区间询问最大值,数据结构随便搞。

B.贪心+数据结构

合并一定是 \(n\) 此操作,只考虑交换要多少次。
如果一个线段(被)包含于另一个线段,那么显然这两个线段不会产生交换次数,所以即求在一个区间内有多少线段只出现了一个端点。
那么可以将其按左端点排序,询问区间内有多少线段的右端点,数据结构维护即可。

C.构造

当 \(h=2\) 时问题很好解决,手推一点就会了。
如果 \(h>2\) 且 \(w=2\) 那么可以翻转坐标,变成 \(h=2\) 的情况解决。
如果 \(h>2\) 且 \(w>2\) 判断目标点是否在 \(S := \lbrace (1, 1), (2, 1) (3, 1), \ldots, (h, 1), (h, 2) \rbrace\) 集合内。如果在则翻转坐标变成不在的情况,如果不在则将 \(S\) 集合覆盖并垂直翻转。

D.计数DP

设 \(f[i][j][k]\) 表示走到第 \(i\) 步,已经扩展了 \(j\) 种点,包含 \(1\) 号点的最大的强连通子图的点数为 \(k\) 时的方案数。
起点都在上次移动的终点处,当移动时,终点就有三种情况:
\(1.\) 终点属于未拓展的点 \(f[i+1][j+1][k]+=f[i][j][k]\times (n-j)\)
\(2.\) 终点在不包含 \(1\) 的强连通里 \(f[i+1][j][k]+=f[i][j][k]\times (j-k)\)
\(3.\) 终点在包含 \(1\) 的强连通里 \(f[i+1][j][j]+=f[i][j][k]\times k\)
初始 \(f[0][1][1]=1\) ,答案为 \(f[m][n][n]\)。

标签:20231013,10,00,终点,25,线段,数据结构
From: https://www.cnblogs.com/programmingysx/p/17762942.html

相关文章