当前位置：首页 > news >正文

清北学堂总结（未完待续。。。。。。。）

news 来源：原创 2024/5/8 9:27:58

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];