题解wag-quaternary quaternary balance

思路分析 前置知识：排列是没有重复元素的！ 猜想 我们可以进行一种猜想，对于 \(x\)，输出： \[\begin{cases} x+1&x<N\\ 1&x=N \end{cases}\]将代码提交上去，我们可以发现这种猜想值正确的！ 证明 但是作为一名合格的 OIer我们必须证明这种做法是正确的。 ......

思路分析 因为最终要使得 \(a,b\) 相同，所以我们应该希望让相同的数字尽量相同。所以，我们需要先对 \(a\) 和 \(b\) 进行排序，这样子就可以使用双指针的方法来维护最终值了。 我们定义 \(l\) 指针指向 \(a_l\)，\(r\) 指针指向 \(b_r\)。因为题目要求添加数字的次 ......

思路分析 答题思路 一道纯暴力题！ 因为我们发现数据最大是 \(5\)，而枚举全排列的时间复杂度为 \(\mathcal O(n!)\)，对于这种极小的数据范围是丝毫不用顾虑的，因为我们只需要执行 \(120\) 次。 如何快速求出一个数组的全排列？ 我们可以使用 dfs，一层一层获取这个数组的全排 ......

思路分析 一道很有洛谷个性的模拟签到题。 按照题意，我们只需读入 \(a,b,c,d,e\)，然后对其进行求和，然后依次根据 洛谷咕值系统介绍 进行判断即可。 这样是不是太没有意思了？今天为大家带来一点干货作为福利！ 介绍：accumulate() 函数！ 简略分析：这个函数可以求出一段区间内的数字 ......

思路分析 一道很有洛谷个性的模拟签到题。 按照题意，我们只需读入 \(a,b,c,d,e\)，然后对其进行求和，然后依次根据 洛谷咕值系统介绍 进行判断即可。 这样是不是太没有意思了？今天为大家带来一点干货作为福利！ 介绍：accumulate() 函数！ 简略分析：这个函数可以求出一段区间内的数字 ......

思路分析 我们只需要找到左边第一个大于 \(0\) 的位置 \(l\) 与右边第一个大于 \(0\) 的位置 \(r\)，输出 \(r-l+1\) 即可。 但是很坑的一点是，如果 \(∀i∈[1,n],a_i=0\)，那么 \(l\) 和 \(r\) 会重合，代码会输出 \(1\)！所以，我们需要定 ......

思路分析 一道大模拟。 一共只有 \(34\) 种牌，因此可以一次判断是否“听”这些牌。比如，为了判断是否“听”一万，只需要判断自己拿到这张一万后能否可以继续和牌。这样，问题就转化成了给定 \(14\) 张牌，判断是否可以和牌。为此，我们可以递归求解：首先将两张牌作为“将”，然后每次选 \(3\) ......

思路分析 暴力枚举？ 我们可以枚举每个数字变或不变，最后判断整个矩阵是否满足条件。但是，这样做最多需要枚举 \(2^{255}≈5\times10^{67}\) 中情况，是一定会超时的。 大眼观察 注意到 \(n\le15\)，第一行只有不超过 \(2^{15}=32768\) 种可能，所以第一行的 ......

思路分析 构造排列表 立方体只有 \(4\) 个，暴力法是可行的。但是如果我们要暴力，首先得清楚一个立方体到底有几种不同的旋转方式。 接下来，我们用“姿态”一词代替“旋转方法”。假设 \(6\) 个面的编号为 \(1\sim6\)，从中选择一个面作为“顶面”，“顶面”的对面为“底面”。然后我们在剩下 ......

首先题目翻译是有问题的，求的不是矩形而是最小的正方形。 Solution 先考虑一下若正方形的边都只能平行于坐标轴怎么做：找到 \(x,y\) 方向的坐标最值，那么答案就是 \(\max^2\{X_{\max}-X_{\min},Y_{\max}-Y_{\min}\}\)。 接下来，若正方形可以是斜 ......

（本题解的所有图片使用 Geometry Widget 进行绘制） （一）\(K=1\) 情况 \(K=1\) 是平凡的。 （二）\(K=2\) 情况 显然，对于平面内的两个不交正方形，存在至少一条平行于坐标轴的直线将它们划分到两侧。 以直线平行于 \(y\) 轴为例。 考虑按 \(x\) 轴正方向 ......

orz negiizhao 自底向上确定每个点的所有出边上挂的字符，那么问题就是比较 \(x,y\) 两个子树的字典序大小。直接一起往下 dfs，先找到标记点的子树更小，如果 dfs 过程中一棵树找完了而另一棵树没找完并且还没确定大小，这时还没找完的那棵树应当排到前面。在递归的最浅层也就是比较 \( ......

写在前面的话 本场比赛难度估计大约可能是 \(\text{NOIp}\) 难度？ 考场得分 \(100+100+100+0=300\) ,封榜时排名 \(\text{rank6}\) 。 T1 题目描述： 有一张地铁交通网 \(G\)．\(G\) 拥有 \(n\) 个站点和 \(m\) 条地铁线路． ......

[ABC319E] Bus Stops 题解 题意简介 给定 \(n\) 个公交站。对于第 \(i\) 个公交站，在时刻 \(p_i \times k,k \in \mathbb{N}\) 有一辆公交车出发，在经过 \(t_i\) 的时间后，到达第 \(i+1\) 个公交站。 在走到第一个公交车之前 ......

没有写 F，不确定我的做法对不对。 评价：什么牛逼场次，代码大赛是嘛，从 A 开始就感觉到不对了，而且题面写的真答辩。 A.Legendary Players 题目分析： 直接按题目模拟即可。 代码： 点击查看代码 #include<bits/stdc++.h> using namespace st ......

题目链接 #6515. 「雅礼集训 2018 Day10」贪玩蓝月 - 题目 - LibreOJ (loj.ac) 分析 一个朴素的想法就是模拟这个过程，当询问时做一遍01背包，但这样明显会超时 想象这样一个例子：当两次询问中间夹着一次插入操作 第二次进行01背包，明显只需要在第一次的基础上对新插入 ......

[NOIP1998 普及组] 三连击 思路 想一想桶 得到三个数之后把每一位依次存入桶 然后遍历这个桶，看哪一位为\(0\) 代码 // 语言：C++ #include <iostream> #include <cstring> //memset using namespace std; int m ......

P3533 [POI2012] RAN-Rendezvous 题目大意：给定外向树森林，每次给定两个起始点，求两个点沿边移动最少步数相遇。 \(n\) 个点，\(n\) 条边，并且每个点有唯一的出边，显然构成了多棵基环树，对于每个基环树分别处理：找出环上的点，因为要求支持求出任意两点距离，前缀和一下 ......

思路分析 前言 题解区好似没有用哈希的啊。 发现大家都在用 map 来存是否出现过数字，但是需要注意的是，map 的单次查询时间复杂度是 \(\mathcal O(\log n)\) 的，对于大规模的数据就很可能会 TLE。所以，我们可以使用哈希的方法来判断数字是否出现过。 浅谈哈希 哈希，是通过哈 ......

A.Two Towers 题目描述： 有 \(a,b\) 两座由红蓝色方块垒成的塔,其中 \(a\) 的高度为 \(n\) ； \(b\) 的高度为 \(m\) ，用 R 代表红色；用B代表蓝色。 你可以多次把其中一座顶端的方块移到另一座的顶端（可以不移动）。问有没有一种方法可以使两座塔中均没有连续 ......

思路分析 前言 又是一道小模拟题，不过细节巨多，可以用来锻炼自己的代码能力。 解法 本题实际上就是模拟长除法的计算过程，其中每一步除法时都有被除数及其余数，当被除数出现重复时就表示出现循环节了。所以需要记录每一次的被除数及其在循环小数中的位置，需要判断当除数不够除，每一次补零也需要记录其对应的位置。 ......

题目链接 要想使得数字 \(x\) 是中位数，就必须选出 \(k\) 个小于 \(x\) 的数和 \(k\) 个大于 \(x\) 的数。 我们考虑对数字附上特殊值，小于 \(x\) 的数赋值为 \(-1\)，大于 \(x\) 的数赋值为 \(1\)，\(x\) 则赋值为 \(0\)，那么若一段包含 ......

Codeforces Round 895 (Div. 3) F~G F. Selling a Menageri 考虑如何让卖出的价格翻倍，那么自然是从 \(i \to a_i\) 。通过这样连边，我们可以发现，边集构成了基环树森林。显而易见的是，如果不考虑环，那么图就是拓扑图，按照拓扑关系跑一遍，就 ......

思路分析 前言 一道比较简单的数学题。 解法 根据题意可以推算出最大值 $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 ......

洛谷题目链接 AT原题 考虑构造出来的序列 \(a\) 的特征，因为每次会给 \(a_i\) 加 \(1\)，\(a_j\) 加 \(2\)，所以每次操作后 \(\sum a_i\) 会加上 \(3\)。 所以有\(\sum a_i =3m\) 。 又因为每次操作只给一个数加 \(1\)，所以每次操 ......

CF29D Ant on the Tree 题目知识点：LCA。 题目传送门 题意 给定一棵以 \(1\) 为节点的树，再给定树的所有叶子节点的一个序列。 现在执行一个操作：从 \(1\) 开始遍历每个节点，并返回根，要求每条边经过的次数一定为 \(2\) 。 问是否能够使得访问节点序列中叶子节点的 ......

题目大意： 给定一些指令，计算需要多大的舞台。 这是一道大模拟！！！ 只要遍历每次指令，然后判断是否摔倒，摔倒输出`-1`否则记录，最后求出面积就行了。 最后附上代码 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int xx[] ......

题意 给定一个环形 01 序列，每次变化时，对于每个位置，如果前一个值是 1 ，则当前值翻转。求变化 B 次后的序列。 思路 由于 B 的值很大，所以如果对每一次变化进行模拟，效率非常低下。 不难发现，每一次变化后的状态完全是由当前状态决定的，而 N 的范围很小，所以可能的状态总数 2^N 也不是很 ......

一道递推 由于对于一个数 x ,可得 x+10-x=10（废话） 于是问题就变成了 0+m 次,然后 x+m 就变成 0+x+m （还是废话） 于是可以写一个递推。 首先对于函数 f(m) 可分为 m ≤ 9 和 m>9 ,然后可得出递推式结果为 1 或 f(m-9)+f(m-10) ，所以我们可以 ......

康了康唯一的题解，说没必要用DP，我就给出DP的解法。 这其实是道水题，唯一的坑是有可能楼上没有开的灯，坑了我们机房的一堆人（ WA on test 4 ），剩下的就是DP。 我们用 a[n][0],表示第 n 层的第一个房间，用 a[n][1]，表示第 n 层的最后一个房间。 这里提供一个收集型的 ......