网易 8.20 笔试

题目链接
题目顺序和链接里的图不是一样的, 顺序是链接里的 3 2 1 4

第一题

bfs 但是不知道哪有问题只过了 86.. 有无大佬帮忙找一下 bug

#include <bits/stdc++.h>

using namespace std;

//#define int long long

int a, b;

signed main()
{
    cin >> a >> b;
    queue<pair<int,int>> q;
    set<pair<int,int>> vis;
    int step = 0;
    q.push({a, b});
    vis.insert({a, b});
    for (; ;) {
        if (q.empty()) break;
        step++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto tmp = q.front(); q.pop();
            int ta = tmp.first, tb = tmp.second;
            //cout << ta << " " << tb << endl;
            if (ta == 0 || tb == 0 || ta % tb == 0 || tb % ta == 0) { 
                //cout << "finally: " << ta << " " << tb << endl;
                cout << step - 1 << endl; return 0;
            }
            int t = 10;
            while (ta >= t) {
                int na = ta / t * (t / 10) + ta % (t / 10);
                if (vis.find({na, tb}) == vis.end())
                {q.push({na, tb}); vis.insert({na, tb});}
                t = t * 10;
            }
            int na = ta / t * (t / 10) + ta % (t / 10);
            if (vis.find({na, tb}) == vis.end())
            {q.push({na, tb}); vis.insert({na, tb});}
            t = 10;
            while (tb >= t) {
                int nb = tb / t * (t / 10) + tb % (t / 10);
                if (vis.find({ta, nb}) == vis.end())
                { q.push({ta, nb}); vis.insert({ta, nb}); }
                t = t * 10;
            }
            int nb = (tb / t * (t / 10)) + (tb % (t / 10));
            if (vis.find({ta, nb}) == vis.end())
            { q.push({ta, nb}); vis.insert({ta, nb}); }
        }
        //cout << "----------------" << endl;
    }
    cout << -1 << endl;
    return 0;
}

第二题

扫一遍就行, 保证奇数偶数位都是最大的就行, 特判一下所有数相同的情况 就是那个数据量似乎比题面描述大.. 恶心了好长时间

#include <iostream>

using namespace std;

#define int long long

const int N = 2e5 + 5;

int n, a[N];

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int mx1 = 0, mx2 = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2) mx1 = max(mx1, a[i]);
        else mx2 = max(mx2, a[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (i % 2) res += mx1 - a[i];
        else res += mx2 - a[i];
    }
    if (mx1 == mx2) res += n / 2;
    cout << res << endl;
    return 0;
}

第三题

就贪心的把所有能改的都改了, 过了 37 代码忘存了, 反正也不会... 有无大佬来个思路

第四题

DP 过的比暴力少就离谱, 好歹暴力还过了 57 这里就只贴一下 DP 的代码, 希望有大佬帮找一下 bug

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 5;

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

signed main()
{
    int res = 0;
    map<int,int>mp;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (a[1] == a[3] and a[1] > a[2]) 
        f[3] = 1;
    mp[a[1]] = 1, mp[a[2]] = 2, mp[a[3]] = 3;
    for (int i = 3; i <= n; i++) {
        int last = mp[a[i]];
        f[i] = f[last];
       // if (i == 5) cout << f[i] << " " << f[last] << endl;
        for (int j = last + 1; j < i; j++) 
            if (a[j] < a[last]) f[i]++;
        mp[a[i]] = i;
        res += f[i];
        //if (i == 5) cout << res << endl;
    }
    cout << res << endl;
    return 0;
}