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];未完待续。。。。。。。。。。。。。。。。。。。。。。。。。。。。