LB_tq

题解

/ 注册

全部文章 / 题解（共20篇）

【每日一题】奶牛异或

Solution 要求选出一段子序列使得异或值最大。发现异或运算具有类似于前缀和的性质：由于的性质，可以快速消除前缀影响。设为到的异或值，则即为到的异或值。问题转化为对每个查询使得异或值最大的，字典树实现即可。需要注意的是，异或运算的优先级低于，判断时需要加...

2020-10-29

2 904

【每日一题】The XOR Largest Pair

Solution 题目要求一对数使得异或值最大。考虑异或运算的特点：按位进行且不进位。可以想到转化为二进制数进行操作，对每一位分别处理。把每个整数看做长度为的串构建字典树。最低位为字典树的叶子结点。对于数，在字典树中检索一次，每次都尝试沿着“与当前位相反的字符”向下访问。若存在这样...

2020-10-25

3 875

【每日一题】起床困难综合症

Solution 考虑位运算的特点：不进位。于是可以将答案的每一位分开考虑。从高位到低位枚举每一位所选的情况。若当前位第位经过一系列运算后结果可以为，那就将答案加上。由于枚举时由高到低，贪心地使高位为即可（第位贡献的答案比第位到第位贡献的和还要多）。注意累加值不超过...

2020-10-21

5 901

2020牛客NOIP赛前集训营-提高组（第一场）

A-牛牛的方程式 Solution 对于二元一次不定方程有解的条件是。若该方程有解，可将代换为，三元一次方程可以写为，此时可将看做常数系数，为变量。再次使用判定二元一次方程的方法即可。综上，有解条件为。注意特判模数为的情况。 Code #include #inclu...

2020-10-18

0 611

【比赛】牛客算法周周练1

如果公式炸了，可以去这里看： https://www.luogu.com.cn/blog/taiqi/niu-ke-suan-fa-zhou-zhou-lian-1-post （后台好好的，一到前台就炸。。） A-Maximize The Beautiful Value Solution 由题目中的...

2020-04-08

1 922

【每日一题】Running Median

Solution 经典的动态维护序列中位数问题。采用对顶堆做法：维护一个大根堆和一个小根堆，其中大根堆维护当前序列中较小的一半元素，小根堆维护较大的一半元素。依次插入每个元素：若当前元素小于小根堆堆顶，则插入大根堆。若当前元素大于等于小根堆堆顶，则插入小根堆。每插入一个元素，检查当前两个...

2020-04-08

12 1280

【每日一题】黑白树

Solution 由题意可知叶子节点必定要染色。对于其他节点：若此节点的已经染色的子节点中，可以将它覆盖，那么不需要染色，并借助这个点能覆盖的范围更新最大范围。若此节点的已经染色的子节点中，不能将它覆盖，那么需要将其子节点中范围最大的点染色，并更新最大范围。可以发现这是一个由子节点向父节点...

2020-04-07

1 1249

【每日一题】树

Solution 其实是道数论题。题意可以转化为将树分割为不超过个连通块，每个连通块颜色不同。若将树分割为个连通块，则需要删去条边，故方案数为。同时，要从种颜色中选出中颜色染色，而且是有顺序的，故方案数为。综上，总的方案数为：可以线性求逆元，枚举实现。时间复杂...

2020-04-06

24 1708

【每日一题】数码

Solution 数论分块，就是利用一段区间内的数整除同一个数结果相同的性质减少运算量的技巧。回到题目，要求区间内的答案。已知的是内数当做约数的次数为，所以问题可以转化为区间与区间的答案之差。暴力计算的话，时间复杂度是的，不能承受。所以使用数论分块来减少计算量：由于整...

2020-04-05

2 817

【比赛】牛客OI周赛15-普及组

A-咪咪游戏 Solution 需要满足以下条件：字符串长度为偶数。奇数位是，偶数位是。从前到后扫描一遍即可。时间复杂度。 Code #include <iostream> #include <cstdio> #include <cstring&...

2020-04-03

3 785