#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <ctime>
#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];
stack<char>optr;
stack<long long>opnd;
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 <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <ctime>
#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<int, int> P;
P p[MAXN];
vector<P>gx[MAXN], gy[MAXN];
vector<int>gh, gv;
typedef vector<int>::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;
}
