Regional 2011, Asia - Kuala Lumpur 解题报告

发布时间:2014-10-22 14:18:59编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Regional 2011, Asia - Kuala Lumpur 解题报告",主要涉及到Regional 2011, Asia - Kuala Lumpur 解题报告方面的内容,对于Regional 2011, Asia - Kuala Lumpur 解题报告感兴趣的同学可以参考一下。

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做的了。 正解反正我不太会。。有待了解


上一篇:utu2440内核移植根文件移植配置nfs
下一篇:数字信号产生之对数正态分布的随机数

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款