首页 > ACM题库 > HDU-杭电 > HDU 3837-To Add or to Multiply-计算几何-[解题报告]HOJ
2015
04-13

HDU 3837-To Add or to Multiply-计算几何-[解题报告]HOJ

To Add or to Multiply

问题描述 :

The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the a-C-mfamily (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different operations:

A add a
M multiply by m

The processor receives an integer, executes a sequence of A and M operations (the program) that modifies the input, and outputs the result. For example, the 1-C-2 processor executing the program AAAM with the input 2 yields the output
10 (the computation is 2 ! 3 ! 4 ! 5 ! 10), while the 5-C-3 processor yields 51 with the same program and input (2 ! 7 ! 12 ! 17 ! 51).

You are an a-C-m programmer assigned to a top secret project. This means that you have not been told the precise computation your program should perform. But you are given particular values p, q, r, and s and the following
conditions:

1. The input is guaranteed to be a number between p and q.
2. The output must be some number between r and s.

Given an a-C-m processor and the numbers p, q, r, and s, your job is to construct the shortest a-C-m program which, for every input x such that p <= x <= q, yields some output y such that r <= y <= s. If there is more than one program of minimum length, choose the one that come first lexicographically, treating each program as a string of As and Ms.

输入:

The input contains several test cases. Each test case is given by a line with the six integers a, m, p, q, r, and s as described above (1 <= a, m, p, q, r, s <= 10^9, p <= q and r <= s).

The last test case is followed by a line with six zeros.

输出:

The input contains several test cases. Each test case is given by a line with the six integers a, m, p, q, r, and s as described above (1 <= a, m, p, q, r, s <= 10^9, p <= q and r <= s).

The last test case is followed by a line with six zeros.

样例输入:

1 2 2 3 10 20
1 3 2 3 22 33
3 2 2 3 4 5
5 3 2 3 2 3
0 0 0 0 0 0

样例输出:

Case 1: 1A 2M
Case 2: 1M 2A 1M
Case 3: impossible
Case 4: empty

    首先我们观察加操作和乘操作会对区间产生那些影响。加操作只会平移区间,而乘操作既能移动区间还能放大区间。因此我们不难想到,如果m>1的话乘操作是log级别的,一方面是因为区间的大小不能超过s-r,另一方面区间的最大值不能超过r,这两方面都能决定乘操作的个数是log级别的,因此一种可行的思路就是枚举乘操作的次数,然后再看怎么安排加操作。

    同时我们还能发现,这些操作不会改变区间内数的顺序,因此只要最小值和最大值都在s到r之间就可以,并且如果我们固定了乘操作的次数,相当于固定了最终区间的宽度,这样根据最小值就能推出最大值,因此我们可以只约束最小值在某个范围内,就能使得最小值和最大值都在s到r之间,这样我们又进一步简化了问题。

    现在的问题就是在乘操作固定的情况下,要怎么安排加操作才能使最小值(也就是p)落在这个范围(指前面所说的“我们可以只约束最小值在某个范围内”的这个范围)内。

    我们会发现不论加操作和乘操作的顺序如何,最后p变成的数都能表示成x*p+y的形式,而且x是m的整数次幂,y是m的一些整数次幂和a的乘积,而且如果把y中的那个公因子的a提出来,就会发现剩下的部分就是m的一些整数次幂的和,而且这些整数次幂的系数之和就是加法的次数。

    用数学一点的形式表示上面加粗的部分就是说y=x0 * m^0 + x1* m^1 + x2 * m^2 + …,其中x0 + x1 + x2 …得到的值就是加法的次数,并且x0这个部分表示的是最后才加的那些a,x1这个部分表示的是在进行最后一次乘m的操作前最后加的那些a,x2这个部分表示……

    接下来我们可以先求一个不小于r的一个最小的x*p+y,因为x已经知道了,是m的某次幂,在乘操作次数固定后就是定值了,而且y一定是a的整数倍,那么结合模运算就不难求得y的值了,这样就得到了不小于r的一个最小的x*p+y,如果这个值都不在前面所说的那个范围的话,那么这种乘操作次数下就一定无解了。

    那么如果这个值在所说的那个范围内呢?那么一定会有一个可行解。还会不会有其他可行解呢?是有可能的,因为毕竟我们只求了一个最小的x*p+y,但什么情况下才有可能更新最优解呢?至少也得比我们刚刚算的这个可行解更优吧,但是乘法次数一定固定了呀,那么我们就考虑让加法次数更少一些。而我们刚刚说了y=x0 * m^0 + x1* m^1 + x2 * m^2 + …,这个实际上不就是一个m进制数么,如果想让各个位上的数字之和更小的话就必须要产生进位,这样才可能消掉一部分,但却只付出增加一个进位的代价,这个进位要么只使各位数字之和增加1,要么还能进一步减少各位数字之和的值。所以我们就可以从低位到高位依次考虑可不可以进位了,那么就先考虑能不能通过增加m-x0消掉x0,如果可以的话我们再考虑能不能在原有的基础上再增加(m-x1)*m从而消掉x1,如果可以的话再考虑……就这样一直消到不能消为止,期间每消一次就更新一次最优解。

    前面在讨论什么情况下有可能更新最优解的时候其实少了一点没有考虑,就是操作数是一样的,但是可能字典序会更小。不过这点其实是不用考虑的,因为如果存在这种情况,那么一定是先产生进位之后才能再出现这样的情况,而刚产生进位的时候就要么是操作数一样,要么是操作数更小了,所以就不用再考虑这种情况了,只需要考虑刚进位的时候就行了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXN 110
typedef long long LL;
int A, M, P, Q, R, S;
struct List
{
    int s, n, cnt[MAXN];
    bool add[MAXN];
    bool operator < (const List &t) const
    {
        if(s != t.s) return s < t.s;
        int p = 0, r = cnt[0], tp = 0, tr = t.cnt[0];
        while(p < n && tp < t.n)
        {
            if(add[p] && !t.add[tp]) return true;
            if(!add[p] && t.add[tp]) return false;
            int min = std::min(r, tr);
            r -= min, tr -= min;
            if(r == 0) r = cnt[++ p];
            if(tr == 0) tr = t.cnt[++ tp];
        }
        return p == n && tp < t.n;
    }
}ans;
List gen(int a[], int mn)
{
    List ret;
    ret.s = mn, ret.n = 0;
    for(int i = 0, &n = ret.n; i <= mn; i ++)
    {
        ret.s += a[i];
        if(a[i] > 0)
        {
            ret.cnt[n] = a[i], ret.add[n] = true;
            ++ n;
        }
        if(i < mn)
        {
            if(n == 0 || ret.add[n - 1])
            {
                ret.cnt[n] = 1, ret.add[n] = false;
                ++ n;
            }
            else ++ ret.cnt[n - 1];
        }
    }
    return ret;
}
void process(int mn, int p, int px, int py)
{
    if(p > px) px = p;
    LL sum = ((p - px) % A + A) % A + px;
    if(sum > py) return;
    sum = (sum - p) / A;
    int t = sum, max = (py - p) / A, a[MAXN];
    for(int i = mn; i > 0; i --) a[i] = t % M, t /= M;
    a[0] = t;

    List opt;
    for(int i = mn, fac = 1; i >= 0; i --, fac *= M)
    {
        opt = gen(a, mn);
        if(opt < ans) ans = opt;
        if(i > 0 && a[i] != 0)
        {
            sum += (LL)(M - a[i]) * fac, a[i] = M;
            if(sum > max) break;
            for(int j = i; j > 0 && a[j] == M; j --)
                ++ a[j - 1], a[j] = 0;
        }
    }
}
int main()
{
    int t = 0;
    while(scanf("%d%d%d%d%d%d", &A, &M, &P, &Q, &R, &S), A > 0)
    {
        ans.s = INF;
        LL len = Q - P, p = P;
        for(int i = 0; p <= S - len && len <= S - R; i ++, len *= M, p *= M)
        {
            process(i, p, R, S - len);
            if(M == 1) break;
        }
        printf("Case %d:", ++ t);
        if(ans.s == INF) printf(" impossible");
        else if(ans.s == 0) printf(" empty");
        else
        {
            for(int i = 0; i < ans.n; i ++)
                printf(" %d%c", ans.cnt[i], ans.add[i] ? 'A' : 'M');
        }
        printf("\n");
    }
    return 0;
}

 

参考:http://www.cnblogs.com/staginner/p/3365865.html


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮