2023.11.5

有些仓促，若有错误欢迎指出

1、请找到一个大于 2022 的最小数，这个数转换成十六进制之后，所有的数位（不含前导 0）都为字母（A 到 F）。

// 输出后手动查找一下即可，应该是【2730】
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long LL;

int main()
{
    for(int i = 2023; i < 3000; i ++)
    {
        printf("%d == %x\n", i, i);
    }
    return 0;
}

2、在 Excel 中，列的名称使用英文字母的组合。前 26 列用一个字母，依次为 A 到 Z，接下来 26*26 列使用两个字母的组合，依次为 AA 到 ZZ。 　　

请问第 2022 列的名称是什么？

// 26进制，跑出来之后TYB需要反过来，因为是从低位到高位输出的，ans=【BYT】
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>

using namespace std;
typedef long long LL;

int main()
{
    int x = 2022;
    while(x)
    {
        cout << char(x%26+'A'-1) ;
        x /= 26;
    }
}

3、对于一个日期，我们可以计算出年份的各个数位上的数字之和，也可以分别计算月和日的各位数字之和。请问从 1900 年 1 月 1 日至 9999 年 12 月 31 日，总共有多少天，年份的数位数字之和等于月的数位数字之和加日的数位数字之和。 　　

例如，2022年11月13日满足要求，因为 2+0+2+2=(1+1)+(1+3) 。 　

请提交满足条件的日期的总数量。

// 直接算就好了  ans=【70910】
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long LL;

int days[30] = {0,31,30,31,30,31,30,31,31,30,31,30,31};

LL cal(LL x)
{
    LL cnt = 0;
    while(x)
    {
        cnt += x%10;
        x /= 10;
    }
    return cnt;
}

int main()
{
    LL ans = 0;
    LL sumY = 0, sumD = 0;
    for(LL i = 1900; i <= 9999; i ++)
    {
        sumY = cal(i);
        if((i%400 == 0) || (i%4 == 0 && i%100 != 0))
             days[2] = 29;
        else days[2] = 28;

        for(LL j = 1; j <= 12; j ++)
        {
            for(LL k = 1; k <= days[j]; k ++)
            {
                sumD = cal(j) + cal(k);
                if(sumD == sumY) ans ++;
            }

        }
    }

    cout << ans;

    return 0;
}

4、小蓝有 30 个数，分别为：99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。 　　

小蓝可以在这些数中取出两个序号不同的数，共有 30*29/2=435 种取法。 　　

请问这 435 种取法中，有多少种取法取出的两个数的乘积大于等于 2022 。

// 从前往后取，不重复  ans=【189】
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long LL;

int num[50] = {99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77};

int main()
{
    LL ans = 0;
    for(int i = 0; i < 29; i ++)
    {
        for(int j = i+1 ; j < 30; j ++)
        {
            if(num[i] * num[j] >= 2022)
                ans += 1;
        }
    }

    cout << ans ;
    return 0;
}

5、小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1 。

如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。请问矩阵中最大的连通分块有多大？

// 求最大连通分量，DFS、BFS均可，直接搜索答案，ans=【148】
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

char maze[65][65] =
{
"110010000011111110101001001001101010111011011011101001111110",
"010000000001010001101100000010010110001111100010101100011110",
"001011101000100011111111111010000010010101010111001000010100",
"101100001101011101101011011001000110111111010000000110110000",
"010101100100010000111000100111100110001110111101010011001011",
"010011011010011110111101111001001001010111110001101000100011",
"101001011000110100001101011000000110110110100100110111101011",
"101111000000101000111001100010110000100110001001000101011001",
"001110111010001011110000001111100001010101001110011010101110",
"001010101000110001011111001010111111100110000011011111101010",
"011111100011001110100101001011110011000101011000100111001011",
"011010001101011110011011111010111110010100101000110111010110",
"001110000111100100101110001011101010001100010111110111011011",
"111100001000001100010110101100111001001111100100110000001101",
"001110010000000111011110000011000010101000111000000110101101",
"100100011101011111001101001010011111110010111101000010000111",
"110010100110101100001101111101010011000110101100000110001010",
"110101101100001110000100010001001010100010110100100001000011",
"100100000100001101010101001101000101101000000101111110001010",
"101101011010101000111110110000110100000010011111111100110010",
"101111000100000100011000010001011111001010010001010110001010",
"001010001110101010000100010011101001010101101101010111100101",
"001111110000101100010111111100000100101010000001011101100001",
"101011110010000010010110000100001010011111100011011000110010",
"011110010100011101100101111101000001011100001011010001110011",
"000101000101000010010010110111000010101111001101100110011100",
"100011100110011111000110011001111100001110110111001001000111",
"111011000110001000110111011001011110010010010110101000011111",
"011110011110110110011011001011010000100100101010110000010011",
"010011110011100101010101111010001001001111101111101110011101"
};

int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

struct pos
{
    int x, y;
};

LL bfs(int i, int j)
{
    LL cnt = 0;

    queue<pos> r;
    r.push({i, j});
    maze[i][j] = '0';
    cnt ++;

    while(r.size())
    {
        pos t = r.front(); r.pop();

        for(int i = 0; i < 4; i ++)
        {
            int x = t.x + dir[i][0];
            int y = t.y + dir[i][1];

            if(x < 0 || y < 0 || x >= 30 || y >= 60) continue;

            if(maze[x][y] == '1')
            {
                maze[x][y] = '0';
                r.push({x,y});
                cnt ++;
            }
        }

    }
    return cnt;
}

int main()
{
    LL ans = 0;
    for(int i = 0; i < 30; i ++)
    {
        for(int j = 0; j < 60; j ++)
        {
            if(maze[i][j] == '1')
                ans = max(ans, bfs(i, j));
        }
    }

    cout << ans;
    return 0;
}

6、给定一天是一周中的哪天，请问 n 天后是一周中的哪天？

/*
样例输入
6
10
样例输出
2
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

int main()
{
    LL a, b;
    cin >> a >> b;

    LL ans = (a+b)%7;
    if(ans == 0) ans = 7;

    cout << ans;
    return 0;
}

7、信号塔覆盖圆形区域，问总共覆盖多少整数点，去重统计即可，数据范围不大

/*
样例输入
10 10 2 5
0 0
7 0
样例输出
57
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

int mp[110][110];

int main()
{
    LL w, h, t, r;
    LL ans = 0;

    cin >> w >> h >> t >> r;

    while(t--)
    {
        LL x, y; cin >> x >> y;
        for(int i = 0; i <= w; i ++)
        {
            for(int j = 0; j <= h; j ++)
            {
                LL dis = (i-x)*(i-x) + (j-y)*(j-y);
                if(dis <= r*r && !mp[i][j])
                {
                    ans ++;
                    mp[i][j] = 1;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

8、清理方形区域，数据范围不大，遍历即可（数据范围大的话用前缀和数组）

/*
样例输入
30 20
2
5 5 10 15
6 7 15 9
样例输出
519
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

int mp[110][110];

int main()
{
    int n, m, t;
    int r1, c1, r2, c2;
    LL ans = 0;

    cin >> n >> m >> t;
    while(t--)
    {
        cin >> r1 >> c1 >> r2 >> c2;
        for(int i = r1; i <= r2; i ++)
        {
            for(int j = c1; j <= c2; j ++)
            {
                mp[i][j] = 1;
            }
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(!mp[i][j]) ans ++;
        }
    }

    cout << ans;

    return 0;
}

9、滑雪，每次向上下左右小于当前的数字滑；

记忆化搜索即可

/*
样例输入
4 5
1 4 6 3 1
11 8 7 3 1
9 4 5 2 1
1 3 2 2 1
样例输出
7
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

LL mp[105][105], dp[105][105], ans = 0;
int n, m;

LL solve(int i, int j){
    if(dp[i][j]) return dp[i][j];
    dp[i][j] = 1;
    if(mp[i-1][j] < mp[i][j] && i-1 >= 1)dp[i][j] = max(dp[i][j], solve(i-1, j)+1);
    if(mp[i+1][j] < mp[i][j] && i+1 <= n)dp[i][j] = max(dp[i][j], solve(i+1, j)+1);
    if(mp[i][j-1] < mp[i][j] && j-1 >= 1)dp[i][j] = max(dp[i][j], solve(i, j-1)+1);
    if(mp[i][j+1] < mp[i][j] && j+1 <= m)dp[i][j] = max(dp[i][j], solve(i, j+1)+1);
    return dp[i][j];
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> mp[i][j];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            ans = max(ans, solve(i, j));

    cout << ans;
    return 0;
}

10、求当前数字前K个和后K个中的最小值；用单调队列或者滑动窗口

/*
样例输入
5
5 2 7 4 3
1
样例输出
2 2 2 3 3
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

const int N = 1000010*2, INF = 0x3f3f3f3f;

int n, k;
struct node
{
    int w, id;
}a[N];

deque<node> r;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].w;
        a[i].id = i;
    }
    cin >> k;

    for(int i = n+1; i <= n+k; i++)
    {
        a[i].id = i;
        a[i].w = INF;
    }
    for(int i = 1; i <= n+k; i++)
    {
        while(r.size() && r.back().w >= a[i].w)
        {
            r.pop_back();
        }
        r.push_back(a[i]);
        if(r.front().id <= i-2*k-1) r.pop_front();
        if(i >= k+1) cout << r.front().w << " ";
    }

}

11、给定绳子长度问对折多少次后长度小于1 （每次对折长度变为对折前1/2）

/*
样例输入
256
样例输出
8
样例输入
257
样例输出
9
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef long long LL;

int main()
{
    double len;
    cin >> len;

    LL ans = 0;
    while(len > 1.0)
    {
        len /= 2; ans++;
    }
    cout << ans;
}

12、给定一个由大写字母组成的长度为 n 的字符串，请在字符串中删除 m 个字符，使得剩下的字符串的字典序最小。

用单调栈维护即可

/*
样例输入
7 3
LANQIAO
样例输出
AIAO
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>

using namespace std;
typedef long long LL;

stack<char> r;
stack<char> ans;

int main()
{
    LL n, m;
    string s;

    cin >> n >> m >> s;

    for(int i = 0; i < n; i ++)
    {
        while(m > 0 && r.size() && r.top() > s[i])
        {
            r.pop();
            m -= 1;
        }
        r.push(s[i]);
    }



    while(r.size())
    {
        ans.push(r.top());
        r.pop();
    }

    while(ans.size())
    {
        cout << ans.top();
        ans.pop();
    }
    return 0;
}