noip2019专题

【NOIP2019普及组复赛】题2:公交换乘

题2:公交换乘 【题目描述】 著名旅游城市 B B B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案: 1、在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟,在有效期内可以消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟,即: t b u s − t s u b w a y

noip2019集训测试赛(四)A.fibonacci

Description 给定一个长度为 N 的序列 A={a1,a2,…,an} . M 次操作, 每次操作形如下面两种中的一种: 1 l r x 将 a l , a l + 1 , . . . , a r a_l,a_{l+1},...,a_r al​,al+1​,...,ar​ 都加上 x ; 2 l r 求 ∑ i = l r f ( a i ) m o d ( 1 0 9 + 7

noip2019集训测试赛(三)B.mex

Description 给你一个无限长的数组,初始的时候都为0,有3种操作: 操作1是把给定区间[l,r] 设为1, 操作2是把给定区间[l,r] 设为0, 操作3把给定区间[l,r] 0,1反转。 一共n个操作,每次操作后要输出最小位置的0。 Input 第一行一个整数n,表示有n个操作 接下来n行,每行3个整数op,l,r表示一个操作 Output 共n行,一行一个

noip2019集训测试赛(六)B.匹配

Description Rikka有一张无向联通图 G=⟨V,E⟩ ,其中顶点数 |V|=n ,边数 |E|=n−1 。Rikka可以选择 E 中的一些边删掉。显然这有 2n−1 种方案。 Rikka想知道,有多少种方案使得删边后残余图中的最大匹配数恰好为 m 的倍数。由于答案可能很大,请输出答案对 998244353 取模的余数。 边集 S 是图 G=⟨V,E⟩ 的匹配当且仅当 S 中任意

noip2019集训测试赛(六)C.恐怖分子

Description 有一个 n×m 的网格和 q 名旅行者。初始时第 i 名旅行者在网格 (xi,yi) 上。 不幸的是,这 n×m 个网格中,有 K 个网格里是有恐怖分子的,所以这 K 个网格是不安全的。为了安全起见,旅行者可以从初始坐标 (x1,y1) 走到网格 (x2,y2) 当且仅当对于所有满足 min(x1,x2)≤x≤max(x1,x2),min(y1,y2)≤y≤max(y1

noip2019集训测试赛(二)A.余数

Description Input Output Solution 整除分块:https://blog.csdn.net/gdhy9064/article/details/90112836 通过整除分块,我们可以得到对于每个x ⌊ n x ⌋ \left\lfloor\frac{n}{x}\right\rfloor ⌊xn​⌋的值,那么可以转化原式: ∑ i

noip2019集训测试赛(十一)A.管道(pipe)

Description 给你一个城市下水道网络图,你需要选出一些管道,使得在只使用这些管道的情况下,令整个网络联通,并且花费最小。 网络图可以看做是无向连通图,有n个节点和m条边,每条边连接ui和vi,选择的花费是wi。 不巧的是,由于某些原因,现在市政局要求选定某条特定的边管道,你的任务是求出对于某一条边,在选择这条管道的前提下的最小花费。 Input 第1行包含两个整数n,m,表

Noip2019暑期训练1

题目名称 时空定位 棋子移动 高精度乘法 数独游戏 存盘文件名 location piece mul sudoku 输入文件名 location.in piece.in mul.in sudoku.in 输出文件名 location. out piece.out mul.out sudoku.out 时限 1s 1s 1s 1s 内存限制