方差 题解noip 2021
【luogu题解】T378828 位运算
位运算 题目背景 题目由 daiyulong20120222 创作(me) 并由 QBW1117完善以及数据 。 题目描述 给定两个数\(x,y\) ,在给定一个位运算符号 \(c\)。 请你列出 \(x,y\) 进行 \(c\) 位运算是的算数竖式式。 注: 竖式这么列: 显示出两个数的完整二进制 ......
NOIp2023暂别记
原谅这篇文章的迟到,主要是没有收拾好心情。现在终于平静下来了,这次不魔怔了,游记认真写。 书 接 上 回 day -?????? CQOI2023,100 + 25 + 0 + 0 + 0 + 0,垫底,毋庸置疑。 但是比起垫底对我打击最大的是学长们的离开。他们是那样的勤奋,那样的热爱OI,很难想象 ......
CF1898 C Colorful Grid 题解
Link CF1898 C Colorful Grid Question 给出一个 \(N\times M\) 的网格图 给每一条边染色(R/B),需要存在一条长度为 \(K\) 的路径从 \((1,1)\) 到 \((N,M)\),路径允许重复通过一个节点。 Solution 非常有意思的一道题 ......
CF1898 B Milena and Admirer 题解
Link CF1898 B Milena and Admirer Question 给出一个长度为 \(n\) 的序列 \(a\) ,我们可以做一种操作使得 \(a\) 非降,操作是: 对于一个 \(a_i\) 选择一个整数 \(0 \le x \le a_i\) ,用两个数 \(x,(a_i-x) ......
USACO 2022 December Contest, Silver Problem 3. Range Reconstruction 题解
Link USACO 2022 December Contest, Silver Problem 3. Range Reconstruction Question \(r_{l,r}\) 表示 \(max[l,r]-min[l,r]\) 给出所有的 \(r_{i,j}\) 求一个可行的序列 Solu ......
ABC327 E Maximize Rating 题解
Link ABC327 E Maximize Rating Question 给出 \(N\) 个数 \(Q_i\),从中按照顺序选出 \(k\) 个数,使得 \[R=\frac{\sum^k_{i=1}(0.9)^{k-i}\times Q_i}{\sum^k_{i=1}(0.9)^{k-i}}- ......
CF1891 D Suspicious logarithms 题解
Link CF1891 D Suspicious logarithms Question 我们设 \(y=f(x)\) 表示最大的 \(y\) 满足 \(2^y \le x\) 设 \(z=g(x)\) 表示最大的 \(z\) 满足 \(f(x) ^z \le x\) 求 \[\sum\limits ......
CF1891 C Smilo and Monsters 题解
Link CF1891 C Smilo and Monsters Question 有 \(n\) 个怪物部落,其中 \(a_i\) 表示第 \(i\) 个部落中的怪物数量,你有一个值 \(x\) 初始为 \(0\) ,你有两种方式来消灭所有的怪物 选中一个怪物数量大于 \(1\) 的部落,消灭一个 ......
CF1891 F A Growing Tree 题解
Link CF1891 F A Growing Tree Question 给出了一棵树,初始只有根节点,编号为 \(1\) 现在有两个操作 第一个操作:1 x 添加一个新节点 \(size+1\) ,这个新节点的父亲为 \(x\) 第二个操作 : 1 x val 给 \(x\) 的子树都加上 \( ......
P9771 HUSTFC 2023 排列排序问题 题解
Link P9771 HUSTFC 2023 排列排序问题 Question 给出一个 \(N\) 个元素的排序 \(a\),我们可以对排列进行一些操作 将这个排列切割成若干个序列 将其中一些序列翻转 将这些序列连接起来得到一个新的排列 需要让最后的排列有序 Solution 这个题的描述有点小问题 ......
CF1884 D Counting Rhyme 题解
Link CF1884 D Counting Rhyme Question 给定长度为 \(n\) 的数组 \(a\) 如果两个不同的下标 \(a_i,a_j\) 不能被任意一个元素 \(a_k,(1 \le k \le n)\) 共同整除,那么说明 \((i,j)\) 是"好对" ,求"好对" 的 ......
ABC325 D Printing Machine 题解
Link ABC325 D Printing Machine Question 有 \(N\) 个零件需要打印,每个零件从 \(T_i\) 时间进入机器,从 \(T_i+D_i\) 时间离开机器,每个时间段只能答应一个零件,求最多能打印多少零件 Solution 贪心的去想,对于第 \(i\) 个时 ......
ARC66 D Interval Counts 题解
Link ARC66 D Interval Counts Question 给定正整数 \(n\) 和长度为 \(n\) 的序列 \(x_i,y_i\) 保证 \(x_i\) 单调递增,你需要构造 \(m\) 个去年 \([L_i,R_i]\) ,\(m\) 有你指定,使得每个 \(x_i\)恰好被 ......
ARC166 A Replace C or Swap AB 题解
Link ARC166 A Replace C or Swap AB Qustion 给出两个长度相同的由 \(A,B,C\) 组成的字符串 \(X\) 和 \(Y\) 。 需要使用一些操作使得 \(X\) 和 \(Y\) 一样 将 \(X\) 中的 \(C\) 换成 \(A\) 将 \(X\) 中 ......
NOIP 2023 游记
在长郡考试,爽! 开场开 T1,码上去发现大样例挂了,然后发现题看错了,然后过了五十分钟才过 T1 大样例。 开 T2 感觉像是建图,建了半天啥都没建出来(没观察样例的后果),此时想了半个多小时了,感觉得跑路了,打了 \(40\) 跑路。(\(60\) 分不知道为啥挂了) 开 T3 感觉暴力都不会, ......
T402161 run 题解
Link T402161 run Question 亮亮总共要跑 \(n\) 圈,可以分成多次,但是每次跑的圈数必须要比上一次跑的多,求跑完 \(n\) 圈的方案数 Solution 显然动态规划 定义 \(F[i][j]\) 表示一共跑了 \(i\) 圈,最后一次跑了 \(j\) 圈的方案数,转移 ......
AT_pakencamp_2020_day1_f Fibonaccyan(暂无评定) 题解
题目链接 题目大意: 给定数 \(P\),寻找能把 \(P\) 整除的最小的斐波那契数,然后输出它是斐波那契数列中的第几个,找不到输出的话就输出 -1 。 分析: 主要代码: a[i]=(a[i-1]+a[i-2])%p 思路: 先将 \(a\) 数组的第一项和第二项都初始化为 1 ,然后判断是不是 ......
P1091 合唱队形题解(普及/提高−) 题解
题目传送门 这道题是一个很经典的动态规划。 因为合唱队形的身高是从低——高——低来排的,所以就可以利用分治的思想将队形分成两个部分:低——高是最长上升子序列;高——低是最长下降子序列。 这道题其实可以用二分查找来优化,可是这题n≤100,没有必要优化,需优化题详见P1020 导弹拦截。 做法详见代码 ......
P3370 【模板】字符串哈希(普及−) 题解
题目链接 题目大意 如题,给定 \(N\) 个字符串(第 \(i\) 个字符串长度为 \(M_i\),字符串内包含数字、大小写字母,大小写敏感),请求出 \(N\) 个字符串中共有多少个不同的字符串。 不知道大家知不知道一个字符串函数,叫 \(insert\) 他是 \(STL\) 库中的一个函数, ......
CF1837C Best Binary String(普及−) 题解
题目传送门 题目描述 给定由 1 0 ? 所组成的字符串,你需要用 0 或 1 替换 ?。 我们将 \(s_l,s_{l+1},\dots,s_r\) 反转称为一次操作。 你要使通过“反转”操作使原字符串成为升序的操作次数尽可能的小。 分析 通过观察,我们可以发现一个规律: 若 \(s_i\) 为 ......
P5867 [SEERC2018] Fishermen(暂无评定) 题解
题意 有 \(n\) 条鱼,\(m\) 个渔夫,且这 \(m\) 个渔夫都在横坐标轴上,每个渔夫都有一个长度为 \(l\) 的鱼竿,当鱼和渔夫距离小于或等于 \(l\) 时,鱼能被钓到。 并且渔夫 \((x,0)\) 与鱼 \((a,b)\) 的距离(假设为 \(L\) )满足如下公式 \(|a − ......
P9570 「NnOI R2-T2」Glaciaxion( 普及−) 题解
这道题是洛谷基础赛的第二题 想必各位都AC了吧 没有AC的现在赶紧去做 题目传送门:传送门(最好别点)点了别怪我没提醒 题目链接:传送门< 点这个 做过的直接看下面就行 「NnOI R2-T2」Glaciaxion 题目描述 冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川,这些冰川被编号为 \ ......
P1029 最大公约数和最小公倍数问题(普及−) 题解
题目传送门 想要做这题,我们要先了解一下最大公约数。 最大公因数,也称最大公约数、最大公因子,指两个或多 个整数共有约数中最大的一个。a,b的最大公约数记为 (a,b),同样的,a,b,c的最大公约数记为(a,b, c),多个整数的最大公约数也有同样的记号。求最大公 约数有多种方法,常见的有质因数分 ......
P5451 [THUPC2018] 密码学第三次小作业 题解
P5451 [THUPC2018] 密码学第三次小作业 题解 已知 \((e_1, e_2) = 1\)。 \[\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix} \]现在,已知 \(c_1\) ,\(c_2\),\(e_ ......
83rd 2023/11/15 NOIP Day-2
早上回学校参加国标了,晚上继续停课训练 思考了今天上午其他学校人打的模拟赛,T3是很有意思的网络流建图 T1是一道贪心策略题,思路认真推之下应该能够想出 老师讲了面对比赛应有的态度,是的,应该全力以赴面对这场难得的机会 再补一下短板吧,DP、贪心和网络流建图(虽说不一定用得上),但万无一失总是好的 ......
84th 2023/11/16 NOIP Day-1
一场模拟赛,下去试机了 T1有正解思路,但思路混乱打不出来,主要是最后输出不是很懂如何处理 T3没能完全想出正解,这个去重的思路挺有意思的 主要是通过排序,预处理找到下一个重复位置,然后区间赋值来处理 在一个位置即将重复时删除上一个即可 T2T4待补 ......
85th 2023/11/17 NOIP Day0
明天就要在楼下的考场打了 老师今天给了一整天的自主做题时间,初中生是做题,而高中就是复习了 话不多说直接来到今天的归纳: 斜率优化,要敢于把i,j移动至转移方程的左右,最后归纳为一次函数的形式,并观察需要去最值的东西,凸包似乎挺好维护 关于区间:包含,相交,不相交,三种要考虑全,如:[P5464 缩 ......
86th 2023/11/18 NOIP Day1
已经过去了,总结得写 赛前没什么,直接入题 T1一眼了,T2看了看,手模了一下,觉得非常麻烦,难以处理 T3看一眼认为不太能做,后来还剩0.5h时开了它,发现可以拿分 T4看出了暴力,发现有一当应该是DP的部分分 然后去推T2,然后很自信地认为,按它特殊数据给的数量,可以拿80分 然后20min切了 ......
NOIP 2023比赛报告
第一题 比赛情况 $100$ 分,耗时 $1$ 小时。 题解 对于 $1\le i\le n$ ,比较 $w_i$ 字典序最小的字符 $a_i$ 与每个 $w_j(i\ne j)$ 字典序最大的字符 $b_j$ 。如果有 $b_j\le a_i$ ,则 $w_i$ 不能成为字典序最小的单词,反之可以 ......
NOIP 2023游寄
这种游记真的有什么要写的必要吗…… Day 0 (2023/11/17) 去 lcez 逝机(伏笔) 上了 sdfz 总有一种错觉,老感觉其他学校和我们一样小。 Day 1 (2023/11/18) 1h 看题,1h 切 T1,2h 切 T2 T4DP 没打出来(悲) 最后竟然发现我机子的时钟竟然慢 ......