新思路，先给佬磕一个 这个思路的核心就是修改当前位的值只需要通过x与当前下标中的值的差来修改sum即可，然后就是如何获取当前下标中的值，起初我也有类似的想法，但是没有这么妙，修改所有数的地方我甚至傻傻的把数组a遍历了一遍一个个修改然后重新求和，直接猛猛超时。这道题只需要获得当前位的数值是多少就好了，对于全部的数修改，并不需要实际修改数组。用pair存储是第几次修改以及修改为的数值是多少，然后在修改单个值的时候，只需要判断是在整体修改之后发生，还是之前发生，如果是之前发生，那么当前值，直接使用pair中存储的数值即可，反之同理。 然后不要忘记更新数组中存储的内容。 #include<bit...

这道题思路，很简单，要求最多几个自然数能乘出一个数来，那一定是从最小的数开始尝试，去重或者不去重都无所谓，i是递增的，本来就保证了不会重复。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int M=1e6+5; int a[M]; int n; int main(){ int t; cin>>t; while(t--){ memset(a,0,sizeof(a)); cin>>n; int tot=0; for(int i=1;i<=n;i++){ i...

这道题只让再可能的数中有0或1出现，那么最少可能方案的数量只可能是每个位上的最大的数字，因为一定要在这个位上减去这个数目的一，才可以将这位变成0，接下来就是按每一位的大小求出这一位该有几个数这一位是1 很重要的部分，求出每一个数的每一位是一还是零 for(int i=1;i<=n;i*=10){ int res=(n/i)%10; //求出最后一位的数值 ans=max(ans,res); for(int j=1;j<=res;j++){ //每一位是几，就应该有几个数这个位是1 num[j]+=i; } }  #include<bits/stdc++.h> using...

这道题的思路是贪心，为什么是贪心呢，因为能划分的行、列过道都是有限个数，要是想在有限个数里面选取最优解，那显然是找同一个两行里面交头接耳人数最多的两行中间加过道，列也是如此。 不过这里有坑点，就是他要求输出时候下标要升序排序，样例也是鸡贼，不对下标排序的话能过，然后我就开心的提交了，然后就G了，所以下标也要拍一次序，当然要在选出的那L或者K个大值中排序。 #include<bits/stdc++.h> using namespace std; int m,n,k,L,d; const int M=2e4+5; struct node{ int ind,cnt; bool opera...

一道动态规划求最大子序和的问题，需要知道的是，这里是环，我们需要将环展开成线处理，每一次找最大的子序和，然后把它拿走（变为0） #include<bits/stdc++.h> using namespace std; int n; const int M=2e5+5; int dp[M<<1]; int a[M<<1]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>dp[i]; a[i]=dp[i]; } int cn=1; for(int i=n+1;i<=2*n;i+...

线段树模板题 #include<bits/stdc++.h> using namespace std; int n,q; const int M=2e5+5; typedef long long ll; ll a[M]; ll tree[M<<2]; ll tag[M<<2]; ll ls(ll p){ return p<<1; } ll rs(ll p){ return p<<1|1; } void pushup(ll p){ tree[p]=tree[ls(p)]+tree[rs(p)]; } void pushdown(ll p...

一道简单的bfs搜索题，bfs最早搜到终点的那条路径一定是最短的路径，输出步数即可，然后就是搜过的点没有必要再搜了，既然曾经被走过，那么再重复走这点的路径肯定不是最短路，再次重新走也是多余。 #include<bits/stdc++.h> using namespace std; int x,y; struct node{ int x,y; node(int a,int b){ x=a; y=b; } node(){ } }; bool check(int xx,int yy,int tx,int ty){ double ans=sqrt((xx-tx)*(xx-tx)+(yy-t...

可以提前把施法后的b算出来。因为前面的结果会影响后面的判断 #include<bits/stdc++.h> using namespace std; int n,m; const int M=5e4+5; int a[M],b[M]; int d[M]; int main(){ int t; cin>>t; while(t--){ memset(d,0,sizeof(d)); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } for(int i=1;i<=...

这道题思路就是，预处理前i个数字，二进制位上的1的总数。 因为要求找到一个x对区间内的a[i]做异或操作，使得异或后的区间和最大，而异或运算是这样的0^1=1 0^0=0 1^1=0，我们要想使得区间和最大，显然要让每一个位上的1的数量最大化，所以当1的数量比0少时，就对该位异或1，把0，1数量交换。 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; int n,q; int sum[N][40]; //前i个数，各个位上有几个1 int main(){ cin>>n; f...

这个题不能胡乱选择行或者列，因为你一旦选择了一列以后，接下来选一行一定会受到影响，不符合贪心的特点，就是子问题的求解不影响其他部分。所以可以枚举行，然后贪心列，这样列和列之间不会相互影响，可以贪心的来做，然后就是位运算枚举每一种行的选择情况。 这道题被坑了，主要还是基础知识不扎实，deal函数我直接把数组传进去，我以为里面变，不会影响外面的数组，然后就WA了两个小时，一直以为是什么逻辑上的问题，直到我突发奇想，想把数组输出出来看看，结果@_@ 很难过，所以数组一定要copy一份出来 （QaQ） #include<bits/stdc++.h> using namespace std;...

#include<bits/stdc++.h> using namespace std; const int M=2e5+5; typedef long long ll; ll a[M]; ll sum[M]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); int n,k; cin>>n>>k; for(int i...