程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> TC SRM 559 DIV1

TC SRM 559 DIV1

編輯:C++入門知識

果然沒有適妞,TC是要掉RP的,嗚嗚

開場不順啊,貌似TC arena出了一點問題,不能用有道,而且不能復制粘貼啥的,哭

250PT:

有個重要條件沒有看到啊,有木有,a!=b  2*max(a,b)<min(numRows,numColumns)

有了這個條件,判斷就簡單了有木有,只有可能是2,3,4,6,8

表示沒有看到條件,YY了好久啊,覺得討論太復雜了啊

然後就換了一種寫法

考慮8個方向,每個方向,都有一個區域的位置是可行的,得到8個矩陣,然後求矩陣交啊,TAT

魂淡啊,最後3min才交啊,不過還好PST


[cpp]
struct Node 

    int x1,x2,y1,y2; 
    Node(){} 
    Node(int _x1,int _y1,int _x2,int _y2):x1(_x1),y1(_y1),x2(_x2),y2(_y2){} 
}; 
class HyperKnight 

public: 
    int Bin(int num,int *a,int len) 
    { 
        int low=0,high=len-1,mid; 
        while(low<=high) 
        { 
            mid=(low+high)/2; 
            if(a[mid]==num) return mid; 
            if(a[mid]<num) low=mid+1; 
            else high=mid-1; 
        } 
    } 
    LL countCells(int a,int b,int numRows,int numColumns,int k) 
    { 
        int x[100],y[100],xcnt=0,ycnt=0; 
        if(k==0) return 0; 
        if(a<b) swap(a,b); 
        vector<Node>v;v.clear(); 
        if(numRows>b&&numColumns>a) 
        { 
            v.pb(Node(b+1,a+1,numRows+1,numColumns+1)); 
            x[xcnt++]=b+1;x[xcnt++]=numRows+1; 
            y[ycnt++]=a+1;y[ycnt++]=numColumns+1; 
            v.pb(Node(b+1,1,numRows+1,numColumns-a+1)); 
            x[xcnt++]=b+1;x[xcnt++]=numRows+1; 
            y[ycnt++]=1;y[ycnt++]=numColumns-a+1; 
            v.pb(Node(1,a+1,numRows-b+1,numColumns+1)); 
            x[xcnt++]=1;x[xcnt++]=numRows-b+1; 
            y[ycnt++]=a+1;y[ycnt++]=numColumns+1; 
            v.pb(Node(1,1,numRows-b+1,numColumns-a+1)); 
            x[xcnt++]=1;x[xcnt++]=numRows-b+1; 
            y[ycnt++]=1;y[ycnt++]=numColumns-a+1; 
        } 
        if(numRows>a&&numColumns>b) 
        { 
            v.pb(Node(a+1,b+1,numRows+1,numColumns+1)); 
            x[xcnt++]=a+1;x[xcnt++]=numRows+1; 
            y[ycnt++]=b+1;y[ycnt++]=numColumns+1; 
            v.pb(Node(a+1,1,numRows+1,numColumns-b+1)); 
            x[xcnt++]=a+1;x[xcnt++]=numRows+1; 
            y[ycnt++]=1;y[ycnt++]=numColumns-b+1; 
            v.pb(Node(1,b+1,numRows-a+1,numColumns+1)); 
            x[xcnt++]=1;x[xcnt++]=numRows-a+1; 
            y[ycnt++]=b+1;y[ycnt++]=numColumns+1; 
            v.pb(Node(1,1,numRows-a+1,numColumns-b+1)); 
            x[xcnt++]=1;x[xcnt++]=numRows-a+1; 
            y[ycnt++]=1;y[ycnt++]=numColumns-b+1; 
        } 
        sort(x,x+xcnt);sort(y,y+ycnt); 
        xcnt=unique(x,x+xcnt)-x; 
        ycnt=unique(y,y+ycnt)-y; 
        int cnt[100][100];mem(cnt,0); 
        for(int i=0;i<v.size();i++) 
        { 
            int l=Bin(v[i].x1,x,xcnt),r=Bin(v[i].x2,x,xcnt)-1; 
            int u=Bin(v[i].y1,y,ycnt),d=Bin(v[i].y2,y,ycnt)-1; 
            for(int p=l;p<=r;p++) for(int j=u;j<=d;j++) cnt[p][j]++; 
        } 
        LL ans=0; 
        for(int i=0;i<xcnt;i++) 
        { 
            for(int j=0;j<ycnt;j++) 
            { 
                if(cnt[i][j]==k) 
                { 
                    ans+=(LL)(x[i+1]-x[i])*(LL)(y[j+1]-y[j]); 
                 //   cout<<x[i]<<" "<<x[i+1]-1<<" "<<y[j]<<" "<<y[i+1]-1<<endl;  
                } 
            } 
        } 
        return ans; 
    } 
}; 

struct Node
{
    int x1,x2,y1,y2;
    Node(){}
    Node(int _x1,int _y1,int _x2,int _y2):x1(_x1),y1(_y1),x2(_x2),y2(_y2){}
};
class HyperKnight
{
public:
    int Bin(int num,int *a,int len)
    {
        int low=0,high=len-1,mid;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(a[mid]==num) return mid;
            if(a[mid]<num) low=mid+1;
            else high=mid-1;
        }
    }
    LL countCells(int a,int b,int numRows,int numColumns,int k)
    {
        int x[100],y[100],xcnt=0,ycnt=0;
        if(k==0) return 0;
        if(a<b) swap(a,b);
        vector<Node>v;v.clear();
        if(numRows>b&&numColumns>a)
        {
            v.pb(Node(b+1,a+1,numRows+1,numColumns+1));
            x[xcnt++]=b+1;x[xcnt++]=numRows+1;
            y[ycnt++]=a+1;y[ycnt++]=numColumns+1;
            v.pb(Node(b+1,1,numRows+1,numColumns-a+1));
            x[xcnt++]=b+1;x[xcnt++]=numRows+1;
            y[ycnt++]=1;y[ycnt++]=numColumns-a+1;
            v.pb(Node(1,a+1,numRows-b+1,numColumns+1));
            x[xcnt++]=1;x[xcnt++]=numRows-b+1;
            y[ycnt++]=a+1;y[ycnt++]=numColumns+1;
            v.pb(Node(1,1,numRows-b+1,numColumns-a+1));
            x[xcnt++]=1;x[xcnt++]=numRows-b+1;
            y[ycnt++]=1;y[ycnt++]=numColumns-a+1;
        }
        if(numRows>a&&numColumns>b)
        {
            v.pb(Node(a+1,b+1,numRows+1,numColumns+1));
            x[xcnt++]=a+1;x[xcnt++]=numRows+1;
            y[ycnt++]=b+1;y[ycnt++]=numColumns+1;
            v.pb(Node(a+1,1,numRows+1,numColumns-b+1));
            x[xcnt++]=a+1;x[xcnt++]=numRows+1;
            y[ycnt++]=1;y[ycnt++]=numColumns-b+1;
            v.pb(Node(1,b+1,numRows-a+1,numColumns+1));
            x[xcnt++]=1;x[xcnt++]=numRows-a+1;
            y[ycnt++]=b+1;y[ycnt++]=numColumns+1;
            v.pb(Node(1,1,numRows-a+1,numColumns-b+1));
            x[xcnt++]=1;x[xcnt++]=numRows-a+1;
            y[ycnt++]=1;y[ycnt++]=numColumns-b+1;
        }
        sort(x,x+xcnt);sort(y,y+ycnt);
        xcnt=unique(x,x+xcnt)-x;
        ycnt=unique(y,y+ycnt)-y;
        int cnt[100][100];mem(cnt,0);
        for(int i=0;i<v.size();i++)
        {
            int l=Bin(v[i].x1,x,xcnt),r=Bin(v[i].x2,x,xcnt)-1;
            int u=Bin(v[i].y1,y,ycnt),d=Bin(v[i].y2,y,ycnt)-1;
            for(int p=l;p<=r;p++) for(int j=u;j<=d;j++) cnt[p][j]++;
        }
        LL ans=0;
        for(int i=0;i<xcnt;i++)
        {
            for(int j=0;j<ycnt;j++)
            {
                if(cnt[i][j]==k)
                {
                    ans+=(LL)(x[i+1]-x[i])*(LL)(y[j+1]-y[j]);
                 //   cout<<x[i]<<" "<<x[i+1]-1<<" "<<y[j]<<" "<<y[i+1]-1<<endl;
                }
            }
        }
        return ans;
    }
};

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved