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