csu2146 神奇的金字塔（寻找通项）-白红宇

csu2146 神奇的金字塔（寻找通项）

阅读量：6173 次

发布时间：2019-06-21

本文共 1493 字，大约阅读时间需要 4 分钟。

总所周知，CSU没有金字塔，但在世界某地有一座神奇的金字塔。

神奇的金字塔位于N*N的网格地上。

第0分钟时，金字塔底面很小，只占据(x,y) 这个格子，之后每过一分钟，金字塔会长大，就算超过边界也会继续长大，不过边界外是无限深渊，所以超过边界的部分不算占据的面积，而且由于是无限深渊，不需要考虑什么时候被填满的问题。

那么现在问题来了，至少在第几分钟网格上才至少有C个格子被金字塔占据。

Input

每组数据每一行有4个整数，N,X,Y,C

哇，这题我居然卡了半天，菜哭。就是简单的找出通项然后找到符合条件的最短时间即可。至于如何找通项。我们一开始考虑无边界的情况，每秒的增长就是4t，利用求和公式就可得到1+2*t(t+1).这时由于存在边界，所以还需要把超出边界的增长减去，再加上减重复的。具体见图

黑色为第一秒的水，红色为第三秒。如无边界则此时水的格数就是13.

此时需要减去的是下图所示中的两个三角形

每个三角型的大小均是他们的高的平方，这里也就是4+4

但是可以看到这里实际上是减多了的

因此还需要加上重叠那一块的面积。这里就是1.

所以此时的水覆盖格数就是13-4-4+1=6

考虑到大三角重叠产生的小三角形比较难计算，这里来具体说明一下。

这就是一个起始点位于（x,y）的水源在边长为n的界中第t秒的扩张情况

这时各边的长度是

那么需要减去的两个大三角型的面积，这里就是(2-x+t)^2+(y+t-n+1)^2

再补上重叠的面积即是(y-x+t+1-n)*(y-x+t+2-n)/2

好了具体实现还是看代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              using namespace std;typedef long long LL;int n,x,y;long long le(int t){ long long ans=0; LL a=0,b=0,c=0,d=0; if(x-t<=1)//上 { a=(2-(x-t)); ans+=a*a; } if(x+t>=n)//下 { b=(x+t+1-n);ans+=b*b; } if(y-t<=1)//左 { c=(1-(y-t))+1;ans+=c*c; } if(y+t>=n)//右 { d=(y+t-n)+1;ans+=d*d; } LL e=0,f=0,g=0,h=0; if(a>y&&c>x) e=min(a-y,c-x); if(a>(n-y)+1&&d>x) f=min(a-(n+1-y),d-x); if(b>y&&c>(n-x)+1) g=min(b-y,c-(n+1-x)); if(b>(n-y)+1&&d>(n-x)+1)h=min(b-(n+1-y),d-(n+1-x)); //cout<<<' '<<<' '<
                 
                  <<' '<
                  
                   <<' '<
                   
                    <<' '<
                    
                     <<' '<
                     
                      <<' '<
                      
                       <
                       
                        >n>>x>>y>>c) { long long t=1; dp[1]=1; if(c==1) { cout<<'0'<

转载于:https://www.cnblogs.com/fly-white/p/10092783.html

你可能感兴趣的文章