纯思维题目   给了范围,且, 那么将所有数字对取模,得到的余数0, 1, 2, 3, ... x - 1都至少出现一次     如果是的倍数,那么, 即,那么就不会剩下一个数字,即答案为0   否则我们拿出这个数字：,也只需要拿出一个数字   所以答案只会是0或1   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync...

emm....   将绝对值打开，只有四种情况：            所以就只需要对和排序即可   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define HelloWorld IOS; si...

很不错的二分题目：因为我都不知道这是一道二分题目   在第i行里面：i  1, i  2, i  3, i  4, i  5, ......   如果我要这这一行里面求比 小于等于x 的个数：那么答案是 min(,m).    那么就可以O(n)求出这nm里面有多少个小于等于x的个数！   然后二分即可   总代码：   #include<bits/stdc++.h> using namespace std; #define endl&nbsp...

定义dp[i][0/1]表示跳到第i个阶梯并且最后一次跳跃了偶数/奇数个楼梯   分析dp[i][0]: 最后一次跳跃了偶数个楼梯, 那么最后一次跳跃了2, 4, 6, ...个楼梯, 即上一次是在第i - 2, i - 4, i - 6....阶梯, 又因为跳跃的阶梯是奇偶交替的, 所以跳到第i - 2, i - 4, i - 6....阶梯最后一次是跳了奇数个楼梯   所以dp[i][0] = dp[i - 2][1] + dp[i - 4][1] + dp[i - 6][1] + .......   又因为dp[i - 2][0] = dp[i - 4][1] + dp[i - 6][1...

传统的dp方法的时间复杂度是O(n2)   可以用O(n logn)时间复杂度求得最长长度,但仅是序列长度不是序列本身   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define HelloWorld&n...

很经典的递归题目   void dg(char a, char b, char c, int n) a, b, c分别表示这三个杆子，n表示目前圆盘的个数   然后步骤：   目的：将a上面n个圆盘移动到c上面   第一步：将a上面的n - 1个圆盘移动到b上面   第二步：将a最下面的1个圆盘移动到c上面   第三步：将b上面的n - 1个圆盘移动到v上面   所以递归函数就是：   void dg(char a, char b, char c,&nbs...

操作一：返回栈顶元素   操作二：将value加入push到栈顶   操作三：将栈顶元素删除   操作四：返回栈里面最小的一个元素   操作一,二,三是栈stack的基本操作;   如果用O(1)的时间复杂度直接返回栈里面最小的元素呢？   用第二个栈来维护第一个栈里面的最小元素：sta1, sta2   当执行操作二时：只有当sta2为空或者valuesta2.top()时,才将value加入到sta2的栈顶里,这样做：sta2里面只放入最小的元素(sta2里面的元素可能有多个,但栈顶一定是目前最小的元素)   只要最小的元素还在sta1里面,那么该最小元素就一定在sta2的栈顶   当执行...

递归题目，求表达式的值      求当前字符串s表达式的值,实现需要用栈依次存储数字：   如果当前state是‘+',求push(num)   如果是'-', 就push(-num)   如果是'*',就将栈顶的元素乘以num即可   一开始的时候state定义为'+',相当于0 +   处理数字值:   if('0' <= s[i] && s[i] <= '9'){     sum = sum * 10 +&nbs...

如果你总是只通过86.67%的数据，那么需要注意(x1,y1) = (x2,y2)的情况，因为这种情况下这个格子无论如何也不能到达   很显然是一道BFS问题   有k个幽灵奇数秒在(x1,y1),偶数秒在(x2,y2),能不能从(1,1)走到(n,m)且求最少时间   那么对时间存储格子就有两种状态:   cin >> n >> m >> k; for(int i = 1; i <= k; i ++){ &nbs...

题目意思很简洁明了: 总成本不超过 k的情况下,通过若干次操作,能够得到的字典序最大的序列是什么。   那么一个贪心的想法是将较大的数字尽可能的替换到前面来：   比如[1,1,1,4,1,5],我们希望将所有元素替换为5,变为[5,5,5,5,5,5],但是有k的限制条件   如果k = 0,那么最优是[1,1,1,4,1,5]   如果k = 1,那么最优是[1,1,4,4,1,5]   如果k = 2,那么最优是[1,4,4,4,1,5]   如果k = 3,那么最优是[4,4,4,4,1,5]   如果k = 4,那么最优是[4,4,4,4,5,5]   如果k = 5,那么最优是[5...

题目的意思是在[1,n]区间中执行两种操作：   操作一：给定区间[l,r],依次标记该区间的所有数,如果数字已经在之前的被标记了,则不重复标记   操作二：给定[1,n]中的一个数x,直接输出x是第几个被标记的；如果没有被标记过,直接输出0   显然最直接的操作是遍历[l,r]依次标记,但是肯定会超时。   原因在于将所有数都进行判断:如果没有被标记过,那么我就标记;如果被被标记过,我就跳过   如果能不再判断被标记过的数,而是直接依次标记[l,r]中没有被标记过的数,那么不会超时,因为每个数最多标记一次,所以总共的标记次数为n次   那么我们可以用set来模拟   set<int&g...

题目的意思是给定一个数组，求有多少个子数组满足子数组可以恰好分为若干个"块"   用len[i]表示从i到前面有多少个连续的数等于a[i],例如a[] = {1,1,2,2,2,1},那么len[] = {1,2,1,2,3,1}   显然初始化len[] = {1,1,1,1,1,1},从i  2开始,如果a[i] = a[i - 1],那么len[i] = len[i - 1] + 1   for(int i = 2; i <= n; i ++){    &nbsp...

两种操作：x =以及选择一个整数z,令x = x | z，求最小的操作次数让x = y   从二进制上考虑，那么第一个操作就是x的二进制整体向右移动一位，第二个操作就是增加到某一个数。   如果x的二进制某一位置为1，而y二进制对应的位置为0，那么x只能通过进行操作一将该位置的1抹除掉，所以首先就得进行操作一使得不存在同一二进制位置上x为1，y为0的情况，但可以存在（0，0），（1，1），（0，1）的情况，（0，0），（1，1）不用多说，如果是（0，1），那么就可以进行操作二将（0，1）变为（1，1）   所以如何判断不存在（1，0）这个情况了呢？如果（x | y）= y时，就说明没有（1，0...

首先得知道两个关于位运算的小结论：a + b = (a & b) + (a | b)a | b = (a & b) + (a ^ b)你自己想一下就知道证明过程了所以 a + b - (a ^ b) = 2 * (a & b) = （a & b) << 1那么对于每一个区间查询[l, r]的值，手动模拟一下a[l], a[l + 1], a[l + 2]那么a[l] + a[l + 1] - (a[l] ^ a[l + 1]) = (a[l] & a[l + 1]) << 1然后(((a[l] & a[l + 1]) &l...