地毯noip 2011

2023NOIP A层联测26 T2 competition tjm 的做法，很抽象。 考场思路 考虑每道题被做过多少次肯定不现实，那么考虑每一道题有多少次没有做出来。 假设某一次可以做出来题 \(x\) 的人是 \(i\)，而 \(i\) 下一个人可以做出这道题的人是 \(j\)，于是题 \(x\ ......

2023NOIP A层联测26 T3 tour 有意思的树上主席树。 思路 首先考虑一个点 \(p\) 能计入答案的情况，就是 \(dis(x,p)-a_p \ge a_p\)。 我们把 \(x \to y\) 的路径拆成 \(x \to lca,lca \to y\) 两条。 记录一个点 \(x\ ......

2023NOIP A层联测26 T4 abstract 乱证明求性质的光速幂优化题。 思路 对于每一个节点，到该节点的子树内的叶子节点的路径中（包括路径上的点），出现的值只有 \(k\times(\log V+\log V)\) 个。 那么在以该点为终点，以子树内节点为起点的路径中，取值只有 \(k ......

前言 数论迎我归，数学送我葬 组合数学不容易，又有 DP 当 T3 刚爆零，T4 又遭殃 OI 路上怅前望，且行且彷徨 T1 最大公约数 T1 应该想一想就会，接下来我们讨论是怎么减去他的复杂度的。 题目的关键在于，如果根据给出的 \(a\) 推出 \(\gcd\) 的话，就会有 \(9\times ......

2023NOIP A层联测27 A.kotori 目录2023NOIP A层联测27 A.kotori题目大意思路code 题目大意 琴里的飞船中有 \(n\) 个人，其中有 \(n - 1\) 个通道，所以飞船的内部是一个树形结构。每个人从 \(1-n\) 编号，编号越小代表这个人的投票经验最丰富 ......

应该都和我一样一下水了两题吧 P2491 [SDOI2011] 消防 P1099 [NOIP2007 提高组] 树网的核 题目描述 在一颗 \(n\) 个节点的无根树中，找到一条不超过 \(s\) 的路径，使得图中所有点到此路径距离的最大值最小，图中边权非负 分析 若想将此题转化到树网的核，首先要证 ......

NOIP2023模拟13联测34 总结 目录NOIP2023模拟13联测34 总结比赛过程题目A. origen题目大意思路B.competition题目大意思路C. tour题目大意D.abstract题目大意 比赛过程 看了一下题，感觉就 \(T2\) 有一点思路。 \(T1\) 先打一个 \( ......

NOIP2023模拟13联测34 B.competition 目录NOIP2023模拟13联测34 B.competition题目大意思路code 题目大意 现在有 \(n\) 个区间 \([l_i , r_i]\) ，现在问你选取若干的连续的区间的区间并的大小的和。 思路 设 \(pre_{i , ......

NOIP2023模拟13联测34 A. origen 目录NOIP2023模拟13联测34 A. origen题目大意思路code 题目大意 给定 \(n\) 个整数 \(a_1,a_2,a_3\cdots a_n\) ，求 \[\sum_{i = 1}^n\sum_{j = i}^n(\oplus ......

NOIP2023模拟9联测31 总结 题目 T1 游戏 大意 博弈论，在 \(1—n\) 中 \(\phi(i)\) 小于 \(m\) 都选入集合 \(S\)。在集合 \(S\) 中选数 \(x\)，选择完后把数 \(x\) 及其的因数从 \(S\) 中删去。当不能取数时的人败。给 \(n,m\) ......

2023NOIP A层联测25 总结 题目 T1 构造 大意 构造一个 \(a\times b\) 的矩阵，要求 \(a,b\leq 40\)，且有 \(n\) 个 ryx。（横向，纵向，和 \(45^\circ\) 的方向上的 ryx） 赛时思路 一开始发现求出最大的构造方法后一定可以缩减到另外一 ......

T1 把 \(a_i\) 前缀和，式子就变成了 \(\sum_{i=0}^n\sum_{j=i+1}^na_i\oplus a_j\)，我们把这些贡献看成 \(a_j\) 的贡献。 然后按位考虑，那么一个数的平方就拆成了一些数加和的平方，拆开就会变成一些数的平方，和一些数的乘积的二倍。考虑分开计算这 ......

NOIP2023模拟8联测29 总结 题目 T1 集合 大意 给出一个序列 \(S\)，找出有多少个区间 \([L,R]\)，使得 \([L,R]\) 值域的连续长度不超过 \(k\)。 \(n \leq 2*10^5,k\leq n\) 赛时思路 对于区间 \([L,R]\)，如果有 \([L', ......

NOIP2023模拟9联测30 总结 题目 T1 上海 大意 判断是否存在 \(n\) 正整数 ，使得 \(n^2\) 是 \(k\) 的倍数，且 \(n\) 不是 \(k\) 的倍数。如果存在，输出最小的 \(n\) ；不存在输出 \(-1\) 。 \(k\leq 10^{12}\) 赛时思路 对 ......

NOIP2023模拟9联测32 总结 题目 T1 花菖蒲 大意 构造一个一度点数等于 \(a\)，二度点数等于 \(b\)，总点数小于 \(2000\) 的树。 \(a,b \leq 200\) 赛时思路 构造一条链，去除首位后有 \(b\) 个节点，这 \(b\) 个节点接一个一度点，加上首位两个 ......

补一下往年的构造题。。。 \(k\) 大概是 \(n\) 的两倍往下，这启示我们每个栈最多只放两个元素。 首先考虑 \(k=2n-2\) 的分，容易得到一个策略：留一个空栈不放，每个栈最多放两个。如果当前卡牌存在一个栈顶/栈底和它一样，那当前牌总是可以消掉的。否则当前栈中的卡牌一定两两不同，那一定还 ......

100+100+20+17，T3 按理说应该想到考虑两部分分别的贡献的，明明这个套路很常见。 5k：就喜欢这种数据结构专场，多来点。 A.origen 先前缀和，以下 \(p_i\) 表示前缀异或和。 考虑将一个数 \(k\) 二进制差分，假设拆成 \(2^a+2^b+2^c\)，则 \(k^2=( ......

题目描述 小 AA 和小 BB 决定利用假期外出旅行，他们将想去的城市从 11 到 nn 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 ii 的海拔高度为hihi​，城市 ii 和城市 jj 之间的距离 di,jdi,j​ 恰好是这两个城市海拔高度之差的绝对值 ......

2023NOIP A层联测25 T4 滈葕 配血实验与2-SAT。 思路 \(z=1\) 表示配血实验发生凝集反应，设 \(a_i,b_i\) 分别表示第 \(i\) 个人有无凝集原 A,B。（无凝集原 A，肯定有抗 A 凝集素，B同理）那么发生反应的必要条件是 \(a_x \and \neg a_ ......

2023NOIP A层联测25 T2 游戏 优秀且新颖的期望题。 思路 分析问题，由于双方都是最优策略，所以可以说学生知道老师会选择那些教室设置概率（概率设置好就不能改变），老师也知道学生会怎样选择教室（不是知道一定会去那个）。 设老师选择的集合是 \(S\)。 那么老师在学生不清空的情况下，老师的 ......

NOIP2023模拟12联测33 总结 目录NOIP2023模拟12联测33 总结比赛过程正解A. 构造题目大意思路思路B.游戏题目大意思路C. 数数题目大意D. 滈葕题目大意思路总结 比赛过程 先看了一眼 \(T1\) ，发现又是恶心构造题，果断跳过。 \(T2\) 期望题，这么恶心吗，果断跳过。 ......

NOIP2023模拟12联测33 [tOC] 题目大意 思路 放一段题解的材料 ABO 血型系统是血型系统的一种，把血液分为 A,B,AB,O 四种血型。血液由红细胞和血清等组成，红细胞表面 有凝集原，血清内有凝集素。根据红细胞表面有无凝集原 A 和 B 来划分血液类型。红细胞上只有凝集原 A 的 ......

NOIP2023模拟12联测33 B. 游戏 目录NOIP2023模拟12联测33 B. 游戏题目大意思路code 题目大意 期望题 思路 二分答案 \(mid\) ，我们只关注学生是否能够使得被抓的人数 \(\le mid\) 那我们就只关心 \(a > mid\) 的房间就行了。 设学生有 \( ......

NOIP2023模拟12联测33 A. 构造 题目大意 构造题 思路 想一种构造方法，使得 \(y\) 能够凑成尽可能多的答案 第一行 \(xyry \cdots r\) 第二行 \(ryxy \cdots x\) 第三行 \(xyry\cdots r\) 把最后一列空出来。 此时有 \(2202\ ......

A. 星穹铁道 读完题面就想到了 \(O(n^2)\) 的暴力。很好想，但是只有40分。观察到 \(z_i=\pm 1\) ，然而即便如此，我也没有得到有用的性质。（正解是用到这个性质的） 然后我就暴力写了。 正解的性质“最终在一个区间L,R内，初始也一定在一个连续段内”赛事没有想到。 同时题解用了 ......

100+100+30+100，T4 自己写了 Check 最后一分钟发现 Check 锅了，赌了一发替换了部分分，赢！ A.构造 默认 \(n\geq 3,n\in \{2x+1,x\in N\},m\geq 4\)。 考虑构造 rrrrr yyyyy xxxxx yyyyy rrrrr yyyyy ......

NOIP2021 - 方差 https://www.luogu.com.cn/problem/P7962 想当年我第一次站在 noip 赛场上，过了 T1 剩下三题就一题不会了……幸好这题拿了点分水了个一等。 观察操作：若对于连续的三个数 \(a,b,c\)，对 \(b\) 进行一次操作后就变成了 ......

Day 1 被 ly 干碎。 T1 矩乘，带一个常数 1 和答案总和即可。 T2 等价于找两个相同的子序列并且第一个的结尾位置小于等于第二个的开头位置。枚举第二个的开头位置 \(j\)，设 \(f_{k,a,b}\) 表示分别以 \(a,b\) 结尾的长度为 \(k\) 的子序列有多少个，二维前缀和 ......

模拟11 A层联测24 100+0+20+10=130pts rk32 T1 签到题 T2 最大值的最小竟然没想到二分，退役吧。。爆搜所有路径不知道哪写挂了赛后被卡成零蛋。。。 T3 暴力枚举 T4 二维前缀差分暴力 T1 花菖蒲 首先有解一定满足 \(b\le a-2\)。 当 \(b=0\) 时 ......

T1 判断是否存在一棵树，满足它有 \(a\) 个一度点和 \(b\) 个三度点，如果存在请给出一个节点数不超过 \(1000\) 的构造，否则输出 。 考场看了一个小时发现 和 第一种可以构造等量的一度电和三度电，第二种可以在不勾造三度电的情况下构造一度电，根据阳历六 ans 看出 可惜 没加 r ......