QBXT DAY1

2019-11-14 11:20:45

字體：大中小

來源：轉載

供稿：網友

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位 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.貪心