cpp-exam-1

啊，第一次机考就这么结束了，代码框架逻辑在1h25mins左右写完。

然后获分35分，于是进入了debug阶段，然后分数越改越少，主要是我把一些函数和变量给及乱了。

我的代码有点丑，还很长！不过思路是很简单的！但是最终还是没调对，于是就只有35分了！！！有点可惜，不过也确实，好久都没有写过算法题，没有用cpp刷题玩了，最近事有点多。

然后周五还有个字节的面试，估计面试官面完我后就会觉得，这什么垃圾居然能来面试，怎么敢的鸭！

不过我还是想获得微软的explorer program得offer，可惜居然面试都没给我，太难了！

好了，贴个改正后的代码放下面划水了。

---

题目：cpp-exam-1

鬼知道我居然能些297行！然后疯狂debug，面向脑容量编程，都记不住了！！！

---

2021-04-29

好家伙，得分都出来了，我是菜鸡！

助教跟新了test-case: test-case-1

#include <iostream>
#include <string>
using namespace std;

struct RNode {
    int size = -1;
    int rowHead = -1;
    int rowTail = -1;
};

using RowInfor = struct RNode*;

int heapSize, objCnt, N;
string strs[10000];
RowInfor rowInfor = new struct RNode[2500];




string int2Bit(int num)
{
    string ret;
    for (int i = 0; i <= 31; ++i) {
        if (num % 2 == 0) {
            ret += '0';
        }
        else {
            ret += '1';
        }
        num >>= 1;
    }
    string res;
    for (int i = 31; i >= 0; --i) {
        res += ret[i];
    }
    return res;
}


string bit2Hex(string s)
{
    string ret;
    for (int i = 0; i <= 7; ++i) {
        string tmp;
        for (int j = i * 4; j <= i * 4 + 3; ++j) {
            tmp += s[j];
        }
        if (tmp == "0000") {
            ret += "0";
        }
        else if (tmp == "0001") {
            ret += "1";
        }
        else if (tmp == "0010") {
            ret += "2";
        }
        else if (tmp == "0011") {
            ret += "3";
        }
        else if (tmp == "0100") {
            ret += "4";
        }
        else if (tmp == "0101") {
            ret += "5";
        }
        else if (tmp == "0110") {
            ret += "6";
        }
        else if (tmp == "0111") {
            ret += "7";
        }
        else if (tmp == "1000") {
            ret += "8";
        }
        else if (tmp == "1001") {
            ret += "9";
        }
        else if (tmp == "1010") {
            ret += "a";
        }
        else if (tmp == "1011") {
            ret += "b";
        }
        else if (tmp == "1100") {
            ret += "c";
        }
        else if (tmp == "1101") {
            ret += "d";
        }
        else if (tmp == "1110") {
            ret += "e";
        }
        else {
            ret += "f";
        }
    }
    return ret;
}


string hex2Bit(string s) {
    //cout << s << endl;
    string ret;
    for (int i = 0; i <= 7; ++i) {
        if (s[i] == '0') {
            ret += "0000";
        }
        else if (s[i] == '1') {
            ret += "0001";
        }
        else if (s[i] == '2') {
            ret += "0010";
        }
        else if (s[i] == '3') {
            ret += "0011";
        }
        else if (s[i] == '4') {
            ret += "0100";
        }
        else if (s[i] == '5') {
            ret += "0101";
        }
        else if (s[i] == '6') {
            ret += "0110";
        }
        else if (s[i] == '7') {
            ret += "0111";
        }
        else if (s[i] == '8') {
            ret += "1000";
        }
        else if (s[i] == '9') {
            ret += "1001";
        } else if(s[i] == 'a') {
            ret += "1010";
        }
        else if (s[i] == 'b') {
            ret += "1011";
        }
        else if (s[i] == 'c') {
            ret += "1100";
        }
        else if (s[i] == 'd') {
            ret += "1101";
        }
        else if (s[i] == 'e') {
            ret += "1110";
        }
        else {
            ret += "1111";
        }
    }
    return ret;
}

int bit2Int(string s) {
    int ret = 0;
    int base = 1;
    for (int i = 28; i >= 0; --i) {
        if (s[i] == '1') {
            ret += base;
        }
        base *= 2;
    }
    return ret;
}



void Initialize(int row)
{
    int num = 4 * row - 8;
    string str_row0 = int2Bit(num);
    str_row0 = str_row0.substr(0, 29) + "000";
    strs[0] = bit2Hex(str_row0);
    strs[row - 1] = bit2Hex(str_row0);
    for (int i = 1; i <= row - 2; ++i) {
        strs[i] = "dfdfdfdf";
    }
}


void show(int row)
{
    for (int i = 0; i <= row - 1; ++i) {
        cout << strs[i] << endl;
    }
}


void freeMemory(int row, int objCnt, int id)
{
    if (id > objCnt || rowInfor[id-1].rowHead == -1) {
        cout << "invalid memory access" << endl;
    }
    else {
        heapSize += rowInfor[id - 1].size;
        string tmp = strs[rowInfor[id - 1].rowHead];
        tmp = hex2Bit(tmp);
        tmp[31] = '0';
        tmp = bit2Hex(tmp);
        strs[rowInfor[id - 1].rowHead] = tmp;
        strs[rowInfor[id - 1].rowTail] = tmp;
        rowInfor[id - 1].rowHead = -1;
        rowInfor[id - 1].rowTail = -1;
        cout << "succeeded to free object " << id << endl;
    }
}


void allocMemory(int row, int objCnt, int id, int size)
{
    if (id > objCnt || rowInfor[id - 1].rowHead != -1) {
        cout << "failed to alloc object " << id << endl;
    }
    else if (heapSize < size){
        cout << "failed to alloc object " << id << endl;
    }
    else {
        bool HAVE = false;
        for (int i = 0; i <= row - 1; ++i) {
//            cout << strs[i] << endl;
            string bits = hex2Bit(strs[i]);
            if (bits[31] == '0') { // ??? 内存访问异常？
                int bytes = bit2Int(bits) * 8;
                int j = i + bytes / 4 + 1;
                if (bytes >= size) {
                    // ok!
                    HAVE = true;
                    int rowHead = i;
                    int rowTail = i + size / 4 + 1;
                    rowInfor[id - 1].rowHead = rowHead;
                    rowInfor[id - 1].rowTail = rowTail;
                    rowInfor[id - 1].size = size;
                    heapSize -= size;
                    // TODO
                    string str = int2Bit(size / 8);
                    str = bit2Hex(str.substr(3, 32) + "001");
                    strs[rowHead] = str;
                    strs[rowTail] = str;
                    if (bytes > size) {
                        int nextRowHead = rowTail + 1;
                        int nextRowTail = j;
                        str = bit2Hex(int2Bit((bytes - size - 8) / 8).substr(3, 32) + "000");
                        strs[nextRowHead] = str;
                        strs[nextRowTail] = str;
                    }
                    cout << "succeeded to alloc object " << id << endl;
                    break;
                }
            }
        }
        if (!HAVE) {
            cout << "failed to alloc object " << id << endl;
        }
    }
    //show(row);
}


int up28(int num) {
    while (num % 8 != 0) {
        num += 1;
    }
    return num;
}

int main()
{
    cin >> heapSize >> objCnt;
    cin >> N;
    int row = heapSize >> 2;
    heapSize -= 8;
    Initialize(row);
    // show(row);
    while (N > 0) {
        // show(row);
        N -= 1;
        string instr;
        cin >> instr;
        if (instr == "SHOW") {
            show(row);
        }
        else if (instr == "FREE") {
            int id;
            cin >> id;
            freeMemory(row, objCnt, id);
        }
        else if (instr == "ALLOC") {
            int id, size;
            cin >> id >> size;
            size = up28(size);
            allocMemory(row, objCnt, id, size);
        }
    }
    return 0;
}