题解 教科书 教科p4593
迷宫题解( •̀ ω •́ )y
这道题很明显是一个dfs的问题 这道题首先要在主函数里完成建造迷宫但在建造迷宫之前,你要把所有的位置标为可以去 memset(a,'.',sizeof(a)); 他给你了下标,所以你就可以直接建造迷宫,代码如下 for(int i=1;i<=T;i++){ cin>>xx>>yy; a[xx][yy ......
[ABC271E] Subsequence Path 题解
[ABC271E] Subsequence Path 题解 思路解析 很好的一道题,很有迷惑性,表面上是一道图论实际上是 dp,定义 \(f_{i}\) 为从 \(1\) 到 \(i\) 的最短 “好路”。先把每条边对应的起点,终点和边权记录下来,然后输入每个 \(e\),由于是子序列顺序不会改变, ......
CF1886C Decreasing String 题解
Problem - C - Codeforces Decreasing String - 洛谷 p.s. 本题提到的所有 \(s_i\) 的 \(i\) 均表示 \(s\) 字符串的下标,而不是第 \(i\) 个字符串。因为我懒不想改了 每次遇到这种题都想不到最好的解决方法,我是不是应该把所有比赛的 ......
HDU2544 最短路 题解 Bellman-Ford算法
题目链接:https://acm.hdu.edu.cn/showproblem.php?pid=2544 题目大意:一道简单的最短路。主要是记录一下 bellman-ford 算法的实现。 示例程序(bellman-ford): #include <bits/stdc++.h> using name ......
AT_joisc2016_k 题解
传送门 题意 通信题。Anya 和 Boris 有一棵有根树,每一天 Anya 会标记一些边,她可以给 Boris 发送一个不超过 1000 位的二进制串,Boris 要多次回答一个点到根的路径上有多少条边被标记过,他不知道这个二进制串,但是每次回答可以查看这个二进制串的 20 位。要求你给出两人的 ......
UVA10364 题解
题意简述 给定 \(n\) 根木棍,第 \(i\) 根的长度为 \(a_{i}\),求能否使用全部木棍拼成一个正方形。 题目分析 这道题和 P1120 很像,都考察了对于 DFS 的剪枝优化。 具体地,我们有以下几个剪枝策略 计算出每根木棍的长度之和,记为 \(sum\),若 \(sum \bmod ......
P2726 [SHOI2005] 树的双中心 题解
Description \(n\leq 5\times 10^4\),树的深度 \(\leq 100\)。 Solution 对于每个 \(x,y\),满足 \(d(v,x)\leq d(v,y)\) 或者 \(d(v,x)\geq d(v,y)\) 的点一定构成一个子树,所以可以枚举这个子树的根, ......
CF763E Timofey and our friends animals题解
题目链接:CF 或者 洛谷 简单来说就是求 \([l,r]\) 这些点都存在的情况下,连通块的数量,看到七秒时限,而且每个点相连的边数很少,可以想到离线下来使用莫队类的算法解决 连通块问题,一般可以考虑使用并查集解决。对于并查集来说,它的增加是非常简单的,但删除是困难的,可持久化并查集时空常数都较大 ......
P8078 [WC2022] 秃子酋长题解
题目链接: P8078 [WC2022] 秃子酋长 题目所求较难理解,我们考虑转化下,首先这是个 \(1 \sim n\) 的排列,而且要求相邻对应的原位置的绝对值最大我们先考虑最简单的一种情况:\([1,n]\) 的答案。 来看这张我画的丑图。 以样例为例,如果求 \([1,n]\) 的答案,我们 ......
P9474 [yLOI2022] 长安幻世绘题解
题目链接: [yLOI2022] 长安幻世绘 比较不错的综合题。考虑下处理极差的绝对值我们应该怎么做,很显然排序是有必要的,我们需要带着下标排序。 考虑几个核心点: 1.假如没有其他限制考虑极差与序列长度有啥关系,很显然长度越长,极差单调不降,具备单调性。 2.考虑对于一个长度为 \(L\) 的连续 ......
[ABC271G] Access Counter 题解
[ABC271G] Access Counter 题解 思路 挺难的 DP。 状态里面不能含有天数,只能从时间点入手,一眼矩阵快速幂所以考虑以登录次数作为阶段设计状态。 可以得到这个DP:\(g_{i ,j}\) 表示登录 \(i\) 次,且第 \(i\) 次登录在 \(j\) 时刻的概率。 转移可 ......
「ABC334F Christmas Present 2」题解
Cnblogs 线段树优化 dp?线段树优化 dp! Solution 题目来源:ABC334F(in 洛谷| in AtCoder)题目大意很清晰就不讲了。 我们发现礼物是固定从 \(1\sim n\) 房间送的,唯一要分讨的地方就是什么时候要回去拿礼物。所以很容易想到二维 dp。 定义 \(f_ ......
CF1545C AquaMoon and Permutations 题解
题目链接 点击打开链接 题目解法 很不错的题 首先题目保证了一定有解,所以不用考虑奇怪的无解情况 从列中的数字种类入手 如果一列中有数字 \(c\) 恰好只有第 \(x\) 行存在,那么第 \(x\) 行一定在答案序列中 考虑选了第 \(x\) 行会牵连一些行不能选,那么把这些行去掉,继续跑上面的操 ......
P10009 [集训队互测 2022] 线段树 题解
题目链接:P10009 [集训队互测 2022] 线段树 神仙分块题,先给一下出题人的神仙官解:官解 前面还看得懂。后面是啥?这不是 ds 题咋和 dp、轮廓线扯上关系了。看了半天,还是这个启发了我: 其手玩下,在 Excel 里写一下,可以理解到这里其实是想表达的一个核心意思是啥:对于一组序列而言 ......
P9993 [Ynoi Easy Round 2024] TEST_133 题解
题目链接: [Ynoi Easy Round 2024] TEST_133 首先历史最大加,吉司机跑不掉了,维护历史最大加标记以及历史最大,那么根据吉司机标记思想更新操作应该为 \[new \Leftarrow \max{(h_{max},a_i+h_{addMax})} \]新的历史最大值,由原来 ......
P9989 [Ynoi Easy Round 2023] TEST_69 题解
题目链接: [Ynoi Easy Round 2023] TEST_69 首先GCD有比较良好的一些性质。我们观察到一次 \(GCD(a_i,x)\) 操作,会有以下两种变化。 如果 \(x \bmod a_i == 0\),那么很显然 \(\gcd(a_i,x)==a_i\),不会发生任何改变。 ......
CF1916G Optimizations From Chelsu 题解
Optimizations From Chelsu 题意 给定 \(n\) 个结点的树,边有正整数边权 \(w_i\)。定义 \(len(u,v)\) 表示 \(u\) 到 \(v\) 的路径的边数,\(\gcd(u,v)\) 表示 \(u\) 到 \(v\) 的路径上所有边权的 \(\gcd\), ......
P4681 [THUSC2015] 平方运算 题解
考虑模数给定,且给定模数最大为 \(9977\)。 这启示我们每个数字最多平方取模 \(9966\) 次就会开始重复。但是事实上可能要小得多,于是我们尝试打表验证规律。 打表程序:code 我们验证了确定模数时,所有数字的循环节的 \(\text{lcm} \le 60\)。 事实上,这相当于对于每 ......
P10035题解
P10035题解 此题是一道找规律题。 将 A,B,C 前六位列出: A : 101010 B : 010101 C : 001001 我们可以发现:对于 A,B,C 中前六位的匹配字符的个数是相同的(均为三位)。 所以说,对于每一个 N ,也就是 $3^N$ 级台阶,我们都只需要判断最后三位求出最 ......
P9933 [NFLSPC #6] 9.pop_book(); 题解
题目链接: P9933 [NFLSPC #6] 9.pop_book(); 先考虑一个最基本的式子: \(x=v \times t\),很显然的一点是,除了 Alek岁,每个人的运动路程函数写出来都是一条一次函数,斜率为速度 \(v\),而截距暂时无法确定。 我们考虑下 Alek岁 的变化情况。很显 ......
CF1909G Pumping Lemma 题解
题目链接 点击打开链接 题目解法 很 \(nb\) 的字符串题 首先,\(x+y\) 是 \(s,t\) 的公共前缀,\(y+z\) 是 \(s,t\) 的后缀 所以如果 \(s,t\) 的最长公共后缀与 \(lcp\) 不交,那么无解,如果有解,则只留下 \(s,t\) 的最长公共后缀,因为前缀的 ......
P9858 [CCC 2008 S1] It’s Cold Here! 题解
声明: 该题目已不再接受题解 小红题*1 正题 每个城市都有不同的气温,你想要知道哪个城市的气温最低。 现在你统计了一些城市的气温 $(1 \leq$ 城市数量 $\leq 10000$,$-273 \leq$ 气温 $\leq 200)$,请你实现一个代码,求出气温最低的城市名。 乍一看就确定了思 ......
P9960 题解
思路 只要回答是“是”,那么就会排除掉没有这个特征的动物,那么可行集就变少了,要想“是”的回答数量最多,则提问的次数就得越多,我们提问大部分动物有的特征,“不是”的可能会比较小,且可以刷“是”的次数。注意得到的结果要加 \(1\),因为最后不会只剩下一种动物,要再问一遍它们不同的特征才能得到答案。 ......
CF493B 题解
好久没写题解了 思路 统计两个选手的分数,如果不是相同的就直接比大小,否则按字典序的大小,注意这里的字典序是两个选手的分数拼起来,比如样例 \(1\) 5 1 2 -3 -4 3 那么两个选手分别是 123 和 34。如果字典序相同,就看最后一个得分的选手是谁谁就赢。 代码 #include<ios ......
题解 P7165 [COCI2020-2021#1] Papričice
传送门。 题意 有一棵树,可以断掉 \(2\) 条边,会形成三个连通块,求三个连通块中大小最大减最小的最小值。 分析 我们观察两条边之间的关系,分类考虑: 两条边成祖孙关系。 两条边没有祖孙关系。 首先,我们肯定我们的大方向,固一动一(说起来为什么想到了数学题),先固定一条边,再在其他边中取得最适合 ......
U390630 分考场题解
题目链接:U390630 分考场 本题来自于2019年蓝桥杯国赛的题。在洛谷上也被标为了假题。原因是首先官方在需要输出浮点数的情况下,并没有开启spj,并且官方所给的数据当中,总有一两个数据以不知道到底是怎样的一个算法导致能莫名其妙四舍五入了,保留十位小数也看不出不该四舍五入的理由。并且在很明显的树 ......
P9753 [CSP-S 2023] 消消乐 题解
这里是被说烂了的随机化线性做法。 相信大家都已经做过 QOJ 6504,因此我们考虑采用类似的办法通过此题。我们对每个字符随机一个 \(k\times k\) 的矩阵,并求出其矩阵的逆。 然后,我们在偶数位放原矩阵,在奇数位放逆矩阵,这样,一段区间合法当且仅当这段区间的矩阵积为单位矩阵 \(I\), ......
CSP-S 题解
非考场上想出来的会标星号。 T1 密码锁 鲜花:我看到这道题的时候满脑子想的都是春测的 lock。 考虑到只有五个拨圈,每个拨圈只有 \(10\) 个状态,\(n\le 8\),那么直接暴力枚举每个状态即可。 考场代码: // 15: 00 // 15: 24. #include<bits/stdc ......
CF1844G 题解
鉴定为学 MO 学的。 MO 中著名的《数学奥林匹克小丛书高中卷》的第十五本曾经讲过,如果原方程较难解,可以考虑给左右两边同时对 \(M\) 取模,然后研究取模以后的问题,其中 \(M\) 为一个根据问题选取的适当的整数。 我们看见这个问题觉得很烦,因为大家都能发现这个条件给的相当于 \(d_i+d ......
CF1748F 题解
这 3000? 以下,\(\operatorname{op}(i)\) 代表对 \(i\) 进行一次操作。 我们考虑暴力。因为每一位都是分开处理的,我们考虑仅仅把一段区间的端点交换。即我们希望通过 \(\operatorname{solve(l, r)}\) 把 \(a_ia_j\) 交换而其他下标 ......