集训队 题解2019 day
CF387B 题解
思路分析 因为最终要使得 \(a,b\) 相同,所以我们应该希望让相同的数字尽量相同。所以,我们需要先对 \(a\) 和 \(b\) 进行排序,这样子就可以使用双指针的方法来维护最终值了。 我们定义 \(l\) 指针指向 \(a_l\),\(r\) 指针指向 \(b_r\)。因为题目要求添加数字的次 ......
CF431B 题解
思路分析 答题思路 一道纯暴力题! 因为我们发现数据最大是 \(5\),而枚举全排列的时间复杂度为 \(\mathcal O(n!)\),对于这种极小的数据范围是丝毫不用顾虑的,因为我们只需要执行 \(120\) 次。 如何快速求出一个数组的全排列? 我们可以使用 dfs,一层一层获取这个数组的全排 ......
P9516 题解
思路分析 一道很有洛谷个性的模拟签到题。 按照题意,我们只需读入 \(a,b,c,d,e\),然后对其进行求和,然后依次根据 洛谷咕值系统介绍 进行判断即可。 这样是不是太没有意思了?今天为大家带来一点干货作为福利! 介绍:accumulate() 函数! 简略分析:这个函数可以求出一段区间内的数字 ......
P9516 题解
思路分析 一道很有洛谷个性的模拟签到题。 按照题意,我们只需读入 \(a,b,c,d,e\),然后对其进行求和,然后依次根据 洛谷咕值系统介绍 进行判断即可。 这样是不是太没有意思了?今天为大家带来一点干货作为福利! 介绍:accumulate() 函数! 简略分析:这个函数可以求出一段区间内的数字 ......
P9517 题解
思路分析 我们只需要找到左边第一个大于 \(0\) 的位置 \(l\) 与右边第一个大于 \(0\) 的位置 \(r\),输出 \(r-l+1\) 即可。 但是很坑的一点是,如果 \(∀i∈[1,n],a_i=0\),那么 \(l\) 和 \(r\) 会重合,代码会输出 \(1\)!所以,我们需要定 ......
UVA11210 题解
思路分析 一道大模拟。 一共只有 \(34\) 种牌,因此可以一次判断是否“听”这些牌。比如,为了判断是否“听”一万,只需要判断自己拿到这张一万后能否可以继续和牌。这样,问题就转化成了给定 \(14\) 张牌,判断是否可以和牌。为此,我们可以递归求解:首先将两张牌作为“将”,然后每次选 \(3\) ......
UVA11464 题解
思路分析 暴力枚举? 我们可以枚举每个数字变或不变,最后判断整个矩阵是否满足条件。但是,这样做最多需要枚举 \(2^{255}≈5\times10^{67}\) 中情况,是一定会超时的。 大眼观察 注意到 \(n\le15\),第一行只有不超过 \(2^{15}=32768\) 种可能,所以第一行的 ......
UVA1352 题解
思路分析 构造排列表 立方体只有 \(4\) 个,暴力法是可行的。但是如果我们要暴力,首先得清楚一个立方体到底有几种不同的旋转方式。 接下来,我们用“姿态”一词代替“旋转方法”。假设 \(6\) 个面的编号为 \(1\sim6\),从中选择一个面作为“顶面”,“顶面”的对面为“底面”。然后我们在剩下 ......
题解 SP4586 Texas Trip
首先题目翻译是有问题的,求的不是矩形而是最小的正方形。 Solution 先考虑一下若正方形的边都只能平行于坐标轴怎么做:找到 \(x,y\) 方向的坐标最值,那么答案就是 \(\max^2\{X_{\max}-X_{\min},Y_{\max}-Y_{\min}\}\)。 接下来,若正方形可以是斜 ......
题解 P8389【[COI2021] Izvanzemaljci】
(本题解的所有图片使用 Geometry Widget 进行绘制) (一)\(K=1\) 情况 \(K=1\) 是平凡的。 (二)\(K=2\) 情况 显然,对于平面内的两个不交正方形,存在至少一条平行于坐标轴的直线将它们划分到两侧。 以直线平行于 \(y\) 轴为例。 考虑按 \(x\) 轴正方向 ......
「题解」P9558 [SDCPC2023] Trie
orz negiizhao 自底向上确定每个点的所有出边上挂的字符,那么问题就是比较 \(x,y\) 两个子树的字典序大小。直接一起往下 dfs,先找到标记点的子树更小,如果 dfs 过程中一棵树找完了而另一棵树没找完并且还没确定大小,这时还没找完的那棵树应当排到前面。在递归的最浅层也就是比较 \( ......
[EDISOI] Round 1 题解
写在前面的话 本场比赛难度估计大约可能是 \(\text{NOIp}\) 难度? 考场得分 \(100+100+100+0=300\) ,封榜时排名 \(\text{rank6}\) 。 T1 题目描述: 有一张地铁交通网 \(G\).\(G\) 拥有 \(n\) 个站点和 \(m\) 条地铁线路. ......
[ABC319E] Bus Stops 题解
[ABC319E] Bus Stops 题解 题意简介 给定 \(n\) 个公交站。对于第 \(i\) 个公交站,在时刻 \(p_i \times k,k \in \mathbb{N}\) 有一辆公交车出发,在经过 \(t_i\) 的时间后,到达第 \(i+1\) 个公交站。 在走到第一个公交车之前 ......
【题解】 AtCoder Beginner Contest 319
没有写 F,不确定我的做法对不对。 评价:什么牛逼场次,代码大赛是嘛,从 A 开始就感觉到不对了,而且题面写的真答辩。 A.Legendary Players 题目分析: 直接按题目模拟即可。 代码: 点击查看代码 #include<bits/stdc++.h> using namespace st ......
day13
C++面试题 1.说一下常见的linux指令 ls:查看当前文件目录 cd:切换当前目录 rm:删除文件或者文件夹 cp:复制文件或者文件夹 cat:查看文件内容 touch:创建一个新文件 pwd:显示当前工作目录 2.请你说说delete和free的区别?1.delete是运算符,free是库函 ......
算法训练day4: LeetCode 24
算法训练day4: LeetCode 24.19.142.面试题07.02 24.两两交换链表中的结点 题目 题目24. 两两交换链表中的节点 - 力扣(LeetCode) 题解 讲解代码随想录 (programmercarl.com) 第一想法:模拟的方法,使用三个指针,将结点两两交换。 clas ......
LOJ#6515. 「雅礼集训 2018 Day10」贪玩蓝月题解
题目链接 #6515. 「雅礼集训 2018 Day10」贪玩蓝月 - 题目 - LibreOJ (loj.ac) 分析 一个朴素的想法就是模拟这个过程,当询问时做一遍01背包,但这样明显会超时 想象这样一个例子:当两次询问中间夹着一次插入操作 第二次进行01背包,明显只需要在第一次的基础上对新插入 ......
ZROI - CSP 七连测 Day2 赛总
Genral 惊险刺激。但还是菜。 统计: 得分 得分率 挂分率 AC 数 200 50% 0% 2 各题目详情: 题目 A B C D Total 期望得分 100 0 100 0 200 实际得分 100 0 100 0 200 挂分 0 0 0 0 0 A \(n≤4\)?直接搜! 于是就没了 ......
【题解】三连击
[NOIP1998 普及组] 三连击 思路 想一想桶 得到三个数之后把每一位依次存入桶 然后遍历这个桶,看哪一位为\(0\) 代码 // 语言:C++ #include <iostream> #include <cstring> //memset using namespace std; int m ......
P3533 [POI2012] RAN-Rendezvous 题解
P3533 [POI2012] RAN-Rendezvous 题目大意:给定外向树森林,每次给定两个起始点,求两个点沿边移动最少步数相遇。 \(n\) 个点,\(n\) 条边,并且每个点有唯一的出边,显然构成了多棵基环树,对于每个基环树分别处理:找出环上的点,因为要求支持求出任意两点距离,前缀和一下 ......
[刷题记录Day 23]Leetcode二叉树
No.1 题目 修剪二叉搜索树 思路 递归法 有点抽象,要对具体案例做模拟才好懂 递归分析 返回值:节点,参数:节点,[下界,上界] 终止条件:遇到空节点,返回空 单层递归逻辑:判断不在范围内的情况:当前节点小于下界/大于上界,直接返回右/左子树递归结果;若在范围内,则递归筛查左右子树,返回当前节点 ......
CF1570D 题解
思路分析 前言 题解区好似没有用哈希的啊。 发现大家都在用 map 来存是否出现过数字,但是需要注意的是,map 的单次查询时间复杂度是 \(\mathcal O(\log n)\) 的,对于大规模的数据就很可能会 TLE。所以,我们可以使用哈希的方法来判断数字是否出现过。 浅谈哈希 哈希,是通过哈 ......
【题解】Educational Codeforces Round 143(CF1795)
A.Two Towers 题目描述: 有 \(a,b\) 两座由红蓝色方块垒成的塔,其中 \(a\) 的高度为 \(n\) ; \(b\) 的高度为 \(m\) ,用 R 代表红色;用B代表蓝色。 你可以多次把其中一座顶端的方块移到另一座的顶端(可以不移动)。问有没有一种方法可以使两座塔中均没有连续 ......
UVA202 题解
思路分析 前言 又是一道小模拟题,不过细节巨多,可以用来锻炼自己的代码能力。 解法 本题实际上就是模拟长除法的计算过程,其中每一步除法时都有被除数及其余数,当被除数出现重复时就表示出现循环节了。所以需要记录每一次的被除数及其在循环小数中的位置,需要判断当除数不够除,每一次补零也需要记录其对应的位置。 ......
题解 [CQOI2009] 中位数
题目链接 要想使得数字 \(x\) 是中位数,就必须选出 \(k\) 个小于 \(x\) 的数和 \(k\) 个大于 \(x\) 的数。 我们考虑对数字附上特殊值,小于 \(x\) 的数赋值为 \(-1\),大于 \(x\) 的数赋值为 \(1\),\(x\) 则赋值为 \(0\),那么若一段包含 ......
[题解] Codeforces Round 895 (Div. 3) F~G
Codeforces Round 895 (Div. 3) F~G F. Selling a Menageri 考虑如何让卖出的价格翻倍,那么自然是从 \(i \to a_i\) 。通过这样连边,我们可以发现,边集构成了基环树森林。显而易见的是,如果不考虑环,那么图就是拓扑图,按照拓扑关系跑一遍,就 ......
JAVA SE day4
JAVA SE 基本的Dos 命令 #盘符切换 D:#查看当前目录下的所有文件 dir#切换目录(/d 换盘符 写在cd 后) cd 文件夹#返回上一级cd..#清理屏幕 cls#打开应用 calc 计算机 ,notepad 记事本,mspaint 画图#ping 命令 可以获得 IP地址 延迟 一 ......
UVA11809 题解
思路分析 前言 一道比较简单的数学题。 解法 根据题意可以推算出最大值 $v=\Big(1-\dfrac{1}{2{M+1}}\Big)\times2{2{E-1}}=A\times10B$。因为两边都比较大,所以可以同时求以 $10$ 为底的对数:$\lg v=\lg(2{M+1}-1)-(M+1 ......
[AGC036C] GP 2 题解
洛谷题目链接 AT原题 考虑构造出来的序列 \(a\) 的特征,因为每次会给 \(a_i\) 加 \(1\),\(a_j\) 加 \(2\),所以每次操作后 \(\sum a_i\) 会加上 \(3\)。 所以有\(\sum a_i =3m\) 。 又因为每次操作只给一个数加 \(1\),所以每次操 ......
2019 ICPC Universidad Nacional de Colombia Programming Contest
A. Amazon 给定\(n\)条直线(存在共线的情况),在每两条垂直的直线的交点处需要建一个交叉点,求交叉点的数量,注意需要去除共线时候的交叉点 题解 因为要除去共线的情况,我们考虑将一条直线以方向向量\(v\),与\(x\)轴的交点的横坐标\(x\)的方式存储 注意: 对于\(v\)来说需要最 ......