T1：Spelling Check

题意：

给定两个字符串，寻找上面字符串比下面多余的字母，并删除。如果不可以只删除一个字母来将上面的字符串变成下面的，就输出0即可。

思路：

双指针遍历两个字符串，找到第一个不同的位置，如果s[i] != t[j]，说明s[i] 是多出来的，记录位置i+1, 如果前面的字符串都是相同的，就记录最后一个n,去重输出。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    int p = 0;
    while (p < m && s[p] == t[p])
    {
        p++;
    }
    int q = 0;
    while (q < m && s[n - 1 - q] == t[m - 1 - q])
    {
        q++;
    }
    vector<int> ans;
    for (int i = 0; i < n; i++)
    {
        if (i <= p && n - 1 - i <= q)
        {
            ans.push_back(i + 1);
        }
    }
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
    {
        if (i > 0)
        {
            cout << " ";
        }
        cout << ans[i];
    }
    cout << "\n";
    
    return 0;
}

复制

T2：Prefix-Suffix Palindrome (Easy version)

题意：

给定一个字符串s，寻找满足条件的最长字符串t，条件：
1.t的长度不超过s
2.t是一个回文字符串
3.存在前缀a和后缀b

思路：

先找出首尾相同的最大长度，中间部分再找个最长回文串拼起来。

代码：

#include<bits/stdc++.h>
using namespace std;
bool hui(const string& s, int l, int r)
{
    while (l < r)
    {
        if (s[l] != s[r])
        {
            return false;
        }
        l++;
        r--;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        int n = s.size();
        int l = 0, r = n - 1;
        while (l < r && s[l] == s[r])
        {
            l++;
            r--;
        }
        if (l >= r)
        {
            cout << s << "\n";
            continue;
        }
        string mid = s.substr(l, r - l + 1);
        int m = mid.size();
        string best = "";
        for (int i = m - 1; i >= 0 && i + 1 > best.size(); i--)
        {
            if (hui(mid, 0, i))
            {
                best = mid.substr(0, i + 1);
                break;
            }
        }
        for (int i = 0; i < m && m - i > best.size(); i++)
        {
            if (hui(mid, i, m - 1))
            {
                string cur = mid.substr(i);
                if (cur.size() > best.size())
                {
                    best = cur;
                }
                break;
            }
        }
        cout << s.substr(0, l) + best + s.substr(r + 1) << "\n";
    }
    
    return 0;
}

复制

T3：Palindrome Pairs

题意：

给定一个全是字母的字符串数组，可以将这个数组里的任意两组字符串相加变成一个回文字符串，求有多少个回文对。

思路：

一，先遍历，把每一种组合都相加，用栈来把所有的组合存起来。二，再建一个变量sum来记录回文对的数量，
每一组都把偶数的相同字母建一个数组存起来，奇数的再建一个数组存起来，如果奇数有两个及以上，return。
把偶数对从小到大的排列在新建数组的两边最后再检查一遍，如果没有问题就sum+1，否则不加。循环这个方法，
sum++,最后输出sum

代码：

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    unordered_map<int, int> h;
    long long ans = 0;
    for (int i = 0; i < n; i++) 
    {
        string s;
        cin >> s;
        int mask = 0;
        for (char c : s)
        {
            mask ^= (1 << (c - 'a'));
        }
        ans += h[mask];
        for (int j = 0; j < 26; j++) 
        {
            ans += h[mask ^ (1 << j)];
        }
        h[mask]++;
    }
    cout << ans << "\n";
    return 0;
}

复制

T4:Erase and Extend (Easy Version)

题意：

从原串删后缀再无限复制，截断取长度为k的字典序最小串。

思路：

枚举保留前缀长度，复制拼接到k取字典序最小的。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    string ans = "";
    for (int i = 0; i < n; i++)
    {
        string f = s.substr(0, i + 1);
        string cur = "";
        while (cur.size() < k)
        {
            cur += f;
        }
        cur = cur.substr(0, k);
        if (ans == "" || cur < ans)
        {
            ans = cur;
        }
    }
    cout << ans << "\n";
    return 0;
}

复制

T5：Fixed Prefix Permutations

题意：

给定n个长度为m的排列，求每个排列与任意排列相乘后能得到的最大前缀连续匹配长度。

思路：

预处理出所有排列两两相乘的美丽值后，对每个排列直接取它所在行的最大值作为答案。

代码：

#include<bits/stdc++.h>
using namespace std;
struct Node 
{
    int next[11];
    Node() 
    {
        memset(next, -1, sizeof(next));
    }
};
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;  
    while (t--) 
    {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(m));
        vector<vector<int>> inv(n, vector<int>(m + 1));
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < m; j++) 
            {
                cin >> a[i][j];
            }
            for (int j = 0; j < m; j++) 
            {
                inv[i][a[i][j]] = j + 1;
            }
        }
        vector<Node> trie(1);
        for (int i = 0; i < n; i++) 
        {
            int node = 0;
            for (int k = 1; k <= m; k++) 
            {
                int val = inv[i][k];
                if (trie[node].next[val] == -1) 
                {
                    trie[node].next[val] = trie.size();
                    trie.emplace_back();
                }
                node = trie[node].next[val];
            }
        }
        for (int i = 0; i < n; i++) 
        {
            int node = 0;
            int len = 0;
            for (int k = 0; k < m; k++) 
            {
                int val = a[i][k];
                if (trie[node].next[val] == -1) 
                {
                    break;
                }
                node = trie[node].next[val];
                len++;
            }
            cout << len << " ";
        }
        cout << "\n";
    }
    return 0;
}

复制

T6：Sasha and One More Name

题意：

给定一个回文串，求最少的切割次数，使得切割后的各段重新排列拼接，能组成一个与原串不同的回文串。

思路：

1.如果字符串全由同一个字符组成，无论怎么切拼结果都是一样的，那么就输出"Impossible"。
2.如果字符串长度是偶数，直接在正中间切一刀，把左右两半互换位置即可,然后输出1。
3.如果字符串长度是奇数，在中间那个字符的两侧各切一刀，把左右两半互换位置即可，输出2。

代码：

#include<bits/stdc++.h>
using namespace std;
bool ispal(const string& s) 
{
    int l = 0, r = s.size() - 1;
    while (l < r) 
    {
        if (s[l] != s[r]) return false;
        l++, r--;
    }
    return true;
}
bool same(const string& s) 
{
    for (int i = 1; i < s.size(); i++) 
    {
        if (s[i] != s[0]) return false;
    }
    return true;
}
bool c(const string& s) 
{
    int n = s.size();
    for (int i = 1; i < n; i++) 
    {
        int l = 0, r = n - 1;
        bool ok = true;
        for (int j = 0; j < n; j++) 
        {
            char left = s[(i + j) % n];
            char right = s[(i + n - 1 - j) % n];
            if (left != right) 
            {
                ok = false;
                break;
            }
        }
        if (ok) 
        {
            if (s.substr(i) + s.substr(0, i) != s) 
            {
                return true;
            }
        }
    }
    return false;
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    if (n <= 1 || same(s)) 
    {
        cout << "Impossible\n";
        return 0;
    }
    if (c(s)) 
    {
        cout << 1 << "\n";
    } 
    else 
    {
        cout << 2 << "\n";
    }
    
    return 0;
}

复制