Logic
向着梦想进发
Logic's Blog

【个人VP】2022csp-s2

虽然没参加,但是还是记录一下。
没时间写代码,只是瞟了一眼题目想了一下思路而已。
CCF出题真的长啊,读题就花了我好久...

T1 假期计划

第一眼感觉是 $O(kn^2)$ 的 dp,但好像消除不了后效性
考虑暴力:Floyd+全排列 $O((k+2)n^2+n^4)$. 或许40pts?
又发现k=0,再加30pts?

正解是折半搜索+剪枝?

T2 策略游戏

一开始还以为是博弈论,结果只是简单的分类讨论+线段树
鉴定为 "水"

T3 星战

大意好像是有n个点m条单向边,u的入边称为u的虫洞
打击方式有两种 1.边 2.u&u的虫洞
反攻条件 1.缩点后只有一个强连通分量 2.每个u都只有一个出边

只想的到暴力:每次询问把修改的点标记一下,跑一次tarjan $O((n+m)q)$
或许能拿 40pts?

T4 数据传输

建图时将能直接连接的点加一条边
然后每次询问都跑一遍最短路?
$O(Qnlog_2n)$ 44pts?

今年的题还是很好拿分的?(还是我的错觉?)

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/2022csp-s2/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可

发表回复

textsms
account_circle
email

Logic's Blog

【个人VP】2022csp-s2
虽然没参加,但是还是记录一下。
扫描二维码继续阅读
2022-11-05