【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 I

【试题编号】
2005 I
【名称】
Workshops
【题目大意】
有好几个课题和房间 每个课题和房间都有时间和人数 求没房间讨论的课题最少 相同的情况下求没房间讨论的人数最少
【算法讨论】
贪心 先把房间按时间排序 然后顺序循环 对于一个房间 取所有没被取的课题 能被取的课题里 人数最多的一个
证明: 大概可以是这样 就是不考虑人数的限制 当前限制已经是最严格的 然后取可以取的人数最多的 就满足两个都最严格了
更严谨的证明就是 考虑交换两个房间的课题 一定不会更优
【时空复杂度】
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
#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;

const int maxn = 1005;

struct point
{
    int n, t;
}a[maxn], b[maxn];

int n, m, tot, num[maxn], br[maxn];

bool cmp(point a, point b)
{
    return a.t < b.t;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int test = 0;
    while (scanf("%d", &n), n)
    {
        memset(num, 0, sizeof(num));
        memset(br, 0, sizeof(br));
        tot = 0;
        for (int i = 0; i < n; ++i)
            scanf("%d%d", &a[i].n, &a[i].t), tot += a[i].n;
        scanf("%d", &m);
        for (int i = 0; i < m; ++i)
        {
            int h, m;
            scanf("%d %d:%d", &b[i].n, &h, &m);
            b[i].t = (h - 14) * 60 + m;
        }
        sort(b, b + m, cmp);
        int ans1 = n - m;
        for (int i = 0; i < m; ++i)
        {
            int mx = -1, k = -1;
            for (int j = 0; j < n; ++j)
                if (!br[j] && a[j].n <= b[i].n && a[j].t <= b[i].t)
                    if (mx < a[j].n)
                        mx = a[j].n,
                        k = j;
            if (k == -1)
            {
                ++ans1;
                continue;
            }
            br[k] = 1;
            tot -= mx;
        }
        printf("Trial %d: %d %d\n", ++test, ans1, tot);
    }
    fclose(stdin);fclose(stdout);
}

【World Finals】2013F

【试题编号】
2013F
【名称】
Low Power
【题目大意】
有n台机器 每台2个芯片 每个芯片k个电池 每个电池有个独立的电量 对于一个芯片 能量是最小的电池的电量 一个机器的性能是两个芯片的能量差 求机器性能最大最小
【算法讨论】
因为对于每个芯片 只有最小电池有用 于是对于每个芯片只要考虑最小的电池 再考虑电池的选用
可以证明 对于一台机器的两个芯片的最小电池一定是连续的两个
先二分答案 显然 对于一个固定的delta 取得越前面越好 只要能取满 那么这个delta就是合法的
【时空复杂度】
O(nlogn)
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
#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;
int a[1000005], n, k, m;
bool check(int mid)
{
    for (int i = 0, tot = 0, as = 0; i < m; ++i)
    {
        if (a[i + 1] - a[i] <= mid)
        {
            tot += (k - 1) * 2;
            if (++as == n) break;
            ++i;
        }
        else if (--tot < 0) return false;
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &k);
    m = 2 * n * k;
    for (int i = 0; i < m; ++i)
        scanf("%d", &a[i]);
    sort(a, a + m);
    int l = -1, r = 10000 * 10000 * 10;
    while (l + 1 < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%d", r);
}