题解914b cf

思路 首先，我们可以考虑两个人会怎么操作，如果是选择了两个偶数和两个奇数，那么答案不会减小，如果选择了一个奇数一个偶数，那么答案会减小一。 所以想使答案大的人应该尽量选择前一种方案，想使答案小的人应该尽量选择后一种方案。 但这还不是最优的，想使答案大的人在可以选择两个奇数时，绝对不会选择两个偶数，因 ......

思路 看到题目要求求一个数 \(x\)，满足它的最大的两个因数分别是 \(a\) 和 \(b\)，并且规定一个数本身不是他的因数。 首先 \(x\) 需要是 \(a\) 和 \(b\) 的倍数，所以想到最小公倍数，如果不考虑最小公倍数等于 \(b\)，最小公倍数就一定是答案，因为最小公倍数是最小的满 ......

题意 给定一个序列，维护下列操作。 区间加 区间查询数中只包含 \(4, 7\) 数的个数。 所有数前后不超过 \(1e4\)。 Sol 块块版。 \(1e4\)，发现满足条件的数的个数只有 \(30\) 个。 对于每个块开一个桶，记录每种数有多少个。 查询时暴力枚举 \(30\) 个数，暴力判断即 ......

题意 给定一棵大小为 \(n\) 的树，有 \(k\) 个人，第 \(i\) 个人在节点 \(a_i\)。 从第 \(1\) 秒开始，依次操作第 \(1, 2, 3, \ldots, k, 1, 2, 3, \ldots, k, \ldots, k, \ldots\) 个人，把这个人移动到没有走过的 ......

CF1916B 分析 题目给出的是 \(x\) 的两个小于 \(x\) 的最大因子，首先考虑 \(a\) 不整除 \(b\) 的情况。既然 \(a\) 不整除 \(b\)，那么 \(a\times b\) 必定是 \(x\) 的倍数，但是此时 \(a,b\) 就不一定是最大的，所以需要除以一些东西， ......

题目传送门（CF） 题目传送门（luogu） 容易发现，选择两个偶数对于答案没有任何影响，因此先手必然会优先选择两个奇数合并在一起，而后手必然会优先选择一个奇数和一个偶数在一起，我们举个例子，有一个序列 \(\{1,1,1,1,1,1\}\)，先手先取编号为 \(1,2\) 的两个数，后手再取编号为 ......

Question 杭州电子科技大学2023新生赛 G 逃离节奏面 题太长自己看吧 Solution 考虑到如果走了几步后走到了相同节奏面的相同点是没有意义的，所以直接 BFS ，对于走过的节奏面的哪个点不需要走就能刷出最短路了 实际上实现的时候细节很多，要注意一下 Code #include<bit ......

Question 杭州电子科技大学2023新生赛 E 树 给定一颗包含 \(n\) 个节点的带边权的树，定义 \(xordist(u,v)\) 为节点 \(u\) 到 \(v\) 的简单路径上所有边权值的异或和 有 \(q\) 次询问，每次给出 l r x 求 \(\sum_{i=l}^r xord ......

省选题解第一发～ 【省选联考2020】树 我和这道题还挺有缘分的。 有一次看大佬的省选游记（不知道是哪一年），然后提到有一道是01trie整体加一，当时我就印象深刻，然后在 oiwiki 上看了一下，心想这整体加一也只能从低位到高位维护 01trie 啊，又不能查询最大值，有什么卵用（划掉）。 这是 ......

Tree Queries Luogu CF1254D 题面翻译 给定一棵 \(N\) 个节点的树，有 \(Q\) 次操作。 \(1\ v\ d\) 给定一个点 \(v\) 和一个权值 \(d\)，等概率地选择一个点 \(r\)，对每一个点 \(u\)，若 \(v\) 在 \(u\) 到 \(r\) ......

Treeland and Viruses Luogu CF1320E 题面翻译 有一棵有 \(n\) 个节点的树，\(q\) 次询问（询问互相独立），每次给定 \(k_i\) 个颜色，每个颜色有一个起始点 \(v_j\) 和移动速度 \(s_j\)，每一个颜色在每一次操作中会使它周围没有被染色的连通 ......

CF1547E Air Conditioners 题目传送门 这道题我的思路严重劣于题解思路，所以请慎用 但是自认为我的贪心比dp好理解点 题意 有 \(q\) 组数据，每组第一排表示有 \(n\) 个方格和 \(k\) 个空调，第二排是每个空调的位置 \(a_i\) ,第三排是每个空调的温度 \( ......

CF1545A AquaMoon and Strange Sort 题目传送门 题意 有 \(n\) 个人从左到右站成一排，从左数第 \(i\) 个人的衣服上印着 \(a_i\)。每个人的朝向可以是朝左、朝右。一开始所有人的方向都是朝右。 您可以对这些人做一些“操作”，每次操作允许您找两个相邻的人让 ......

可以看出来出题人很想出一道把李超和别的什么东西凑起来的题目，于是给了这么一个缝合怪。 https://www.luogu.com.cn/problem/P4069 符号有点混乱。比如箭头又可以表示路径又可以表示赋值，代入语境应该还是好理解的。 看到 \(a\times dis + b\) 就应激反应 ......

Problem - D - Codeforces Counting Rhyme - 洛谷 法1： 我们之前肯定看过这样一道非常经典的题： 求 \(a_i\) 中有多少对 \((i,j)\)，满足 \(\gcd(a_i,a_j)=1\) \(n \leq 10^6\) 这题是莫反板子题，但显然可以不用 ......

在前面的cf比赛中发现引用nextint和nextline会出现问题，下面重新理一下next，nextint，nextline next()、nextInt()读取数据后指针还在当前行，如果紧跟nextLine()，读取数据会出错，因为nextInt()以回车作为结尾标志且它会把回车符留在内存中，当 ......

题目传送门 一道贪心题。 数量为 \(2\) 的袜子不用考虑，因为最好的情况就是相同颜色的配一对。 我们只需要考虑那 \(k\) 种只有 \(1\) 个的袜子，如果 \(k\) 为偶数，答案为相邻两数之差之和；如果 \(k\) 为奇数，就枚举删掉一个数，让剩下的数按照 \(k\) 为偶数的情况做，最 ......

题目传送门 一道 dfs 题。 先统计出绿连通块数量，然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为 \(1\) 的绿连通块，但若是有不同的绿连通块与其相邻，答案又会减少 \(1\)。 Code #include <bits/stdc++.h> cons ......

Description 给你一个数组 \(l_1,l_2,\dots.l_n\) 和一个数字 \(d\)。问你是否能够构造一棵树满足以下条件： 这棵树有 \(n+1\) 个点。 第 \(i\) 条边的长度是 \(l_i\)。 树的直径是 \(d\)。 只需要判断是否有解即可。 \(2\le n\le ......

tg.BZOJ 4403序列统计 pj.BZOJ 4403序列统计 没啥用的题解 \(QWQ\)——无脑思考 首先要想怎么求单调不上升序列的个数，因为可能会有重复的数，所以不能直接用排列组合。 那这道题怎么打呀？ 我不知道啊\(\dots\) \((~:\) 因为原来是单调不下降序列，将第 \(i\ ......

题目链接 Easy version Hard version 题目解法 参考 DeaphetS 的题解 很有意思的题，感觉 \(F1\) 不到 \(*2900\)，\(F2\) 超过 \(*2900\) F1 简化题目中的操作：把 \(n\) 个数放到 \(n-k\) 组中，求 \(\max(\su ......

[CF30E] Tricky and Clever Password 题解 注意到一个合法字符串首尾相同，考虑用 S 的反转和 S 跑 KMP。 对于只有一个串，暴力 manacher 即可。 匹配到某一位置 \((i, j)\) 时，查询区间最长的奇回文串长度，用二分 + ST 表解决，因为回文串 ......

更好的阅读体验 CF566C Logistical Questions 好强的题，感觉完全想不到。 如果对于每个点都计算答案的话复杂度是 \(\mathcal O(n^2)\)，但是由于题目中给了一个 \(\frac{3}{2}\) 次方这么一个非常恶心人的东西，这个算法基本没有优化空间，所以考虑换 ......

思路 比较典的 ODT 题目。 发现排序是一个非常有性质的操作。 它对区间的更改与颜色段均摊差不多。 那么我们可以想到用 ODT 来维护这一整个序列。 具体的，区间排序操作可以用 ODT 维护每次排序产生的段，每段用线段树维护排序后的结果。 每次修改就可以进行线段树的分裂与合并。 如何查询。 可以发 ......

最开始没看到子树的限制，以为是个极其困难题。 思路 由于问题是在子树下，可以考虑在 dfn 序上扫描线。 考虑一个点 \(u\) 对 \(v,d\) 的贡献。 令 \(dep_u\) 为 \(u\) 的深度，\(mdep_u\) 为 \(u\) 的子树下的最大深度。 \(dep_u< dep_v\) ......

思路 看到时限这么大，考虑暴力做法。 我们将原序列分为 \(\text{B}\) 个块，每个块类似线段树三一样的维护 \(add,maxadd\)，表示这一块需要加的值，加的值的历史最大值。 同时对于每个数可以维护一个真实值与一个历史最值。 那么下传标记可以写成这样。 inline void pus ......

题解怎么都是用暴力日过去的啊。 思路 考虑根号分治，设阈值为 \(B\)。 对于第二维出现次数超过 \(B\) 的，我们可以在修改时暴力更改，这部分复杂度为 \(O(\frac{nm}{B})\)。 对于第二维出现次数小于 \(B\) 的，我们可以在修改是打标记，查询时遍历一遍，这部分的复杂度为 \ ......

思路 题目即要求删除区间中的一个或多个颜色。 考虑假如枚举删除颜色 \(k\)。 那么在 \(l,r\) 中的答案为： \[\max_{i=1}^{m+1} a_i-a_{i-1} \]其中 \(a_i\) 为颜色 \(k\) 在 \(l\sim r\) 中的出现位置，\(a_{0}=l,a_{m+ ......

CF1538F Interesting Function 题目传送门 题意 给定两个正整数 \(l, r\)（\(l < r\)），将 \(l\) 不断加 \(1\) 直到 \(l = r\)，求出这一过程中 \(l\) 发生变化的位数总数。 位数变化指： \(l=909\)，将 \(l+1\) 后 ......

problem 希望这篇题解不要明年才审完。 标签：线段树 记录 \(Lsum_p\) 为这个区间有多少个 ( 不能匹配，\(Rsum_p\) 为这个区间有多少个 ) 不能匹配。 对于叶子结点如果是 ( 那么 \(Lsum_p\) 为 \(1\)，否则 \(Rsum_p\) 为 \(1\)。 如果不 ......