题解 联盟noip
ABC330 C Minimize Abs 2 题解
Link ABC330 C Minimize Abs 2 Question 给定一个整数 D 求 \(|x^2+y^2-D|\) 的最小值,\(x,y\) 为非负整数 Solution 同时枚举 \(x,y\) 显然是不切实际的,考虑折半枚举 枚举 \(x^2\) 然后寻找接近 \(D-x^2\) ......
NOIP2023 游记
Day 0 打摆。 打摆。 打摆。 看 tarjan。 打摆。 打摆。 打摆。 Day 1 早上很早到了附中,发现准考证上没有照片,黑糊糊一片,被教练强行紧急更换了一个,感觉不换其实也没什么关系。 进考场,发现在最后一排,旁边不认识,前面不认识,前面的旁边不认识,sad。 然后发密码,开 T1,发现 ......
ABC330 E Mex and Update 题解
Link ABC330 E Mex and Update Question 给一个数组 \(a\),有 \(Q\) 次修改 每次把 \(a_i\) 改成 \(x\) 问每次修改后,不在 \(a\) 数组中的最小非负数时多少 Solution 记录每个 \(a_i\) 出现的次数 \(num\) 每个 ......
SP1557 GSS2 - Can you answer these queries II 题解
SP1557 GSS2 - Can you answer these queries II 更好的阅读体验 扫描线。把询问挂在右端点上,扫描右端点,纵轴仍为序列维。 对于这种出现多次的数只算一次的,记 \(pre_i\) 表示 \(i\) 这个值上一次的出现位置,套路化的可以强制让出现多次的在 \( ......
UVA11275 3D Triangles 题解
Link UVA11275 3D Triangles Question 给你三维空间中的两个三角形,请判断它们是否有公共点。 Solution 如果在三维空间中相交,那么,肯定有一个三角形的某一条边穿过了另外一个三角形 Code #include<bits/stdc++.h> using names ......
CF1900 D Small GCD 题解
Link CF1900 D Small GCD Question 定义 \(f(x,y,z)=\gcd(a,b)\) ,其中 \(a,b\) 为 \(x,y,z\) 中较小的那两个数 给出数组 \(a\),求 \[\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \ ......
P1970 [NOIP2013 提高组] 花匠
显然只选峰或者谷,所以记录当前走势是向上还是向下,出现转折时答案加一即可。 因为存在相同的元素,所以开头的走势要特判,把最前面连续相同的一段看成一个元素,因为不确定会转变成哪种走势。后面遇到相同则可以正常做,因为前面走势已经确定了,相当于自动忽略了相同的元素。 ......
P9447 [ICPC2021 WF] Spider Walk 题解
更好的阅读体验 很有意思的一道题。 设 \(f_i\) 表示第 \(i\) 根线的答案,首先有一个关键结论:任意两根相邻的线答案只差一定小于 \(1\)。原因显然,可以在无限远的地方加一根线来构造。该结论可以扩展一下,对于距离为 \(d\) 的两根线,答案之差不会超过 \(d\)。 考虑进行倒着加线 ......
P3375 【模板】KMP( 普及/提高− ) 题解
题目传送门 思路: 首先我们要学习一下 \(KMP\) 算法,不会的可以看这个大佬的文章 那么我们就直接开始讲思路了。 针对于每一位,\(kmp\) 算法已经预处理出了一个对应 \(kmp\) 数组的单元,映射着如果此位失配,它可能的最靠后的一个重新开头是哪一个。 让我们举一个例子:假如让 \(aa ......
CF1900 C Anji's Binary Tree 题解
Link CF1900 C Anji's Binary Tree Question 给出一个树,每个节点上有一个字母 L/R/U ,从 \(1\) 号根节点开始,L 表示接下来走到左节点,R 表示接下来走到右节点,U 表示接下载走到父节点 问,最少修改几个节点上的字母使得从根节点走到叶子节点 Sol ......
P7626 [COCI2011-2012#1] MATRIX( 普及/提高− ) 题解
题目传送门 思路: 首先思考暴力,\(O(n^4)\) 的时间复杂度,不行。 那么我们这里就要运用到一点前缀和的知识了。 我们可以用前缀和对两条对角线进行计数。 每个点有两个对角线运算。 差不多是 \(O(n^2)\) 到 \(O(n^3)\)的时间复杂度。 而 \(n\leq400\) 稳过。 C ......
CF1900 B Laura and Operations 题解
Link CF1900 B Laura and Operations Question 给出 \(1,2,3\) 的个数 \(a,b,c\) 可以分别减少两个不同的数,增加一个与两个数都不同的数 问,是否能经过一些操作使得 就剩下 \(1\) 或 \(2\) 或 \(3\) Solution 先考虑 ......
CF1900 A Cover in Water 题解
Link CF1900 A Cover in Water Question 给出一个 \(n\) 个格子,有些格子被堵塞了,有些格子是空的,我需要在进行一些操作,使得所有空的格子里面都有水 操作 1:给任意一个格子装上水 操作 2:把一格水从一个地方搬运到另外一个空的格子里 如果一个空的格子的相邻的 ......
ABC330 A-E 题解
ABC330题解 AtCoder Beginner Contest 330 A - Counting Passes 思路: 枚举一遍,当前数大于\(L\)使\(ans+1\)即可. 代码: #include<iostream> #define int long long using namespac ......
Information Graph 题解
题目链接 Information Graph 分析 在线并不好做,考虑离线,先将树建出来 \(2\) 操作时 \(x\) 节点 与 当前根节点 之间的点都会获得文件 当前根节点可以用并查集维护 对于查询的节点判断它是否为链上的点即可 具体的,若该节点为 \(rt\) 子树中的点 且 该节点的子树包含 ......
P8706 [蓝桥杯 2020 省 AB1] 解码 ( 入门 ) 题解
题目传送门 思路: 有一个原串 \(t\)。 将原串 \(t\) 转换成简写字符串 \(s\) 的规则如下: 如果有连续的 \(2\sim9\) 个相同字母,那么可以将它改为字母+数字的格式。 如果是单独的字符,也就是与左右两边的字母都不相同,在简写字符串中一模一样。 所以,现在告诉我们简写字符串, ......
ICPC2022Xian G Perfect Word 题解
Link ICPC2022Xian G Perfect Word Question 给出 \(n\) 个串,我们称 \(t\) 串是 "good" 当且仅当 \(t\) 的所有子串都在 \(n\) 个串中出现过 问最长的 "good" 的串的长度 Solution 由于所有串的子串个数为 \(L\t ......
ICPC2022Xian E Find Maximum 题解
Link ICPC2022Xian E Find Maximum Question 定义 \(f(x)\) 求 Solution 通过打表我们可以发现 \(f(x)\) 表示三进制表达中有效位数与数码和之和 接下来考虑如何获得最大的 \(f(x)\) 贪心的去考虑,假设答案为 \(Ans\),\(( ......
P1090 [NOIP2004 提高组] 合并果子
原题链接 题解 每次从所有果子堆中选重量最小的两堆并累加,观察到只需要找出 最小 因此考虑用堆 代码 #include<bits/stdc++.h> using namespace std; int pile[10005]={0}; int len=0; void in(int x) { pile[ ......
NOIP 历年真题 贪心
数据范围较小时,可以考虑 dp。设 \(f(i,j)\) 表示当前段末尾为 \(i\),上一段末尾为 \(j\) 的最小代价。转移为: \[f(i,j)= \min _{s_i-s_j \ge s_j-s_k}f(j,k)+(s_i-s_j)^2 \]时间复杂度 \(O(n^3)\)。 不难想到一个 ......
【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\) 的子树都加上 \( ......