【AK】2023/10/9深信服技术笔试F卷

T1 循环节

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1e18;

const int N = 1e6;

int rec[N], idx = 1;
unordered_map<int, int> mp;

int main() {
    int a, b;
    cin >> a >> b;
    long long ret = a;
    mp[a % 10] ++ ;
    rec[0] = a % 10;
    rec[idx] = a % 10;
    for(int i = 2; i <= b; i ++) {
        ret *= a;
        if(mp.count(ret % 10)) {
            break;
        }
        mp[ret % 10] ++ ;
        rec[++ idx] = ret % 10;
        ret %= 10;
    }

    cout << rec[b % idx == 0 ? idx : b % idx] << endl;

    return 0;
}

T2 01背包

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    vector<int> times;
    vector<int> score;
    int t;
    t = stoi(c);

    a += ',', b += ',';

    int rec = 0;
    for (char i : a) {
        if (i == ',') times.push_back(rec), rec = 0;
        else rec = rec * 10 + (i - '0');
    }

    rec = 0;
    for (char i : b) {
        if (i == ',') score.push_back(rec), rec = 0;
        else rec = rec * 10 + (i - '0');
    }

    vector<vector<int>> f = vector<vector<int>> (times.size() + 10, vector<int>(t + 10));

    for(int i = 1; i <= times.size(); i ++) {
        int x = times[i - 1], y = score[i - 1];
        for(int j = 0; j <= t; j ++) {
            if(j < x) f[i][j] = max(f[i][j], f[i - 1][j]);
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - x] + y);
        }
    }

    cout << f[times.size()][t] << endl;
    return 0;
}

T3 双指针、哈希表

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> nums;
    int x;
    while(cin >> x) {
        nums.push_back(x);
    }

    unordered_map<int, int> mp;

    int ans = 0;
    for(int i = 0, j = 0; i < nums.size(); i ++) {
        mp[nums[i]] ++ ;
        while(mp[nums[i]] > 1) {
            if(-- mp[nums[j ++]] == 0) mp.erase(nums[j - 1]);
        }

        ans = max(ans, (int)mp.size());
    }

    cout << ans << endl;
    return 0;
}

T4 DP

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n, m, k;
long long g[N][N];

int main() {
    cin >> k >> n >> m;

    if(k < n + m) cout << 0 << endl;
    else {
        g[0][0] = 1;
        for(int i = 0; i <= n; i ++) {
            for(int j = 0; j <= m; j ++) {
                if(i > 0) g[i][j] += g[i - 1][j];
                if(j > 0) g[i][j] += g[i][j - 1];
            }
        }
        cout << g[n][m] << endl;
    }
    return 0;
}