Solution 题目要求一对数使得异或值最大。考虑异或运算的特点：按位进行且不进位。可以想到转化为二进制数进行操作，对每一位分别处理。 把每个整数看做长度为 的 串构建字典树。最低位为字典树的叶子结点。对于数 ，在字典树中检索一次，每次都尝试沿着“与 当前位相反的字符”向下访问。若存在这样的字符指针，令答案加上当前位代表的二进制数即可。由于二进制表示下第 位比第 位到第 位之和都大，所以保证了贪心的正确性。 具体实现时，注意数组大小开 的 倍。 Code #include<iostream> #include<cstdio> #include<...

有大佬能讲讲双向链表是怎么实现翻转和查询的嘛。。题解看不懂

Solution 考虑位运算的特点：不进位。 于是可以将答案的每一位分开考虑。从高位到低位枚举每一位所选的 情况。若当前位第 位经过一系列运算后结果可以为 ，那就将答案加上 。由于枚举时由高到低，贪心地使高位为 即可（第 位贡献的答案比第 位到第 位贡献的和还要多）。注意累加值不超过 。 Code #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=1e5+10; struct node{ string o...

A-牛牛的方程式 Solution 对于二元一次不定方程 有解的条件是 。若该方程有解，可将 代换为 ，三元一次方程可以写为 ，此时可将 看做常数系数， 为变量。再次使用判定二元一次方程的方法即可。 综上，有解条件为 。注意特判模数为 的情况。 Code #include #include #include #define ll long long using namespace std; ll T,a,b,c,d; ll gcd(ll x,ll y){ if(!y) return x; return gcd(y,x%y); } int main(...

如果公式炸了，可以去这里看： https://www.luogu.com.cn/blog/taiqi/niu-ke-suan-fa-zhou-zhou-lian-1-post （后台好好的，一到前台就炸。。） A-Maximize The Beautiful Value Solution 由题目中的计算公式可以发现，越向后的数所占的比重越大。因为给出的序列是单调不降的，所以给出的顺序一定是和最大的。 所以只需要移动最少的距离使影响最小，即移动 个单位。之后考虑移动每个数对总和产生的影响。 若将第 个数左移 位，设序列前缀和数组为 ，则序列 的总和 的变化量为 。 在所有的 中取最...

Solution 经典的动态维护序列中位数问题。 采用对顶堆做法：维护一个大根堆和一个小根堆，其中大根堆维护当前序列中较小的一半元素，小根堆维护较大的一半元素。依次插入每个元素： 若当前元素小于小根堆堆顶，则插入大根堆。 若当前元素大于等于小根堆堆顶，则插入小根堆。 每插入一个元素，检查当前两个堆的大小之差是否超过 ，若超过 ，则调整为相等大小。这样，每到序列有奇数位时，元素较多的堆的堆顶即为当前序列的中位数。 时间复杂度： 。 Code #include<iostream> #include<cstdio> #include<cmath> #in...

Solution 由题意可知叶子节点必定要染色。对于其他节点： 若此节点的已经染色的子节点中，可以将它覆盖，那么不需要染色，并借助这个点能覆盖的范围更新最大范围。 若此节点的已经染色的子节点中，不能将它覆盖，那么需要将其子节点中范围最大的点染色，并更新最大范围。 可以发现这是一个由子节点向父节点更新的过程，所以可以使用 。每次贪心地更新能覆盖的最大距离，不能覆盖就进行染色。 时间复杂度： 。 Code #include <iostream> #include <cstdio> #include <cstring> using namespace st...

Solution 其实是道数论题。 题意可以转化为将树分割为不超过 个连通块，每个连通块颜色不同。若将树分割为 个连通块，则需要删去 条边，故方案数为 。同时，要从 种颜色中选出 中颜色染色，而且是有顺序的，故方案数为 。 综上，总的方案数为： 可以线性求逆元，枚举 实现。 时间复杂度： 。 Code #include <iostream> #include <cstdio> #define ll long long using namespace std; const ll mod=1e9+7; const ll maxn=310; ll n,k,an...

Solution 数论分块，就是利用一段区间内的数整除同一个数结果相同的性质减少运算量的技巧。 回到题目，要求区间 内的答案。已知的是 内数 当做约数的次数为 ，所以问题可以转化为区间 与区间 的答案之差。 暴力计算的话，时间复杂度是 的，不能承受。所以使用数论分块来减少计算量：由于整除向下取整的性质，所以必然存在很多段区间，区间内部整除结果相同，可以合并计算。具体的分块方法：将 作为整个区间。证明过程可以百度。( 好难) 由于本题要求只统计最高位，所以可以将每一位分开处理，方便计算。 时间复杂度： 。 Code #include <iostream> #inclu...

A-咪咪游戏 Solution 需要满足以下条件： 字符串长度为偶数。 奇数位是 ，偶数位是 。 从前到后扫描一遍即可。 时间复杂度 。 Code #include <iostream> #include <cstdio> #include <cstring> const int maxn=1e5+10; using namespace std; int n,q; char ch[maxn]; int main(){ ios::sync_with_stdio(false); cin>>q; int x; ...

Solution 由题意可知是一个树形结构。若要使两两之间边权最小，尽量不能选重边，也就是说尽可能在节点所在子树里寻找答案。 显然与叶子节点相连的边必须选。然后考虑其他边： 若一棵子树中的节点有偶数个，那么两两配对即可，不用添加新的边权。 若一棵子树有奇数个节点，那么根节点要和其他子树连边，所以还要加上根节点与其父节点之间的边的边权。 综上， 统计子树大小，偶数不用处理，奇数加边权即可。 数据范围较大，注意开 。 时间复杂度： 。 Code #include <iostream> #include <cstdio> #include <cstring>...

Solution 直观的想法是直接扫描两个字符串进行比较。这样的复杂度是 的。 然后可以发现子序列中字母的相对位置是不变的，所以可以维护一个数组 ， 表示第 个位置之后最近的字母 所在的位置。这个数组可以 处理： ，然后在倒序循环一遍即可预处理出 数组。 对于每个要判断的字符串 ，建立一个指针 ，初始值为 。然后判断 的每一位是否在 中出现，并更新指针 即可。 时间复杂度： 。字符集常数较大。 Code #include <iostream> #include <cstdio> #include <cstring> using na...

Solution 由题意可知给定的图是一棵树。树上的最优化问题可以想到树形 。 按照常用的状态设计方式，可以设 为根节点为 的最少代价。使以 为根的子树的叶子节点无法到达 的方式有两种： 割断与 直接相连的边 割断与 的子节点直接相连的边 两种方式取最小值即可。故状态转移方程为 其中 为与 直接相连的子节点。 因此可以以 节点为根，进行 ，目标状态为 。 时间复杂度： 。 Code #include <iostream> #include <cstdio> #include <cstring> #define ll long lo...