day1上午 1搜索： 先写出基本的搜索模板，然后将大小变量放入dfs返回值去，根据dfs中变量的数量开相应维数的数组，写出记忆化搜索，再根据边界条件和记忆化搜索写出dp。 2差值维护：
#include<cstdio> using namespace std; int n;int m; int a[888][999],s[999][999]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); s[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; } for(int i=1;i<=m;i++) { int x,y,k,x1,y1; scanf("%d%d%d%d%d",&x,&y,&x1,&y1,&k); s[x][y]+=k; s[x1+1][y1+1]+=k; s[x][y1+1]-=k; s[x1+1][y]-=k; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { a[i][j]=s[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]; } printf("%d"); }好懵啊 3圈地运动 给定一个n*n的矩阵，找一个最大的子矩阵，使得这个子矩阵里面的元素和最大。
work() for (i=1; i<=n; i++) { sum+=b[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];//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];//i为起点列，j为终点列，k为长度，b[k]为从i到j第k列的和。 ans=max(ans,work());然后通过求最大的子区间的和来更新答案。
4 k’th number hard meet in the middle： 就是二分 two point : 有两个从小到大排好序的序列a和b，长度均为n。 现在有一个参数p。 在a中找一个数字ai，b中找一个数字bj，使得ai+bj<=p且ai+bj最大。
for (i=1; i<=n; i++) { while (a[i]+b[t]>p) t--;//两个指针a从前往后，b从后往前,先找到令a[i]+b[t]<p的界限然后用ans更新答案 ans=max(ans,a[i]+b[t]); }到了正题了 有n个数，共有2^n个子集，一个子集的值看做其所有数的和。 求这2^n个子集中第K大的子集。（n超大）
int work(int x) { int sum=0; k=cntb; for (i=1; i<=cnta; i++) { while (a[i]+b[k]>x) k--; sum+=cntb-k; } return sum; } L=0; R=S; mid=(L+R)/2; while (L<=R) { if (work(mid)<k) {R=mid-1;mid=(L+R)/2;} else {L=mid+1; mid=(L+R)/2;} }5 高精 我的代码太多 这是老师的伪代码
for (i=a[0]+1; i<=b[0]; i++) a[i]=0;//高精加 for (i=b[0]+1; i<=a[0]; i++) b[i]=0; for (i=1; i<=max(a[0],b[0]); i++) c[i]=a[i]+b[i]; c[0]=max(a[0],b[0]); for (i=1; i<c[0]; i++) if (c[i]>=10) {c[i+1]++; c[i]-=10;} while (c[c[0]]>=10) {c[0]++; c[c[0]]=1; c[c[0]-1]-=10;} for (i=a[0]+1; i<=b[0]; i++) a[i]=0;//高精减 for (i=b[0]+1; i<=a[0]; i++) b[i]=0; for (i=1; i<=max(a[0],b[0]); i++) c[i]=a[i]-b[i]; c[0]=max(a[0],b[0]); for (i=1; i<c[0]; i++) if (c[i]<0) {c[i+1]--; c[i]+=10;} while (c[c[0]]==0) c[0]--; a[]*k//高精乘1 for (i=1; i<=a[0]; i++) a[i]*=k; for (i=1; i<a[0]; i++) if (a[i]>=10) {a[i+1]+=a[i]/10; a[i]%=10;} while (a[a[0]]>=10) {a[0]++; a[a[0]]=a[a[0]-1]/10; a[a[0]-1]%=10;} 123*178=(100+20+3)*(100+70+8) for (i=1; i<=a[0]+b[0]-1) c[i]=0;//高精乘2 for (i=1; i<=a[0]; i++) for (j=1; j<=b[0]; j++) c[i+j-1]+=a[i]*b[j]; c[0]=a[0]+b[0]-1; for (i=1; i<c[0]; i++) if (c[i]>=10) {c[i+1]+=c[i]/10; c[i]%=10;} while (c[c[0]]>=10) {c[0]++; c[c[0]]=c[c[0]-1]/10; c[c[0]-1]%=10;} a[]/k;//高精除 for (i=a[0]; i>=1; i--) { if (i!=1) a[i-1]+=a[i]%k*10; a[i]/=k; } 压位 cout<<c[c[0]]; for (i=c[0]-1; i>=1; i--) { 10^9 只有3位 补6个0 if (x<10) printf("00000000"); else if (x<100) ... else if (x<1000) printf("000000"); ... printf("%d",c[i]); }6快速幂：
while (b) {c[++cnt]=b%2; b/=2;}//分为2进制 d[1]=a; for (i=2; i<=cnt; i++) d[i]=d[i-1]*d[i-1];//求出d的每个次方 d[2]=a^2; d[3]=a^4; d[4]=a^8 d[5]=a^16 ans=1; for (i=1; i<=cnt; i++) if (c[i]==1)//这位不为0就乘进去 ans=ans*d[i];未完待续。。。。。。。。。。。。。。。。。。。。。。。。。。。。
