首页 > 代码库 > FOJ有奖月赛-2016年8月（daxia专场之过四题方有奖）
FOJ有奖月赛-2016年8月（daxia专场之过四题方有奖）
6/7
这里简单写个题解，由于源代码无法查看，所以过了的题目的代码就不贴了。。。。
题A Problem A Daxia & Wzc‘s problem
题意：略
题解：这个东西显然推公式，最后推得的一个组合数学的公式与第一项和公差有关（具体公式隔太久不记得了，囧）。然后注意到这个m只有一千，虽然这个i很大，但是C（a，b）的运算次数显然是由a和b较小的一个决定，所以可以优化到算一个组合数的复杂度是min（m，i）。
题B Problem B Daxia & Yayamao‘s problem
题意：略
题解：这是一个斜率相关问题，比赛的时候没有做出来，然而赛后的也推了超久的（人太渣没办法），我是参考NOI2007的一道题：cash来学的里面的斜率相关问题。这里简单地解释一下：求的是y = a * x + b，（所有的（a，b）已知），变形一下得：b = -x * a + y，这是一条直线，（a，b）是已知的点，给定-x为斜率，求一个最大的斜率，画图可以发现所有有效的点形成一个“上凸包”，只有凸包上的点才是“候选点”，也就是给定一个斜率，我们可以找到最接近的斜率上面的一个点就是答案。这个过程有两种做法，第一种是二分，第二种是三分。二分是二分斜率，然后查找最接近的大于-x的斜率，三分是三分点，把每个点带入对于每个x一定是形成二次函数的样子。两者都可以，要说优劣，只能说三分比较好些，直接求一个凸包，然后三分一下就可以了，二分可能还有误差问题。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set>10 #include <map>11 #include <iostream>12 #include <algorithm>13 using namespace std;14 15 #define lson l, m, rt*216 #define rson m + 1, r, rt*2+117 #define xx first18 #define yy second19 20 typedef pair<int,int> pii;21 typedef long long LL;22 typedef unsigned long long ULL;23 24 const int N = 1e5 + 10, inf = 1 << 30;25 26 struct Point {27 LL a, b;28 Point(){}29 Point(LL a, LL b) : a(a), b(b) {}30 bool operator < (const Point& o) const {31 return a < o.a || (a == o.a && b < o.b);32 }33 Point operator - (const Point& o) const {34 return Point(a - o.a, b - o.b);35 }36 Point operator + (const Point& o) const {37 return Point(a + o.a, b + o.b);38 }39 } P[N], ch[N];40 41 LL cross(Point A, Point B) {42 return A.a * B.b - A.b * B.a;43 }44 45 int convex(Point *P, int n, Point *ch) {46 sort(P, P + n);47 int m = 0;48 for (int i = 0; i < n; i++) {49 while (m > 1 && cross(P[i] - ch[m - 2], ch[m - 1] - ch[m - 2]) <= 0) m--;50 ch[m++] = P[i];51 }52 return m;53 }54 55 struct Node {56 int x, id;57 Node(int x=0, int id=0) : x(x), id(id) {}58 } line[N];59 60 LL get(Point A, Point B) {61 double x = 1.0 * (A.b - B.b) / (A.a - B.a);62 return (LL)ceil(x);63 }64 65 bool cmp(Node A, Node B) {66 return A.x < B.x;67 }68 69 int main() {70 // freopen("case.in", "r", stdin);71 int n, m;72 while (~scanf("%d%d", &n, &m)) {73 for (int i = 0; i < n; i++) scanf("%I64d%I64d", &P[i].a, &P[i].b);74 int nn = convex(P, n, ch);75 // for (int i = 0; i < nn; i++) cout << ch[i].a << ‘ ‘ << ch[i].b << endl;76 int cnt = 0;77 for (int i = nn - 1; i >= 0; i--) {78 if (i == nn - 1) line[cnt++] = Node(-inf, i);79 else line[cnt++] = Node(get(ch[i], ch[i + 1]), i);80 }81 // sort(line, line + nn, cmp);82 for (int i = 0; i < nn; i++) {83 // cout << line[i].x << ‘ ‘ << line[i].id << endl;84 }85 for (int i = 0; i < m; i++) {86 LL x;87 scanf("%I64d", &x);88 int p = upper_bound(line, line + nn, Node(-x, 0), cmp) - line - 1;89 // cout << line[p].id << endl;90 printf("%I64d\n", ch[line[p].id].a * x + ch[line[p].id].b);91 }92 }93 return 0;94 }
/*zhen hao*/#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <vector>#include <string>#include <stack>#include <set>#include <map>#include <iostream>#include <algorithm>using namespace std;#define lson l, m, rt*2#define rson m + 1, r, rt*2+1#define xx first#define yy secondtypedef pair<int,int> pii;typedef long long LL;typedef unsigned long long ULL;const int N = 1e5 + 10, inf = 1 << 30;struct Point { LL a, b; Point(){} Point(LL a, LL b) : a(a), b(b) {} bool operator < (const Point& o) const { return a < o.a || (a == o.a && b < o.b); } Point operator - (const Point& o) const { return Point(a - o.a, b - o.b); } Point operator + (const Point& o) const { return Point(a + o.a, b + o.b); }} P[N], ch[N];LL cross(Point A, Point B) { return A.a * B.b - A.b * B.a;}int convex(Point *P, int n, Point *ch) { sort(P, P + n); int m = 0; for (int i = 0; i < n; i++) { while (m > 1 && cross(P[i] - ch[m - 2], ch[m - 1] - ch[m - 2]) <= 0) m--; ch[m++] = P[i]; } return m;}struct Node { int x, id; Node(int x=0, int id=0) : x(x), id(id) {}} line[N];LL get(Point A, Point B) { double x = 1.0 * (A.b - B.b) / (A.a - B.a); return (LL)ceil(x);}bool cmp(Node A, Node B) { return A.x < B.x;}LL cal(Point A, LL x) { return A.a * x + A.b;}int main() {// freopen("case.in", "r", stdin); int n, m; while (~scanf("%d%d", &n, &m)) { for (int i = 0; i < n; i++) scanf("%I64d%I64d", &P[i].a, &P[i].b); int nn = convex(P, n, ch); for (int i = 0; i < m; i++) { LL x; scanf("%I64d", &x); int L = 0, R = nn - 1; while (R - L > 2) { int m1 = L + (R - L) / 3; int m2 = R - (R - L) / 3; if (cal(ch[m1], x) < cal(ch[m2], x)) L = m1; else R = m2;// cout << L << ‘ ‘ << R << endl; } LL ans = -(1LL << 60); for (int i = L; i <= R; i++) ans = max(ans, cal(ch[i], x)); printf("%I64d\n", ans); } } return 0;}
题C Problem C Daxia & Suneast‘s problem
题意：略
题解：首先要知道这个SG的规律，白书原题，也可以自己暴力打表发现。然后就是用线段树维护每个点的SG值，区间查询，单点更新即可，实际上是一道水题╮(╯▽╰)╭。
题D Problem D Daxia like YuGiOh
题意：略
题解：没做出来，也没看题，感觉有点难就搁到了现在。。。。
题E Problem E Daxia like acute triangle
题意：略
题解：对于一个圆，先从0度到360度按照逆时针编个号，然后排完序之后对于每个点考虑半圆，从半圆上任意选两个点，方案数为C（n，2），然后一直做到最后一个点就是钝角和直角三角形的数量，最后用C（n，3）减去即可。是道水题，然后比赛的时候脑抽了，整个队在纠结题意。。。。。。
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 #define lson l, m, rt*2 8 #define rson m + 1, r, rt*2+1 9 #define xx first10 #define yy second11 12 typedef pair<int,int> pii;13 typedef long long ll;14 typedef unsigned long long ull;15 16 char s[10];17 int n, r;18 19 int get_id(int x, int y) {20 if (x == r || (x > 0 && y > 0)) return r - x;21 else if (x <= 0 && y > 0) return r - x;22 else if (x < 0 && y <= 0) return 2 * r + r + x;23 else return 3 * r + x;24 }25 26 const int N = 4e4 + 10;27 28 int id[N];29 30 int main() {31 // freopen("case.in", "r", stdin);32 while (~scanf("%d%d", &n, &r)) {33 for (int i = 0; i < n; i++) {34 int x, y;35 scanf("%d%s", &x, s);36 if (x == r || x == -r) y = 0;37 else if (s[1] == ‘>‘) y = 1;38 else y = -1;39 id[i] = get_id(x, y);40 // cout << id[i] << endl;41 }42 sort(id, id + n);43 for (int i = 0; i < n; i++) id[i + n] = id[i] + 4 * r;44 ll res = 1LL * n * (n - 1) * (n - 2) / 6;45 for (int i = 0; i < n; i++) {46 int p = lower_bound(id, id + n * 2, id[i] + 2 * r) - id;47 if (id[p] == id[i] + 2 * r) p++;48 ll len = p - i - 1;49 res -= len * (len - 1) / 2;50 }51 cout << res << endl;52 }53 return 0;54 }
题F Problem F Daxia like uber
题意：略
题解：好像是最短路dij+枚举，队友秒的。
题G Problem G Daxia want to buy house
题意：略
题解：模拟题，读懂题意之后好像要利用指数的特点来优化误差，我语文不行，应该做不出这道题，又是队友秒了。
FOJ有奖月赛-2016年8月（daxia专场之过四题方有奖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。