WF 2019

佚名 6年前 (2019-05-07) 随笔 1243人围观抢沙发百度已收录

A

把价格相同的瓷砖分为一类然后按序贪心匹配，注意要用小的集合匹配大的集合。

  1 #include <bits/stdc++.h>
  2 
  3 #define IL __inline__ __attribute__((always_inline))
  4 
  5 #define For(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++ i)
  6 #define FOR(i, a, b) for (int i = (a), i##end = (b); i < i##end; ++ i)
  7 #define Rep(i, a, b) for (int i = (a), i##end = (b); i >= i##end; -- i)
  8 #define REP(i, a, b) for (int i = (a) - 1, i##end = (b); i >= i##end; -- i)
  9 
 10 typedef long long LL;
 11 
 12 template <class T>
 13 IL bool chkmax(T &a, const T &b) {
 14   return a < b ? ((a = b), 1) : 0;
 15 }
 16 
 17 template <class T>
 18 IL bool chkmin(T &a, const T &b) {
 19   return a > b ? ((a = b), 1) : 0;
 20 }
 21 
 22 template <class T>
 23 IL T mymax(const T &a, const T &b) {
 24   return a > b ? a : b;
 25 }
 26 
 27 template <class T>
 28 IL T mymin(const T &a, const T &b) {
 29   return a < b ? a : b;
 30 }
 31 
 32 template <class T>
 33 IL T myabs(const T &a) {
 34   return a > 0 ? a : -a;
 35 }
 36 
 37 const int INF = 0X3F3F3F3F;
 38 const double EPS = 1E-8, PI = acos(-1.0);
 39 
 40 #define DEBUG(...) fprintf(stderr, __VA_ARGS__)
 41 #define OK DEBUG("Passing [%s] in LINE %d...\n", __FUNCTION__, __LINE__)
 42 
 43 const int MAXN = 500000 + 5;
 44 
 45 struct Item {
 46   int h, val, idx;
 47 
 48   friend bool operator<(const Item &a, const Item &b) {
 49     return a.h == b.h ? a.idx < b.idx : a.h < b.h;
 50   }
 51 } a[MAXN], b[MAXN];
 52 
 53 std::pair<int, int> answer[MAXN];
 54 
 55 IL void GG() {
 56   puts("impossible");
 57   exit(0);
 58 }
 59 
 60 int main() {
 61   int n;
 62   scanf("%d", &n);
 63   For(i, 1, n) {
 64     a[i].idx = b[i].idx = i;
 65   }
 66   auto comp = [](const Item &a, const Item &b) {
 67     return a.val < b.val;
 68   };
 69   For(i, 1, n) {
 70     scanf("%d", &b[i].val);
 71   }
 72   For(i, 1, n) {
 73     scanf("%d", &b[i].h);
 74   }
 75   std::sort(b + 1, b + n + 1, comp);
 76   For(i, 1, n) {
 77     scanf("%d", &a[i].val);
 78   }
 79   For(i, 1, n) {
 80     scanf("%d", &a[i].h);
 81   }
 82   std::sort(a + 1, a + n + 1, comp);
 83   std::set<Item> x, y;
 84   int cur_x = 1, cur_y = 1;
 85   For(i, 1, n) {
 86     if (x.empty()) {
 87       int cost = a[cur_x].val;
 88       for (; a[cur_x].val == cost; x.insert(a[cur_x ++]));
 89     }
 90     if (y.empty()) {
 91       int cost = b[cur_y].val;
 92       for (; b[cur_y].val == cost; y.insert(b[cur_y ++]));
 93     }
 94     if (x.size() <= y.size()) {
 95       auto dx = x.begin(), dy = y.upper_bound({dx->h, dx->val, INF});
 96       if (dy == y.end()) {
 97         GG();
 98       }
 99       answer[i] = {dx->idx, dy->idx};
100       x.erase(dx), y.erase(dy);
101     } else {
102       auto dy = y.begin(), dx = x.lower_bound({dy->h, dy->val, 0});
103       if (dx == x.begin()) {
104         GG();
105       }
106       -- dx;
107       answer[i] = {dx->idx, dy->idx};
108       x.erase(dx), y.erase(dy);
109     }
110   }
111   For(i, 1, n) {
112     printf("%d ", answer[i].second);
113   }
114   puts("");
115   For(i, 1, n) {
116     printf("%d ", answer[i].first);
117   }
118   puts("");
119   return 0;
120 }

View Code

B

把半圆剖成两半，对每个点求出左半圆和右半圆最远能到什么地方，这样就可以$O(1)$判断一个拱形是否合法，然后$O(n^2)\text{dp}$即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 #include <bits/stdc++.h>
 2 
 3 #define IL __inline__ __attribute__((always_inline))
 4 
 5 #define For(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++ i)
 6 #define FOR(i, a, b) for (int i = (a), i##end = (b); i < i##end; ++ i)
 7 #define Rep(i, a, b) for (int i = (a), i##end = (b); i >= i##end; -- i)
 8 #define REP(i, a, b) for (int i = (a) - 1, i##end = (b); i >= i##end; -- i)
 9 
10 typedef long long LL;
11 
12 template <class T>
13 IL bool chkmax(T &a, const T &b) {
14   return a < b ? ((a = b), 1) : 0;
15 }
16 
17 template <class T>
18 IL bool chkmin(T &a, const T &b) {
19   return a > b ? ((a = b), 1) : 0;
20 }
21 
22 template <class T>
23 IL T mymax(const T &a, const T &b) {
24   return a > b ? a : b;
25 }
26 
27 template <class T>
28 IL T mymin(const T &a, const T &b) {
29   return a < b ? a : b;
30 }
31 
32 template <class T>
33 IL T myabs(const T &a) {
34   return a > 0 ? a : -a;
35 }
36 
37 const int INF = 0X3F3F3F3F;
38 const double EPS = 1E-8, PI = acos(-1.0);
39 
40 #define DEBUG(...) fprintf(stderr, __VA_ARGS__)
41 #define OK DEBUG("Passing [%s] in LINE %d...\n", __FUNCTION__, __LINE__)
42 
43 const int MAXN = 10000 + 5;
44 
45 int cd[MAXN], het[MAXN];
46 double left[MAXN], right[MAXN];
47 LL f[MAXN];
48 
49 int main() {
50   int n, h;
51   LL x, y;
52   scanf("%d%d%lld%lld", &n, &h, &x, &y);
53   For(i, 1, n) {
54     scanf("%d%d", &cd[i], &het[i]);
55   }
56   auto getR = [](double a, double b, double c) {
57     return sqrt(2.0 * a * (b - c)) + a + b - c;
58   };
59   For(i, 1, n) {
60     left[i] = -INF;
61     Rep(j, i, 1) {
62       chkmax(left[i], mymin((double)cd[j], cd[i] - 2.0 * getR(cd[i] - cd[j], h, het[j])));
63     }
64     right[i] = INF;
65     For(j, i, n) {
66       chkmin(right[i], mymax((double)cd[j], cd[i] + 2.0 * getR(cd[j] - cd[i], h, het[j])));
67     }
68   }
69   memset(f, 0X3F, sizeof f);
70   f[1] = x * (h - het[1]);
71   For(i, 2, n) {
72     REP(j, i, 1) {
73       if (left[i] <= cd[j] && right[j] >= cd[i]) {
74         chkmin(f[i], f[j] + x * (h - het[i]) + y * (cd[i] - cd[j]) * (cd[i] - cd[j]));
75       }
76     }
77   }
78   if (f[n] >= (LL)INF * INF) {
79     puts("impossible");
80     exit(0);
81   }
82   printf("%lld\n", f[n]);
83   return 0;
84 }