Symmetric Encoding

题目描述

Polycarp has a string $ s $ , which consists of lowercase Latin letters. He encodes this string using the following algorithm:

• first, he constructs a new auxiliary string $ r $ , which consists of all distinct letters of the string $ s $ , written in alphabetical order;
• then the encoding happens as follows: each character in the string $ s $ is replaced by its symmetric character from the string $ r $ (the first character of the string $ r $ will be replaced by the last, the second by the second from the end, and so on).

For example, encoding the string $ s $ ="codeforces" happens as follows:

• the string $ r $ is obtained as "cdefors";
• the first character $ s_1 $ ='c' is replaced by 's';
• the second character $ s_2 $ ='o' is replaced by 'e';
• the third character $ s_3 $ ='d' is replaced by 'r';
• ...
• the last character $ s_{10} $ ='s' is replaced by 'c'.

The string $ r $ and replacements for $ s $ ="codeforces".Thus, the result of encoding the string $ s $ ="codeforces" is the string "serofedsoc".

Write a program that performs decoding — that is, restores the original string $ s $ from the encoding result.

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the string $ b $ .

The second line of each test case contains a string $ b $ of length $ n $ , consisting of lowercase Latin letters — the result of encoding the original string $ s $ .

It is guaranteed that the sum of the values of $ n $ over all test cases in the test does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output the string $ s $ from which the encoding result $ b $ was obtained.

样例 #1

样例输入 #1

5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin

样例输出 #1

codeforces
fft
algorithm
w
meetinthemiddle

本题思路

写映射

AC_code

双指针 写映射

#include <bits/stdc++.h>

using namespace std;

int _, n;

void solve() {
    string s, r;
    cin >> s;
    for(int i = 0; i < n; ++ i) {
        if(count(r.begin(), r.end(), s[i])) continue;//count返回出现次数
        r += s[i];
    }
    sort(r.begin(), r.end());
    vector<char> mp(26);
    for(int i = 0, j = r.size() - 1; i <= j;  ++ i, -- j) {//char数组双指针转换
        mp[r[i] - 'a'] = r[j];
        mp[r[j] - 'a'] = r[i];
    }
    for(auto it : s) cout << mp[it - 'a'];
    cout << endl;
}

int main()
{
    cin >> _;
    while(_ --) {
        cin >> n;
        solve();
    }
    return 0;
}

单指针变化+嵌套

#include <bits/stdc++.h>

using namespace std;

const int N = 2 * 1e5 + 10;

char s[N], t[N], mp[N];
int _, n;

void solve() {
    int vis[26] = {0};//局部变量节省多组输入初始化
    int m = 0;
    for(int i = 1; i <= n; ++ i) {
        if(vis[s[i] - 'a'] == 0)//t数组存出现过的值
            t[++ m] = s[i], vis[s[i] - 'a'] = 1;
    }
    sort(t + 1, t + m + 1);//排序
    //此时已经知道一一对应的关系，映射
    for(int i = 1; i <= m; ++ i) mp[t[i]] = t[m - i + 1];
    for(int i = 1; i <= n; ++ i) {
        s[i] = mp[s[i]];//转换
    }
    puts(s + 1);    
}

int main()
{
    cin >> _;
    while(_ --) {
        cin >> n >> s + 1;
        solve();   
    }
    return 0;
}

get到技能：如何映射并转换

1.指针变换写映射 + 嵌套

for(int i = 1; i <= m; ++ i) mp[t[i]] = t[m - i + 1];
    for(int i = 1; i <= n; ++ i) {
        s[i] = mp[s[i]];//转换
    }

2.双指针扫描 + 值映射

vector<char> mp(26);
for(int i = 0, j = r.size() - 1; i <= j;  ++ i, -- j) {
    mp[r[i] - 'a'] = r[j];
    mp[r[j] - 'a'] = r[i];
}
for(auto it : s) cout << mp[it - 'a'];

总结

取出字符串r没什么难度，赛场脑子掉线写映射被卡(在写用整形+'a'转回字符映射)，然后爆炸了，忽略了直接存一下的可能....

for(int i = 0; i < n; ++ i) {//当时写了一个0～n-1的转换，看起来没什么问题
    cout << s[i] << ' ' << s[n - i - 1] << endl;
}