9.5 吉比特 游戏研发 AC1.5 求大佬第二题正解

第一题 字符串匹配问题

倒着匹配，就是起始点最大了

#include <iostream>
using namespace std;

int getRes(string& a, string& b) {
    int ind1 = a.size() - 1, ind2 = b.size() - 1;
    while(ind1 >=0 && ind2 >= 0) {
        if(a[ind1] == b[ind2])
            ind1--, ind2--;
        else ind1--;
    }
    return ind2 < 0 ? ind1+2 : 0;
}
int main() {
    string a, b;
    cin >> a >> b;
    int res = getRes(a, b);
    cout << res << endl;
    return 0;
}

第二题 修仙问题

无向图的遍历，不过我没有用到一个点可以经过两遍这个条件，默认只走一遍

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void dfs(vector<vector<pair<int,int>>>& grid, vector<int>& used, int cur, int sum, int count, int& res) {
    if(used[cur]++ == 0) count++;
    if(count == grid.size() - 1) {
        res = min(res, sum);
        return ;
    }
    if(used[cur] > 2) return ;

    for(int i=0; i<grid[cur].size(); i++)
        if(used[grid[cur][i].second] == 0) {
            sum += grid[cur][i].first;
            dfs(grid, used, grid[cur][i].second, sum, count, res);
        }
}

int main() {
    int n, m, x, y, c, res = 1e9;
    cin >> n >> m;
    vector<vector<pair<int,int>>> grid(n+1);
    for(int i=0; i<m; i++) {
        cin >> x >> y >> c;
        grid[x].push_back({c, y});
        grid[y].push_back({c, x});
    }
    for(int i=1; i<=n; i++) sort(grid[i].begin(), grid[i].end());

    for(int i=1; i<=n; i++) {
        vector<int> used(n+1, 0);
        dfs(grid, used, i, 0, 0, res);
    }
    if(res == 1e9) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}