T1.5838. 旅游路线
首先想到O(n^4)枚举两个点，用前缀和算，但是200会T。
考虑枚举一条扫描线，这是O(n^2)的，扫描用O(n)，就可以了。
当前和已经小于0，就可以舍去了。
#include<iostream> #include<cstdio> using namespace std; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } const int MAXN=256; int n,m; int a[MAXN][MAXN]; int s[MAXN][MAXN]; int main(){ n=rd();m=rd(); for(register int i=1;i<=n;i++){ for(register int j=1;j<=m;j++){ a[i][j]=rd(); } } for(register int i=1;i<=n;i++){ for(register int j=1;j<=m;j++){ s[i][j]=s[i][j-1]+a[i][j]; } } long long ans=0; for(register int i=1;i<=m;i++){ for(register int j=1;j<=i;j++){ long long tmp=0; for(register int k=1;k<=n;k++){ tmp+=1ll*s[k][i]-s[k][j-1]; ans=max(ans,tmp); if(tmp<0) tmp=0;// } } } printf("%lld ",ans); return 0; }
T2.4737. 金色丝线将瞬间一分为二
卡树状数组差评！卡常差评！
把曼哈顿距离的x和y分开算，变成两个序列问题，现在就需要维护一个数据结构，支持单点插入，查询比它小/大的数的个数，以及这两部分数的和。
第一反应平衡树没救了，幸好看了一眼数据范围感觉常数不行，离散化了用四个树状数组维护一下就好。
不是所有的曼哈顿距离都一定要转化成切比雪夫距离
/*卡BIT差评*/ #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<algorithm> #include<iostream> #include<cstdio> using namespace std; typedef long long ll; inline ll rd(){ ll ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } const int MAXN=1048576; int n; ll m; struct BIT{ ll t[MAXN]; ll query(ll x){ ll ret=0ll; for(;x;x-=x&-x)ret+=t[x]; return ret; } void update(ll x,ll w){ for(;x<=n;x+=x&-x)t[x]+=w; } }tx,ty,cx,cy; ll xs[MAXN],ys[MAXN],savx[MAXN],savy[MAXN]; ll lenx[MAXN],leny[MAXN]; int main(){ n=rd();m=rd(); ll x,y; for(register int i=1;i<=n;i++){ x=rd();y=rd(); lenx[i]=xs[i]=savx[i]=x; leny[i]=ys[i]=savy[i]=y; } sort(savx+1,savx+1+n); sort(savy+1,savy+1+n); int totx=unique(savx+1,savx+1+n)-savx-1; int toty=unique(savy+1,savy+1+n)-savy-1; for(register int i=1;i<=n;i++){ xs[i]=lower_bound(savx+1,savx+1+totx,xs[i])-savx; ys[i]=lower_bound(savy+1,savy+1+toty,ys[i])-savy; } ll sumx=0,sumy=0; for(register int i=1;i<=n;i++){ tx.update(xs[i],lenx[i]); ty.update(ys[i],leny[i]); cx.update(xs[i],1); cy.update(ys[i],1); ll cntx=cx.query(xs[i]-1)+cx.query(xs[i])-cx.query(n); ll cnty=cy.query(ys[i]-1)+cy.query(ys[i])-cy.query(n); ll ansx=cntx*lenx[i],ansy=cnty*leny[i]; ansx+=tx.query(n)-tx.query(xs[i])-tx.query(xs[i]-1); ansy+=ty.query(n)-ty.query(ys[i])-ty.query(ys[i]-1); sumx+=ansx;sumy+=ansy; // cout<<sumx<<" "<<sumy<<endl; if(sumx>m||sumy>m||sumx+sumy>m) return printf("%d ",i),0; } puts("-1"); return 0; }
T3.4738. 神在夏至祭降下了神谕
首先有一个O(n^2)的DP，设f[i]为长度为i的前缀最多有多少种方案数。
f[i]=sigma(f[j]) j<i且[j+1,i]内满足个数差小于m。
这是一个前缀和，树状数组优化一下前缀和即可。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } const int MAXN=100005; const int offset=MAXN<<1; const int MOD=1e9+7; int f[MAXN],a[MAXN]; int n,m; int t[MAXN<<2]; inline int query(int x){ int ret=0; for(int i=x+offset;i;i-=i&-i)ret+=t[i],ret%=MOD; return ret; } inline void update(int x,int w){ for(int i=x+offset;i<=2*offset;i+=i&-i)t[i]+=w,t[i]%=MOD; } int main(){ n=rd();m=rd(); update(0,1); for(int i=1;i<=n;i++) a[i]=rd(); for(int i=1;i<=n;i++) a[i]=a[i]?1:-1; for(int i=1;i<=n;i++) a[i]=a[i-1]+a[i]; for(int i=1;i<=n;i++){ f[i]=query(a[i]+m)-query(a[i]-m-1); if(f[i]<0) f[i]+=MOD; f[i]%=MOD; update(a[i],f[i]); } cout<<f[n]; return 0; }