首页 > 代码库 > BZOJ 刷题记录 PART 2

BZOJ 刷题记录 PART 2

【前言】最近感觉状态不错。做题几乎不看题解了。(一群大牛(FZ&WCY)在旁边喷:你刷水题有意思!)但是至少这也是一种进步吧。特别是权限题中有很多思维题。

【BZOJ1055】就是一个简单的区间DP。重要代码:

for (l=2;l<=L;l++)
    for (i=1;i<=L-l+1;i++)
    {
      j=i+l-1;
      for (k=0;k<4;k++)
        for (cut=i;cut<j;cut++)
          for (p=0;p<4;p++)
            if (f[i][cut][p])
              for (q=0;q<4;q++)
                if (f[cut+1][j][q])
                  f[i][j][k]=f[i][j][k]|map[p][q][k];
    }

【BZOJ3382】直接把绝对值去掉,枚举每一种符号。

【BZOJ2096】这道题一开始觉得是系统堆,结果感觉会爆掉,因为N=100万!!然后就想单调队列怎么也想不出。后来SYC大神跟我说,系统堆不会爆!于是我心安理得的写了。

for (i=1;i<=n;i++) 
  {
    a=Read();
    q1.push((arr){a,i});
    q2.push((arr){-a,i});
    p1=q1.top();p2=q2.top();
    while (q1.top().x+q2.top().x>limit)
    {
      l++;
      while (!q1.empty()&&q1.top().id<l) q1.pop();
      while (!q2.empty()&&q2.top().id<l) q2.pop();
    }
    ans=max(ans,i-l+1);
  }

【BZOJ1856】直接上卡特兰数。但是YY大神说可以避免逆元,直接用中国剩余定理做。跪!

【BZOJ1875】刚开始看的时候:不是裸的矩阵乘法吗?但是发现不能重复走,于是就傻掉了。厚颜无耻的看了题解(难免要看的啊),发现可以重新构图。思路巧妙!

【BZOJ3175】原来真的有种东西叫做“黑白染色”。做这道题的时候,自然而然的想到,走马步肯定是黑格走到白格。于是就随便构图了(以下是代码)。

for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
      num[i][j]=++T;
  T++;S=0;cnt=1;
  for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
      if (map[i][j]=='0')
      {
        ans++;
        if ((i+j)&1) {add(num[i][j],T,1);continue;}
        add(S,num[i][j],1);
        for (d=0;d<8;d++)
        {
          x=i+dx[d];y=j+dy[d];
          if (x<1||x>n||y<1||y>n||map[x][y]=='1') continue;
          add(num[i][j],num[x][y],INF);
        }
      }
【BZOJ3152】这道题的主要难点是:题意不清。经过SYC大神不断的讲解,我才明白,大致如下:有一段数,你要添加几组括号(尽量的少)。首先,规定你必须添一组1..n的括号(最外层)。如果你在L--R外面添了一层括号,那么可以把L--R这些数看成一个数,他的权值就是原来第L个数字减少(R-L)。无论怎么操作,你必须保证所有数都是正整数。无解输出-1。题解是用堆的贪心。

【BZOJ1221】这道题搞了我很长时间。费用流的建图就是神奇。值得注意的是,毛巾可以这个月不洗,直接连到下个月去(我开始觉得也可以直接从当前的第K月连向第K+F+1,K+F+2...,F是间隔。但是显然时间效率很萎)

【BZOJ2749】真的很神奇。看了题解。把分解成1转化成分解成2。

【BZOJ2721】原来看到这道题的时候以为是数论神题,然后就跳过了。在翻Foreseeable大神的博客时偶然发现解法。1/x+1/y=1/z,设y=z+d,化简后得x=z^2/d+z。显然只要d能整除z^2即可。然后我们用分解质因数的方法做。

for (i=2;i<=n;i++)
  {
    if (!flag[i]) prime[++cnt]=i;
    for (j=1;j<=cnt&&prime[j]*i<=n;j++)
      flag[i*prime[j]]=1;
  }
  ans=1ll;
  for (i=1;i<=cnt;i++)
  {
    count=0;
    for (k=prime[i];k<=n;k*=prime[i])
      count+=n/k;
    ans=ans*(count*2ll+1ll)%P;
  }