4.15 携程笔试 AK，附C++代码

1小时AK，简单分享下思路和代码。

第一题：模拟

计算同时包含 'y' 'o' 'u'三个字母 矩阵的总个数。

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

const int maxn = 1005;
char g[maxn][maxn];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < m; ++j) cin >> g[i][j];
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            unordered_set<char> st;
            st.insert(g[i][j]);
            st.insert(g[i][j + 1]);
            st.insert(g[i + 1][j]);
            st.insert(g[i + 1][j + 1]);
            if (st.count('y') && st.count('o') && st.count('u')) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

第二题：贪心

1. n为奇数，则 n/2 与 n/2 + 1互质，最小公倍数最大
2. n为偶数，从中间数 n/2开始枚举 a,b ，直到gcd(a,b) = 1

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

int main() {
    int t; cin >> t;
    while (t--) {
        long long n; cin >> n;
        if (n & 1) {
            cout << n / 2 << ' ' << n / 2 + 1 << endl;
        } else {
            for (long long i = n / 2; i < n; ++i) {
                if (gcd(i, n - i) == 1) {
                    cout << n - i << ' ' << i << endl;
                    break;
                }
            }
            
        }
    }
    return 0;
}

第三题：dfs枚举

题目数据量1000，可以考虑 复杂度

• 枚举每个节点做为根形成的满足条件的路径
• 注意数据范围，最大为, 超过范围提前终止，否则会产生错误结果。

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

typedef long long LL;
const int maxn = 1005;
LL n, l, r, ans = 0, inf = 1e15;
vector<int> g[maxn];
int w[maxn];

// 枚举以u为根的所有合法路径
void dfs(int u, LL val, int p) {
    val = (val << 1) | w[u];
    if (val > inf) return;	
    if (p != -1 && val >= l && val <= r) ans++;   // p != -1：排除单个节点的情况
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, val, u);
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 1; i <= n; ++i) {
        char ch; cin >> ch;
        w[i] = ch == '1';
    } 
    for (int i = 1; i <= n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) dfs(i, 0, -1);
    cout << ans << endl;
    return 0;
}

第四题：思维题，中心扩展

• 先计算单个段产生的结果, 如 0000或11111。 长度为, 则回文串个数为
• 考虑3个段、5个段...产生的结果， 如111001111 ，可以在 "0段"的左右两侧添加1构成新的回文串，如果左右两侧段的个数相同，考虑继续扩展， 直到边界或者左右个数不同

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

typedef long long LL;
const int maxn = 1005, mod = 1e9 + 7;
LL a[maxn];

int main() {
    int n; cin >> n;
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ans = (ans + (a[i] + 1) * a[i] / 2) % mod;
    }
    for (int i = 1; i < n - 1; ++i) {
        bool flag = true;
        int j = i - 1, k = i + 1;
        while (j >= 0 && k < n && flag) {
            ans = (ans + min(a[k], a[j])) % mod;
            if (a[j--] != a[k++]) flag = false;
        }
    }
    cout << ans << endl;
    return 0;
}