思路 因为题目的数据很小，所以直接二进制枚举就好了。 思路就是枚举每一行的二进制形式，1表示有人，0表示没人，dp[i][[j]表示第i行的放置状态是j  下面考虑下判断操作是否合法：  1、首先上一层 放了人的地方下一层必须不放，既上一层第 i位位1，下一层第i位必须为0，上一层第 i 位为0下一层可放可不放 ， 这个操作可以用 & 运算符 j & k ，j表示上一层的状态，k表示这一层 ，当j & k 为 0 时说明这一层放置方法为k合理 2、本层Map[i] 的第j位为0表示这层不能放人，假设放置方法为 k ，则 (Map[i] & k) == k 表示操...

思路 这里我是用了一个bool数组 表示第i个文档是否存在，然后建一个set里面存没有建的文档 建立文档的时候直接取set的首元素就好，删除就查询，若为true就输出Successful，并向set中插入该元素 简单来说直接模拟就好 代码 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include<bits/stdc++.h> using namespace std; typedef l...

思路 1、T的根结点为R，其类型与串S的类型相同 2、若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2 意思就是如果这个串都是0那根节点就是B，都是1根结点就是I，有0也有1根节点就是F 树的遍历通常都是用递归实现，这里左子树和右子树的长度相同，所以对一个字符串来说可以递归分成两个部分 （l,(l+r)>>1）和(1+((l+r)>>1)),r)接下来输出就行 代码 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC op...

思路 这题可以用树状数组做个数组 表示元素 i 是否存在，为1表示存在 第i个元素X的逆序对个数就是在i前面的数并且比i大，即 c[x] ~ c[n]位置为1的个数  树状数组函数getsum(i)表示 数组 所以getsum(n) - getsum(x)表示c[x]到c[n]的为1的个数 代码 #p...

思路 这题考的应该是自己写一个排序的规则，可以写一个cmp函数，像这样： bool cmp (const node &A,const node &B){ if(A.h != B.h) return A.h < B.h; if(A.m != B.m) return A.m < B.m; return A.s < B.s; }这个函数用法直接 sort(q,q+n,cmp);排序规则就是如果返回true表示A应该排在B前面，false表示A应该排再B后面 或者重载 < 号，就像我下面的代码 ps：如果老记不得返回true是谁排在谁前面可以自己输入几个数再输出...

思路 要让字典序最大很明显就要让更大的那个数先出栈。 我这里用了一个数组 表示第i项到第n项的数的最大值。  如果栈顶元素大于 第i项到第n项的最大值，说明如果让这个元素出栈此时的字典序肯定会更大。 如果栈顶元素小于 第i项到第n项的最大值，那就让该元素入栈，因为让大的先出栈总总能保证字典序最大  如果所有元素都已经入栈了，那记得输出栈内剩余的元素 代码 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #...

思路 最开始懒得离散化直接开1e8的数组用差分做，提交发现能ac，良心出题人啊给了这么大的空间 就说明这个位置有人，因为可能多次赶一个地方的人，所以差分数组有可能是负数  如果没学过差分的同学可以去看看这篇大佬的博客 正解应该是离散，计算被清除的区间长度，总长度减掉区间长度加一就是答案。维护终点即可。为什么加一就不用说了吧（长度为L的区间位置0，1，2.。。L有人，加起来L+1个人） 这里要注意的就是 0 这个位置也是有一个人的，不要忘记了加。 直接差分代码 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize...

题意 一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。 现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。  就是找一个边长为R的正方形使得val最大 思路 典型的二维前缀和，如果不清楚什么是二维前缀和可以看一下我之前写的这篇博客里面有详细的二维前缀和解析 代码 #include<bits/stdc++.h> using name...

题意 对一个容器进行一系列操作，这题题目有点问题，操作说明多了个a 1 从前面插入元素a 2 从前面删除一个元素 3 从后面插入一个元素a 4 从后面删除一个元素 5 将整个容器头尾翻转 6 输出个数和所有元素 7 对所有元素进行从小到大排序 思路 因为要从队头队尾插入删除元素，我们可以用STL中的deque（双端队列）便于操作 这些是deque的一些基本操作： push_back(x)/push_front(x) //把x压入后/前端back()/front() //访问(不删除)后/前端元素pop_back() pop_front() //删除后/前端元素empty() //判断deque...

题意  n个整数 a[ 1 ] ~ a[ n ] 可以进行 m 次操作，每次操作 可以对 或是 求m次操作后最大值与最小值差的最大值可能是多少 思路 进行m次操作肯定是对同一个数操作m次,如果操作分散是不能让要求的差最大的 先找到原数组的最大值和最小值，让后对数组每一个数分别操作m次找最大值就好，直接遍历就行 注意特判 n == 1的情况 代码 #include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #pragma GCC optimize(3) typedef long long ll; #defi...

思路 因为每次查询都是找不在集合S中的数，所以不妨逆向思维建立一个集合K，集合K为不在集合S中的所有元素 想到这里如果直接把不在S中的集合全部加到K中那初始时就要加入 1 ~ 1e10 共1e10个元素，那肯定是会超时的 观察一下，每次查找都是找最小的大于x的数并且不在集合S中的，那就是在集合K中的大于元素X的，我们可以离线预处理，先把所有插入删除查找的元素X和X+1都插入集合K，其他的元素在这个数据中无关，就不用都插入到集合K中，查找用二分查找lower_bound就好 代码 #include<bits/stdc++.h> using namespace std; #pragma...

题意 有n件货物，每件货物重 每次操作可以让 区间 i ~ j 内的货物重量加一 或减一求能让所有货物重量相等的最少操作次数 思路 这题能用差分数组求解 ,差分数组  物品之间的重量相等那差分数组 全部为0 对于每次操作对区间 i ~ j 所有物品加一，差分数组  对于每次操作对区间 i ~ j 所有物品减一 ，差分数组  所以只要统计差分数组中正数之和和负数之和，取大的那个就好 为什么取大的那个？ 假如差分数组为 a[i] = {1， -2， 3， 4}，我们要让这个数组i >=2 && i <=4的数全部变为0 （数组设1为初始位置） 经过上面的分析要让数组中的...

思路 冲撞障碍物后有两个可能，增加稳定型 or 减少稳定性，所以分两种情况分析 1、靠常识我们会先撞增加稳定性的障碍物，增加稳定性的当然是要先撞a小的，因为后面可能有a很大的，目前的稳定性可能不够，需要打小怪升级一下，如果直接撞可能会散架。 2、接下来就是撞稳定性减少的，因为必须全部撞完所有的障碍物，所以这里受到的伤害是一个定值 那要如何保证不那么任意散架呢，当然是回复力（ ）更大的在前面更好,先吃到更多的回复才有能力撞下一个 代码 #include<bits/stdc++.h> using namespace std; inline ll read(){ ll s = 0, w ...

思路 注意到这里是求某段区间的和，而且不修改，那肯定是用前缀和了 sum[ n ]表示  接下来就是要选择两个长度为k的区间求最大，最原始的思路当然是枚举每个可能的区间更新最大值，代码就是  ll ans = 0; for(int i = k ; i <= n-k ; ++i){ for(int j = i+k ; j <= n ; ++j){ ans = max(ans,a[i]-a[i-k] + a[j] - a[j-k]); } }结果当然是T的果断，那肯定要想想怎么优化。如果 两段区间分别是 （L,L+1,.....L+k） (R,R+1,.....,R+k)假设 X为 两...