题意：n*n网格中染色m个格子，染色格子的最长轮廓线

 

贪心

将格子分为4类

1、隔一个选一个，互不相邻的格子

2、4个角上的格子

3、边界除角的格子

4、内部的格子

 

4类从上到下依次选

1对答案有4的贡献

2对答案无贡献

3对答案有-2的贡献

4对答案有-4的贡献

 

对n奇偶分类讨论

当n为奇数时，在分左上角的格子在第1类还是第2类讨论

 

#include
     
      #include
      
       using namespace std;int main(){    freopen("data.txt","r",stdin);    freopen("my.txt","w",stdout);    long long ans1,ans2,n,sum,rest,now,tmp;    while(scanf("%lld%lld",&n,&sum)!=EOF)    {        if(!n) return 0;        if(n&1)        {            if(sum<=n*n>>1 || sum<=n*n/2+1)             {                printf("%lld\n",sum<<2);                continue;            }            if(sum<=n*n/2+4) ans1=n*n/2*4;            else            {                tmp=sum-4-n*n/2;                ans1=n*n/2<<2;                rest=n/2-1<<2;                if(tmp<=rest) ans1-=tmp<<1;                else                {                    ans1-=rest<<1;                    tmp-=rest;                    ans1-=tmp<<2;                }            }            ans2=n*n/2+1<<2;            now=n*n/2+1;            rest=n/2<<2;            if(sum-now<=rest) ans2-=sum-now<<1;            else            {                ans2-=rest<<1;                now+=rest;                ans2-=sum-now<<2;            }            printf("%lld\n",max(ans1,ans2));        }        else        {            if(sum<=n*n>>1)            {                printf("%lld\n",sum<<2);                continue;            }            if(sum<=n*n/2+2)            {                printf("%lld\n",n*n/2*4);                continue;            }            ans1=n*n>>1<<2;            tmp=sum-n*n/2-2;            rest=n/2-1<<2;            if(tmp<=rest) ans1-=tmp<<1;            else            {                ans1-=rest<<1;                tmp-=rest;                ans1-=tmp<<2;            }            printf("%lld\n",ans1);        }    }}
      
     

 

 

同一种思路大佬的写法就是短

#include
     
      #include
      
       using namespace std;typedef long long ll;ll l,n,a,b,c,ans;ll cal(){    if(n<=a) return n*4;    if(n<=a+b) return a*4;    if(n<=a+b+c) return a*4-(n-a-b)*2;    return a*4-c*2-(n-a-b-c)*4;}int main(){    freopen("data.txt","r",stdin);    freopen("std.txt","w",stdout);    while(cin>>l>>n,l||n)    {        if(l%2==0)        {            a=l*l/2;            b=2;            c=l/2-1<<2;            ans=cal();        }        else        {            a=l*l/2;            b=l==1 ? 1:4;            c=l==0 ? 0:(l-3)/2*4;            ans=cal();            a=l*l/2+1;            b=0;            c=(l-1)/2*4;            ans=max(ans,cal());        }        cout<
       
        <