noip2023专题
NOIP2023模拟16联测37 大眼鸹猫
题目大意 有两个长度为 n n n的序列 a , b a,b a,b，这两个序列都是单调不降的。 你可以对 a a a进行不超过 m m m次操作，每次操作你可以选择一个 i i i满足 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n，然后选择一个整数（可以是负数） x x x，将 a i a_i ai加上 x x x，这次操作要花费 x 2 x^2 x2的代价。 在操作的过程
NOIP2023模拟16联测37 总结
NOIP2023模拟16联测37 总结 T 1 T1 T1 求有多少区间的异或和为 k k k 的因子， n , k ≤ 1 0 5 n , k \le 10^5 n,k≤105 。看到异或就想到了前几天的拿到按位考虑的题目，想了半小时没想到。突然想前缀和，对每个 k k k 的因子记录一下 a ⊕ k a \oplus k a⊕k 的数量就好了 。 T 2 T2 T2 每次可以删去
NOIP2023模拟16联测37 D. 小猫吃火龙果
NOIP2023模拟16联测37 D. 小猫吃火龙果 文章目录 NOIP2023模拟16联测37 D. 小猫吃火龙果题目大意思路code 题目大意 有 n n n 个物品 A A A , B B B , C C C ， A A A 吃 B B B， B B B 吃 C C C， C C C 吃 A A A，有两种操作，给 [ l , r ] [ l , r ]
NOIP2023模拟13联测34 B.competition
NOIP2023模拟13联测34 B.competition 文章目录 NOIP2023模拟13联测34 B.competition题目大意思路code 题目大意 现在有 n n n 个区间 [ l i , r i ] [l_i , r_i] [li,ri] ，现在问你选取若干的连续的区间的区间并的大小的和。 思路 设 p r e i , j pre_{i ,
NOIP2023模拟1联测22 爆炸
NOIP2023模拟1联测22 爆炸 题目大意 自己看 思路 当一个炸弹被引爆后，它的方向是固定的。如果被竖着引爆，那么应该选择横着引爆，否则选择竖着引爆，这是显然 的。 考虑对于每个炸弹 ( i , j ) (i , j) (i,j) 将第 i i i 行和第 j j j 列连边 对于每个水晶 ( i , j ) (i , j) (i,j) 如果 i i i 行和
NOIP2023模拟13联测34 competition
题目大意 有一场题目数量为 m m m的比赛，有一个团队想要来参加。 这个团队有 n n n个选手，编号为 i i i的选手能做第 l i ∼ r i l_i \sim r_i li∼ri道题，每题他都有 100 % 100\% 100%的概率做出来。 这个团队会随机派出一只队伍来参加这个比赛。 因为编号相邻的人关系更好，默契度也更高，所以一个团队派出的队伍一直都是编号为连续区间的选手
NOIP2023模拟12联测33 滈葕
题目大意 给定一个有 n n n个点 m m m条边的 0 / 1 0/1 0/1权有向图，你要给每个点赋予 A B C D ABCD ABCD中的一个字母使得每条有向边 ( u , v , w ) (u,v,w) (u,v,w)都满足 w = 1 ⇐ ⇒ ( a u , a v ) ∈ { ( A , D ) , ( A , B ) , ( B , D ) , ( B , A ) ,
NOIP2023模拟12联测33 总结
NOIP2023模拟12联测33 总结 文章目录 NOIP2023模拟12联测33 总结比赛过程正解A. 构造题目大意思路 思路B.游戏题目大意思路 C. 数数题目大意 D. 滈葕题目大意思路 总结 比赛过程 先看了一眼 T 1 T1 T1 ，发现又是恶心构造题，果断跳过。 T 2 T2 T2 期望题，这么恶心吗，果断跳过。 看看 T 3 T3 T3 发现好像有
NOIP2023模拟12联测33 D. 滈葕
NOIP2023模拟12联测33 D. 滈葕 文章目录 NOIP2023模拟12联测33 D. 滈葕题目大意思路code 题目大意 思路 放一段题解的材料 ABO 血型系统是血型系统的一种，把血液分为 A,B,AB,O 四种血型。血液由红细胞和血清等组成，红细胞表面 有凝集原，血清内有凝集素。根据红细胞表面有无凝集原 A 和 B 来划分血液类型。红细胞上只有凝集原
NOIP2023模拟12联测33 B. 游戏
NOIP2023模拟12联测33 B. 游戏 文章目录 NOIP2023模拟12联测33 B. 游戏题目大意思路code 题目大意 期望题 思路 二分答案 m i d mid mid ，我们只关注学生是否能够使得被抓的人数 ≤ m i d \le mid ≤mid 那我们就只关心 a > m i d a > mid a>mid 的房间就行了。 设学生有
NOIP2023模拟12联测33 构造
题目大意 给定一个非负整数 n n n，请构造出一个不超过 40 × 40 40\times 40 40×40的矩阵，每个位置填 r r r、 y y y、 x x x三者之一，使得连续的三个格子按顺序构成字符串 r y x ryx ryx恰好 n n n个。 这里连续的是指同一行、同一列或者同一 4 5 ∘ 45^{\circ} 45∘度斜线，方向任意（共 8 8 8个方向）。 0 ≤
NOIP2023模拟11联测32 百日草
题解 有一个有 n n n个点 m m m条边的有向图，每条边上有一个正整数边权，你需要顺着图上的有向边从 1 1 1号点走到 n n n号点。 假设你经过的边边权依次为 w 1 , w 2 , … , w t w_1,w_2,\dots,w_t w1,w2,…,wt，则你的疲惫程度为 max i = 1 t i ⋅ w i \max\limits_{i=1}^ti\cdot w_i
NOIP2023模拟10联测31 涂鸦
题目大意 有一面由 n × m n\times m n×m个格子组成的墙，每个格子要么是黑色，要么是白色。你每次将会进行这样的操作：等概率随机选择一个位置 ( x , y ) (x,y) (x,y)和一个颜色 c c c（黑色或白色），（ 1 ≤ x ≤ n , 1 ≤ y ≤ m 1\leq x\leq n,1\leq y\leq m 1≤x≤n,1≤y≤m，选择任意 ( x , y , c
NOIP2023模拟10联测31 游戏
题目大意 Alice \text{Alice} Alice和 Bob \text{Bob} Bob在玩一个游戏：有一个由正整数组成的集合 S S S，两人轮流从中选数， Alice \text{Alice} Alice先手。每次一个人可以从当前集合中选一个数 x x x，把 x x x以及 x x x在集合中所有的因数从集合中删除，注意 x x x必须在集合中。当一个人无法选数（也就是集合为空
NOIP2023模拟9联测30 D. 金牌
NOIP2023模拟9联测30 D. 金牌 文章目录 NOIP2023模拟9联测30 D. 金牌题目大意思路code 题目大意 有一棵 n n n 个节点的树。 假设一条路径的长度为 d d d ，那么这条路径的价值为 2 d 2^d 2d 现在有 k k k 个询问，每次给定两个整数 x , y x , y x,y ，询问所有同时通过顶点 x x x 和
NOIP2023模拟9联测30 总结
T1 一眼看去是水题，发现当 μ ( n ) \mu(n) μ(n) 不为零，就是 − 1 -1 −1，于是打了 miller_rabbin，又分解质因数（其实可以不用 miller_rabbin）。用时 20min。 T2 分析了性质，发现数字 6 6 6 很特殊，想到枚举 6 6 6 在哪些位置，用 dp 求出方案数。n^3 过不了，后面又打了部分分。用时 1h。赛后发现只需要固定
NOIP2023模拟9联测30-华二
Ayano \text{Ayano} Ayano 喜欢 GCD。 现在她有一个长度为 n n n 的数列 A = ( a 1 , ⋯ , a n ) A=(a_1,⋯,a_n) A=(a1,⋯,an)，其中 1 ≤ a i ≤ 9 1\leq a_i \leq 9 1≤ai≤9。对于其中相邻的两项的 a i a_i ai 和 a i + 1 a_{i+1} ai+1 ，满足
NOIP2023模拟7联测28 花之舞
题目大意 有一个花园，每朵花可以表示为平面直角坐标系上的 N N N个点，第 i i i个点的坐标为 O ( x i , y i ) O(x_i,y_i) O(xi,yi)。定义两朵花之间的距离为它们的切比雪夫距离，即 d i s ( u , v ) = max ( ∣ x u − x v ∣ , ∣ y u − y v ∣ ) dis(u,v)=\max(|x_u-x_v|,|y_u-
NOIP2023模拟8联测29 蛋糕
题目大意 有一块二维蛋糕，它可以从左到右分成 n n n列，每列高为 a i a_i ai。对于每一列，又可以从下到上分为 a i a_i ai块，并且最上面的权值为 1 1 1，从上到下的权值依次加 1 1 1。每一列的最上面的权值为 1 1 1的块上有奶油。 121312423153412 你现在要把这个蛋糕分为若干个矩形，要求每个矩形上都有奶牛，即每个矩形要包含至少一个权值为 1
NOIP2023模拟6联测27 旅行
题目大意 有一个有 n n n个点 n n n条边的无向连通图，一开始每条边都有一个颜色 c c c。 有 m m m次操作，每次操作将一条两个端点为 x , y x,y x,y的边的颜色修改为 c c c。求每次修改之后，图中有多少个颜色相同的连通块。 一个颜色相同的连通块指的是一个由一些相同颜色的边组成的连通块。 有 T T T组数据。 1 ≤ T ≤ 10 , 3 ≤ n , m
NOIP2023模拟7联测28 距离
题目大意 给一棵 n n n个节点的无根树，每条边都有一个边权 w i w_i wi。令 d i s ( x , y ) dis(x,y) dis(x,y)为点 x x x到点 y y y的距离。 你需要维护一个初始为空的点对集合 S S S，有 m m m次操作，每次操作有两种类型： 1 a b往 S S S中插入点对 ( a , b ) (a,b) (a,b)2 x y查询下面的式子并
NOIP2023模拟6联测27 无穷括号序列
题目大意 小 C C C有一个括号序列 A A A，其长度为 m m m，且序列元素只包含左右括号。他想生成一个无限长的括号序列 B B B，由于 B B B的长度为正无穷，所以其下标可以为任意整数（可以为负）。为了由 A A A生成 B B B，小 C C C采用如下方式： { b i = a i , 0 ≤ i < n b i = b i − n , i ≥ n b i = b i +
NOIP2023模拟6联测27 C. 点餐
NOIP2023模拟6联测27 C. 点餐 题目大意 有 n n n 种菜品，每样菜品有 a i , b i a_i , b_i ai,bi 假设有某位顾客点了 k k k 样菜品，那么价格为 ∑ i = 1 k a p i + max i = 1 k b p i \sum_{i = 1}^k a_{p_i}+\max_{i = 1}^kb_{p_i} ∑i=1kapi
NOIP2023模拟5联测26 零二
题目大意 有一个长度为 n n n的序列 A A A，你可以将 A A A中的元素进行重排得到一个新的序列 B B B，规则如下： 令 B B B初始为空，同时维护一个初始为空的小根堆 T T T，然后进行以下两类操作各 n n n次： 将当前 A A A的第一个元素删除并加入小根堆 T T T中将小根堆的堆顶删除并加入 B B B的末尾，需要保证 T T T非空 操作的顺序是任意的，问总
NOIP2023模拟5联测26 零
题目大意 完全无向图是指任意一对顶点间都有边连接的简单无向图， n n n个结点的完全无向图有 M = n ( n − 1 ) 2 M=\dfrac{n(n-1)}{2} M=2n(n−1)条边。 如果有一个有 n n n个结点的带权完全无向图， M M M条边的权值是 1 1 1到 M M M的一个排列，则这张图是合法的。 现在给定一个有 n n n个结点 m m m条边的带权无向连通图
NOIP2023模拟3联测24-博弈树
NOIP2023模拟3联测24-博弈树 文章目录 NOIP2023模拟3联测24-博弈树题目大意思路code 题目大意 A l i c e Alice Alice 和 B o b Bob Bob 又开始玩游戏了： 给定一颗 n n n 个节点的树， A l i c e Alice Alice 和 B o b Bob Bob 随机选择一个节点作为起点放上棋子，由 Ali