搜索结果
查询Tags标签： 题解，共有 1043条记录-
CF1715D 题解
前言 题目传送门！ 更好的阅读体验？ 感觉挺不错的一道图论转化题。（其实也和图论关系不大。） 思路 对于每个条件 \(a_u \mid a_v = x\)，二进制拆掉 \(x\)。如果 \(x\) 的二进制位 \(j\) 是 \(1\)，说明 \(a_u\) 和 \(a_v\) 中，当前位也肯定有至少一个为 \(1\)。标记一…
2022/8/27 23:22:54 人评论 次浏览 -
CF1715B 题解
前言 题目传送门！ 更好的阅读体验？ 看起来挺难，其实一分钟就能想出来。 思路 首先考虑什么时候无解。由于 \(k \times \left\lfloor\dfrac{a}{k}\right\rfloor \le a \le \left\lfloor\dfrac{a}{k}\right\rfloor + (k - 1)\)，\(a\) 与 \(k\) 是自然数。 所以可得下式。…
2022/8/27 23:22:54 人评论 次浏览 -
CF1720D2 题解
前言 题目传送门！ 更好的阅读体验？ 感觉 D1 和 D2 不是同一个难度档次的呀...... 思路 设 \(a_j\oplus i < a_i \oplus j\)，这意味着数字 \(a_j\oplus i\) 中，从个位起前 \(k\) 位和 \(a_i \oplus j\) 相同，之后第 \(k+1\) 位就不同了。 两个不同下标的数有点难处…
2022/8/27 23:22:53 人评论 次浏览 -
CF1715A 题解
前言 题目传送门！ 更好的阅读体验？ 赛时瞎胡了个结论，然后就过了。 思路 Megan 从左下角到右上角，至少也得要 \((n + m - 1)\) 步。于是考虑让 Stanley 少走几步。如图，容易看出他最少走 \(\min(n - 1, m - 1)\) 步。 答案就是 \(n + m - 1 + \min(n - 1, m - 1)\) 了…
2022/8/27 23:22:52 人评论 次浏览 -
CF1548B 题解
前言 题目传送门！ 更好的阅读体验？ 做法：ST 表加尺取。 思路 看到同余，立刻想到作差。我们建立差分数组 \(c_i = |a_i - a_{i-1}|\)，注意取了绝对值。 此时，我们只需在 \(c_i\) 中寻找最长区间 \(\left[l, r\right]\)，使得 \(\gcd(c_l, c_{l+1}, \cdots, c_r) >…
2022/8/27 23:22:52 人评论 次浏览 -
CF1720D1 题解
前言 题目传送门！ 更好的阅读体验？ 有点思维难度的 DP 优化题。 小知识 在做这道题之前，你需要知道：\(x - y, y - x \le x \oplus y \le x + y\)。 证明非常简单，利用异或的性质即可。 思路 容易想到类似 LIS 的东西。设 \(dp_i\) 表示以 \(i\) 下标元素结尾，最长子…
2022/8/27 23:22:51 人评论 次浏览 -
CF1720C 题解
前言 题目传送门！ 更好的阅读体验？ 赛时锁题后看别人代码，怎么都和我想法不一样？幸好没有被 hack。 思路 以下把 L 字形的覆盖网格，直接称为 L。 贪心思考，我们想让每次 L 覆盖的 \(1\) 的数量少一些。 手玩一遍样例，我们发现：第一次 L 可能会覆盖多几个 \(1\)，之…
2022/8/27 23:22:51 人评论 次浏览 -
CF1550C 题解
前言 题目传送门！ 更好的阅读体验？ 比赛时，这题写了一个 \(O(n^3)\) 算法，然后就过了。 以为是数据水，实际上可以证明时间复杂度是 \(O(n)\) 的。 思路 关键是一个结论：当 \(i < j < k\) 时，若 \(a_i, a_j, a_k\) 单调不降或单调不升，则三元组 \((a_i, i), …
2022/8/27 23:22:49 人评论 次浏览 -
P8444 题解
前言 题目传送门！ 更好的阅读体验？ 普及组月赛第二题。特殊数据好恶心啊，考试差点丢分了。 思路 贪心题，先给 \(a\) 数组排个序。 首先，肯定是买小于等于 \(w\) 的最大价格的物品。如果买不到，直接输出 \(0\)。 上面一点可以使用二分实现，速度快一点（直接用 STL 就…
2022/8/27 23:22:47 人评论 次浏览 -
CF1506G 题解
前言 题目传送门！ 更好的阅读体验？ 校内考试题目。写一篇题解。 思路 首先记录每个字符出现了多少次，然后创建单调栈。 看当前字符是否入栈，如果没有入栈，就不停 pop()，直到：栈空了。 栈顶字典序大于当前字符。 栈顶元素已经被删掉了（因为栈外面用 cnt[i] 记录了每…
2022/8/27 23:22:46 人评论 次浏览 -
CF1710D Recover theTree
题意： 给定每个区间是不是连通块，还原这棵树。(\(n\leqslant 2000\)) 题解： 我肯定是做不出来，也不理解是怎么想的。不如直接讲做法，然后证明正确性，也是对 wc 题解的补充。 先贴个代码： #include<bits/stdc++.h> using namespace std; const int maxn=2e5+1…
2022/8/27 6:23:13 人评论 次浏览 -
P8400 题解
前言 题目传送门！ 或许更好的阅读体验？ 这题非常简单，考察读入读出，以及较简单的代数运算。 思路 我们可以利用代数解这道题目。 设一共有 \(n\) 个大盒子，\(m\) 个小盒子。 得出：大盒子一共可以装 \(3\cdot n\) 个蛋糕，小盒子一共可以装 \(8 \cdot m\) 个蛋糕。 所…
2022/8/26 6:24:52 人评论 次浏览 -
AT2580 题解
前言 题目传送门！ 更好的阅读体验？ 这题是常规的二分答案。 前置知识：二分答案 教大家一个小技巧：如何判断一题是否可以使用二分答案，以及如何编写程序？设计 \(f(x)\) 函数，确认其是否满足单调性。 如果不满足单调性，可能是 \(f(x)\) 函数设计错了，但更有可能是本…
2022/8/26 6:24:51 人评论 次浏览 -
P8344 题解
### 前言 题目传送门 \(\color{red}{see}\space \color{green}{in}\space \color{blue}{my}\space \color{purple}{blog}\) 这题作为本次比赛的 T1，难度感觉还行，算是一道结论题。 已经尽量讲得简单一些，没有用复杂的求和符号。 思路 很容易想到贪心策略，如下。 第 \(…
2022/8/26 6:24:49 人评论 次浏览 -
gdfzoj 比赛题解
前言 本次比赛：初一训练5.21 / 编号531 题目难度中等偏上，有几题比较简单，有两三题较难。 T1 题目：gdfzoj1441 思路： 算是一道暴力题。 由于 \(h_{i, j}\) 范围很小，考虑二分答案。 二分答案的范围应该是 \([0, 110]\)。 对于 chk() 函数，可以暴力枚举所有差为 \(\…
2022/8/26 6:23:42 人评论 次浏览
