Regional 2011， Asia - Kuala Lumpur 解题报告 - c++编程基础

TOP

Regional 2011， Asia - Kuala Lumpur 解题报告

2014-11-23 21:46:35 来源: 作者: 【大中小】浏览:8次

Tags：Regional 2011 Asia Kuala Lumpur 解题报告

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAXN 111111
#define eps 1e-7
#define INF 1000000007
using namespace std;
char str1[555], str2[555];
char s1[555], s2[555];
int nei[333], wai[333];
int len;
int nm[33];
stackoptr;
stackopnd;
bool flag;
long long calculate(long long x, long long y, char c)
{
    switch(c)
    {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '^':
        long long tmp = 1;
        for(int i = 0; i < y; i++) tmp *= x;
        return tmp;
    }
}
char cmp(char a, char b)
{
    if(nei[a] > wai[b]) return '>';
    else if(nei[a] == wai[b]) return '=';
    return '<';
}
long long gao(char *s)
{
    int i = 0;
    long long num;
    while(s[i] != '#' || optr.top() != '#')
    {
        num = 0;
        if(!flag) return -1;
        if(s[i] >= '0' && s[i] <= '9')
        {
            while(s[i] >= '0' && s[i] <= '9')
            {
                num *= 10;
                num += s[i] - '0';
                i++;
            }
            opnd.push(num);
        }
        else if(s[i] >= 'a' && s[i] <= 'z')
        {
            opnd.push(nm[s[i] - 'a']);
            i++;
        }
        else
        {
            switch(cmp(optr.top(), s[i]))
            {
                case '<' : optr.push(s[i]); i++; break;
                case '=' : optr.pop(); i++; break;
                case '>' :
                if(opnd.empty())
                {
                    flag = false;
                    return -1;
                }
                long long ta = opnd.top();
                opnd.pop();
                if(opnd.empty())
                {
                    flag = false;
                    return -1;
                }
                long long tb = opnd.top();
                opnd.pop();
                opnd.push(calculate(tb, ta, optr.top()));
                optr.pop();
                break;
            }
        }
    }
    return opnd.top();
}
void init()
{
    while(!opnd.empty()) opnd.pop();
    while(!optr.empty()) optr.pop();
    optr.push('#');
}
int main()
{
    nei['+'] = 2; wai['+'] = 1;
    nei['-'] = 2; wai['-'] = 1;
    nei['*'] = 4; wai['*'] = 3;
    nei['^'] = 6; wai['^'] = 5;
    nei[')'] = 8; wai[')'] = 0;
    nei['('] = 0; wai['('] = 8;
    nei['#'] = -1; wai['#'] = -1;
    int T;
    scanf("%d", &T);
    getchar();
    srand(time(0));
    while(T--)
    {
        gets(str1);
        len = 0;
        for(int i = 0; str1[i]; i++)
            if(str1[i] != ' ') s1[len++] = str1[i];
        s1[len++] = '#';
        s1[len] = '\0';
        gets(str2);
        len = 0;
        for(int i = 0; str2[i]; i++)
            if(str2[i] != ' ') s2[len++] = str2[i];
        s2[len++] = '#';
        s2[len] = '\0';
        flag = 1;
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 26; j++) nm[j] = labs(rand()) % 100;
            init();
            long long t1 = gao(s1);
            init();
            long long t2 = gao(s2);
            //printf("%lld %lld\n", t1, t2);
            if(t1 != t2)
            {
                flag = 0;
                break;
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

刚开始看错题意。敲了一个小时。

然后发现错了之后换了方法就过了。

大意是一个在二维坐标系上有一些点。

一个人会沿一些直线巡视。

这些直线是平行于X或Y轴的

然后首先这条线上的点他能看见。

他在线上走的时候也会左右瞅。当然看的视线是垂直于行走方向的

然后如果一个点在一个点后边。他是看不到的。因为被挡住了

最后问的是

是否看到了所有点中60%的点

那么我的思路是：

离散化是肯定的

首先从左到右，看每个x坐标，将其所有y坐标塞进一个vector里，并先按y排序

然后把所有走的路线中的水平线坐标塞进一个vector里

然后遍历该x对应的vector中的y坐标。

在水平线那个vector里lower_bound找其附近的两条水平线

看是否被其他点给挡住了。

这样的话就可以了。同理看每个y坐标

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAXN 211111
#define eps 1e-7
#define INF 1000000007
using namespace std;
int n, m;
int xx[MAXN], yy[MAXN];
int ok[MAXN];
typedef pair P;
P p[MAXN];
vectorgx[MAXN], gy[MAXN];
vectorgh, gv;
typedef vector::iterator Iter;
char op[5];
int main()
{
    int T, cc;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < MAXN; i++) gx[i].clear(), gy[i].clear();
        memset(ok, 0, sizeof(ok));
        gh.clear();
        gv.clear();
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", &p[i].first, &p[i].second);
            xx[i] = p[i].first;
            yy[i] = p[i].second;
        }
        sort(xx, xx + n);
        sort(yy, yy + n);
        int nx = unique(xx, xx + n) - xx;
        int ny = unique(yy, yy + n) - yy;
        for(int i = 0; i < n; i++)
        {
            int px = lower_bound(xx, xx + nx, p[i].first) - xx;
            int py = lower_bound(yy, yy + ny, p[i].second) - yy;
            gx[px].push_back(make_pair(p[i].second, i));
            gy[py].push_back(make_pair(p[i].first, i));
        }
        for(int i = 0; i < nx; i++) sort(gx[i].begin(), gx[i].end());
        for(int i = 0; i < ny; i++) sort(gy[i].begin(), gy[i].end());
        for(int i = 0; i < m; i++)
        {
            scanf("%s%d", op, &cc);
            if(op[0] == 'H') gh.push_back(cc);
            else gv.push_back(cc);
        }
        sort(gh.begin(), gh.end());
        sort(gv.begin(), gv.end());
        unique(gh.begin(), gh.end());
        unique(gv.begin(), gv.end());
        for(int i = 0; i < nx; i++)
        {
            int sz = gx[i].size();
            for(int j = 0; j < sz; j++)
            {
                int ty = gx[i][j].first;
                int id = gx[i][j].second;
                Iter it = lower_bound(gh.begin(), gh.end(), ty);
                if(it != gh.end())
                {
                    if(*it == ty) ok[id] = 1;
                    if(*it > ty)
                    {
                        if(j + 1 < sz)
                        {
                            if(*it <= gx[i][j + 1].first) ok[id] = 1;
                        }
                        else ok[id] = 1;
                    }
                }
                if(it != gh.begin())
                {
                    it--;
                    if(j > 0)
                    {
                        if(*it >= gx[i][j - 1].first) ok[id] = 1;
                    }
                    else ok[id] = 1;
                }
            }
        }
        for(int i = 0; i < ny; i++)
        {
            int sz = gy[i].size();
            for(int j = 0; j < sz; j++)
            {
                int tx = gy[i][j].first;
                int id = gy[i][j].second;
                Iter it = lower_bound(gv.begin(), gv.end(), tx);
                if(it != gv.end())
                {
                    if(*it == tx) ok[id] = 1;
                    if(*it > tx && j + 1 < sz && *it <= gy[i][j + 1].first)
                    ok[id] = 1;
                }
                if(it != gv.begin())
                {
                    it--;
                    if(j > 0 && *it >= gy[i][j - 1].first) ok[id] = 1;
                }
            }
        }
        int cnt = 0;
        for(int i = 0; i < n; i++)
            if(ok[i]) cnt++;
        //printf("%d\n", cnt);
        if((double)cnt / (double)n >= 0.6) puts("PASSED");
        else puts("FAILED");
    }
    return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：排列	下一篇：C++中的引用和移动语义

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: