阿里3.14笔试

T1

题目大意：给出一个16进制的字符串，要求统计其二进制表示中1的个数

len <= 2*10^5

//
// Created by 86139 on 2022/3/14.
//

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

/*
 * 0xeeeeedddddccccc11111
 * 45
 * */
using namespace std;

unordered_map<char, int> map;


int main() {
    map['0'] = 0;
    map['1'] = 1;
    map['2'] = 1;
    map['3'] = 2;
    map['4'] = 1;
    map['5'] = 2;
    map['6'] = 2;
    map['7'] = 3;
    map['8'] = 1;
    map['9'] = 2;
    map['a'] = 2;
    map['b'] = 3;
    map['c'] = 2;
    map['d'] = 3;
    map['e'] = 3;
    map['f'] = 4;

    string s;
    cin >> s;
    int ans = 0;
    for (int i = 2; i < s.size(); ++i) {
        cout << s[i] << ' ';
        ans += map[s[i]];
    }
    cout << ans << endl;
    return 0;
}

T2

题目大意：给出大小为n ∗ m 的01矩阵，从每个0的位置上下左右看，问所有在位置上下左右看一共能看到多少个1.(视线是一条直线)
n,m<=1e3

//
// Created by 86139 on 2022/3/14.
//

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 1010;
int q[N][N], l[N][N], r[N][N], u[N][N], d[N][N];
int n, m;

/*
2 4
0 1 0 0
1 0 1 0
 * */
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> q[i][j];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            l[i][j] = l[i][j - 1] | q[i][j];
            u[i][j] = u[i - 1][j] | q[i][j];
        }

    for (int i = n; i >= 1; --i)
        for (int j = m; j >= 1; --j) {
            r[i][j] = r[i][j + 1] | q[i][j];
            d[i][j] = d[i + 1][j] | q[i][j];
        }

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!q[i][j]) res += l[i][j] + r[i][j] + u[i][j] + d[i][j];
        }
    }
    cout << res << endl;
    return 0;
}

T3

​ 题目大意：你有一个8*8的棋盘，每个格子上的棋有rgb三种状态，你在上面玩消消乐(可能不是?)，每次选一个格子，将它的连通块全部消掉。消掉之后还指定了一种方向让所有棋子向一个方向下落。还有一种填充棋子的方法，需要你模拟这个过程(输出每次消除的棋子个数)。
opt < = 10000

//
// Created by 86139 on 2022/3/14.
//

/*
 *
2
rbbbrrrb
ggggbrbr
rrrggbrr
gbrgbrrr
bgbgrrrg
bgbgbrrb
rggrgggg
bgbrgrgr
bbrgggggbbgbbbrg
bbgbrgbgbbgbbbrg
brgbgbbggbbgbbbr
gbbgbbbrggrbbgrb
bgrbbrgggrbrgbrr
brgbrgbrgrgbrgbr
brbbrbbbrbrrggrg
ggrbrgbgbrgggrbr
1 5 w
1 4 d
 *
4
7
 * */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 10010;
int n, m;
int cnt;
char g[15][15];
string s[15];
int v[15][15];
int nw[15]; // 用于标记某行某列的元素适用情况
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};


void dfs(int x, int y);

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= 8; ++i)
        for (int j = 1; j <= 8; ++j)
            cin >> g[i][j];
    for (int i = 1; i <= 8; ++i) cin >> s[i];
    while (n --) {
        int x, y;
        char op;
        cin >> x >> y >> op;
        for (int i = 1; i <= 8; ++i)
            for (int j = 1; j <= 8; ++j)
                v[i][j] = 0;

        cnt = 0;
        dfs(x, y);
        printf("%d\n", cnt);

        if (op == 'w') {
            for (int j = 1; j <= 8; ++j) {  // 遍历每一列
                vector<char> tmp;
                tmp.clear();
                for (int i = 1; i <= 8; ++i) if (!v[i][j]) tmp.push_back(g[i][j]); // 将该列未标记的元素添加到tmp
                for (int i = 0; i < tmp.size(); ++i) g[i + 1][j] = tmp[i];  // 填充到上一列
                for (int i = tmp.size() + 1; i <= 8; ++i) g[i][j] = s[j][nw[j] ++]; // 填补下面的空格，s[j][nw[j]++]表示第j行的第nw[j]个元素
            }
        } else if (op == 's') {
            for (int j = 1; j <= 8; ++j) {
                vector<char> tmp;
                tmp.clear();
                for (int i = 1; i <= 8; ++i) if (!v[i][j]) tmp.push_back(g[i][j]);
                for (int i = 8, k = tmp.size() - 1; k >= 0; --i, --k) g[i][j] = tmp[k];
                for (int i = 8 - tmp.size(); j >= 1; --j) g[i][j] = s[j][nw[j]++];
            }
        } else if (op == 'a') {
            for (int i = 1; i <= 8; ++i) {
                vector<char> tmp;
                tmp.clear();
                for (int j = 1; j <= 8; ++j) if (!v[i][j]) tmp.push_back(g[i][j]);
                for (int j = 0; j < tmp.size(); ++j) g[i][j + 1] = tmp[j];
                for (int j = tmp.size() + 1; j <= 8; ++j) g[i][j] = s[i][nw[i]++];
            }
        } else if (op == 'd') {
            for (int i = 1; i <= 8; ++i) {
                vector<char> tmp;
                tmp.clear();
                for (int j = 1; j <= 8; ++j) if (!v[i][j]) tmp.push_back(g[i][j]);
                for (int j = 8, k = tmp.size() - 1; k >= 0; --j, --k) g[i][j] = tmp[k];
                for (int j = 8 - tmp.size(); j >= 1 ; --j) g[i][j] = s[i][nw[i]++];
            }
        }
    }
    return 0;
}

// 标记连通块
void dfs(int x, int y) {
    v[x][y] = 1;
    cnt ++;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > 8 || ny < 1 || ny > 8 || v[nx][ny] || g[x][y] != g[nx][ny]) continue;
        dfs(nx, ny);
    }
}