GESP 4级¶

B3939 [GESP样题四级] 绝对素数¶

B3940 [GESP样题四级] 填幻方¶

B3850 [GESP202306 四级] 幸运数¶

提示

// 按字符串读入处理

// 数位拆分

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    while (n--) {
        string s;
        cin >> s;

        int sum = 0;
        for (int i = s.size() - 1, j = 1; i >= 0; i--, j++) {
            int t = s[i] - '0';

            if (j % 2) {
                t *= 7;
                while (t > 9) {
                    int x = 0;
                    while (t) {
                        x += t % 10;
                        t /= 10;
                    }
                    t = x;
                }
            }

            sum += t;
        }

        if (sum % 8 == 0) cout << 'T' << endl;
        else cout << 'F' << endl;
    }

    return 0;
}

B3851 [GESP202306 四级] 图像压缩-好题多练¶

提示

// 输入n行偶数长度的字符串，每两位表示一个灰色

// 要统计数量最多的前16种灰色，然后把现有的这些灰色向选出来的16种靠拢。

// 思路，使用.substr()来拆出来每两位的字符串，map维护出现次数

// 把string,次数，存到一个结构体里，进行自定义排序，选出来前16种

// 重新遍历一遍之前的二维数组，每两位进行替换，替换的过程可以直接枚举16种，和哪个更接近。即可

代码

#include <bits/stdc++.h>

using namespace std;

string g[25], ans[25];
int n;
map<string, int> mp;
string str = "0123456789ABCDEF";
struct node {
    string s;
    int cnt;
}a[300];

int to_num(string s) {
    return str.find(s[0]) * 16 + str.find(s[1]);
}

bool cmp(node a, node b) {
    if (a.cnt != b.cnt) return a.cnt > b.cnt;
    return a.s < b.s;
}

char check(string s) {
    int ret = 0;
    int delta = 0x3f3f3f3f;

    for (int i = 0; i < 16; i++) {
        int t = abs(to_num(s) - to_num(a[i].s));
        if (t < delta) {
            delta = t;
            ret = i;
        }
    }

    return str[ret];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> g[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0, len = g[i].size(); j < len; j += 2) {
            string t = g[i].substr(j, 2);
            mp[t]++;
        }
    }

    int idx = 0;
    for (auto x : mp) {
        a[idx].s = x.first, a[idx].cnt = x.second;
        idx++;
    }

    sort(a, a + idx, cmp);

    for (int i = 0; i < n; i++) {
        for (int j = 0, len = g[i].size(); j < len; j += 2) {
            string t = g[i].substr(j, 2);
            ans[i] += check(t);
        }
    }

    for (int i = 0; i < 16; i++) cout << a[i].s;
    puts("");
    for (int i = 0; i < n; i++) cout << ans[i] << '\n';

    return 0;
}

B3869 [GESP202309 四级] 进制转换¶

代码

// 转成10进制
#include <bits/stdc++.h>

using namespace std;

int n, k;
string s;
string ss = "0123456789ABCDEF";

int main() {
    cin >> n;
    while (n--) {
        cin >> k >> s;

        long long sum = 0, t = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            sum += t * ss.find(s[i]);
            t *= k;
        }

        cout << sum << endl;
    }

    return 0;
}

B3870 [GESP202309 四级] 变长编码-好题¶

提示

// 新定义，变长编码。

// 先转成二进制

// 每组7bit，划分成不同的组

// 从低位的每组开始，填补上第8位bit。如果是最高位的组，补0；其他补1

// 输出每一组，转换成2位16进制数，用空格隔开。

代码

#include <bits/stdc++.h>

using namespace std;

int a[100], idx;
string str = "0123456789ABCDEF";

int main() {
    long long n;
    cin >> n;

    if (n == 0) a[0] = 0, idx = 1;
    while (n) {
        a[idx++] = n % 2;
        n /= 2;
    }

    for (int i = 0; i < idx; i += 7) {
        int t[10];
        for (int j = 0; j < 7; j++) 
            if (i + j < idx) t[j] = a[i + j];
            else t[j] = 0;

        if (i + 7 < idx) t[7] = 1;
        else t[7] = 0;

        int x = t[0] + t[1] * 2 + t[2] * 4 + t[3] * 8;
        int y = t[4] + t[5] * 2 + t[6] * 4 + t[7] * 8;

        cout << str[y] << str[x] << ' ';
    }

    return 0;
}

提示02

// 官方题解给的示范代码，是用位运算来获取每7位的，& 0x7f

// 将第8位赋值成1，按位或，| 80

// 输出两位16进制数的时候，也采用了 &0x07 >>=4 这种操作

// 比较巧妙，学习了。代码比我这个简便

代码02

#include <bits/stdc++.h>

using namespace std;

int split[10], idx;
long long n;
string str = "0123456789ABCDEF";

int main() {
    cin >> n;

    if (n == 0) split[idx++] = 0;
    while (n) {
        split[idx++] = n & 0x7F;
        n >>= 7;
    }

    // 第8位置成 1
    for (int i = 0; i < idx - 1; i++) split[i] |= 0x80;

    for (int i = 0; i < idx; i++) {
        cout << str[split[i] >> 4] << str[split[i] & 0x0F] << ' ';
    }

    return 0;
}

B3927 [GESP202312 四级] 小杨的字典¶

提示

// 有翻译就翻，没有就输出UNK

// 抠单词，map

代码

#include <bits/stdc++.h>

using namespace std;

map<string, string> mp;

int main() {
    int n;
    cin >> n;
    while (n--) {
        string a, b;
        cin >> a >> b;
        mp[a] = b;
    }

    string s;
    cin >> s;
    for (int i = 0, len = s.size(); i < len; i++) {
        if (!(s[i] >= 'a' && s[i] <= 'z')) {cout << s[i]; continue;}

        string t;
        int j = i;
        while (j < len && s[j] >= 'a' && s[j] <= 'z') t += s[j++];

        if (mp.count(t) == 0) cout << "UNK";
        else cout << mp[t];

        // 此时j是第一个不是单词的位置
        i = j - 1;
    }

    return 0;
}

B3928 [GESP202312 四级] 田忌赛马¶

提示

贪心

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    int ret = 0;
    for (int i = 1, j = 1; i <= n; i++)
        if (a[i] > b[j]) ret++, j++;

    cout << ret;

    return 0;
}

B3958 [GESP202403 四级] 相似字符串-好题¶

提示

// 长度一样，看不同的元素是否<=1

// 长度相差1，就看少一个能不能匹配上(这个不好操作)

// 长度相差>1，直接不可能

// 长度相差1，用短去比大的，可能是子串，也可能是中间断开

// 中间断开的情况，就判断当前字符不同，如果和下一位也不同，就结束。

// 如果和下一位下同，则后面的所有字符都要相同

提示2

// 长度一样：

// 完全一样 s1 == s2

// 有一个不一样 for一遍看几个不一样

// 长度差1个：短的是长的一部分

// xxxxx. .find()

// .xxxxx

// xxx.xx 模拟一遍

代码

#include <bits/stdc++.h>

using namespace std;

int T;
string a, b;

bool check() {
    int lena = a.size(), lenb = b.size();
    if (abs(lena - lenb) > 1) return false;

    if (lena == lenb) {
        int cnt = 0;
        for (int i = 0; i < lena; i++) if (a[i] != b[i]) cnt++;
        return cnt <= 1;
    }
    else {
        if (lena > lenb) swap(a, b), swap(lena, lenb);

        int cnt = 0, i = 0, j = 0;
        while (i < lena && j < lenb) {
            if (a[i] != b[j]) cnt++, j++;
            else i++, j++;
        }

        return cnt <= 1;
    }

    return false;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> a >> b;
        if (check()) cout << "similar" << endl;
        else cout << "not similar" << endl;
    }

    return 0;
}

B3959 [GESP202403 四级] 做题¶

提示

// 排序，然后从前往后，贪心的选取

// 如果当前题目不够第i天使用的，就往后看

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    sort(a + 1, a + 1 + n);

    int ret = 0;
    for (int i = 1, k = 1; i <= n; i++) {
        if (a[i] >= k) ret = k++;
    }

    cout << ret;

    return 0;
}

B4005 [GESP202406 四级] 黑白方块¶

提示

// n,m <= 10，直接枚举所有子矩阵，\(O(n^6)\)

// 字符串读入

// 有类似问题，枚举所有子矩阵

代码

#include <bits/stdc++.h>

using namespace std;

string s[20];
int n, m, maxn;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int i2 = i; i2 < n; i2++)
                for (int j2 = j; j2 < m; j2++) {
                    int one = 0, zero = 0;
                    for (int p = i; p <= i2; p++)
                        for (int q = j; q <= j2; q++)
                            if (s[p][q] == '0') zero++;
                            else one++;

                    if (one == zero) maxn = max(maxn, one + zero);
                }

    cout << maxn;

    return 0;
}

B4006 [GESP202406 四级] 宝箱¶

提示

//保证价值对大切，x - y <= k;

代码

#include <bits/stdc++.h>

using namespace std;

int a[1010];
int tmp;

int main(){
    int n, k;
    cin >> n >> k;

    for(int i = 0 ; i < n; i++){
        cin >> a[i];
    }
    sort(a, a + n);
    for(int i = 0 ; i < n; i++){
        int j = 0;
        int sum = 0;
        while(abs(a[i] - a[i + j]) <= k && i + j < n){
            sum += a[i + j];    
            j++;
        }
        if(sum > tmp) tmp = sum; 
    }

    cout << tmp << '\n';

    return 0;
}

B4040 [GESP202409 四级] 黑白方块¶

提示

// 写一个check函数

代码

#include <bits/stdc++.h>

using namespace std;

char s[110][110];
int a[110][110], n, m, T;

bool check(int x, int y) {
    for (int j = y; j < y + 4; j++) if (a[x][j] || a[x + 3][j]) return false;
    for (int i = x; i < x + 4; i++) if (a[i][y] || a[i][y + 3]) return false;
    if (!a[x + 1][y + 1] || !a[x + 1][y + 2] || !a[x + 2][y + 1] || !a[x + 2][y + 2]) return false;
    return true;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> s[i];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) a[i][j] = s[i][j] - '0';

        bool flag = false;
        for (int i = 0; i < n - 3 && !flag; i++)
            for (int j = 0; j < m - 3 && !flag; j++) {
                if (check(i, j)) flag = true;
            }

        if (flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }


    return 0;
}

B4041 [GESP202409 四级] 区间排序¶

提示

// 用sort排序

代码

#include <bits/stdc++.h>

using namespace std;

int a[110], n, q, l, r;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    while (q--) {
        cin >> l >> r;
        l--, r--;
        sort(a + l, a + r + 1);
    }

    for (int i = 0; i < n; i++) cout << a[i] << ' ';


    return 0;
}

B4068 [GESP202412 四级] Recamán¶

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;

int a[N], n;
map<int, int> mp;

int main() {
    cin >> n;

    a[1] = 1;
    mp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int t = a[i - 1] - i;
        if (t > 0 && mp.count(t) == 0) a[i] = t;
        else a[i] = a[i - 1] + i;
        mp[a[i]] = 1;
    }

    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';

    return 0;
}

B4069 [GESP202412 四级] 字符排序¶

提示

// 对字符串进行排序，然后枚举一遍，是否满足升序的关系

代码

#include <bits/stdc++.h>

using namespace std;

int T, n;
string s[110];

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> s[i];

        sort(s, s + n);

        string t;
        for (int i = 0; i < n; i++) t += s[i];

        bool flag = false;
        for (int i = 1, len = t.size(); i < len; i++)
            if (t[i - 1] > t[i]) {flag = true; break;}

        if (flag) cout << 0 << endl;
        else cout << 1 << endl;
    }

    return 0;
}

B4263 [GESP202503 四级] 荒地开垦-代码难度较大¶

提示

// n,m <= 1000

// 这个题目读题上，会有一点困难，得理解理解让我们干什么

// 先把所有肯定可以开垦的统计处理

// 维护一遍，每一个杂物的位置，如果去掉它，可以增加几个可以开垦的荒地。打擂台求一个最值

// 答案就是，肯定能开垦的+新增的delta

// 写了一发，这个感觉代码实现，很费劲

代码

#include <bits/stdc++.h>

using namespace std;

string s[1010];
int n, m, cnt, maxn;

int check(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m) return 1;
    if (s[i][j] == '#') return 1;
    if (!(i == 0 || (i >= 1 && s[i - 1][j] == '.'))) return 1;
    if (!(i == n - 1 || (i < n - 1 && s[i + 1][j] == '.'))) return 1;
    if (!(j == 0 || (j >= 1 && s[i][j - 1] == '.'))) return 1;
    if (!(j == m - 1 || (j < m - 1 && s[i][j + 1] == '.'))) return 1;

    return 0;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            if (s[i][j] == '.') {
                if (!check(i, j)) cnt++;
            }
            else {
                int sum = 0;
                s[i][j] = '.';
                if (!check(i, j)) sum++;
                if (!check(i - 1, j)) sum++;
                if (!check(i + 1, j)) sum++;
                if (!check(i, j - 1)) sum++;
                if (!check(i, j + 1)) sum++;

                maxn = max(maxn, sum);
                s[i][j] = '#';
            }

    cout << cnt + maxn;

    return 0;
}

B4264 [GESP202503 四级] 二阶矩阵¶

提示

// 二维数组的枚举

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int a[N][N], n, m, cnt;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++) {
            if (a[i][j] * a[i + 1][j + 1] == a[i][j + 1] * a[i + 1][j]) cnt++;
        }

    cout << cnt;

    return 0;
}

B4360 [GESP202506 四级] 画布裁剪¶

提示

// 二维字符数组的读入(要注意正确的读入方式)

// 注意变量命名y1的问题，下标从0开始的问题

// 注意输入顺序

代码

#include <bits/stdc++.h>

using namespace std;

string s[110];
int n, m, xa, ya, xb, yb;

int main() {
    cin >> n >> m >> xa >> xb >> ya >> yb;
    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = xa - 1; i < xb; i++) {
        for (int j = ya - 1; j < yb; j++) cout << s[i][j];
        cout << endl;
    }

    return 0;
}

B4361 [GESP202506 四级] 排序¶

提示

// 定义结构体比较关系，用冒泡求逆序对

// 身高从高到低，体重从重到轻

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;

struct node{
    int h, w;
}a[N];

int n, cnt;

bool check(int i, int j) {
    if (a[i].h < a[j].h) return true;
    if (a[i].h == a[j].h) return a[i].w < a[j].w;
    return false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].h >> a[i].w;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n - 1; j++)
            if (check(j, j + 1)) swap(a[j], a[j + 1]), cnt++;

    cout << cnt;

    return 0;
}

B4415 [GESP202509 四级] 排兵布阵¶

提示

// n,m<=12，直接枚举

// n^2 * n^2 * n^2

代码

#include <bits/stdc++.h>

using namespace std;

int a[20][20], n, m;
int maxn;
int s[20][20];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int i2 = i; i2 <= n; i2++)
                for (int j2 = j; j2 <= m; j2++) {
                    int cnt = s[i2][j2] - s[i - 1][j2] - s[i2][j - 1] + s[i - 1][j - 1];
                    if (cnt == (i2 - i + 1) * (j2 - j + 1)) maxn = max(maxn, cnt);
                }

    cout << maxn;

    return 0;
}

B4416 [GESP202509 四级] 最长连续段¶

提示

排序，去重

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);

    int p = 1;
    for (int i = 1; i < n; i++)
        if (a[i] != a[i - 1]) a[p++] = a[i];
    n = p;

//  for (int i = 0; i < n; i++) cout << a[i] << ' ';

    int cnt = 1, maxn = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1] + 1) {
            cnt++;
            maxn = max(maxn, cnt);
        }
        else cnt = 1;
    }

    cout << maxn;

    return 0;
}

代码02

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;

int main() {
    cin >> n;

    vector<int> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];

    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());

    int cnt = 1, maxn = 1;
    for (int i = 1, n = A.size(); i < n; i++) {
        if (A[i] == A[i - 1] + 1) {
            cnt++;
            maxn = max(maxn, cnt);
        }
        else cnt = 1;
    }

    cout << maxn;

    return 0;
}

B4451 [GESP202512 四级] 建造¶

代码

#include <bits/stdc++.h>

using namespace std;

int m, n, h;
int a[1010][1010];
int ans;

int main() {
    cin >> m >> n >> h;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];

    for (int i = 1; i <= m - 2; i++)
        for (int j = 1; j <= n - 2; j++) {
            int maxn = -1, minn = 2e9, sum = 0;
            for (int ii = i; ii <= i + 2; ii++)
                for (int jj = j; jj <= j + 2; jj++) {
                    maxn = max(maxn, a[ii][jj]);
                    minn = min(minn, a[ii][jj]);
                    sum += a[ii][jj];
                }

            if (maxn - minn <= h) ans = max(ans, sum);
        }

    cout << ans;

    return 0;
}

B4452 [GESP202512 四级] 优先购买¶

提示

//小明有m元，商店有n个商品，卖东西的规律为：

//总是优先买优先级最高的东西；

//有多个最高优先级商品，购买价格最低的；

//有多个优先级最高且价格最低的商品，购买商品名字典序最小的。

//满足要求的，按字典序从小到大输出。

//利用结构体和自定义排序，将所有物品排好序，最后根据m循环统计输出