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);
  }

【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);
        }
      }

【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;
  }

BZOJ 刷题记录 PART 2,布布扣,bubuko.com

BZOJ 刷题记录 PART 2

原文：http://blog.csdn.net/jiangshibiao/article/details/29587837