Regional 2011， Asia - Kuala Lumpur 答题报告
Regional 2011， Asia - Kuala Lumpur 解题报告
E.Social Holidaying
G.Writings on the Wall
H.Robotic Traceur
A.Smooth Visualization
不说了。大水题
B.Arnooks's Defensive Line
貌似judge挂了。数据结构吧。
最暴力的方法应该是二维树状数组。。不过要离散化
其他的方法没研究过
C.Equivalence
不多说。基本的四则运算表达式。
给参数赋随机值，判断是否相等。我跑了10遍。
#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;
}
D.Tree Inspections
刚开始看错题意。敲了一个小时。
然后发现错了之后换了方法就过了。
大意是一个在二维坐标系上有一些点。
一个人会沿一些直线巡视。
这些直线是平行于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;
}
E.Social Holidaying
题目大意就是给出A，B两个序列
然后从A中不重复的选出最多的二元组，使每个二元组的和都等于B中的某个元素值
一看数据范围。才400吧。可以用二分图搞一下。
加边的时候多加了一次。所以答案要除以二
朱老板写的。不贴代码了。
F.Orienteering
这题其实巨水。。
给出n个点(n <= 30) 在二维坐标系上，每个点都有一个价值。
有若干选手，每个选手都有一定的体力值，然后从原点出发，可以走任意循序任意个这些点，
问能回到原点取得的最大价值是多少。
注意，从一个点到另一个点消耗的体力就是其欧氏距离。 然后一个点的价值取过后就不能再去取了。
那么。
可以看到点很少。价值的话总和是6000。体力也不过1W而已
刚开始我想用dp[i][j]表示走到i剩余j体力能取到的最大价值。
但是发现体力会是浮点数
还好价值总和也比较小
那就用dp[i][j]表示走到i点取到j价值的最小体力好了
转移的时候。
因为题目说了要按序号是升序选。
所以转移就太简单了。。
dp[k][j + p[k].w] = min(dp[k][j + p[k].w] , dp[i][j] + dis(i, k))
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 100000005
#define MAXN 70000
using namespace std;
int n;
char name[555];
double dp[33][6666], d;
struct node
{
double x, y;
int w;
}p[33];
double getdis(int i, int j)
{
return sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
}
int main()
{
int cas = 0;
while(scanf("%d", &n) != EOF && n)
{
p[0].x = 0, p[0].y = 0;
for(int i = 1; i <= n; i++) scanf("%lf%lf%d", &p[i].x, &p[i].y, &p[i].w);
for(int i = 0; i <= n; i++)
for(int j = 0; j <= 6000; j++)
dp[i][j] = INF;
dp[0][0] = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= 6000; j++)
{
for(int k = i + 1; k <= n; k++)
dp[k][j + p[k].w] = min(dp[k][j + p[k].w], dp[i][j] + getdis(i, k));
}
printf("Race %d\n", ++cas);
while(true)
{
scanf("%s %lf", name, &d);
if(name[0] == '#') break;
int ans = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= 6000; j++)
if(getdis(i, 0) + dp[i][j] <= d)
ans = max(ans, j), printf(" %d %d\n", i, j);
printf("%s: %d\n", name, ans);
}
}
return 0;
}
G.Writings on the Wall
这题我竟然忘了KMP咋写了。
然后就用hash乱搞了一下。
大概就是用一个P进制的数表示一个串吧。
P是素数。
然后可能会有冲突。。不过竟然过了
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <ctime>
#define MAXN 100007
#define eps 1e-7
#define INF 1000000007
using namespace std;
char Str1[MAXN], Str2[MAXN];
long long h1[MAXN], h2[MAXN];
long long mod = INF;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%s%s", Str1, Str2);
int len1 = strlen(Str1);
int len2 = strlen(Str2);
long long now = 1;
h1[len1] = 0;
int ans = 0;
for(int i = len1 - 1; i >= 0; i--)
{
h1[i] = (h1[i + 1] + (long long)(Str1[i] - 'a') * now) % mod;
now = now * 101LL % mod;
}
for(int i = 0; i < len2; i++)
{
if(i == 0) h2[i] = Str2[i] - 'a';
else h2[i] = (h2[i - 1] * 101LL + (long long)(Str2[i] - 'a')) % mod;
if(len1 - 1 - i >= 0 && h2[i] == h1[len1 - 1 - i]) ans++;
}
printf("%d\n", ans + 1);
}
return 0;
}
H.Robotic Traceur
BFS或者SPFA 随便过吧。。
I.Shortest Leash
就不说某人用
random_shuffle做的了。
正解反正我不太会。。有待了解