• 不知道是不是因为最后一次笔试，不太想要人了，感觉过于简单..

第一题 第i个盒子里有a[i]个b[i]的盒子 小模拟

#include <bits/stdc++.h>

using namespace std;
int const maxn = 1e5 + 10;
int const MOD = 1e9 + 7;
typedef long long ll;


ll ans[maxn];
ll a[maxn], b[maxn];
int n;
int main(void) {
    cin >> n;
    ans[1] = 1;
    for (int i = 2; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 2; i <= n; i++) {
        cin >> b[i];
    }

    for (int i = 2; i <= n; i++) {
        ans[i] = (a[i] * ans[b[i]]) % MOD;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }

    return 0;
}

第二题 字典序前100的全排列 dfs

#include <bits/stdc++.h>

using namespace std;
int const maxn = 1e5 + 10;
int const MOD = 1e9 + 7;
typedef long long ll;

vector<vector<int>> ans;
vector<int> v;
int vis[maxn];
int n;

void dfs(int step) {
    if (step >= n + 1) {
        ans.emplace_back(v);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            int pos = v.size() + 1;
            if (pos == i) continue;
            v.emplace_back(i);
            vis[i] = 1;
            dfs(step + 1);
            v.pop_back();
            vis[i] = 0;
        }
    }
}

int main(void) {
    cin >> n;

    dfs(1);

    cout << ans.size() << endl;
    sort(ans.begin(), ans.end());
    for (int i = 0; i < min((int)ans.size(), 100); i++) {
        for (auto &x : ans[i]) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

第三题 判断树 裸并查集 输入有点恶心

#include <bits/stdc++.h>

using namespace std;
int const maxn = 1e5 + 10;
int const MOD = 1e9 + 7;
typedef long long ll;

int fa[maxn];
int n, m;

void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find(int x) {
    if (x == fa[x]) {
        return x;
    }
    return fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
        return false;
    }
    return true;
}

void mergeEdge(string &s) {
    vector<int> v;
    int tmp = 0;
    for (auto &x : s) {
        if (x == ']' || x == ',') {
            v.emplace_back(tmp);
            tmp = 0;
            continue;
        }
        if (x >= '0' && x <= '9') {
            tmp = tmp * 10 + (x - '0');
        }
    }
    for (int i = 0; i < v.size(); i += 2) {
        int x = v[i], y = v[i + 1];
        merge(x, y);
    }
}

int main(void) {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        getchar();

        int flag = 0;
        if (n - 1 != m) {
            flag = 1;
        }
        string edgestr;
        getline(cin, edgestr);
        init(n);
        mergeEdge(edgestr);
        int dx = 0;
        for (int i = 1; i <= n; i++) {
            if (find(i) == i) {
                dx++;
                if (dx > 1) {
                    flag = 1;
                    break;
                }
            }
        }
        if (flag) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    }

    return 0;
}

第四题 a^x MOD m = y 最小的x

其实，不太会，然后想着拿快速幂去暴力下，骗一个分，结果居然过了，可能数据水了...

#include <bits/stdc++.h>

using namespace std;
int const maxn = 1e5 + 10;
int const MOD = 1e9 + 7;
typedef long long ll;

ll pow_mod(ll a, ll x, const ll &mod) {
    if (x == 0) return 1;
    ll ans = pow_mod(a, x >> 1, mod);
    ans = ans * ans % mod;
    if (x & 1 == 1) 
        ans = ans * a % mod;
    return ans;
}

int main(void) {
    int t;
    cin >> t;
    while (t--) {
        ll a, m, y;
        cin >> a >> m >> y;
        int ans = -1;
        for (int i = 0; i <= 100000; i++) {
            ll ret = pow_mod(a, i, m);
            if(ret == y) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }   

    return 0;
}

第五题 双端队列模拟 注意m的范围 对n离散化

#include <bits/stdc++.h>

using namespace std;
int const maxn = 1e5 + 10;
int const MOD = 1e9 + 7;
typedef long long ll;

struct node {
    int opt, id, sid;
};

int main(void) {
    int n, m;
    cin >> n >> m;
    vector<int> v;
    vector<node> opts;
    for (int i = 0; i < m; i++) {
        int opt, id, sid;
        cin >> opt;
        if (opt == 1) {
            cin >> id >> sid;
            v.push_back(id);
            opts.push_back({opt, id, sid});
        } else {
            cin >> id;
            v.push_back(id);
            opts.push_back({opt, id, -1});
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    n = v.size();
    vector<deque<int>> qs(n + 1);
    for (int i = 0; i < m; i++) {
        node o = opts[i];
        int opt = opts[i].opt, id = opts[i].id, sid = opts[i].sid;
        id = lower_bound(v.begin(), v.end(), id) - v.begin() + 1;
        if (opt == 1) {
            qs[id].push_back(sid);
        } else {
            if (qs[id].size() == 0) {
                cout << -1 << endl;
            } else {
                int ret = qs[id].front();
                qs[id].pop_front();
                cout << ret << endl;
            }
        }
    }


    return 0;
}