2023noip专题
2023NOIP A层联测28-大眼鸹猫
给你两个长度为 n n n 的序列 a , b a,b a,b，这两个序列都是单调不降的。 你可以对 a a a 进行不超过 m m m 次操作，每次操作你可以选择一个 i i i 满足 1 ≤ i ≤ n 1\le i\le n 1≤i≤n，然后选择一个整数（可以是负数） x x x，将 a i a_i ai 加上 x x x，这一次操作需要花费 x 2 x^2 x2 的代
2023NOIP A层联测26-origen
给定 n n n 个整数 a 1 , a 2 … a n a_1,a_2\dots a_n a1,a2…an，求 ∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\left(\bigoplus\limits_{k=i}^{j}a_k\right)^2 i=1∑nj=i∑n(k
2023NOIP A层联测26-competition
现在有一个题目数量为 m m m 的比赛，有一个团队想要来参加。 这个团队有 n n n 位选手，编号为 i i i 的选手能做第 l i ∼ r i l_i\sim r_i li∼ri 道题，每一道题他都有 100 % 100\% 100% 的概率能做出来。 这个团队会随机派出一支队伍来参加这个比赛。 因为编号相邻的人关系更好，默契度也更高，所以说一个团队派出的队伍一直都是编
2023NOIP A层联测25-构造
ryx 有一个非负整数 n n n。他希望你构造出一个不超过 40 × 40 40\times40 40×40 的矩阵，每个位置填 r、y、x 三者之一，使得连续的三个格子按顺序构成字符串 ryx 恰好有个。 这里连续的是指同一行、同一列或者同一45°斜线，方向任意（共 8 个方向）。 n ≤ 2222 n\le2222 n≤2222 先给出一种最大的构造方案 40 40ryx
2023NOIP A层联测25-滈葕
给定一个 01 权有向图，给每个点赋予 ABCD 中的一个字母使得每条有向边 ( u , v , w ) (u,v,w) (u,v,w) 都满足 w = 1 ⟺ ( a u , a v ) ∈ { ( A , B ) , ( A , D ) , ( B , A ) , ( B , D ) , ( C , A ) , ( C , B ) , ( C , D ) } w=1\Longleftrig
2023NOIP A层联测25 总结
T1 让你构造 40 × 40 40\times40 40×40 的只含 r,y,x 的矩阵，含有 r y x ryx ryx 的个数恰好为 n n n， n ≤ 2222 n\le2222 n≤2222。看完题后就开始想构造，一开始想构造 3 ∗ 3 3*3 3∗3, 5 ∗ 5 5*5 5∗5 的单位矩阵的，但是始终不够数。后面去看 T2，是期望，类型从未见过，没多想回去看 T1。大概
2023NOIP A层联测25-游戏
有 n n n 间物理实验室，第 i i i 间实验室有 a i a_i ai个人，他们全都在打游戏。 同学 A \text{A} A 可以选择进入一间实验室，然后让其中的所有个人停止打游戏。 然后老师 B \text{B} B 可以选择进入一间实验室，然后抓住其中所有在打游戏的人。 同学 A \text{A} A 的目标是让老师 B \text{B} B 抓到的人最少，而老
2023NOIP A层联测24 总结
T1 给出树的一度点和三度点的数量，构造树的形态，节点数不超过 2000 2000 2000。我考虑先构造出三度点，发现这一度点至少是三度点+2，打完后测样例不对，发现加一度点时要特判是否为三度点，花 5min 打完，不放心，又手写 spj。用时 40min T2 一个图，用 1 1 1 走到 n n n 代价为 ∑ i = 1 t t w t \sum\limits_{i=1}^ttw
2023NOIP A层联测23-总结
这场比赛四道题三道题期望，再加一个博弈论，不是正常的比赛。 T1 看了很久性质，都没看出来。大概 9 点，打了 70pts 状压暴力，打表发现 sg 函数有性质，就不可以总司令一手。估计能A T2 看完后想了一个高斯消元的 60pts 暴力，但是没调出来。 T3,T4 没看懂题目。 期望得分：[70,100]+0+0+0=[70,100] 实际得分：100+12+0+0=112 总结：
2023NOIP A层联测22-差后队列
定义差后队列为一个数据结构，支持两种操作： pop 随机删除一个不是最大值的的数。如果只有一个数则删除该数。push 插入一个数（正常插入）。 给定操作序列，求每次删的数的期望，以及每个数期望被删的时间（如果到最后也没被删则删除时间为 0 0 0）。 n ≤ 1 0 6 n\le10^6 n≤106 容易发现，一个数如果不是最大值，都是一样的。 对于一个数，如果它是当前的最大值，
2023NOIP A层联测17 爆炸
题目大意 有一个 n × m n\times m n×m的网格图，其中一些格子上有一个炸弹，一些格子上有一个水晶，剩下的格子为空地。 炸弹可以引爆，每当一个炸弹被引爆，它必须选择：引爆它所在的这一行或者引爆它所在的这一列。水晶被引爆后会消失（即如果一个水晶所在的行列均被引爆，也只计算一次），炸弹被引爆后，会产生连锁反应，被引爆的炸弹也会选择引爆它所在的行或者列，如此下去直到没有新的炸弹被引爆。
2023NOIP A层联测16 货物运输
题目大意 有一个有 n n n个点 m m m条边的无向连通图，每条边的长度为 w i w_i wi，并且任意一条边最多在一个简单环内。每个点都有 s i s_i si个单位的资源，你想要均分这些资源，即让每座城市的资源数等于 ∑ s i n \dfrac{\sum s_i}{n} n∑si（数据保证 ∑ s i n \dfrac{\sum s_i}{n} n∑si是整数）。 已知
2023NOIP A层联测17-黑暗料理
简要题意：在 n n n 个数中选尽可能多的数，使得任意两个数之和不是质数。 n ≤ 750 , a i ≤ 1 0 9 n\le750,a_i\le10^9 n≤750,ai≤109 两个数之和为质数，说明两个数一奇一偶，或者都是 1 1 1。 把重复的 1 1 1 删去，因为后面不会同时选多个 1 1 1。 建立二分图，奇数放在左边，偶数放在右边，若两个数之和为质数，就
2023NOIP A层联测16 数学题
题目大意 给定一个长度为 n n n的字符串 S S S和一个长度为 m m m的字符串 T T T，两个字符串都由小写字母组成。 一个匹配指 T T T作为一个子序列在 S S S中出现。 设 T T T的每个字符出现的位置为 p o s 1 , p o s 2 , … , p o s m pos_1,pos_2,\dots,pos_m pos1,pos2,…,posm，则该匹配的权
2023NOIP A层联测14-选举
Byteland \texttt{Byteland} Byteland 的选民们要进行选举。一共有位 n n n 选民和 m m m 位候选人，编号分别从 1 1 1 到 n n n 和从 1 1 1 到 m m m。 每位选民有一个非空的喜欢的候选人的列表，这个列表是按照喜欢程度排序的。比如说一位选民的列表是 { 2 , 4 , 7 } \{2,4,7\} {2,4,7}，那么他
2023NOIP A层联测14 修路
题目大意 有一个有 n n n个点 m m m条边的无向连通图，第 i i i条边连接点 u i u_i ui和 v i v_i vi，长度为 l i l_i li。 你想要求这个图的一棵生成树，并规定一个中心点 m i d mid mid。定义一种规划的拥挤指数为 k × S + ∑ i = 1 n d i s ( i , m i d ) k\times S+\sum\limits_{
2023NOIP A层联测14-选举
Byteland \texttt{Byteland} Byteland 的选民们要进行选举。一共有位 n n n 选民和 m m m 位候选人，编号分别从 1 1 1 到 n n n 和从 1 1 1 到 m m m。 每位选民有一个非空的喜欢的候选人的列表，这个列表是按照喜欢程度排序的。比如说一位选民的列表是 { 2 , 4 , 7 } \{2,4,7\} {2,4,7}，那么他
2023NOIP A层联测9 风信子
题目大意 有一个长度为 n n n的序列 a a a。 定义一个合法的二元组 ( i , j ) (i,j) (i,j)满足 i , j i,j i,j为整数且 i ≤ j i\leq j i≤j，合法二元组的分数为 a i − a j a_i-a_j ai−aj。定义一个合法二元组 ( i , j ) (i,j) (i,j)在区间 [ l , r ] [l,r] [l,r]内，当且仅当
2023NOIP A层联测9 长春花
题目大意 给定一个质数 p p p，对于每个 0 ≤ x < p 0\leq x<p 0≤x<p，设 f ( x ) f(x) f(x)表示最小的非负整数 a a a，使得存在一个非负整数 b b b，满足 ( a 2 + b 2 ) m o d p = x (a^2+b^2)\bmod p=x (a2+b2)modp=x。 求 max { f ( 0 ) , f ( 1 ) , f (
2023NOIP A层联测10-子序列
给定一个长为 n n n 的仅有小写英文字母构成字符串 S = S 1 S 2 ⋯ S n S=S_1S_2\cdots S_n S=S1S2⋯Sn。我们定义一个字符串是好的，当且仅当它可以用两个不同的字母 x 和 y 表示成 xyxyxyx... 的形式。例如，字符串 abab、tot、z 是好的，但字符串 abc、aa 不是好的。 现在有 q q q 组询问，每次给定 1 ≤
2023NOIP A层联测6 数点
题目大意 给你一个排列 p p p，对于每一个 i i i，我们在平面上，放置一个点 ( i , p i ) (i,p_i) (i,pi)。对于坐标上下限都在 1 ∼ n 1\sim n 1∼n内的全体 ( n ( n + 1 ) 2 ) 2 (\frac{n(n+1)}{2})^2 (2n(n+1))2矩形，求每个矩形内部点数的 k k k次方之和。 形式化地，请你计算 ∑ 1 ≤
2023NOIP A层联测6 冒泡排序趟数期望
题目大意 对于一个排列 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an，进行一趟冒泡排序的代码为： for(int i=1;i<n;++i){if(a[i]>a[i+1]) swap(a[i], a[i+1]);} 若排列在 k k k趟冒泡排序之后变为有序的，则最小的 k k k定义为 r e s res res。 给一个长度
2023NOIP A层联测6 万花筒
题目大意 有一张有 n n n个点 m m m条边的无向带权图 G G G，小艾将它放到一个万花筒中观察。在万花筒中，对于每条边 ( u , v , w ) ∈ G (u,v,w)\in G (u,v,w)∈G，会在 H H H中生成全体 ( ( u + 1 ) m o d + 1 , ( v + i ) m o d n + 1 , w ) ((u+1)\bmod+1,(v+i)\bmod n+
2023NOIP A层联测6 T2 冒泡排序趟数期望（bubble）
对于排列 a [ 1 … n ] a[1\dots n] a[1…n]，其进行一趟冒泡排序的代码如下： for(int i=1;i<n;++i){if(a[i]>a[i+1]) swap(a[i], a[i+1]);} 若排列在 k k k 趟冒泡排序之后变为有序，则最小的 k k k 定义为 r e s res res。 给一个长度为 n n n 的随机排列（ n ! n! n