【World Finals】2011 A

【试题编号】
2011 A
【名称】
To Add or to Multiply
【题目大意】
一个数x 你可以对他进行+a操作 或*m操作 给定的数范围在p~q 最后达到的范围要是r~s 问是否可行 如果可行 输出字典序最小的方案
【算法讨论】
可以发现 M操作的次数很小 不妨枚举M的次数i 然后p,q变为p*M^i,q*M^i 然后再某个位置的一个A 可以看成+a*m^j 贪心的从次数高的开始加 能加就加 一定是当前i的最优解 然后跟一个全局的答案比较 更新
【时空复杂度】
O(logn*logn)
O(logn)
【code】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
ll c[35], a, m, p, q, r, s, t[35], ans, as[35];
bool check()
{
    for (ll cc = c[34], aa = as[34]; cc >= 0 && aa >= 0; --cc, --aa)
    {
        if (c[cc] < as[aa]) return false;
        if (c[cc] > as[aa]) return true;
    }
    return false;
}
int main()
{
    ll test = 0;
    while (scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &a, &m, &p, &q, &r, &s) && (a | m | p | q | r | s))
    {
        ans = 0x7fffffff;
        printf("Case %I64d: ", ++test);
        if (p >= r && q <= s)
        {
            printf("empty\n");
            continue;
        }
        int k = -1;
        if (m != 1)
        for (ll i = 1, lf = p * m, rt = q * m; rt <= s; ++i, lf *= m, rt *= m)
            if (lf >= r && rt <= s)
            {
                k = i;
                break;
            }
        if (q - p > s - r)
        {
            printf("impossible\n");
            continue;
        }
        if (m == 1)
        {
            if (p + ((r - p + a - 1) / a) * a >= r && q + ((r - p + a - 1) / a) * a <= s)
            printf("%I64dA\n", ((r - p + a - 1) / a));
            else printf("impossible\n");
            continue;
        }
        t[0] = 1;
        for (ll i = 0, k = 1; q * k <= s && (q - p) * k <= (s - r); ++i, k *= m)
        {
            if (i) t[i] = t[i - 1] * m;
            ll lf = r - p * t[i], rt = s - q * t[i], z = -1, tans = 0;
            memset(c, 0, sizeof(c));
            if (lf > 0)
            for (ll j = i; j >= 0; --j)
            {
                z = j;
                c[j] = rt / t[j] / a;
                if (lf - c[j] * t[j] * a <= 0)
                    c[j] = (lf + t[j] * a - 1) / t[j] / a;
                lf -= c[j] * t[j] * a;
                rt -= c[j] * t[j] * a;
                tans += c[j];
                if (lf <= 0) break;
            }/*
            for (ll j = 0; j < z; ++j)
                if (lf + t[z] - t[j] <= 0)
                {
                    c[z] -= 1;
                    c[j] += 1;
                    break;
                }*/

            if (lf > 0) tans = 0x7fffffff;
            c[34] = i;
            tans += i;
            if (tans < ans || (tans == ans && check()))
            {
                ans = tans;
                for (ll j = 0; j < 35; ++j)
                    as[j] = c[j];
            }
        }
        if (ans >= 0x3f3f3f3f) printf("impossible");
        else
        for (ll i = as[34]; i >= 0;)
        {
            if (as[i]) printf("%I64dA ", as[i]);
            if (i)
            {
                --i;
                ll t = 1;
                while (i && !as[i])
                    --i, ++t;
                printf("%I64dM ", t);
            }
            else break;
        }
        printf("\n");
    }
}

【World Finals】2005 E【X】

【试题编号】
2005 E
【名称】
Lots of Sunlight
【题目大意】
给一堆楼 求某间被照的时间段
【算法讨论】
枚举
【时空复杂度】
O(n^2)
O(n)
【code】

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
166
167
168
169
170
171
172
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
//===========================Geometry_Base=============
struct Geometry_Base
{
    public:
    static const double eps = 1e-8;
    double pi;
    struct point
    {
        double x, y;
        point() {}
        point(double _x, double _y) : x(_x), y(_y) {}
        point operator-(point a) { return point(x - a.x, y - a.y); }
        point operator+(point a) { return point(x + a.x, y + a.y); }
        point operator*(double a) { return point(x * a, y * a); }
        point operator/(double a) { return point(x / a, y / a); }
        double operator&(point a) { return x * a.y - y * a.x; }
        double operator|(point a) { return x * a.x + y * a.y; }
        bool operator==(point a) { return !cmp(x, a.x) && !cmp(y, a.y); }
        bool operator!=(point a) { return !(!cmp(x, a.x) && !cmp(y, a.y)); }
        bool operator<(point a) const { return cmp(x, a.x) == -1 || (cmp(x, a.x) == 0 && cmp(y, a.y) == -1); }
        point operator-=(point a) { x -= a.x, y -= a.y; return *this; }
        point operator+=(point a) { x += a.x, y += a.y; return *this; }
        point operator*=(double a) { x *= a, y *= a; return *this; }
        point operator/=(double a) { x /= a, y /= a; return *this; }
    };
    struct segment
    {
        point a, b;
        segment() {};
        segment(point _a, point _b) : a(_a), b(_b) {};
        bool operator==(segment A) { return (a == A.a && b == A.b) || (b == A.a && a == A.b); }
        bool operator!=(segment A) { return !((a == A.a && b == A.b) || (b == A.a && a == A.b)); }
    };
    Geometry_Base() { pi = acos(-1.); }
    void create() {}
    double sqr(double a) { return a * a; }
    point rotate(point a, double b) {   return point(a.x * cos(b) - a.y * sin(b), a.x * sin(b) + a.y * cos(b)); }
    double dist(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }
    static int cmp(double a, double b) { return abs(a - b) < eps ? 0 : (a < b ? -1 : 1); } // (0 =) (-1 <) (1 >)
    int pos(point a, point b) { return cmp(a & b, 0); } // (0 =) (-1 right) (1 left)
    int pos(segment a, segment b) { return pos(a.b - a.a, b.b - b.a); } // (0 =) (-1 right) (1 left)
    int pos(segment a, point b) { return pos(a, segment(a.a, b)); } // (0 =) (-1 right) (1 left)
    bool init(segment a, point b)   {   return !cmp(dist(a.a, a.b), dist(a.a, b) + dist(a.b, b));   }
    segment get_vertical(segment a, point b) { return segment(b, b + rotate(a.b - a.a, pi / 2)); }
    point get_foot(segment a, point b) { return cross(a, get_vertical(a, b));   }
    point get_mid(segment a) { return (a.a + a.b) / 2; }
    double dist(segment a, point b) {   return dist(get_foot(a, b), b); }
    double dist2(segment a, point b) { point p = get_foot(a, b); return init(a, p) ? dist(p, b) : min(dist(a.a, b), dist(a.b, b)); }
    int check(segment a, segment b)
    {
        if (pos(a, b) == 0)
        {
            if (pos(a, b.a)) return 0;
            if (!cmp(a.a.x, a.b.x))
            {
                if (a.a.y > a.b.y) swap(a.a, a.b);
                if (b.a.y > b.b.y) swap(b.a, b.b);
                if (a.a.y > b.a.y) swap(a, b);
                return cmp(a.b.y, b.a.y) >= 0 ? -1 : 0;
            }
            else
            {
                if (a.a.x > a.b.x) swap(a.a, a.b);
                if (b.a.x > b.b.x) swap(b.a, b.b);
                if (a.a.x > b.a.x) swap(a, b);
                return cmp(a.b.x, b.a.x) >= 0 ? -1 : 0;
            }
        }
        return pos(a, b.a) * pos(a, b.b) <= 0 && pos(b, a.a) * pos(b, a.b) <= 0 ? 1 : 0;
    }
    double get_k(segment a)
    {
        if (!cmp(a.a.x, a.b.x)) return 0;
        return (a.b.y - a.a.y) / (a.b.x - a.a.x);
    }
    double get_b(segment a)
    {
        if (!cmp(a.a.x, a.b.x)) return 0;
        return a.a.y - a.a.x * get_k(a);
    }
    point cross(segment a, segment b)
    {
        if (!pos(a, b)) return point(0, 0);
        if (!cmp(b.a.x, b.b.x)) swap(a, b);
        if (!cmp(a.a.x, a.b.x))
        {
            double k = (b.b.y - b.a.y) / (b.b.x - b.a.x),
                         b_ = b.a.y - b.a.x * k;
            return point(a.a.x, k * a.a.x + b_);
        }
        else
        {
            double k1 = (a.b.y - a.a.y) / (a.b.x - a.a.x),
                         k2 = (b.b.y - b.a.y) / (b.b.x - b.a.x),
                         b1 = a.a.y - a.a.x * k1,
                         b2 = b.a.y - b.a.x * k2,
                         x  = (b2 - b1) / (k1 - k2),
                         y  = k1 * x + b1;
            return point(x, y);
        }
    }
}gb;;
typedef Geometry_Base::point gbp;
typedef Geometry_Base::segment gbs;
//===========================Geometry_Base=============
const double PI = 3.14159265358;
const int st = 20220;
const int delta = 45600;
const int maxn = 105;
int x[maxn], h[maxn], n, p, q, d[maxn];
void print(double k)
{
    int t = (int)k;
    printf("%.02d:%.02d:%.02d", t / 3600, t / 60 % 60, t % 60);
}
int main()
{
    int test = 0;
    while (scanf("%d", &n), n)
    {
        printf("Apartment Complex: %d\n", ++test);
        scanf("%d%d", &p, &q);
        memset(x, 0, sizeof(x));
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &h[i]);
            if (i == 1) x[i] = 0;
            else x[i] = x[i - 1] + p + d[i - 1];
            if (i < n) scanf("%d", &d[i]);
        }
        int m;
        while (scanf("%d", &m), m)
        {
            printf("Apartment %d: ", m);
            int X = m % 100, Y = m / 100;
            if (X > n || X <= 0 || Y > h[X] || Y <= 0)
            {
                printf("Does not exist\n");
                continue;
            }
            gbs s = gbs(gbp(x[X], (Y - 1) * q), gbp(x[X] - 1, (Y - 1) * q));
            for (int i = 1; i < X; ++i)
                if (gb.pos(s, gbs(gbp(x[X], (Y - 1) * q), gbp(x[i] + p, h[i] * q))) == -1)
                    s = gbs(gbp(x[X], (Y - 1) * q), gbp(x[i] + p, h[i] * q));
            print((PI - atan2((s.b - s.a).y, (s.b - s.a).x)) / PI * delta + st);
            printf(" - ");
            s = gbs(gbp(x[X] + p, (Y - 1) * q), gbp(x[X] + p + 1, (Y - 1) * q));
            for (int i = X + 1; i <= n; ++i)
                if (gb.pos(s, gbs(gbp(x[X] + p, (Y - 1) * q), gbp(x[i], h[i] * q))) == 1)
                    s = gbs(gbp(x[X] + p, (Y - 1) * q), gbp(x[i], h[i] * q));
            print((PI - atan2((s.b - s.a).y, (s.b - s.a).x)) / PI * delta + st);
            printf("\n");
        }
    }
}

BZOJ 3140: [Hnoi2013]消毒

每次消的一定是1*N*N的一块
因为如果某次删的最小边是k
那么另外两条边一定是取到最大
对于这个清洗 可以分成k个1*N*N的步骤
考虑到最小的边长最大只会有17
可以枚举这个维度哪些要取
然后就变成了经典的棋盘最小覆盖问题
可以用二分图匹配做
对于点(x,y)连接左部x点和右部的y的点
最大匹配即为ans
这题卡常数
卡得还非常没节操
看了它的数据 里面1的个数非常少
所以对每行 哪几列有1 用链表存储 就可以过了

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 5005;

struct line
{
  int to, next;
}li[maxn * 10], li2[maxn * 1000];

int x, y, z, a[maxn], t[maxn], b[20], ans, fa[maxn], be[maxn], br[maxn], l, be2[maxn], l2;

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

void makeline2(int fr, int to)
{
  ++l2;
  li2[l2].next = be2[fr];
  be2[fr] = l2;
  li2[l2].to = to;
}

bool can(int now)
{
  br[now] = 1;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (fa[to] == -1 || (!br[fa[to]] && can(fa[to])))
    {
      fa[to] = now;
      return true;
    }
  }
  return false;
}

int check()
{
  for (int i = 0; i < z; ++i) fa[i] = -1;
  for (int i = 0; i < y; ++i) be[i] = 0;
  l = 0;
  for (int i = 0; i < x; ++i)
    if (!b[i])
      for (int j = 0; j < y; ++j)
        for (int k = be2[i * y + j]; k; k = li2[k].next)
        {
          int to = li2[k].to;
          makeline(j, to);
        }
  int ans = 0;
  for (int i = 0; i < y; ++i)
  {
    for (int j = 0; j < y; ++j) br[j] = 0;
    if (can(i)) ++ans;
  }
  return ans;
}

void dfs(int now, int tot)
{
  if (now == x)
  {
    ans = min(ans, check() + tot);
    return;
  }
  b[now] = 1;
  dfs(now + 1, tot + 1);
  b[now] = 0;
  dfs(now + 1, tot);
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
  scanf("%d%d%d", &x, &y, &z);
  memset(be2, 0, sizeof(be2));
  l2 = 0;
  for (int i = 0; i < x * y * z; ++i) scanf("%d", &t[i]);
  if (x <= y && x <= z)
  {
    for (int i = 0; i < x; ++i)
      for (int j = 0; j < y; ++j)
        for (int k = 0; k < z; ++k)
          a[i * y * z + j * z + k] = t[i * y * z + j * z + k];
  }
  else
  if (z <= x && z <= y)
  {
    for (int i = 0; i < x; ++i)
      for (int j = 0; j < y; ++j)
        for (int k = 0; k < z; ++k)
          a[k * y * x + j * x + i] = t[i * y * z + j * z + k];
    int tx = x, ty = y, tz = z;
    x = tz, y = ty, z = tx;
  }
  else
  if (y <= z && y <= x)
  {
    for (int i = 0; i < x; ++i)
      for (int j = 0; j < y; ++j)
        for (int k = 0; k < z; ++k)
          a[j * x * z + i * z + k] = t[i * y * z + j * z + k];
    int tx = x, ty = y, tz = z;
    x = ty, y = tx, z = tz;
  }
  ans = 0x7fffffff;
  for (int i = 0; i < x; ++i)
    for (int j = 0; j < y; ++j)
      for (int k = 0; k < z; ++k)
        if (a[i * y * z + j * z + k])
          makeline2(i * y + j, k);
  dfs(0, 0);
  printf("%d\n", ans);
  }
}