A. Common Prefixes

题意：构造n + 1个字符串，使得每两个字符串的最长公共前缀的长度为给定值

思路：给第一个字符串赋初值aaaaaa................(200个a)，后面的字符串由前一个字符串修改第一个不同的字符得到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-3;
const int inf = 0x3f3f3f3f;
const int N = 105;

int a[N];

int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        string s(200, 'a');
        cout<<s<<'\n';
        for(int i = 1; i <= n; ++i) {
            if(s[a[i]] == 'a')
                s[a[i]] = 'b';
            else
                s[a[i]] = 'a';
            cout<<s<<'\n';
        }
    }
    return 0;
}

 C. String Transformation 1

 

题意：问字符串a至少通过几次变换变为字符串b，每次变换可以选择a中若干个（>= 1）相同的字符，将它们全部替换为一个严格大于该字符的字符，若不能变为b输出-1

思路：

（1）显而易见，若存在a[i] > b[i]，不可能变成b；

（2）若a[i] == b[i]，a[i]肯定是不能被替换的，因为被替换后肯定大于原字符了，所以不用管

（3）把所有需要操作的字符对（u, v）插入set中，从字典序小的开始操作，u相同的字符对只操作v最小的那个（u, v0），剩余的(u, v1)、（u, v2）……可以看作变为了(v0, v1)、（v0, v2）……所以把(u, v1)、（u, v2）……从set中删除，将(v0, v1)、（v0, v2）……插入set

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-3;
const int inf = 0x3f3f3f3f;
const int N = 105;

set<int>st[30];

struct node
{
    int u, v;
    node(){};
    node(int uu, int vv):u(uu), v(vv){}
    bool operator < (const node &a)const
    {
        if(u != a.u)
            return u < a.u;
        else
            return v < a.v;
    }
};

int main()
{
    int t, n;
    string a, b;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        cin >> a >> b;
        for(int i = 0; i < 30; ++i) st[i].clear();
        bool flag = 1;
        for(int i = 0; i < n; ++i) {
            if(a[i] > b[i]) {
                cout<<"-1"<<'\n';
                flag = 0;
                break;
            }
            if(a[i] != b[i])
                st[a[i] - 'a'].insert(b[i] - 'a');
        }
        if(!flag) continue;
        set<node>q;
        set<int>::iterator it;
        for(int i = 0; i < 26; ++i) {
            for(it = st[i].begin(); it != st[i].end(); ++it) {
//                cout<<i<<' '<<*it<<'\n';
                q.insert(node(i, *it));
            }
        }
        int ans = 0;
        while(q.size()) {
            node tmp = *q.begin();
            q.erase(q.begin());
            ans++;
//            cout<<q.size()<<' '<<tmp.u<<' '<<tmp.v<<'\n';
            while(q.size() > 1 && (*q.begin()).u == tmp.u) {
//                cout<<tmp.u<<' '<<tmp.v<<' '<<(*q.begin()).v<<'\n';
                q.insert(node(tmp.v, (*q.begin()).v));
                q.erase(q.begin());
            }
        }
        cout<<ans<<'\n';
        q.clear();
    }
    return 0;
}