被黄大队坑了。。。。过了三题。自己过了两个，还有一个最水的给了黄大队过了。比赛实在不能忍，黄大队这场比的态度太低了。。还有些题带回补上。
1002
这题trick太多，就是求最大速度的点是否可达到无限区域。
- 重点情况
- 包围的情况，求凸包，记住凸包包含重点
- 最大速度为0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 | /************************************************************************* > File Name: 1002.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月14日 星期四 13时00分56秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 #define X first #define Y second #define MAXN 505 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} int n, x, y, v, ans[MAXN], Cas = 1, len; vector < pair< pair<int, int>, int > > vec; map < pair<int, int>, int > ma; struct Point { int x, y, pos; Point() {} Point(int _x, int _y, int _p):x(_x), y(_y), pos(_p) {} } p[MAXN], bag[MAXN]; void init() { vec.clear(); ma.clear(); memset(ans, 0, sizeof(ans)); memset(p, 0, sizeof(p)); memset(bag, 0, sizeof(bag)); len = 0; } int compare(const void *t1, const void *t2) { Point *p1 = (Point*)t1; Point *p2 = (Point*)t2; if (p1->y == p2->y) return p1->x - p2->x; return p1->y - p2->y; } int xmult(Point p1, Point p2, Point p0) { return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } int make_bag(Point *p, Point *bag, int n) { int i, j; qsort(p, n, sizeof(Point), compare); bag[0] = p[0]; int len = 1; for (i = 1; i < n; i ++) { while (len >= 2 && xmult(bag[len-2], bag[len-1], p[i]) <= 0) len --; bag[len ++] = p[i]; } j = len + 1; for (i = n - 2; i >= 0; i --) { while (len >= j && xmult(bag[len-2], bag[len-1], p[i]) <= 0) len --; bag[len ++] = p[i]; } len --; return len; } void work() { printf("Case #%d: ", Cas ++); int Ma = 0; init(); for (int i = 1; i <= n; i ++) { scanf("%d %d %d", &x, &y, &v); Ma = Max(Ma, v); vec.pb(mp(mp(x, y), v)); } for (int i = 0; i < n; i ++) { if (vec[i].Y == Ma) { if (ma.find(vec[i].X) == ma.end()) { ma.insert(mp(vec[i].X, 1)); } else { ma[vec[i].X] ++; } } } if (Ma == 0) { for (int i = 1; i <= n; i ++) { printf("0"); } printf("\n"); return ; } for (int i = 0; i < n; i ++) { if (vec[i].Y < Ma) { ans[i + 1] = 1; } else { if (ma[vec[i].X] > 1) { ans[i + 1] = 1; } p[len ++] = Point(vec[i].X.X, vec[i].X.Y, i + 1); } } if (len <= 2) { for (int i = 1; i <= n; i ++) { printf("%d", !ans[i]); } printf("\n"); return; } int lbag = make_bag(p, bag, len); for (int i = 0; i < len; i ++) { int flag = 0; for (int j = 0; j < lbag; j ++) { if (p[i].x == bag[j].x && p[i].y == bag[j].y) { flag = 1; break; } else { if (xmult(bag[j], bag[(j+1) % lbag], p[i]) == 0) { flag = 1; break; } } } if (!flag) { ans[p[i].pos] = 1; } } for (int i = 1; i <= n; i ++) { printf("%d", !ans[i]); } printf("\n"); } int main() { //freopen("in", "r", stdin); while (scanf("%d", &n) != EOF) { if (n == 0) break; work(); } return 0; } |
1006
水题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | /************************************************************************* > File Name: 1006.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月14日 星期四 17时29分32秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} LL h, a, b, k; int Cas = 1; void work() { printf("Case #%d: ", Cas ++); if (h <= a) { printf("YES\n"); return ; } else { if (b >= a) { printf("NO\n"); return ; } else { if ((h - a) / (a - b) < k) { printf("YES\n"); return ; } LL c = (a - b) * k - b; if (c > 0) { printf("YES\n"); } else { printf("NO\n"); } } } } int main() { while (cin >> h >> a >> b >> k) { if (h == 0 && a == 0 && b == 0 && k == 0) break; work(); } return 0; } |
1008
晕，这道题黄大队想了2个多小时，等我过了1002，还没有想出来。思路就是枚举到当前一项 
的
时，复杂度为
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | /************************************************************************* > File Name: 1008.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年08月14日 星期四 14时13分27秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} LL x, k; int Cas = 1, pos; void work() { printf("Case #%d: ", Cas ++); for (int i = 1; i <= 100; i ++) { if (x % i) { pos = i; break; } } if (k < pos) { cout << x << endl; return ; } else { for (int i = 2; i <= k; i ++) { LL d1 = x / (i - 1); if (d1 < i) { LL ans = k * d1; cout << ans << endl; return ; } else { if (x % i) { x = i * (x / i + 1); } else { x = i * (x / i); } } } cout << x << endl; } } int main() { while (cin >> x >> k) { if (x == 0 && k == 0) break; work(); } return 0; } |