A、 国际旅行Ⅰ

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10, M = N * 2;
int a[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m, q; cin >> n >> m >> q;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
    }
    sort(a, a + n);
    while(q --){
        int x; cin >> x;
        cout << a[x - 1] << endl;
    }
    return 0;
}

D、 A*BBBB

参考
考虑具体的样例找到每一位上数字的规律

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10, M = N * 2;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t; cin >> t;
    while(t --) {
        string a, b; cin >> a >> b;
        int k = b[0] - '0', len = a.size() + b.size();
        reverse(a.begin(), a.end());
        string res = "";
        int l = 0; // 当前位的值
        for (int i = 0, sum = 0; i < len; i ++)
        {
            if (i < a.size()) sum += a[i] - '0';
            if (i >= b.size()) sum -= (a[i - b.size()] - '0');
            l += sum * k;
            res += l % 10 + '0';
            l /= 10;
        }
        while (res.size() > 1 && res.back() == '0') res.pop_back();
        reverse(res.begin(), res.end());
        cout << res << endl;
    }
    return 0;
}

E、 “好”字符

遍历所有的字符（最多26个），每次使用字符串哈希算法将对应的字符串处理成一个01串（和字符相等的为1），然后使用哈希O(1)内进行判断即可。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6 + 10, M = N * 2, P = 131;
ULL h1[M], h2[M], p[M];
int n;

void init(string s, char op, ULL h[])
{
    for (int i = 1; i < s.size(); i ++)
        h[i] = h[i - 1] * P + (s[i] == op);
}

ULL get(int l, int r, ULL h[])
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    string a, b; cin >> a >> b;
    set<char>st(a.begin(), a.end());

    a = " " + a + a;
    b = " " + b;

    p[0] = 1;
    for (int i = 1; i < N * 2; i ++)
        p[i] = p[i - 1] * P;

    int res = 0;
    for (auto ch : st)
    {
        // 分别处理a、b串
        init(a, ch, h1);
        init(b, ch, h2);
        for (int i = 1; i <= n; i ++)
            if (get(i, i + n - 1, h1) == get(1, n, h2)) {
                res ++;
                break;
            }
    }
    cout << res << endl;

    return 0;
}

F、 水灵灵的小学弟

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10, M = N * 2;

void solve()
{
    int a, b; cin >> a >> b;
//  if (a == b) {
//      cout << "DHY" << endl;
//      return;
//  }
//  if (a > b) swap(a, b);
//  int cnt = a - 2 + b - 1 + 2;
//  
//  if (cnt & 1) cout << "DHY" << endl;
//  else cout << "DHY" << endl;
    cout << "DHY" << endl;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t; cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

G、 lxy的通风报信

计算若干个点之间的最短距离，要想到最小生成树。本题首先通过bfs算法构建所有军队之间的边，然后使用kruskal算法找到最小生成树即为最短的合并代价。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
#define int long long
const int N = 1010, M = N * 2, INF = 0x7f7f7f7f;
char g[N][N];
int n, m;
vector<PII>node;
int dist[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int cnt, p[N * N];
bool st[N][N];

struct Edge
{
    PII a, b;
    int w;
    bool operator<(const Edge&T) const
    {
        return w < T.w;
    }
}e[N * N];

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

void bfs(int x, int y)
{
    memset(dist, -1, sizeof dist);
    dist[x][y] = 0;
    queue<PII>q;
    q.push({x, y});
    while(!q.empty()) {
        //TODO
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;

        for (int i = 0; i < 4; i ++)
        {
            int sx = x + dx[i], sy = y + dy[i];
            if (sx <= 0 || sx > n || sy <= 0 || sy > m || g[sx][sy] == '#' || dist[sx][sy] != -1) continue;
            dist[sx][sy] = dist[x][y] + 1;
            q.push({sx, sy});
        }
    }

    st[x][y] = true;
    for (int i = 0; i < node.size(); i ++)
        if (dist[node[i].first][node[i].second] != -1 && !st[node[i].first][node[i].second])
            e[cnt].a = {x, y}, e[cnt].b = node[i], e[cnt ++].w = dist[node[i].first][node[i].second];
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> g[i] + 1;

    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j ++)
            if (g[i][j] == '*') node.push_back({i, j});

    for (int i = 0; i < node.size(); i ++)
        bfs(node[i].first, node[i].second);

    // 注意这里
    for (int i = 1; i <= n * m + 10; i ++) p[i] = i;
    sort(e, e + cnt);
    int res = 0, c = 0;
    for (int i = 0; i < cnt; i ++)
    {
        int a = e[i].a.first * n + e[i].a.second, b = e[i].b.first * n + e[i].b.second;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            p[pa] = pb;
            res += e[i].w;
            c ++;
        }
    }

    if (c != node.size() - 1) cout << "No" << endl;
    else cout << res << endl;

    return 0;
}

H、 狼狼的备忘录

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
#define int long long
typedef long long LL;
const int N = 30, M = N * 2;

struct Node
{
    string name;
    set<string>s;
    bool operator<(const Node &T) const {
        return name < T.name;
    }
}a[N];

int get(string s)
{
    int res = 0;
    for (int i = 0; i < s.size(); i ++)
        res = res * 10 + (s[i] - '0');
    return res;
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n; cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        string name; cin >> name;
        bool flag = false;
        for (int j = 0; j < cnt; j ++) {
            if (a[j].name == name) {
                flag = true;
                int k; cin >> k;
                while(k --) {
                    string x; cin >> x;
                    a[j].s.insert(x);
                }
                break;
            }
        }
        if (!flag) {
            a[cnt].name = name;
            int k; cin >> k;
            while(k --) {
                string x; cin >> x;
                a[cnt].s.insert(x);
            }
            cnt ++;
        }
    }

    // 去重
    for (int i = 0; i < cnt; i ++)
    {
        vector<string>q;
        for (auto x1 : a[i].s) {
            for (auto x2 : a[i].s) {
                if (x1 != x2 && x1.size() < x2.size())
                {
                    bool flag = true;
                    for (int j = x1.size() - 1, k = x2.size() - 1; j >= 0; j --, k --)
                        if (x1[j] != x2[k]) {
                            flag = false;
                            break;
                        }
                    if (flag) q.push_back(x1);
                }
            }
        }
        for (auto x : q) a[i].s.erase(x);
    }

    sort(a, a + cnt);

    cout << cnt << endl;
    for (int i = 0; i < cnt; i ++) {
        cout << a[i].name << " " << a[i].s.size() << " ";
        for (auto x : a[i].s) cout << x << " ";
        cout << endl;
    }
    cout << endl;

    return 0;
}

I、 重生之zbk要拿回属于他的一切

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 1e5 + 10, M = N * 2;
string s, p = " chuan";
int ne[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _; cin >> _;
    cin >> s;
    s = " " + s;
    int n = p.size() - 1, m = s.size() - 1;

    for (int i = 2, j = 0; i <= n; i ++) 
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    int cnt = 0;
    for (int i = 1, j = 0; i <= m; i ++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == n) 
        {
            cnt ++;
            j = ne[j];
        }
    }

    cout << cnt << endl;

    return 0;
}

J、 这是签到

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set>

using namespace std;
#define PII pair<int,int>
typedef long long LL;
const int N = 10, M = N * 2, INF = 0x7f7f7f7f;
int a[N][N], res = INF;

void solve(int n)
{
    int p[N];
    for (int i = 1; i <= n; i ++) p[i] = i;
    int ans = 0;
    do{
        int cnt = 0;
        for (int i = 1; i <= n; i ++)
            for (int j = i + 1; j <= n; j ++)
                if (p[i] > p[j]) cnt ++;

        int r = 1;
        for (int i = 1; i <= n; i ++)
            r *= a[i][p[i]];
        if (cnt & 1) r = -r;
        ans += r;
    }while(next_permutation(p + 1, p + n + 1));

    res = min(res, ans);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> a[i][j];

    for (int i = 1; i <= max(n, m); i ++) {
        solve(i);
    }

    cout << res << endl;

    return 0;
}