题解

13 条题解

  • 1
    @ 2022-07-25 20:07:06

    看了一下没人发题解,我发一个我的做法。

    #1 Accepted 82ms 6.867 MiB
    #2 Accepted 6ms 640.0 KiB
    #3 Accepted 5ms 896.0 KiB
    #4 Accepted 8ms 1.0 MiB
    #5 Accepted 9ms 2.0 MiB
    #6 Accepted 9ms 2.875 MiB
    #7 Accepted 30ms 3.625 MiB
    #8 Accepted 20ms 5.125 MiB
    #9 Accepted 24ms 6.125 MiB
    #10 Accepted 47ms 6.875 MiB

    主要思路是动态规划,我的代码是记忆化搜索。 根据长度来设定状态,每个状态记录当下所至少使用的 ADD DEL MOVE。

    #include <stdio.h>
    #include <stdlib.h>
    #include <vector>
    #include <string.h>
    
    #define DIGIT_LEN 7
    /*
     *     1
     *   2   3
     *     4
     *   5   6
     *     7
     */
    int digit[10][DIGIT_LEN] = {
            {1,1,1,0,1,1,1},
            {0,0,1,0,0,1,0},
            {1,0,1,1,1,0,1},
            {1,0,1,1,0,1,1},
            {0,1,1,1,0,1,0},
            {1,1,0,1,0,1,1},
            {1,1,0,1,1,1,1},
            {1,0,1,0,0,1,0},
            {1,1,1,1,1,1,1},
            {1,1,1,1,0,1,1}
    };
    
    
    #define ABS(X) ((X) < 0 ? (-X) : (X))
    
    int p[3], q[3];
    class Num;
    
    static Num* fixOneAddr;
    
    class Num {
    
        //add del move
        int i[3];
    public:
        Num() {
            i[0]=i[1]=i[2]=-1;
        }
        Num(int a,int b, int c)  {
            i[0] =a;
            i[1]=b;
            i[2]=c;
        }
        bool isEqual(Num & o) {
            return i[2] == o.i[2] && i[1] == o.i[1] && i[0] == o.i[0];
        }
    
        //方向并不重要
        bool isDefinitelyBetter(Num& o) {
            return (i[2]) <= (o.i[2])
                   && (i[1]) <= (o.i[1]) && (i[0]) <= (o.i[0]);
    //        return ABS(i[2]) >= ABS(o.i[2])
    //               && ABS(i[1]) >= ABS(o.i[1]) && ABS(i[0]) >= ABS(o.i[0]);
        }
    
        inline bool isValid() {
            return i[0] >= 0;
        }
    
        inline bool isMustInvalid() {
            return i[0] == -2;
        }
    
        inline void markMustInvalid() {
            i[0] = -2;
        }
    
    //    inline bool advance() {
    //        if(i[2] > 0) {
    //            i[0]++;
    //            i[1]++;
    //            i[2]--;
    //        }
    //    }
    
        inline void fill(int* add, int* del, int* move) {
            *add = i[0];
            *del = i[1];
            *move = i[2];
        }
    
        int totalCost() {
            int sum = 0;
            for(int j=0;j<3;j++) {
                int t = i[j];
                sum += t * q[j];
                sum += p[j] * (t+1)*t/2;
            }
            return sum;
        }
    
        void checkIfCanReplace (Num& base, int extra_add, int extra_del, int extra_move) {
            int sum = 0;
            int temp[3] = {extra_add, extra_del, extra_move};
            for(int j=0;j<3;j++) {
                int t = base.i[j] + temp[j];
                sum += t * q[j];
                sum += p[j] * (t+1)*t/2;
            }
    
            if(i[0] == -1 || totalCost() > sum) {
                for(int j=0;j<3;j++) {
                    i[j] = base.i[j] + temp[j];
                }
            }
    //      if(this == fixOneAddr) {
    //          printf("weird set value\n");
    //      }
        }
    };
    using namespace std;
    vector<Num> calcFirst[10][10];
    
    /**
     * n1(old) -> n2(new)
     */
    void tellDiff(int n1, int n2, int* more, int* less) {
        int* na1 = digit[n1];
        int* na2 = digit[n2];
        int moreOut = 0;
        int lessOut = 0;
        for(int i=0;i<DIGIT_LEN;i++) {
            if(na1[i] == na2[i]) continue;
    
            if(na1[i]) moreOut++;
            if(na2[i]) lessOut++;
        }
        *more = moreOut;
        *less = lessOut;
    }
    
    void addNum(vector<Num>& v, Num& wantIn) {
        for(int i=0;i<v.size();i++) {
            if(v[i].isEqual(wantIn)) {
                return;
            }
            if(v[i].isDefinitelyBetter(wantIn)) {
                return;
            }
        }
        v.push_back(wantIn);
    }
    
    #define LEVEL_LINE 1400
    Num (*fn)[2800];
    int a1[200], a2[200];
    
    /**
     *  > LEVEL_LINE mean  before 'maxOne' there are more
     *  or                                 there are less
     */
    
    static Num validOne(0,0,0);
    //#define MY_DEBUG
    #ifdef MY_DEBUG
    bool forTest[200][2800];
    #endif
    
    Num& getGoodOne(int maxOne, int level) {
    
    
        if(maxOne ==-1) {
            static Num fixOne;
            if(level != LEVEL_LINE) {
                return fixOne;
            }
            return validOne;
        }
        Num& cache = fn[maxOne][level];
        if(cache.isMustInvalid()) {
            return cache;
        }
        if(cache.isValid()) {
            return cache;
        }
    
    #ifdef MY_DEBUG
        {
            if(maxOne == 0 && level == 1488) {
                printf("got you\n");
            }
            if(forTest[maxOne][level]) {
                printf("may reEnter for %d %d\n", maxOne, level);
                exit(0);
            }
            forTest[maxOne][level] = true;
    //      static int enterCount = 0;
    //      enterCount++;
    //      if(enterCount % 100 == 0)
    //          printf("now enter %d\n", enterCount);
        }
    #endif
    
        int num1 = a1[maxOne], num2 = a2[maxOne];
        vector<Num>& vi = num1 > num2 ? calcFirst[num1][num2] : calcFirst[num2][num1];
    
        for(int i=0;i<vi.size();i++) {
            Num& preStrategy = vi[i];
            int add, del, move;
            preStrategy.fill(&add, &del, &move);
    
            if(add >= 0) { //需要 add 意味着缺少, =0 只是为了至少有一个情况
                for(int add_myself=0; add_myself<=add;add_myself++) {
                    int needByOther = add - add_myself;
                    Num& before = getGoodOne(maxOne-1, level + needByOther);
                    if(before.isValid()) {
                        cache.checkIfCanReplace(before, add_myself, del, move + needByOther);
                    }
                }
            }
            if(del > 0) {
                for(int del_myself=0; del_myself<=del;del_myself++) {
                    int needByOther = del - del_myself;
                    Num& before = getGoodOne(maxOne-1, level - needByOther);
                    if(before.isValid()) {
                        cache.checkIfCanReplace(before, add, del_myself, move);
                    }
                }
            }
    
            for(;move>0; ) {
                add++;
                del++;
                move--;
                Num& before = getGoodOne(maxOne-1, level);
                if(before.isValid()) {
                    cache.checkIfCanReplace(before, add, del, move);
                }
            }
        }
    
        if(!cache.isValid()) {
            cache.markMustInvalid();
        }
        return cache;
    }
    
    void preCalc() {
        fixOneAddr = &validOne;
        for(int i=0;i<10;i++) {
            for(int j=0;j<i;j++) {
                for(int k=0;k<10;k++) {
                    int m_i, l_i;
                    int m_j, l_j;
                    tellDiff(i, k, &m_i, &l_i );
                    tellDiff(j, k, &m_j, &l_j );
                    int more = m_i+m_j;
                    int less = l_i + l_j;
    
                    int common = std::min(more, less);
                    Num num(less - common,more - common,common);
                    addNum(calcFirst[i][j], num);
                }
    
                vector<Num>& preBuild = calcFirst[i][j];
                for(int k=0;k<preBuild.size();k++) {
                    for(int k2=k+1;k2<preBuild.size();k2++) {
                        if(preBuild[k2].isDefinitelyBetter(preBuild[k])) {
                            preBuild.erase(preBuild.begin() + k);
                            k--;
                            break;
                        }
                    }
                }
            }
            calcFirst[i][i].emplace_back(0,0,0);
        }
    }
    
    int main() {
        preCalc();
    
        int n;
        scanf("%d", &n);
        fn = (Num(*)[2800])(malloc(n * sizeof(Num) * 2800));
        memset(fn, -1,n *  sizeof(Num) * 2800);
        getchar();
    
        for(int i=0;i<n;i++) a1[i] = getchar() - '0';
        getchar();
        for(int i=0;i<n;i++) a2[i] = getchar() - '0';
        getchar();
    
        for(int i=0;i<3;i++) scanf("%d%d", &p[i], &q[i]);
        Num& ans = getGoodOne(n-1, LEVEL_LINE);
        printf("%d", ans.totalCost());
    
        return 0;
    }
    
    
  • 0
    @ 2020-07-13 06:21:53

    /*这个解过了题目举的两个例子,但测试一个都没过,很无语不知道为什么*/

    #include <stdio.h>

    int count(int num) {
    int c = 0;
    while (num != 0) {
    c += num % 2;
    num /= 2;
    }
    return c;
    }

    int getSevenRepresent(int num) {
    switch(num) {
    case 0:
    return 119; //0b1110111;
    case 1:
    return 18; //0b0010010;
    case 2:
    return 93; //0b1011101;
    case 3:
    return 91; //0b1011011;
    case 4:
    return 58; //0b0111010;
    case 5:
    return 107; //0b1101011;
    case 6:
    return 111; //0b1101111;
    case 7:
    return 82; //0b1010010;
    case 8:
    return 127; //0b1111111;
    case 9:
    return 123; //0b1111011;
    default:
    fprintf(stderr, "getSevenRepresent: value %d not a digit", num);
    return 0;
    }
    }

    void getdiff(int leftNum, int rightNum, int *leftRm, int *leftAdd, int digit) {
    int leftDigit, rightDigit;
    for (int i=0;i<digit; i++) {
    leftDigit = getSevenRepresent(leftNum % 10);
    rightDigit = getSevenRepresent(rightNum % 10);
    *leftRm += count(leftDigit & ~rightDigit);
    *leftAdd += count(~leftDigit & rightDigit);

    leftNum /= 10;
    rightNum /= 10;
    }
    }

    int main(void) {
    int digit = 0;
    int leftNum = 0, rightNum = 0;
    int p[3], q[3];
    scanf("%d", &digit);
    scanf("%d", &leftNum);
    scanf("%d", &rightNum);
    for (int i=0;i<3;i++) {
    scanf("%d", &p[i]);
    scanf("%d", &q[i]);
    }

    int leftRm = 0, leftAdd = 0;
    getdiff(leftNum, rightNum, &leftRm, &leftAdd, digit);
    int result = 0, rm = 1, add = 1, mov = 1;

    // printf("leftRm = %d\n", leftRm);
    // printf("leftAdd = %d\n", leftAdd);

    while (leftRm != 0 || leftAdd != 0) {
    int movCost = p[2] * mov + q[2],
    addCost = p[0] * add + q[0],
    rmCost = p[1] * rm + q[1];

    if (movCost < (addCost + rmCost) &&
    leftRm != 0 && leftAdd != 0) {
    result += (p[2] * mov + q[2]);
    leftAdd--;
    leftRm--;
    mov++;
    } else if (leftAdd == 0 || rmCost < addCost) {
    result += (p[1] * rm + q[1]);
    leftRm--;
    rm++;
    } else {
    result += (p[0] * add + q[0]);
    leftAdd--;
    add++;
    }
    // printf("result = %d\n", result);
    // printf("leftRm = %d\n", leftRm);
    // printf("leftAdd = %d\n", leftAdd);
    }
    printf("%d", result);
    }

  • -1
    @ 2021-12-12 18:51:16

    啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊,怎么这么难~~

  • -4
    @ 2017-05-14 19:24:47

    var a,b:longint;
    begin
    read(a,b);
    write(a+b);
    end.

  • -5
    @ 2016-01-10 18:25:19

    虽然我没有AC但我来抢个沙发

  • -6
    @ 2017-01-07 12:38:32

  • -6
    @ 2017-01-07 12:37:22

  • -6
    @ 2017-01-07 12:37:09

    1

  • -6
    @ 2017-01-07 12:36:27

  • -6
    @ 2017-01-07 12:34:05

  • -6
    @ 2017-01-07 12:33:06

    *This is *
    vijos!!!

  • -6
    @ 2017-01-07 12:32:29

    hfhsgfdagajsgasga

  • -6
    @ 2017-01-07 12:32:12
    hhh
    
    

    hjdg

  • 1

信息

ID
1854
难度
7
分类
(无)
标签
递交数
78
已通过
16
通过率
21%
被复制
1
上传者