题解 联盟noip
题解 CF1651F【Tower Defense】
一个塔防游戏。
一共有 $n$ 个塔按 $1 \sim n$ 的顺序排成一列,每座塔都有魔力容量 $c_i$ 和魔力恢复速率 $r_i$。对于一座塔 $i$,每过一秒它的魔力 $m_i$ 会变为 $\min(m_i+r_i, c_i)$。每座塔初始时满魔力。
一共有 $q$ 个怪物,每个怪物有两... ......
【题解 CF840C & P4448】 On the Bench & 球球的排列
On the Bench 题面翻译 给定一个序列 \(a(a_i\le 10^9)\),长度为 \(n(n\le 300)\)。 试求有多少 \(1\) 到 \(n\) 的排列 \(p_i\),满足对于任意的 \(2\le i\le n\) 有 \(a_{p_{i-1}}\times a_{p_i} ......
P9506 题解
blog。First solution /kx。 容易想到断环成链。打开标签发现是 DP,于是就可以 DP 了。 code,时间复杂度 \(O(\text{能过})\)。 ......
NOIP2018PJ T3 摆渡车(2023.10第二版题解)
题目链接 题意: 时间轴上分布着$n$位乘客($1\le n\le 500$),$i$号乘客的位置为$t_i$(0\le t_i\le 4\times 10^6),用互相距离不小于$m$的车次将时间轴分为若干部分,并管辖以自己为右端点的这个区间(除了第一趟车包括$0$,其他车次左开右闭),求最小费用 ......
2023noip赛前20天冲刺 Day7 原神场
不愧是花花 /cf 溜大了(100+60+50+0) 哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄🙀哇袄㈹ ......
AT_arc100_b 题解
题意 这道题是让我们把一段区间分成四个不为空的连续子序列,并算出每个区间的和,最后用四个和的最大值减去最小值,算出最终答案。 分析 大家首先想到的肯定是暴力法用三个循环枚举四个区间,对于每一个区间,在单独算和,这样的时间复杂度 $O(n^4)$,肯定会超时。 现在我们进行优化:最后求和的过程我们可以 ......
SP26719题解
考虑动态规划。 思路 设 \(dp_{i,j}\) 为 \((1,1)\) 到 \((i,j)\) 的方案数,而如果要到这个点,肯定是从左边和上边来。 所以递推公式为:\(dp_{i,j}= dp_{i,j-1} + dp_{i-1,j}\)。 预处理:将横或纵坐标为 1 的点赋值为 1,因为到达这 ......
P9700题解
思路 看数据范围,发现范围很小,直接用搜索。 搜索时枚举每个点,如果有棋子就枚举方向,如果这个方向合法,则将剩余棋子数减一,继续搜索。 搜索时参数只需要传当前棋子数就行了。 有以下几点需要注意 多组数据每次需要初始化。 判断是否合法时要注意。 每次记得回溯棋子。 AC CODE #include<b ......
CF1873B题解
这题其实可以数学方法差小积大解决。 差越小积越大,那肯定是让最小的数加一啦。将所有数的积除以最小值再乘上最小值加一。 #include<bits/stdc++.h> using namespace std; signed main(){ int T; cin>>T; while(T--){ long ......
AT_abc134_d Preparing Boxes题解
简述题意 这什么破翻译,看了 AtCoder 的英文才看懂。 给定一个长度为 \(n\) 序列 \(a\),要求构造一个数列 \(b\),使得对于任意 \(i\),满足: \(1 \le i \le n\) 将 \(b\) 序列下标为 \(i\) 的倍数的值相加使得这个总和模 2 等于 \(a_i\ ......
P4899 [IOI2018] werewolf 狼人 题解
P4899 [IOI2018] werewolf 狼人 题解 题目描述 省流: \(n\) 个点,\(m\) 条边,\(q\) 次询问,对于每一次询问,给定一个起点 \(S\) 和终点 \(T\) ,能否找到一条路径,前半程不能走 \(0\thicksim L-1\) 这些点,后半程不能走 \(R+ ......
【题解 P8773】 选数异或
[蓝桥杯 2022 省 A] 选数异或 题目描述 给定一个长度为 \(n\) 的数列 \(A_{1}, A_{2}, \cdots, A_{n}\) 和一个非负整数 \(x\), 给定 \(m\) 次查询, 每次询问能否从某个区间 \([l, r]\) 中选择两个数使得他们的异或等于 \(x\) 。 ......
CF1868C Travel Plan 题解
原题 翻译 发现所有长度相同的简单路径的权值可能情况相同,且最长的简单路径长度为 \(O(\log n)\) 级别,考虑维护所有长度的简单路径在一棵树上出现的次数,每种简单路径的权值在所有树上出现的次数,相乘即使答案。 我们考虑长度为 \(x\) 的路径对答案的贡献,考虑枚举这条路径的贡献 \(k\ ......
P5018 [NOIP2018 普及组] 对称二叉树
先递归判断当前子树是不是对称二叉树,如果是就取 \(\max\) 然后退出,否则继续递归左儿子的左子树和右儿子的右子树、左儿子的右子树和右儿子的左子树判断。 最坏情况是每次都递归到叶子,也就是每层都是 \(O(n)\)。但一共只有 \(O(\log n)\) 层,所以时间复杂度是 \(O(n\log ......
【dp】【竞赛图的性质】ARC163D Sum of SCC 题解
ARC163D 发现这个竞赛图一定能被分为两个集合 \(A\),\(B\)。满足 \(\forall u\in A,v\in B\),均有 \(u\to v\in E\)。答案就是划分这两个集合的方案数。 证明: 首先,竞赛图缩完点后一定是一条链,对强连通分量进行标号,满足编号小的强连通分量指向编号 ......
【根号分治】P9212 「蓬莱人形」 题解
P9212 看到除法相关容易想到根号分治。 先对 \(x,y\) 进行讨论,不妨令 \(0\le x,y<m\)。 \(x<y\) 时,当满足 \(a_i+y < m\) 或 \(a_i+x\ge m\) 时,即当 \(a_i<m-y\) 或 \(a_i\ge m-x\) 满足 \((a_i+x)\ ......
【前缀和优化 dp】CF1542E1 Abnormal Permutation Pairs (easy version) 题解
CF1542E1 首先时间复杂度肯定是 \(\mathcal{O}(n^3)\) 的。 容易想到先枚举最长公共前缀,然后枚举 \(p_{len+1}\) 和 \(q_{len+1}\),再枚举逆序对数进行统计。 令 \(f_{i,j}\) 表示有 \(j\) 个逆序对的 \(i\) 阶排列的个数。 ......
【前缀和优化 dp】CF1542E2 Abnormal Permutation Pairs (hard version) 题解
CF1542E2 首先时间复杂度肯定是 \(\mathcal{O}(n^3)\) 的。 容易想到先枚举最长公共前缀,然后枚举 \(p_{len+1}\) 和 \(q_{len+1}\),再枚举逆序对数进行统计。 令 \(f_{i,j}\) 表示有 \(j\) 个逆序对的 \(i\) 阶排列的个数。 ......
【树上背包】CF1856E1 PermuTree (easy version) 题解
CF1856E1 发现题目的要求只需要相对的大小关系,考虑一个子树时,不妨令子树内部编号连续。类似于一个 dp,这样也可以更好地将信息由儿子转移到父亲。 设 \(u\) 的孩子为 \(v_1,v_2,\dots,v_k\)。由于每棵子树内的编号是连续的,令以 \(v_i\) 为根的子树的编号为 \( ......
【区间 dp】P5189 [COCI2009-2010#5] ZUMA 题解
P5189 容易想到区间 dp,考虑设计状态。 首先如果只有 \(l,r\) 两维的话,是无法转移的。然后发现 \(m\) 是转移的一个必要的条件,可加入 \(m\) 这一维。由于是区间 dp,所以只需考虑向左或向右加珠子,不妨令 \(f_{i,j,k}\) 消除 \([i,j]\) 以及 \(i\ ......
【dp】【进制】P3464 [POI2007] WAG-Quaternary Balance 题解
P3464 显然的,先将原数变为四进制的数。 由于算的是进位/不进位的代价最小值和方案数,容易想到 dp。 这里假定该四进制数是从高位到低位的,顺序显然是由低位到高位。 令 \(f_{i,0/1}\) 表示第 \(i\) 位进 / 不进位的最小代价,\(g_{i,0/1}\) 表示的是最小代价下的方 ......
[题解] CF1790E - XOR Tree
CF1790E - XOR Tree 题意 给定一颗无根树,在可以改变任意一个点的点权操作基础上,让树上任意简单路径的异或和不为 \(0\) ,问最少需要多少次操作。 思路 假设某个点为根,设 \(pre_x\) 为 \(x\) 点到根的树上前缀异或和, \(a_x\) 为 \(x\) 的点权,则 ......
[题解]CF514D R2D2 and Droid Army
思路 首先,可以转化题意,找到一个极长的区间 \([l,r]\) 使得(其中 \(mx_i\) 表示 \([l,r]\) 区间中属性 \(i\) 的最大值): \[\sum_{i = 1}^{m}mx_i \leq k \]显然对于这个东西当 \(l,r\) 发生移动时,是极其好维护的,所以想到双指 ......
题解——2023年码谷提高组模拟赛1016
题解——2023年码谷提高组模拟赛1016 一套被各种转来转去的题;参考:https://blog.csdn.net/liuziha/article/details/127353981、https://www.luogu.com.cn/blog/Chen5201314/xiao-nei-bi-sai ......
「BZOJ2505」tickets 题解
preface 网上目前还没看到我的方法,就大概讲一下做法 solution 首先想到贪心,考虑 \([l, r]\) 的最大次数,一定是找到最小的 \(x\) 满足 \(l \sim x\) 的位数的和大于等于 \(k\),然后递归的求解 \([x + 1, r]\),易证。 还是考虑将 \(Qu ......
2023年石门中学NOIP模拟测试(2023.10.17)
原题大战,还是 \(4\) 道计数... 放个头图: 一蓝一紫两黑,简单且原题 0.o? 出模拟赛搬原题演都不演了,他真的我哭死。那这总结不写也罢 T1 \(n\leq 10^3\)。 简单来说,要选出子序列满足相同颜色连续的方案数。 签到题,但写了 \(\text{1h}\) 的我是 sb。 直接 ......
CF1879F Last Man Standing 题解
原题 翻译 观察题目,容易发现当题目难度为 \(x\) 时一个 OIer 存活时间为 \(h_i \lceil \frac{a_i}{x} \rceil\) 发现 \(a_i\) 较小,所以我们先考虑暴力枚举 \(x \in [1, \max a_i]\) ,然后把原数组按 \(a_i\) 排个序, ......
10-16 NOIP模拟赛
10-16 NOIP模拟赛 这周末就要去考 CSP-S 啦!!! 所以改变答题策略,放弃之前死磕第一题正解的做题方法,以暴力为主,得分为主,思考出正解认为能得分后才写。 然后发现把第一题暴力打了以后,正解也浮出水面了。 明天继续尝试,然后注意休息,一定要保持良好睡眠。 T1 购买饮料(buy) 题目 ......
2023noip赛前20天冲刺 Day6 复活赛
回来吧牢大 \sad 小时候看这集复活赛打赢了。(100+100+10+15) 回来吧 刺激战场 我最骄傲的信仰 历历彩目的G港 眼泪莫名在流淌 你是记得98K 还有给力的装备 把敌人都给打退 就算通宵也不累 A.嗯鸥哀劈(noip) B.讴不死塔扣(obstacle) C.钙绿(probabili ......