排序后，对于一个数 ，寻找第一个满足的。 此时 左边的都是不会发生冲突的，对自己的贡献是 此时和右边的都是会发生冲突的，对自己的贡献是 但这里麻烦是，左右两边可能包含自己。然后可能有连续相同数字，注意处理就好 当 ，寻找到的第一个满足冲突的，必定满足不大于，如果是等于，会是相同值的第一个元素，此时计算右边多扣了一次，加回去 当，寻找到的第一个满足冲突的，一定大于，在计算左边时会多计算一次自身，减回去 #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false),cin.tie(0); typedef long lo...

思路： 把0看成-1，把1看成能把分数清零的一个值，当分数被扣成-k时，游戏结束。 当人物消失时，一定是在第k个0处消失的，由于连续的k个0才会让人物消失，所以贪心地把第k个0变为1，然后直至下次死亡，这就是x=1的情况，每次死亡就记录当前操作至多x次的最长存活天数，由于操作是连贯的，故可以直接枚举i，时间复杂度O(n) #include<iostream> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int N=2e5+7...

观察样例大胆猜测：答案是 因为任意两个数的gcd一定有一个因子是总体的gcd，也就是这个数一定是总体的倍数，连续gcd后，最终的数必然都会变成全体的最大公约数，不可能比这个还小，因为gcd最小就能让一个数减少到全体的公约数，不会使得一个数比这个全体的公约数还要小，因此我们简单证明了这个答案是最小的，另外再证明这个答案一定取得到，只需要第一个与第二个操作，第二个与第三个操作，以此类推，第一个与第二个操作变成__gcd(a1,a2)，第二个与第三个操作变成__gcd( ___gcd(a1,a2),a3)，一趟下来与求gcd(a1,a2,a3,...,an)是等价的。 #include <io...

假设当前数字是114514，我们得到的答案必定是114514abcd   枚举扩展位数，由于答案说明在18位以内，故扩展位数最多枚举18次   获取扩展后的，例如我们扩展了2位，应该得到11451400   寻找第一个大于等于11451400的完全平方数，在二分的时候二分的是 中的，由于最大答案不会超过18位，因为直接枚举到 即可   当这个数减去11451400的结果小于100时（即恰好可以填完00，他前面几个数和没扩展的一样），说明可以构成答案，否则就继续扩展。   总时间复杂度，事实上这个常数非常小，跑了不到。 #include <iostream> #include &lt...

思路 答案一定可以是输入的字符串中的一个，因为若答案字符串长这样（红色）  完全可以去掉分割线右边多余的，不影响答案 此时答案变成，是否能找到一个字符串，使得这个字符串包含了恰好K-1个其他字符串 暴力枚举的时间复杂度是 ，但是看图可知，这个答案如果要包含其他字符串，一定其他字符串是他的前缀，于是可以想到用字典树 枚举字典树进行dfs，记 为恰好在编号x结束的字符串数量，当遍历到某处，在此时的之和恰好等于k时，该字符串便是答案。 #include <iostream> #include <vector> using namespace std; const int N=...

注意到十进制数的构成是形如，由于高位带了权重，所以一定可以被5整除，只需要看个位数。 个位数有 种取值范围，其对应的模5余数只在0~4，其中0没有贡献不计 当最后一位取值为x时，我们也无需关心他拼在一起是怎么样的，只需要关心这个数字的个位数，  也就是每个数都可以有(n-1)！个方案数，其贡献是x取模于5。 对于实现上，完全可以直接计算出这个倍数，每+10，贡献就多20,10以内的单独算就好了,时间复杂度 #include <iostream> using namespace std; const int M=1e9+7; const int N=2e5+7; typedef lo...

实际上就是问我们，能找出多少对区间 ，使满足这一段被挖去后，剩余的字符串中有一个子序列是。 观察时间复杂度，大概是 的级别，我们考虑这样一件事：   如果 是合法答案，那么往里缩也一样合法，因为往里缩会减少字符数量。   如果 不是答案，那么扩大一样不合法，因为往外扩会额外增加字符负担   如果 ，那么一定不合法，因为子序列长度不可能超过两边的长度。   于是很容易想到滑动窗口的做法： 初始时，设，   若当前区间合法，则   若当前区间不合法，显然是合法区间，答案有个，累计答案后   特别地：若不是合法区间，需要R++一次   枚举的时间复杂度是，判断合法(即S是否是T的子序列）的时间复杂度...

思路：看一眼数据，回答最多，但很显然这题要求我们用，也就是推一个式子。由于必须O(1)回答，所以对于1到j的最短路径，一定是直接边结论1：两个不同的正整数异或结果一定非负，既。已知可以让原本偶数+1，奇数-1,假设有中间转点k，则其路径至少是。若，也就是至少 ，容易发现无论j是奇数还是偶数，都不比这个方案数劣。若 ，根据异或结果不小于差值可以证明，这里不展开现在分析结果的输出，由于，所以结果是考虑n是奇数的情况 除了1每一项都有个1跟他异或，所以有偶数个1，由于结合律和分配率，我们可以把偶数个1先进行异或，由于自己和自己异或一定得0，而0和任何数异或都得任何数，所以最终就变成若x是奇数，则x和...

跟 【小红的区间查询】这一题如出一辙，仍然可以离线查询，对查询进行排序后使用双指针优化。构建前缀和数组，原问题等价问，第k个时刻处于前几个区间，大众做法是每次二分前缀和数组，找出第一个大于等于的S[k]，k问答案。我们可以将每次询问保存起来，最后排序，排完序后是单调不减的，那么越往后的询问，对k的要求只会越来越大，因此我们枚举前缀和的时候不需要重新回退i=1开始，而是像双指针那样每次决策，这样下来，时间复杂度是 ，二分的做法是最后跑出来是17ms，排名第7. #include <iostream> #include <vector> #include <algor...

这题大多数人用的是二分查找，我想到了一个双指针的写法，虽然综合时间复杂度仍然是的，但二分写法实际上是，而该写法可以优化成，即对于T次询问，总时间复杂度是。 首先先对区间左端点排序，对于一个询问x，我们不做在线回答，而是收集起来做离线回答。 先对询问进行排序。 记当前的询问是 ，当前的区间是，有以下几种情况   ：说明x正中下怀，只需要将答案记录为 即可（从0开始） ：由于区间被排序了，若当前的x连左端点都够不到，说明往后都不会够到了，故答案是-1 ：即当前的很大，能够越过的右端点，此时需要i++，也就是寻找下一个左端点更强的区间，才能保证右端点能够包住  特别地： 不需要重新枚举，因为越大的数...

CSDN看到的一个另外一种容易想到的解法，原文链接如果a[n]确定了，那么整个数组也就确定的，很容易发现，符合条件的数组一定是单调不降的，因为取模只会把数字变小，或者不变，不可能变大。故当a[n]越小时，其往前的数字的可取值范围就越小，就更容易取到相同值，使数组出现不同种类的数字就更难，因此答案具有单调性，当a[n]越大，不同的种类也就不可能比之前还少。check函数：每次枚举a[n]的大小，然后往前推，这样的时间复杂度是O(nlogn)的，但是注意到一个优化：当下标为i，值为a[i]时，若有a[i]<i，例如i=300,a[i]=1，那么由于一个数取模于比他大的数一定会不变，那么i=3...

我们希望1到X和X到1都是最短路，有个难点是多个起点到终点的最短路，就要用到反向建边，反向建一个图，然后跑1到x的最短路，得到的结果就是x到1的最短路，因为这条路径是反着的，我们扭回来就正好是x到1了。在形式上不要写的像我一样，可以用vector模拟静态邻接链表。时间复杂度O(mlogn) #include <iostream> #include <queue> #include <algorithm> #include <string.h> using namespace std; typedef long long ll; #define I...

题目等价于异或，异或后的数字有几个1就是有几个不同，统计1可以用lowbit来统计，时间复杂度O( a,b的位数) #include <iostream> using namespace std; typedef long long ll; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl cout<<"\n"; const int N=1e3+7; const int M=1e5+7; int ans; int a[N][N]; int n; #define lowbi...

先看题意，只对后2位操作，再看数据范围，这大概是一个O(n)或O(nlogn)复杂度的题目，但由于题目不允许排序，这样会破坏后2位的位置，所以大概是一个O(n)的做法，题目要求计数，脑海里想到了是否是某数学题目，但题目要求不太可能是，先从小范围考虑。若n=1，此时当且仅当a[1]=i的方案数为1，其他为0，当a[1]不是一位数时，方案数全0.若n=2，此时只可能是a[n]+a[n-1]和a[n]*a[n-1]各自的数字取个位数后的2个数字有一个方案数若n=i，我们现在如果要把第i项改成数字j（j是一位数），而且已经知道第i+1项数字为k的方案数，怎么递推？例如，现在的a[i]是3，要改成数字6...