QBXT DAY1

2019-11-14 12:48:50

字体：大中小

来源：转载

供稿：网友

1.枚举 2.前缀和维护差值维护（详见上一篇） 3.最大字段和

for (i=1; i<=n; i++){ sum+=a[i]; if (sum<0) sum=0; ans=max(ans,sum);}下见应用圈地运动（化面为线）求最大子区间和for (i=1; i<=n; i++) for (j=1; j<=n; j++) s[i][j]=s[i-1][j]+a[i][j];for (i=1; i<=n; i++) for (j=i; j<=n; j++) { for (k=1; k<=n; k++) b[k]=s[j][k]-s[i-1][k]; ans=max(ans,work());//work()是求最大子段和，b的（化为一维） }

4.不易出错的二分

//二分//k a从小到大排好序了L=1; R=n; mid=(L+R)/2;while (L<=R){ if (a[mid]<=k) {L=mid+1; mid=(L+R)/2;} else {R=mid-1; mid=(L+R)/2;}}cout<<R<<endl;//最终 L=R+1

5.two point a,b 数组，从中各取一个数，使其和最大但小于k

//、、two point!!两子针t=n;for (i=1; i<=n; i++){ while (a[i]+b[t]>p) t--; ans=max(ans,a[i]+b[t]); }

6.折半搜索（这个我也不会）直接贴标程

、、、、折半搜索+two point体积之和<=m价值之和最大给两部分体积之和都排个序m=105 100 100 5 100 1004 5 63 3 4nw[i],c[i]mid=n/2;1~mid mid+1~nvoid dfs(int x,int X,int y,int z){ if (x==X+1) { a[++cnta].x=y; a[cnta].y=z; return; } dfs(x+1,X,y+w[x],z+c[x]); dfs(x+1,X,y,z);}void dfs2(int x,int X,int y,int z){ if (x==X+1) { b[++cntb].x=y; b[cntb].y=z; return; } dfs2(x+1,X,y+w[x],z+c[x]); dfs2(x+1,X,y,z);} dfs(1,mid,0,0);dfs2(mid+1,n,0,0);将a和b按照.x从小到大排序。for (i=1; i<=cnta; i++) a[i].y=max(a[i-1].y,a[i].y);for (i=1; i<=cntb; i++) b[i].y=max(b[i-1].y,b[i].y);t=cntb;for (i=1; i<=cnta; i++){ while (a[i].x+b[t].x>m) t--; if (t) ans=max(ans,a[i].y+b[t].y);}meet in the middle 折半搜索（meet in the middle）上面！n<=40 2^(n/2) 2^(n/2)*n n^4 n^5n<=35 2^(n/2)*n 2^(n/2)*n^2 n^5 n^6

7.贪心 8.压位

压位（一般压为10^4或10^9）详见下一篇补5位 PRintf("%05d",a[i]);

9.待写 K’th number hard

10.快速幂数组版（x进制）

二进制

while (b) {c[++cnt]=b%2; b/=2;}d[1]=a;for (i=2; i<=cnt; i++) d[i]=d[i-1]*d[i-1];ans=1;for (i=1; i<=cnt; i++) if (c[i]==1) ans=ans*d[i];

进制

s=a; while(k>1) { if(k%2==1) ans=ans*s; s=s*s; k=k/2; } ans=s*ans;

递归版

11.贪心

上一篇：【c++】函数模板

下一篇：go环境安装