牛客周赛 Round 63

iter / 2024-10-14 / 原文

A.小红的好数

题意:

满足数位为2, 且个位数和十位数相等

思路:

通过输入字符串, 首先判断字符串的个数是否为2, 在判断个位数和十位数是否相等

复杂度:

O(1)

Code:

#include <bits/stdc++.h>
    
using namespace std;
using i64 = int64_t;  

void solve() {
    string s;
    cin >> s;
    if (s[0] == s[1] && s.size() == 2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B.小红的好数组

题意:

找到区间为k长度的连续区间且不是回文数组但是可以修改一次得到回文数组, 计算当前满足回文数组条件的个数

思路:

直接暴力枚举长度为k的连续区间, 判断是否修改一次满足是回文数组

复杂度:

O(n * k)

Code:

#include <bits/stdc++.h>
 
using namespace std;
using i64 = int64_t;
    
void solve() {
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i <= n - k; i++) {
        vector <int> b(a.begin() + i, a.begin() + i + k);
        int cnt = 0; 
        for (int l = 0, r = k - 1; l < r; l ++, r --) {
            if (b[l] != b[r]) {
                cnt++;
                if (cnt > 1) { 
                    break;
                }
            } 
        }
        if (cnt == 1) {
            ans++;
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C.小红的矩阵行走

题意:

从(0, 0)出发, 只能走下或右且每走一步都收集数字, 走到(n - 1, m - 1)且所有收集的数字都是相同的

思路:

一道基础的板子题，写法很多

Code:

#include <bits/stdc++.h>
    
using namespace std;
using i64 = int64_t; 
constexpr int N = 1e2 + 5;
int dirs[3] = {1, 0, 1}, n, m, a[N][N];
bool ok = 1;

bool check (int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void dfs (int x, int y) {
    if (x == n - 1 && y == m - 1) {
        ok = 0;
        return ;
    }
    for (int i = 0; i < 2; i++) {
        int dx = dirs[i] + x, dy = dirs[i + 1] + y;
        if (check(dx, dy) && a[dx][dy] == a[0][0]) { 
            dfs(dx, dy);
        }
    }
}

void solve() { 
    cin >> n >> m; 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    } 
    ok = 1;
    dfs(0, 0);
    cout << (!ok? "Yes" : "No") << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
    
using namespace std;
using i64 = int64_t; 
constexpr int N = 1e2 + 5;
int dirs[3] = {1, 0, 1}, a[N][N], n, m;

bool check (int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

void solve() { 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    queue <pair<int, int>> q;
    q.push({0, 0});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == n - 1 && y == m - 1) {
            cout << "Yes" << '\n';
            return ;
        }
        for (int i = 0; i < 2; i++) {
            int dx = dirs[i] + x, dy = dirs[i + 1] + y;
            if (check(dx, dy) && a[dx][dy] == a[0][0]) {
                q.push({dx, dy});
            }
        }
    }
    cout << "No" << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
    
using namespace std;
using i64 = int64_t;
constexpr int N = 1e2 + 5; 
int n, m, dp[N][N], a[N][N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            dp[i][j] = 0;
        }
    }
    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            if (a[i][j] != a[1][1]) continue; 
            dp[i][j] = (i > 1 ? dp[i - 1][j] : 0) || (j > 1 ? dp[i][j - 1] : 0);
        }
    }
    cout << (dp[n][m] ? "Yes" : "No") << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D:小红的行列式构造

题意:

构造一个3阶行列式, 满足每个元素的绝对值不小于1, 且最后的值等于x

思路:

[a, b, c]
[d, e, f]
[g, h, i]

-> a * e * i + b * f * g + c * d * h - a * f * h - b * d * i - c * e * g
-> a * (e * i - f * h) + b * (f * g - d * i) + c * (d * h - e * g)

假设 a, b, c都是相同的, 那么我们令它们为1
-> 1 * (e * i - f * h) + 1 * (f * g - d * i) + 1 * (d * h - e * g)
-> d * (h - i) + e * (g - i) + f * (g - h)

如果假设d, e, f都是相同导致最终的结果为0, 也就是得到一个结论
如果a, b, c相同且d, e, f相同最终结果一定为0

那么我们只能在d, e, f挑不是相同, 那么e, f 为1, d为2, 通过计算式子可以得到
-> 2 * (h - i) + 1 * (g - i) + 1 * (g - h)
-> 2 * (h - i) + g - i - g + h - i
-> 2 * (h - i) + 0
h - i = x 那么只要满足这个式子都可以, 那么我可以假设i = 101那么我的h就是x + 101
为什么不能是x + (值 < 101) 是因为行列式的值的绝对值需要大于等于x也就因为这, 最小情况只能是[g, x + 101 x]
其次发现g在这个式子是直接被约掉的, 那么abs(g) >= 1的值都可以 
那么这题就顺利解决了

Code:

#include <bits/stdc++.h>
    
using namespace std;
using i64 = int64_t;  

void solve() {
    int x;
    cin >> x;
    if (x == 0) {
        cout << "1 1 1\n1 1 1\n1 1 1\n";
    } else {
        cout << "1 1 1\n2 1 1\n" << 2 << ' ' << x * 2 << ' ' << x << '\n';
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}