0

これを実装するための最良の方法（アプローチ）を知りたいです。座標（x、y）のセットが与えられます。
次に、 1.C ab =>のような座標に基づいてクエリが実行され ます。ここで、aとbは、座標の初期セットの整数インデックスです。したがって、インデックス範囲aからbにある、第1、第2、第3、および第4象限にあるポイントの数を出力する必要があります。


2.X ab =>ここで、aとbは、座標の初期セットの整数インデックスです。したがって、x軸に沿ってathからbthのインデックス付き座標をミラーリングする必要があります。


3.Y ab =>ここで、aとbは、座標の初期セットの整数インデックスです。したがって、y軸に沿ってathからbthのインデックス付き座標をミラーリングする必要があります。

最大で100000の座標またはポイントと、それらに対する500000のそのようなクエリが存在する可能性があります。

すべてのクエリでブルートフォースメソッドをループしてみましたが、TLE（Time Limit Exceeded）がありました。

そのようなタイプの質問ではどうすればよいですか？

これが私のコードです

#include <iostream>
#include <stdio.h>

using namespace std;

char flipX[4] = { 3, 2, 1, 0 };
char flipY[4] = { 1, 0, 3, 2 };

int main(int argc, char **argv)
{
    int n,x,y;
    char c[100000];
    scanf("%d",&n);
    //coord *c=new coord[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        scanf("%d",&y);
        if(x<0 && y<0)
            c[i]=2;
        else if(x>0 && y>0)
            c[i]=0;
        else if(x>0 && y<0)
            c[i]=3;
        else
            c[i]=1;
    }

    int q,i,j,a,cnt[4];
    char ch;
    scanf("%d",&q);
    while(q--)
    {
        //cout<<"q:"<<q<<endl;
        cin>>ch;
        scanf("%d",&i);
        scanf("%d",&j);
        i--;j--;
        if(ch=='X')
        {
            //case 'X':
                for(a=i;a<=j;a++)
                    c[a]=flipX[c[a]];
            //  break;
        }
        else if(ch=='Y')
        {
            //case 'Y':
                for(a=i;a<=j;a++)
                    c[a]=flipY[c[a]];
            //  break;
        }   
        else if(ch=='C')
        {
                cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
                for(a=i;a<=j;a++)
                {
                    cnt[c[a]]++;
                }
                printf("%d %d %d %d\n",cnt[0],cnt[1],cnt[2],cnt[3]);
        }
    }
    return 0;
}

助けてください。

4

2 に答える 2

1

nneonneoに同意します。

const size_t MAX_COORDS = 100000;
vector<char> quadrant( MAX_COORDS );

ここでquadrantは、値（0〜3）を維持します。条件なしで象限を反転するのは非常に簡単です。

char flipX[4] = { 2, 3, 0, 1 };
char flipY[4] = { 3, 2, 1, 0 };

vector<char>::iterator itLeft = quadrant.begin() + left;
vector<char>::iterator itRight = quadrant.begin() + right + 1;

for( vector<char>::iterator it = itLeft; it != itRight; it++ )
{
    *it = flipX[*it];
}

また、象限を数えるのも同様に簡単です。

unsigned int count[4] = {0};
for( vector<char>::iterator it = itLeft; it != itRight; it++ )
{
    count[*it]++;
}

それよりも高速にする必要がある場合は、動的計画法を採用し、すべてのポイントとすべての象限の象限数をメモ化する必要があります。これにより、O（1）範囲検索が可能になりますが、ミラーリング操作のコストが大幅に高くなります。範囲カウントがどのように機能するかを次に示します。

vector< vector<char> > counts( 4, vector<char>(MAX_COORDS) );

// ...

for( size_t i = 0; i < 4; i++ ) {
    count[i] = counts[i][right] - (left > 0 ? counts[i][left-1] : 0);
}
于 2012-09-27T03:18:27.543 に答える
0

Ok。怠惰なセグメントツリーがそのトリックを行いました。皆さんの助けに感謝します

于 2012-10-04T05:55:19.550 に答える