4.15米哈游前端笔试-算法题部分-通俗易懂题解

一个数，从哪里劈开，两侧的差最小

第一题100，盲猜从中间分开，得到的差最小，因为两边此时位数最接近

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

typedef pair<int, int> pii;
typedef long long ll;
#define rep(i, start, end) for (int i = start; i <= end; i++)
#define lop(i, start, end) for (int i = start; i >= end; i--)
int main() {
    ios_base::sync_with_stdio(0);
    // freopen("t.in", "r", stdin);
    string s;
    cin >> s;
    string sl = s.substr(0, s.size() / 2), sr = s.substr(s.size() / 2);
    ll l = stoll(sl), r = stoll(sr);
    cout << l + r;
    return 0;
}

一个二维字符数组，I 和F相互抵消

第二题100，先标记，再清除即可（不能边遍历边处理，会影响后面的 反例是

3 4

FIF.

.FIF

.FFI

）

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

typedef pair<int, int> pii;
typedef long long ll;
#define rep(i, start, end) for (int i = start; i <= end; i++)
#define lop(i, start, end) for (int i = start; i >= end; i--)
int need[1005][1005];
int main() {
    ios_base::sync_with_stdio(0);
    // freopen("t.in", "r", stdin);//!!!提交前去掉
    // 消除每个I周围的F 消除每个F周围的I 不能直接遍历并修改,应该先扫描出要改的位置来,然后一起改
    // 还不对.... 找到bug!
    memset(need, 0, sizeof need);
    int n, m;
    cin >> n >> m;
    vector<string> g;
    rep(i, 1, n) {
        string tmp;
        cin >> tmp;
        g.push_back(tmp);
    }
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {
        1,
        -1,
        0,
        0,
    };
    // vector<vector<int>> need(n, vector<int>(m, 0));
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (g[i][j] == 'I') {
                rep(k, 0, 3) {
                    int xx = i + dx[k], yy = j + dy[k];
                    if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == 'F') {
                        need[xx][yy] = 1, need[i][j] = 1;
                    }
                }
            }
            if (g[i][j] == 'F') {
                rep(k, 0, 3) {
                    int xx = i + dx[k], yy = j + dy[k];
                    if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == 'I') {
                        need[xx][yy] = 1, need[i][j] = 1;
                    }
                }
            }
        }
    }

    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (g[i][j] == '.' || need[i][j] == 1) {
                cout << ".";
            } else {
                cout << g[i][j];
            }
        }
        cout << endl;
    }
    return 0;
}

第三题95，不知道哪里卡了，用数学方式推导

假定有一个数组ai i>=0,i<n；bi=ai + ai-1 我们知道全部的bi，请问ai有多少种可能的组合 n 1e5,bi 1e9

先写出前几项，找规律，若我们假定第一项是x，那么所有的ai都可以用b和x表示，因此我们需要让所有的ai大于0都成立，转化为了一系列关于x的方程组，均大于0；

那么多写几项有没有规律呢，有的，除了x的剩下部分，也就是前面的全b的部分挺相似的。即所有的奇数项，偶数项成等差数列；注意起始项不同，且奇数是－x，偶数是+ x

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

typedef pair<int, int> pii;
typedef long long ll;
#define rep(i, start, end) for (int i = start; i <= end; i++)
#define lop(i, start, end) for (int i = start; i >= end; i--)
int main() {
    ios_base::sync_with_stdio(0);
    // freopen("t.in", "r", stdin);
    // 数学?
    int n;
    cin >> n;
    vector<ll> b(n), t(n);
    rep(i, 0, n - 2) {
        cin >> b[i];
    }
    t[1] = b[0], t[2] = b[1] - b[0];
    ll up = LONG_LONG_MAX, down = LONG_LONG_MIN;
    for (int i = 3; i <= n; i += 2) {
        t[i] = b[i - 1] - b[i - 2] + t[i - 2];
    }
    for (int i = 4; i <= n; i += 2) {
        t[i] = b[i - 1] - b[i - 2] + t[i - 2];
    }

    for (int i = 1; i < n; i += 2) {
        up = min(up, t[i]);
    }
    for (int i = 2; i < n; i += 2) {
        down = max(down, -t[i]);
    }
    if (down < 0) {
        down = 0;
    }
    cout << up - down - 1;
    return 0;
}