X操作
100分以下做法:我也不知道怎么写
100分做法:
首先,判断的第一条件是m>=abs(x-y),表示操作次数大于两数的差,因为如果操作次数小于两数的差了,那么x一定时无法变成y的,其次,如果操作abs(x-y)次后使x变成了y,这时如果操作次数是奇数,那么就无法达成,是偶数,我们可以通过反复加减的方式来使得x==y。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t; scanf("%d",&t); while(t--) { ll x,y,m; scanf("%d%d%d",&x,&y,&m); ll s=abs(x-y); if(m>=s&&(s&1)==(m&1)) printf("Yes\n"); else printf("No\n"); } }
填数
100分以下做法:我也不知道怎么写
100分做法:
首先,对于没有限制的,显然我们填1即可,对于限制1,贪心的使得a[i]==a[i-1],对于限制2,贪心的使得a[i]==a[i-1]+1,这样贪心下去,然后判断最终得到的总和是否小于等于m即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; int b[N]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&b[i]); bool flag=true; int pre=0,sum=0; for(int i=1;i<=n;i++) { if(b[i]==0) sum++,pre=1; else if(b[i]==1) sum+=pre; else sum+=pre+1,pre++; if(sum>m) {flag=false;break;} } printf(flag?"Yes\n":"No\n"); } }
区间中最多的数
10分做法:暴力枚举
100分做法:1<=a[i]<=100,用前缀和维护1100每个数出现的次数,就可以O(1)的查询某个数在区间里出现的次数了,然后对于一次查询,只需要O(100)的暴力去统计即可,时间复杂度O(100q+100n)100每个数出现的次数,咋们就可以TLE了,时间复杂度O(100qlog2(n)+100nlog2(n))。
50分做法:在100分做法的基础上,用数据结构去维护1
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,q,a[N],sum[N][105]; int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=1;j<=100;j++) sum[i][j]=sum[i-1][j]+(a[i]==j); while(q--) { int l,r,mx=0,ans; scanf("%d%d",&l,&r); for(int i=1;i<=100;i++) if(sum[r][i]-sum[l-1][i]>=mx) ans=i,mx=sum[r][i]-sum[l-1][i]; printf("%d\n",ans); } }
子段和
100分以下做法:我也不知道怎么写
100分做法:
1.f[i][j]表示[i,j]这段区间的和,开一个vis数组保存每个和出现的次数,如果之星操作1,我们只需要删除n个区间的值,执行操作2,只需要假如n个区间的值,时间复杂度O(nm)。
2.记录前缀和和一个vis数组,vis数组里保存某个前缀和出现的次数,对于每次查询O(n)的去跑所有前缀和,判断sum-x这个前缀和是否存在即可,时间复杂度最坏O(nm)。
3.由于数据水,时间复杂度O(n^2 m)的算法也被放过了,很遗憾我的数据这么水。
做法1:
#include<bits/stdc++.h> using namespace std; const int N=255; int n,m,a[N],sum[N],vis[N*100000]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i],vis[sum[i]]++; vis[0]=1; while(m--) { int opt,x; scanf("%d",&opt); if(opt!=1) scanf("%d",&x); if(opt==1) vis[sum[n]]--,n--; else if(opt==2) a[++n]=x,sum[n]=sum[n-1]+a[n],vis[sum[n]]++; else { bool flag=false; for(int i=n;i>=1;i--) if(sum[i]>=x&&vis[sum[i]-x]) flag=true; printf(flag?"Yes\n":"No\n"); } } }
做法2:
#include<bits/stdc++.h> using namespace std; const int N=255; int n,m,a[N],f[N][N],vis[N*100000]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { if(i==j) f[i][j]=a[i]; else f[i][j]=f[i][j-1]+a[j]; vis[f[i][j]]++; } while(m--) { int opt,x; scanf("%d",&opt); if(opt!=1) scanf("%d",&x); if(opt==1) { for(int i=1;i<=n;i++) vis[f[i][n]]--; n--; } else if(opt==2) { a[++n]=x; for(int i=1;i<=n;i++) { if(i==n) f[i][n]=a[n]; else f[i][n]=f[i][n-1]+a[n]; vis[f[i][n]]++; } } else printf(vis[x]?"Yes\n":"No\n"); } }
做法3:
#include<bits/stdc++.h> using namespace std; const int N=255; int n,m,a[N]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(m--) { int opt,x; scanf("%d",&opt); if(opt!=1) scanf("%d",&x); if(opt==1) n--; else if(opt==2) a[++n]=x; else { bool flag=false; for(int i=1;i<=n;i++) { int t=0; for(int j=i;j<=n;j++) { t+=a[j]; if(t==x) flag=true; } } printf(flag?"Yes\n":"No\n"); } } }