题意：有一个初始血量为h的怪物，有n个回合，每回合怪物的血量加di，如果怪物血量小于等于0，则怪物死亡，如果怪物不是，则n个回合循环运行，如果怪物无法死亡，则输出-1，否则输出怪物死的回合. 思路：记录n个回合中对怪物伤害最大的一个回合,即d数组的最小前缀和，记录值mi.如果mi+h<=0,则怪物在n回中会死亡，则暴力模拟即可。如果mi+h>0,则看n回合对怪物造成的是否能对怪物造成伤害，如果不能，则怪物不会死，则输出-1，否则计算何时h+mi<=0,执行（h+mi）/p(p是n回合对怪物的伤害)，求出执行了多少个n回，然后模拟即可. 代码： #include<bits...

题意：你可以进行二种操作: 操作一：可以将x变成F(x),F(x)=(x * x * x+x * x)%233;操作二：可以将x变成G(x),G(x)=(x * x * x-x * x)%233; 求最少多少次可以使a变成b，如果无解则输出-1； 思路：先对233以内的数到233以内的数进行预处理：d[i][j]表示i变成j的最少操作次数。初始化dp[i][j]=一个极大值dp[i][i]=0;如果i可以通过一次操作变成j，则dp[i][j]=1;使用Floyd算法求出i到j的最少操作次数。 预处理后，我们分以下三种情况判断：①：a==b，输出0；②：b>=233,输出-1；③：a先操作...

题意：有一颗n个节点的树，有m个询问，每个询问给出x和y两个节点，让你求树上节点到这两个节点距离相等的数目。 思路：①：如果x和y深度相同，则他们的最近公共祖先lca（x,y)的非这二个节点方向的节点以外的节点到x和y的距离相等.②：如果x和深度不同，则他们的路径为奇数时无解，为偶数时中点在深度大的一方，该点到x和y的方向节点以外的节点到x和y的距离相等. 代码： #include<bits/stdc++.h> #define ll long long using namespace std; int read() { int x=0, g=1; char c=g...

题意：给你一个有n个城市的国家，n-1道路将城市连接（即为树），首都为节点1，有m支军队，每支军队可以在一个城市设立一个检查点，问使从首都到任意一个边境节点都会碰到检查点军队移动最少时间为多少，军队可以同时移动。 思路：如果军队数少于与首都直接相连的节点数则输出-1，否则一定有解。我们可以发现时间越久军队越可能完成任务，即具有单调性，所以二分答案。如何判断该时间是否满足：在该时间内尽可能往根节点走，如果可以到根节点则记录一下（倍增处理加速），不能则在能走到离根最近的节点设立检查点，然后看哪个根的子树的边境节点无法达到要求，将不能达到要求的子树的根节点记录，如果已经有军队从该子树走到了根节点，则...

题意：有一颗n个节点的树，现在有m个询问，每个询问给与三个节点，求这三个节点在哪个节点集合时总距离最小？输出集合节点和总距离。 思路：我们知道在树上求任意两个节点可以用lca求取，求三个节点怎么转换成求两个节点呢，我们画一颗树然后任找三个点可以发现两两之间的lca的值要么三个相等，此时该点为集合点，要么就是有两点相等，一个点不同，此时该不同点为集合点时总距离最短，可参考https://blog.nowcoder.net/n/0424b84aa132430f81321b11fe63e804 这位大佬的。集合点知道了，直接用lca分别三点求出与集合点的距离再加起来。 代码： #include&lt...

题意：给你一颗有n个节点的无向树，你可以往树中加无向边，求你形成1节点到任意一个节点距离小于等于2的图加边的最小次数？ 思路：你可以认为是求一个变形的最小支配集，即求以1节点为根节点时第0，1，2层无需考虑的最小支配集，所以可以用动态规划和贪心算法解决。 代码： #include<bits/stdc++.h> #define ll long long using namespace std; vector<int> g[300005]; const ll inf=1000000007; int dp[300005][3], ans=0; void dfs(int v...

题意：给你一个长度为n的数组，请你按顺序分成k份，然后将每一份的和进行位与操作，求结果最大为多少？ 思路：从高位到低位枚举结果，即如果加入该位后结果满足条件则将该位加入结果，否则舍弃该位。判断结果是否满足条件使用dp：dp[i][j]表示将前i个数分成j组是否满足条件；dp[i][j]=(dp[i][j]||((dp[l][j-1])&&(((sum[i]-sum[l])&x)==x)));(x表示你要判断的结果，dp[l][j-1]表示前l个数是否能分成j-1组，((sum[i]-sum[l])&x)==x))表示[l+1,i]是否能分成1组，当二者都成立是d...

题意：给你一个长度为n的数组，然后有m次询问，每次询问有一个值x，让数组的每一个值异或x后，求数组中不存在的最小非负整数。 思路：先将数组中的元素按01trie树建立， 然后每一次查询查询相当于原数组和（当前的值和前面次数的值异或）异或。01trie树上找答案：如果与当前位异或为0的点不存在则输出当前结果。如果与当前位异或为0的点为根的子树满了则往异或为1找，如果还不存在则加上该位的值再输出结果。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; int a[33], cnt[920...

题意：给你一个长度为n的序列，让你选择你个连续的子序列做Xor操作求最大值为多少？并且该区间是什么？（如果有多个解，则取右边界最小（第一关键词），区间长度最短（第二关键词））。 思路：对数组求前缀异或和，即求[1,2][1,3]....[1,n]等区间的异或和，然后你将二个区间异或后可以发现是一个连续区间的异或和。然后用01trie求取结果。 注意当n=1时的结果。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; int a[33], cnt[3200005][2], ji=1; ...

题意：给你n个整数，让你选择两个数进行Xor操作后值最大为多少？ 思路：建一颗01trie树，从高位到低位，然后从遍历数组，利用01trie树求每一个数与其中某一个一个数Xor的最大值，然后取总的最大值。取法：如果该数在该位上是1则尽可能在01trie树该位取0使其Xor为1。如果该数在该位上是0则尽可能在01trie树该位取1使其Xor为1。 注意：从高位到低位建树。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; int a[33], cnt[3200005][2], ji=1...

题意：让你选择一个0-m的值，求出在经历n次位操作后最大值为多少？ 思路：进行位操作时，每一个位的值是独立的，所以我们可以按下列情况进行计算：①：如果该位为0时结果该位为1时该位取0。②：如果该位为0时结果为0且该位为1时结果为1时该位取1。（不超出m的范围，否则取0）③：如果该位为0和1时结果都为0时该位取0。输出最大的结果就好了，详情看代码。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll w[65], t; string s; int main() { ios:...

题意：给你一个长度为n的序列，使序列呈先升序再降序的最少操作次数为多少？每次操作可以交换相邻的两个数。 思路：对于每一个数来说，它最终要么左边的数全比它小，要么右边的数全比他小，每次移动相邻两个位置，所以你只需要判断它左边比它大的数的个数和右边比它大的个数的最小值（哪边小与那边大于它的交换），用树状数组统计大于它的个数(由于数状数组计算的是比它小的个数，所以你可以一开始就将数组内数的大小颠倒，则比它小的个数即为比它大的数)。 代码： #include<bits/stdc++.h> typedef long long ll; using namespace std; const i...

题意：有n台笔记本电脑，它们有一个初始电量ai，和每分钟耗电量bi,有一场训练需要持续k分钟，在每一分钟开始时电量不能为负，你能使用一个多大功率的充电器使其能完成训练，如果没有，则输出-1. 思路：二分枚举答案，如果一个超大的功率都不行，则说明没有，输出-1，判断一个功率是否可行，可以记录在该功率时每台笔记本最迟充电时间点并记录，然后判断在时间上是否有冲突即可。 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; ll n, k; struct w { ll a, b; }w[2...

题意：有一个n*m的地图，为1表示为有障碍物，你可以移走t个障碍物，求二个可以相互到达的点最大的欧几里德距离? 思路：dfs暴力求出每一个点在移走t个障碍物后能到达的点，然后暴力求最大距离。 代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; int d[35][35], dis[35][35], f[35][35], dx[4]= {1,0,0,-1}, dy[4]= {0,1,-1,0}; double ju(int x,int y,int a,int b) { retur...