day1上午

1搜索：

先写出基本的搜索模板，然后将大小变量放入dfs返回值去，根据dfs中变量的数量开相应维数的数组，写出记忆化搜索，再根据边界条件和记忆化搜索写出dp。

2差值维护：

#include
     
      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]

到了正题了

有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)

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
     
      =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
      
       =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;//高精乘2for (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
       
        =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<
        
         =1; i--){10^9 只有3位  补6个0if (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^16ans=1;for (i=1; i<=cnt; i++) if (c[i]==1)//这位不为0就乘进去 ans=ans*d[i];

未完待续。。。。。。。。。。。。。。。。。。。。。。。。。。。。