9月8号鹰角技术笔试AK代码

好不容易ak一次， 给自己攒点人品
1.第一题，因数分解, 有9都ok，有3只能找3和9，啥也没有只能找9.

#define ll long long
long long cnt(vector<int>& nums){
    int a[3] = {0};
    ll ans = 0;
    for(auto& num : nums){
        if(num % 9 == 0){
            ans += a[0] + ans[1] + ans[2];
            ++ans[2];
        }
        else if(num % 3 == 0){
            ans += a[1] + a[2];
            ++ans[1];
        }
        else{
            ans += a[2];
            ++a[0];
        }
    }
    return ans;
}

2.第二题，模拟，没啥好说的，注意越界和统计开始的数目（题目没有说开始都大于0）

int leftCnt(vector<vector<int>> &a, int k, vector<vector<int>>& attacks){
    int ans = 0, m = a.size(), n = a[0].size();
    for(auto& row : a){
        for(auto& num : row){
            if(num > 0)++ans;
        }
    }

    int range[8][2] = {
        {-1, -1}, {-1, 0}, {-1, 1}, 
        {0, -1}, {0, 1}, 
        {1, -1}, {1, 0}, {1, 1}, 
    };
    int aoe = (3 * k) / 2, cur = 0; // 有效攻击次数，注意不能像剑圣双刀被动那样，这里被动不会积攒次数
    for(auto& pos : attacks){
        int x = pos[0] - 1, y = pos[1] - 1;
        if(a[x][y] <= 0)continue;
        if(cur == 2){
            a[x][y] -= 3 * k;
            if(a[x][y] <= 0)--ans;
            for(auto& s : range){
                int nx = x + s[0], ny = y + s[1];
                if(nx < 0 || nx >= m || ny < 0 || ny >= n || a[nx][ny] <= 0)continue;
                a[nx][ny] -= aoe;
                if(a[nx][ny] <= 0)--ans;
            }
            cur = 0;
        }
        else{
            a[x][y] -= k;
            if(a[x][y] <= 0)--ans;
            ++cur;
        }
    }
    return ans;
}

3.bfs暴搜，9位26进制数记录状态

#define ll long long

void swap(int& a, int& b){
    a += b;
    b = a - b;
    a -= b;
}

ll calc(vector<string>& mat){
    ll ans = 0;
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j)
            ans = ans * 26 + mat[i][j] - 'a';
    }
    return ans;
}

bool isqualified(vector<string>& mat){
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            if(i + 1 < 3 && mat[i][j] == mat[i + 1][j])return false;
            if(j + 1 < 3 && mat[i][j] == mat[i][j + 1])return false;
        }
    }
    return true;
}

vector<int> swapcnt(vector<vector<string>>& matrixs){
    vector<int> ans;
    for(auto& mat : matrixs){
        map<ll, int> mp;
        mp[calc(mat)] = 1;
        queue<vector<string>> q;
        q.push(temp);
        int op = 0;bool flag = false;
        while(!q.empty()){
            ll len = q.size();
            while(len--){
                auto temp = q.front();
                q.pop();
                if(isqualified(mat)){
                    flag = true;
                    break;
                }
                for(int i = 0; i < 3; ++i){
                    for(int j = 0; j < 3; ++j){
                        if(i + 1 < 3){
                            swap(temp[i][j], temp[i + 1][j]);
                            ll val = calc(temp);
                            if(mp.count(val) == false){
                                mp[val] = 1;
                                q.push(temp);
                            }
                            swap(temp[i][j], temp[i + 1][j]);
                        }
                        if(j + 1 < 3){
                            swap(temp[i][j], temp[i][j + 1]);
                            ll val = calc(temp);
                            if(mp.count(val) == false){
                                mp[val] = 1;
                                q.push(temp);
                            }
                            swap(temp[i][j], temp[i][j + 1]);
                        }
                    }
                }
            }
            if(flag)break;
            ++op;
        }
        if(flag)
            ans.push_back(op);
        else
            ans.push_back(-1);
    }
    return ans;
}