用dp会爆时间和空间，考虑贪心先考虑3只3只的买，剩下的再单独买3只买的最便宜价格不一定就是b元，也可能是3*a元。这里决策一下，剩下的不够3只，要么考虑一只一只买，买完，要么直接买3只。极端情况就是：3只的价钱贵的离谱，但1只的价钱很便宜，乘3也抵不过直接买3只的b元，也可能出现1只价格贵的离谱，3只的反而很便宜，最后只剩下一只或两只的时候，直接买3只会比分开买更便宜。为什么先3只3只的买一定是最优的呢？因为如果你不这样买，你一只一只买，每买3只其实还是等价于直接买3只，只不过我们讨论是按3*a还是b而已 #include <iostream> using namespace s...

前置知识 唯一分解定理：一个大于1的正整数可以被表示为多个质数的乘积，一般表示为  完全平方数：注意到完全平方数可以表示为，而根据唯一分解定理，k又是可以被表示为质因子乘积，因此我们有结论：  即，一个完全平方数，每个不同质因子的幂次一定是偶数。 另外：平方数×平方数还是平方数 思路 还是唯一分解定理，有：  我们只需要把每个非偶数的次幂填到偶数，得到一个平方数（至少是他），这个平方数如果超出了R说明无解。 至此，我们至少得到了一个数，乘他能变成平方数，怎么让他变成[L,R]之间的数？我们想办法乘上一个数，让他变到里面，贪心地思考，就是，但乘上这个数就可能导致不是平方数了，我们要乘上一个数不变...

可以被5整除的充分必要条件是个位是0或5 由于排列可以随便排，所以只需要数字中有0或者有5就可以了 void solve(){ cin>>n; string s=to_string(n); if(s.find('5')!=-1 || s.find('0')!=-1)cout<<"YES\n"; else cout<<"NO\n"; return; } int main(){ ios::sync_with_stdio(false),cin.tie(0); int tt=1;cin>>tt; while(tt--)solve(); return 0;...

代码： int L[10001], R[10001]; class Solution { public: int ans = 0, minh = 1e9, maxh = -1; int maxArea(vector<int>& height) { for (int i = 0; i < 10001; i++) { L[i] = 1e9; R[i] = -1; } for (int i = 0; i < height.size(); i++) { int h = height[i]; L[h] = min(L[h], i); R[h] = max(R[h], i)...

这题大部分题解都是 和 放进去，其实只离散化 也是可以的. 每次查询目标值在离散化数组的排名，然后查询排名数量即可。 这样做的时间复杂度是 ，常数应该是上面写法的2倍左右，不过实测速度挺快名列前茅 代码如下： #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) using namespace std; using ll = long long; const int N = 1e5 + 7; ll s[N], ss[N]; int fa[N]; int n, len; ll k, ...

容易发现只有左右两边都是0的时候才能修改为1,否则必定和左右两边任意一个1相邻，然后贪心地修改为1，只需要判断可以被执行的位置数量超过m没有即可 #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N=2e5+7; const int M=1e9; typedef long long ll; typedef pair<int,int> pii; int n,s[N],b[N]; ll m,k,ans; void solve(...

N个点，如果直接走，就是dist(a,b)*2秒，或者缩放后走，走的消耗会变低，但缩放后要放大到最大，这2个操作也有自己的耗时，求所有点的最短耗时总和。容易发现每次都是从最大缩放计算，所以每个点都是独立的。可以列得耗时函数，其中k是用在缩放屏幕的时间，e是不缩放时候的走路时间（对于单个点来说是个常数），因此这是一个关于k的函数，对k求个导，得到：然后求极值点，分情况讨论即可 #include <iostream> #include <cmath> #include <iomanip> using namespace std; const double L=l...

由于炸弹可以直接把在同一个连通块杂草全清除，那么剩余不能被清除的就是不在同一个连通块的杂草，也就是被石头或边界包围着的杂草，也就是求我们所在连通块，尽可能去扩展，得到的杂草数量。在实现上可以用BFS，然后由于每个点至多入队一次，至多出队一次，可以手写队列缩小一下常数。 #include <iostream> #include <queue> using namespace std; const int N=1e6+7; char a[1003][1003]; int n,m,x,y; int dir[][2]={{0,1},{1,0},{-1,0},{0,-1}}; i...

思考点1：求中位数需要选取子序列后排序思考点2：子序列可以是非连续的序列思考点3：既然如此，我们只需要考虑将原数组排序，因为无论怎么选，最终排序后的结果与原序列一致。思考点4：那说明我们只需要关心0和1的个数现在问题变成，长度为n，且有a个1，n-a个0的数组，计算长度为k的子序列中位数之和。假设前面选了cnt个0，后面就必选k-cnt个1。当cnt=k/2向上取整时，说明中位数是0，否则就是1，然而中位数是0对答案并没有贡献，所以我们需要枚举cnt在k/2以前的即当选了0个0，后面就选k个1。有几种？当选了1个0，后面就选k-1个1。有几种？以此类推。这里推荐使用乘法逆元，因为这里需要查询次...

观察样例发现就是矩阵面积，打个表，发现1e5以内的坐标都可以通过简单的几次变化到，猜结论就是矩阵面积，于是直接输出。注意输出要用LL就是 #include <bits/stdc++.h> using namespace std; typedef long long ll; void solve(){ int a,b,c,d; cin>>a>>b>>c>>d; ll q=c-a+1; ll h=d-b+1; cout<<q*h<<"\n"; return; } int main(){ ios:...

考虑,直接输出 考虑,直接输出 考虑,为了不重复计数，新增的路径数只可能是第三层多出来那些叶子结点 他们既可以向上两层（有多少个叶子结点，就有多少个这样的方案数，对应图中红色的路径） 又可以向上一层向下一层（显然有几个上一层有几个，就有多少个方案数，因为兄弟之间才能做一次这样的路径，对应图中蓝色路径） 满二叉树第层一共有 个节点，于是每多一层，计数就多 个红色路径，同时又多 个蓝色路径 在实现上使用快速幂即可时间复杂度：,预处理 数组可以加速到。  #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++...

一道不算难，但写起来有点难的dp。 记 为前 项中，最后一位一定为 的最小开销 显然 ，即第一个字符一定为第一个字符是不需要修改的。 而，即第一个字符如果要修改为别的字符，就是花费1个代价。 考虑如何转移，如果要考虑第 项改为，那前一项可以是 ，其中 是 符合和谐条件的两个字母，二者取一个最小值，然后加上第项改为的代价 现在我们并不知道步长，所以还需要外层额外枚举一次步长。 总时间复杂度是的，其中是字符集大小，这里 ,这里的空间复杂度达到了惊人的,由于每次枚举新的步长，都要重新设定数组，所以空间复杂度很难堪。 又借助熟悉的滚动数组方式，但是借助的 可能比当前大，也可能比当前小，所以没办法只优化...

赛时为数不多做出来的数学题 观察样例发现很难构造，因为第 位要放一个数字，不可能真像 那样这么好枚举，但是第二个样例提醒了我们，如果是无限循环小数，就不需要管位置。 考公的时候学过百化分，注意到 ,那么就分为以下几种情况   数字为0：如果要求放小数点后第一位，可以直接是，如果不是，可以 直接是   数字为9：也就是需要，但并没有这样的数字，但算多几个百化分就知道，，也就是偶数位一定是9，如果 是偶数，就直接输出这个，那么是奇数的话，就前移一位，也就是   数字在 之间，直接输出，但注意，由于和 有一个约数，事实上可以直接输出和。   代码如下： #include <bits/stdc+...

T1题意： 给定一个环状数组，求否存在一个长度为n的递增区间思路：​ 破环成链，复制多一份，然后逆序枚举，当长度为n的时候就输出YES #include <iostream> using namespace std; const int N=2e5+7; int n; int a[N]; void solve(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } int len=1; int end=a[2*n]; for(int i=2*n-1;i>=1;i--){ if(a[i...