CSP/NOIP 2024 游记
发表于
|
0
|
阅读次数
211
??? - 9.20开摆。9.21初赛日。下午去考场,随便考。打开试卷,选择好简单,看阅读程序,第二篇想了想,其他好简单。看完型,全nm是 A。速通。写语文随笔。晚上对答案 96。
P4694「PA2013」 Raper
你需要生产 $k$ 张光盘。每张光盘都要经过两道工序:先在 A 工厂进行挤压,再送到 B 工厂涂上反光层。
你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间,每天可以先送一张光盘到 A 工厂(或者不送),然后再送一张已经在 A 工厂加工过的光盘到 B 工厂(或者不送),每家工厂一天只能对一张光盘进行操作,同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。
求生产出 $k$ 张光盘的最小花费。$1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant a_i, b_i \leqslant 10^9$。
P6295 有标号 DAG 计数
对 $n$ 个点有标号的有向无环图进行计数,要求:弱连通图(所有的有向边替换为无向边后的图为连通图)。输出答案对
$998244353$ 取模的结果。$1 \le n \le 10^5$。
CF1588F Jumping Through the Array
题目描述你有个长度为 nnn 的数组 aaa 和一个长度为 nnn 的排列 ppp,对于每一个 iii 有一有向边 (i,pi)(i,p_i)(i,pi)。有如下三种操作:1 l r 询问 ∑i=lrai\sum_{i=l}^r a_i∑i=lrai。2 v x 将所有 vvv 能到达的节点所
CF81E Pairs
题目描述给定一颗黑白内向基环树,你要对其进行匹配,让匹配数最多的同时最大化异色匹配。并且给出一种方案。1≤n≤1051 \le n \le 10^51≤n≤105。思路暴力考虑流。对于一颗普通的树,进行黑白染色变成二分图,跑网络流即可得到最大匹配。如果是异色匹配费用流即可。对于这道题,不妨直接断开环
CF1307F Cow and Vacation
有一颗 $n$ 个节点树,其中有 $k$ 个点是关键点。现在有 $m$ 次询问,每次询问是否存在一条 $u \to v$ 的路径(不一定是简单路径),使得路径上任意两个关键点并且 $u,v$ 和路径上与其最近的关键点的距离小于等于 $k$。
$n,m,k \le 2\times10^5$。