题目 思路： 失败的情况：n个数全部相加一遍总和<=0,且前缀和的最大数max也比所询问的数x小 成功的情况：因为询问的次数较多，用二分查找优化，先创造个二分的递增条件 对于能在一个循环就找到符合条件的答案 x<=max(上文提及) 模拟一下过程，3 -2 2 -1 5 4 -3 , 前缀和： 3 1 3 2 7 11 8 如果x=7 要用二分找出第一个>=7的数所在位置，可以知道对于3后面的那个1来说前面的3已经小于7了，1比它小也不可能大于所以这个1是无效的，只有出现>3的数才有可能大于等于7，所以我们令1变为3去维护一个非递减数列，同理2变为3，8变为11. 新的...

题目 a/b=i, a%b=i -> a=i*(b+1)，(对于一个b可以配出几个i就可以产生几个贡献)可以知道对于给出的x,y 取任意1<=b<=y，一个b产生的贡献为min(x/(b+1)，b-1) 当x>=(b+1)(b-1)时对于此时的b的贡献全取b-1 当x<(b+1)(b-1)时按x/(b+1)的贡献，此时用整除分块求解 另注意下范围，细节见代码 Code: #include<iostream> #include<cmath> #define FAST ios::sync_with_stdio(false),cin.tie(0)...

题目 思路：先来看一个简化版的问题，就是对于 2 9 2 3 8 5 ，我是第3个人，那么答案其实就是 前面二人取(前面两个)2，9 max(2,5)=5 前后各一个 2，5 max(9,8)=9 后面两个 8, 5 max(2,3)=3 答案为min(5,9,3)=3 即最小都能达到的 先在来看原问题，我们还可以指定选k个人，那么其实也就只有k种情况，让k个人全取前面0个人取后面，k-1人取前1人取后面…O（n^2）可以实现。而假设指定1个人取前面，1个人取后面，就相当于将原数列前面1个、最后面1个元素去掉，从9 2 3 8再取两个（假设我是第四人可以指定俩人），此时再取的操作和上面的简化版...

题目 题意：一个字符串如果只是其中字符顺序被打乱则称其和原字符串相互为字谜。对于两个互为字谜的字符串，两个字符串按相同的位置分割开成为n(n>=2)个小串，然后每个小串都互为字谜，则称这两个字符串是互为可还原的，现在给我们一个字符串，再给出q次问询，每次问询给出一个区间，要我们判断区间内的字符串是否具有任意一个不可还原的字符串与之对应（不可还原需要两个字符串互为字谜且不是可还原的）。 思路：其实判断其是不是可还原串拆成n个小串变为拆成2个小串就可以了，因为可以拆成n个必定也可以拆成2个。然后我们构造一下哪几种情况可以找到不可还原串 1.单独一个字母 如： a 因为可还原串要求至少有两段 ...

题目 思路：如横纵坐标相加为奇数则将对应位置的数变为奇数+1或不加，如横纵坐标相加为偶则将对应位置数变为偶数。 这题我觉得要培养一种感觉，看到一个题目，它给了什么条件要按给的条件那个方向去多思考一下，就像本题说可以加一或不加，那么我们想想加一其实比较容易想到的就是改变奇偶性。而有些题它给了一些数据大小，其实也是一种引导，引导着我们要去用符合数据范围的算法，从出题人的角度想想这些条件可能要考什么。 #include<iostream> using namespace std; int main() {  int a, b, t;cin >> t; while (t--) ...

题目 从结果来分析，最小的步数必然是往右走多少步使一部分盗贼到达安全区域，然后再向上走一部分使余下的盗贼到达安全区域。那么我们从0到1e6+1枚举所有向右走的步数加上在该步数下最小向上走的步数，取其中最小值即为答案。那么问题来了，这个最小向上走的步数我们如何能够快速得到答案？其实只需要一个从后往前遍历记录的向上移动所需最大值数组即可。 简单来说就是，对于一个盗贼x,y，灯塔tx，ty，可以让盗贼向右移动tx-x+1使其脱离范围，也可以使其向上移动ty-y+1使其脱离范围。然后我们用一个数组dis[tx-x+1]=max(dis[tx-x+1],ty-y+1)记录在最小向右移动tx-x+1就能脱...

题目 从结果分析，答案必定是数组中的一个值，那么我们将值排个序开始二分。check的话，对于我们将要检查的值mid，将原数组中所有小于mid的值设为-1，大于等于mid的值设为1，对于一段区间看其中位数是否>=mid，只要看变化后该区间的总和，如果>0则其中位数>=mid。用一个前缀和sum记录即可，从k开始遍历（最小长度为k），假设遍历到了 k+3，那么sum[k+3]-sum[0] sum[k+3]-sum[1] … sum[k+3]-sum[3]都可以取用，我们想要使值尽可能大，只需取sum[1—3]中的最小值相减，用一个数组维护前面前缀和的最小值即可。 Code: #...

题目 对于easy情况的做法是，对每个范围都询问两次第二大值，借用第二大值确定最大值所在范围，然后缩小范围。 hard情况的做法是，先询问第二大值所在位置p，然后根据最大值所在其左还是右分情况进行二分，其比easy询问次数少了一半是因为每次问询都使用mid—p（假设最大值在p左边），如果第二大值位置还等于p，说明最大值位于mid—r范围内，使 l=mid,如果第二大值位置不等于p,说明最大值位置不位于mid—r范围内，使 r=mid-1，最大值在p右边的情况也类似。还要注意下不能询问范围为1的区间。 Code: #include<iostream> #include<algo...

第一个>=x的位置 l while (l <= r) {  int mid = (l + r) / 2; if (lst[mid] < x) l = mid + 1; else r = mid - 1; } 最后一个=x的位置 l-1 while (l <= r) {  int mid = (l + r) / 2; if (lst[mid] <= x) l = mid + 1; else r = mid - 1; } while(l<r) 如果为check成功 l=mid，else r=mid-1 mid=(l+r+1)/2 如果为check成功 r=mid...

题目 思路：对于答案我们只需求取每相邻的两个元素的最大相差再从所有的最大相差取最大的即可，那么贪心一下假如要求取的是第一个和第二个元素的最大相差，那么就是第一个元素第一次出现的位置和第二个元素最大的能使得后面能完全匹配第二个数组的位置。简单来说就是—在前面匹配好了的情况，后一个元素取最后面那个刚好能使后面也匹配的位置。然后从后往前遍历得到刚好使后面达成匹配的最大位置，从前面遍历得到完成前面匹配的第一个出现位置，细节见代码。 Code: #include<iostream> #define pii pair<int,int> #define FAST ios::sync_...

题目 这一道题思路其实都有，主要细节比较多，我就wa了很多次… 对于x的构造前面b个a后面全是0 如 3 6 6 x:111111000 再看b的构造 首先当k<=a 前面1—b-1全为1，第b+k个元素为1，其余0 如 4 3 2 x:1110000 y:1100100 当a<k<=a+b-2 第a+b个元素为1，再从b-(k-a)+1—b为1，然后就是还剩下的1的个数c=b-1-(k-a)使最开始的c个元素为1,即1—c为1。 如 3 6 6 x: 111111000 y: 110111001 还有一些特殊情况 当 0 1 0 时 x,y都只有一个元素 1 当b=1||a...

题目 思路：先构造成最小的情况，从前k个数的每个数开始，之后每隔k个数令其等于前面的该数，如 lst[3]=2 i=3(k=4) lst[7] lst[11] lst[15]…=lst[3]=2， 如果此时构造出来的数满足大于原数，则输出。如果不满足则把lst[k] lst[2k] lst[3k]…全体+1，但可能会发生+1后变为10，所以需要从lst[k]往前找到第一个小于9的数位置噢p，将其每隔k个全变为lst[p]+1 lst[p+k]=lst[p]+1…然后再将p—k的数每隔k个全部转化为0，因为已经保证新数一定大于原数了，将后面的变为最小。 Code: #include<ios...

题目 对于下面这个图可以知道当U涂中间三个时是不会对其它的三种产生限制的，而如果涂了4个则必然会占到L R其中一个相邻的格子，涂了5个必然会占掉相邻的L R两个格子，这样就产生了限制，我们只需把不满足限制的情况为NO，其余为YES即可。我们来看满足条件的情况，假如U<mark>n,D</mark>n，得出L>=2 R>=2，因为必然会占掉L R两个相邻的格子，如果L或R为n，则L>=1 R>=1.假如U或D有一个=n-1，那么L R必然有一个格子会被占掉，得出L+R>=2*(U D等于n的个数)+1*（U D等于n-1的个数)，对于U Ｄ ...

题目 运用黑白染色，求出的最少颜色的棋子就是答案。因为当把棋盘用黑和白染色后，每放一个格子必然会占掉黑格和白格各一个，看能最多占掉多少个相邻的黑白格。 Code: #include<iostream> using namespace std; typedef long long ll; int main() {  int t;cin >> t; ll f = 1, h = 0, b = 0; while (t--) {  int n;cin >> n; if (t%2==1) {  h += (n + 1) / 2; b += n / 2; } else {...