精华内容
下载资源
问答
  • Polycarp and String Transformation 题目链接 首先这个题的字母的删除顺序可以先确定下来,最后删除的字母最后出现,倒二删除的字母倒二出现...... 然后可以根据删除字母的顺序找到原串,因为第一个删除的字母肯定...

    E. Polycarp and String Transformation

    题目链接

    首先这个题的字母的删除顺序可以先确定下来,最后删除的字母最后出现,倒二删除的字母倒二出现......
    然后可以根据删除字母的顺序找到原串,因为第一个删除的字母肯定是原串该字母的个数,第二个则是两倍,第三个则是三倍,
    以此类推,然后最后再按照题意模拟,看看最后可不可以得到初始串。
    
    #include <algorithm>
    #include <deque>
    #include <iomanip>
    #include <iostream>
    #include <map>
    #include <math.h>
    #include <queue>
    #include <set>
    #include <stack>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <string>
    #include <unordered_map>
    #include <vector>
    #define ll long long int
    #define ms(a, b) memset(a, b, sizeof(a))
    #define lowbit(x) (x & -x)
    #define fi first
    #define se second
    #define Size(a) int((a).size())
    #define ull unsigned long long
    #define lson (rt << 1)
    #define rson (rt << 1 | 1)
    #define endl "\n"
    #define bug cout << "----acac----" << endl;
    #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    using namespace std;
    const ll mod = 1e9 + 7;
    const int maxn = 1e6 + 10;
    const int maxm = 5e3 + 50;
    const double eps = 1e-8;
    const ll inf = 0x3f3f3f3f;
    const ll lnf = 0x3f3f3f3f3f3f3f3f;
    const double pi = acos(-1);
    
    string s;
    int vis[30];
    int main()
    {
    
        int T;
        cin >> T;
        while (T--)
        {
            ms(vis, 0);
            cin >> s;
            int cnt = 0;
            string ans = "";
            for (int i = Size(s)-1; i >=0; i--)//从后往前找
            {
                if (!vis[s[i] - 'a'])
                {
                    cnt++;
                    ans = s[i] + ans;
                }
                vis[s[i] - 'a']++;
            }
            int len = 0;
            for (int i = 0; i < Size(ans); i++)
            {
                len += vis[ans[i] - 'a'] / (i + 1);//初始串的长度
            }
            string t = s.substr(0, len);
            string temp = t, ans1 = t;
            for (int i = 0; i < Size(ans); i++)
            {
                string tt = "";
                for (int j = 0; j < Size(t); j++)
                {
                    if (ans[i] == t[j])
                        continue;
                    tt += t[j];
                }
                temp += tt;
                t = tt;
            }
            if (temp == s)
            {
                cout << ans1 << " " << ans << endl;
            }
            else
            {
                cout << "-1" << endl;
            }
        }
        return 0;
    }
    
    展开全文
  • Polycarp and String Transformation

    Polycarp and String Transformation
    题意:有字符串s ,字符串t开始为空,重复以下过程直到s为空,第一步t = t + s ,第二步删去s中的全部的某字母。
    现在给出最后的t串,输出开始的s串和对应的字母删除顺序。

    思路:删除的字母就是t串出现的字母,既然每次都执行了t=t+s,所以后删的字母一定在t串的后面,所以只需要倒着找到不同的字母,然后把找到的字母再倒过来就是字母的删除顺序(只能倒着找,因为每次新加的s串在后面),例如:abacabaaacaac,倒着找到cab,倒过来bac为删除顺序。
    找s串:从题目过程分析
    •先删b,t串中b的个数除以1就是原s串b的个数
    •再删a,因为删b的时候a的个数又加了一遍,所以t串中a的个数除以2就是原s串a的个数
    •最后删c,毋庸置疑t串中c的个数除以3就是原s串c的个数。
    以上加起来总和就是s串的字符个数,从t串左边截取下来就是s串。
    判断只需要照着题目要求,把s串变成t串比较即可。

    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<string>
    using namespace std;
    int a[26];//数组记录字母数
    string s,t,ss,sss,ans,tmp;//tmp为空串,用于初始化其他串
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            cin>>t;
            ans=tmp;
            for(int i=t.size()-1; i>=0; i--)
            {
                if((++a[t[i]-'a'])==1)//既寻找了第一次出现的字母,又记录了每个字母的个数
                    ans+=t[i];
            }
            int x=ans.size(),l=0;//ans为删除的字母
            for(int i=0; i<=(x-1)/2; i++)
                swap(ans[i],ans[x-i-1]);//变为正确的删除顺序
            for(int i=0; i<x; i++)
                l+=a[ans[i]-'a']/(i+1);//截取s串长度
            s=ss=t.substr(0,l);//找到s串
            for(int i=0; i<x; i++)//模拟题目过程
            {
                sss=tmp;
                for(int j=0; j<s.size(); j++)
                    if(s[j]!=ans[i])
                        sss+=s[j];
                s=sss;
                ss+=s;
            }
            if(ss==t)//判断
                cout<<t.substr(0,l)<<" "<<ans<<endl;
            else cout<<-1<<endl;
            memset(a,0,sizeof(a));
        }
        return 0;
    }
    
    展开全文
  • Polycarp and String Transformation #739 (Div. 3)E. Polycarp and String Transformation Polycarp has a string s. Polycarp performs the following actions until the string s is empty (t is initially an ...

    E. Polycarp and String Transformation

    #739 (Div. 3)E. Polycarp and String Transformation

    Polycarp has a string s. Polycarp performs the following actions until the string s is empty (t is initially an empty string):

    he adds to the right to the string t the string s, i.e. he does t=t+s, where t+s is a concatenation of the strings t and s;
    he selects an arbitrary letter of s and removes from s all its occurrences (the selected letter must occur in the string s at the moment of performing this action).
    Polycarp performs this sequence of actions strictly in this order.

    Note that after Polycarp finishes the actions, the string s will be empty and the string t will be equal to some value (that is undefined and depends on the order of removing).

    E.g. consider s=“abacaba” so the actions may be performed as follows:

    t=“abacaba”, the letter ‘b’ is selected, then s=“aacaa”;
    t=“abacabaaacaa”, the letter ‘a’ is selected, then s=“c”;
    t=“abacabaaacaac”, the letter ‘c’ is selected, then s="" (the empty string).
    You need to restore the initial value of the string s using only the final value of t and find the order of removing letters from s.

    Input
    The first line contains one integer T (1≤T≤104) — the number of test cases. Then T test cases follow.

    Each test case contains one string t consisting of lowercase letters of the Latin alphabet. The length of t doesn’t exceed 5⋅105. The sum of lengths of all strings t in the test cases doesn’t exceed 5⋅105.

    Output
    For each test case output in a separate line:−1, if the answer doesn’t exist;
    two strings separated by spaces. The first one must contain a possible initial value of s. The second one must contain a sequence of letters — it’s in what order one needs to remove letters from s to make the string t. E.g. if the string “bac” is outputted, then, first, all occurrences of the letter ‘b’ were deleted, then all occurrences of ‘a’, and then, finally, all occurrences of ‘c’. If there are multiple solutions, print any one.

    • 输入
      7
      abacabaaacaac
      nowyouknowthat
      polycarppoycarppoyarppyarppyrpprppp
      isi
      everywherevrywhrvryhrvrhrvhv
      haaha
      qweqeewew
    • 输出
      abacaba bac
      -1
      polycarp lcoayrp
      is si
      everywhere ewyrhv
      -1
      -1

    还是一道思路比较直接的题目,当时卡的也很离谱,现在也不知道是为什么会被卡

    • 思路:首先会发现每一个字母的价值就是最后第几个删除,如果一共删除了n次,那么最后一个删除的字母就是重复了n次,所以统计一下这个字母总共出现的次数,然后再/这个字母删除的次序,就可以得到答案,而在这里,删除的次序就是从后往前数出现的次序,因为如果一个字母(假设x)在第二次删除,那么第三次输出的时候我们一定会枚举出第四个和第五个~~删除的字母,所以从后往前跑一边就可以
    #include <bits/stdc++.h>
    using namespace std;
    
    int num[30];
    int fie[30];
    
    int main()
    {
        int T;
        cin >> T;
        while (T--)
        {
            memset(num, 0, sizeof num);
            string s;
            cin >> s;
            string ans1 = "";  //这是我们的删除顺序
    
            int n = s.size();
    
            for (int i = n - 1; i >= 0; i--)
            {
                if(!num[s[i]-'a'])
                    ans1+=s[i];
            
                num[s[i] - 'a']++;  //存储一共有多少个这样的字母
            }
            reverse(ans1.begin(), ans1.end());  //反转 得到我们所需要的删除顺序
    
            int liuzhuo = ans1.size();
            for (int i = 0; i < liuzhuo; i++)
                fie[ans1[i] - 'a'] = i;
            for (int i = 0; i < 26; i++)
                num[i] = num[i] / (fie[i] + 1);  //这就是原始字符串的每一个字母应该有的数量
    
            string ans = "";
    
            for (int i = 0; i < n; i++)
            {
                if (num[s[i] - 'a'])
                {
                    num[s[i] - 'a']--;
                    ans += s[i];
                }
                else
                    break;
            }
            int fla = 1;
            for (int i = 0; i < 26; i++)  //如果无法用完所有的字母 说明这是不符合条件的
            {
                if (num[i])
                {
                    fla = 0;
                    break;
                }
            }
    
            if (!fla)
                cout << "-1\n";
            else
            {
                int m = ans1.size();
                string sss = ans;
    
                int l = 0;  //下面是跑了一个暴力 验证答案是否正确
                for (int i = 0; i < m; i++)
                {
                    int n = ans.size();
    
                    for (int j = l; j < n; j++)
                    {
                        if (ans[j] == ans1[i])
                            continue;
    
                        ans +=ans[j];
                    }
                    l = n;
                }
                if (ans != s)
                    cout << "-1\n";
                else
                    cout << sss << " " << ans1 << endl;
            }
        }
    }
    
    展开全文
  • Note that the only difference between String Transformation 1 and String Transformation 2 is in the move Koa does. In this version the letter y Koa selects must be strictly greater alphabetically than...

    Note that the only difference between String Transformation 1 and
    String Transformation 2 is in the move Koa does. In this version the
    letter y Koa selects must be strictly greater alphabetically than x
    (read statement for better understanding). You can make hacks in these
    problems independently.

    Koa the Koala has two strings A and B of the same length n (|A|=|B|=n)
    consisting of the first 20 lowercase English alphabet letters (ie.
    from a to t).

    In one move Koa:

    selects some subset of positions p1,p2,…,pk (k≥1;1≤pi≤n;pi≠pj if i≠j)
    of A such that Ap1=Ap2=…=Apk=x (ie. all letters on this positions are
    equal to some letter x). selects a letter y (from the first 20
    lowercase letters in English alphabet) such that y>x (ie. letter y is
    strictly greater alphabetically than x). sets each letter in positions
    p1,p2,…,pk to letter y. More formally: for each i (1≤i≤k) Koa sets
    Api=y. Note that you can only modify letters in string A.

    Koa wants to know the smallest number of moves she has to do to make
    strings equal to each other (A=B) or to determine that there is no way
    to make them equal. Help her!

    Input Each test contains multiple test cases. The first line contains
    t (1≤t≤10) — the number of test cases. Description of the test cases
    follows.

    The first line of each test case contains one integer n (1≤n≤105) —
    the length of strings A and B.

    The second line of each test case contains string A (|A|=n).

    The third line of each test case contains string B (|B|=n).

    Both strings consists of the first 20 lowercase English alphabet
    letters (ie. from a to t).

    It is guaranteed that the sum of n over all test cases does not exceed
    105.

    Output For each test case:

    Print on a single line the smallest number of moves she has to do to
    make strings equal to each other (A=B) or −1 if there is no way to
    make them equal.

    输入

    5
    3
    aab
    bcc
    4
    cabc
    abcb
    3
    abc
    tsr
    4
    aabd
    cccd
    5
    abcbd
    bcdda

    输出

    2
    -1
    3
    2
    -1

    这道题乍一看好像可以取巧,我尝试了发现自己的推测太naive,就不说明错误的做法了。官方给了一个图论的解法
    s1串中的各个顶点u到s2串中对应的顶点v建立图
    每个部分的最好情况是每个部分的顶点数-1,取加和就得到了答案
    解法的证明:
    Each connected component require at least n−1 operations (because they are connected). Since there are no cycles in the graph a topological order exists. Find one and select each pair of consecutive nodes in this order as the list of operations.
    每个连通的部分需要至少n-1个步骤相连。由于图中不存在环,则有拓扑顺序存在。

    为什么双向建边:双向建边可以确保处于一个连通部分的点不会被忽略掉,因为每步操作都会减去没被标记过的点作为答案

    #include <bits/stdc++.h>
    
    using namespace std;
    bool marks[25];
    vector<int> rec[25];
    void dfs(int i)
    {
        marks[i]=1;
        for(auto v : rec[i])
            if(!marks[v])dfs(v);
    }
    int main()
    {
        ios::sync_with_stdio(0);
        int t;
        cin>>t;
        while(t--){
            int n;
            memset(marks,0,sizeof marks);
            for(int i=0;i<20;i++)rec[i].clear();
            string s1,s2;
            cin>>n;
            cin>>s1>>s2;
            int flag=1;
            for(int i=0;i<n;i++){
                if(s1[i]>s2[i]){
                    flag=0;break;
                }
                rec[s1[i]-'a'].push_back(s2[i]-'a');
                rec[s2[i]-'a'].push_back(s1[i]-'a');//加入边
            }
            if(!flag){
                cout<<-1<<endl;
            }
            else{
              int ans=20;
              for(int i=0;i<20;i++){
                if(!marks[i]){
                    dfs(i);
                    ans--;
                }
              }
              cout<<ans<<endl;
        }
    
        }
    }
    
    
    展开全文
  • Note that the only difference between String Transformation 1 and String Transformation 2 is in the move Koa does. In this version the letter y Koa selects must be strictly greater alphabetically than...
  • [codeforces 1384C] String Transformation 1 并查集 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.com/contest/1384/problem/C Problem Lang ...
  • C. String Transformation 1 time limit per test1 second memory limit per test...Note that the only difference between String Transformation 1 and String Transformation 2 is in the move Koa does. In this v
  • 7040: String Transformation时间限制: 1 Sec 内存限制: 128 MB提交: 69 解决: 21[提交][状态][讨论版][命题人:admin]题目描述Bobo has a string S = s1 s2...sn consists of letter a , b and c . He can ...
  • Bobo has a string S=s1s2…sn consists of letter a, b and c. He can transform the string by inserting or deleting substrings aa, bb and abab. Formally, A=u∘w∘v (“∘” denotes string concatenation)...
  • 题目链接:String Transformation 题意 给定一个字符串 sss,可以将这个字符串的任意一个字符变成它的下一个字符(按 ASCIIASCIIASCII 顺序),问给定的字符串能否通过任意次这种操作成为一个含有子字符序列 abc...
  • vector<int> transform(string s) { vector<int>v; int sum=0; for (int i=0;i();i++) { if(i==s.size()||s[i]=='c') { v.push_back(sum); sum=0; } else sum^=s[i]; } return v; } int main () { ...
  • 思路: 在相对应的位置,只要 aaa 串上的字母大于 bbb 串上的字母,那么无解,否则一定有解。 要找到最小的步数,其实最大步数也就20吧。 我们首先从小的开始选择字母,对于选定的字母,我们可以把它变成什么呢?...
  • String Transformation time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Let s be a string whose ...
  • #include <string.h> #include using namespace std; const int maxn = 1e4+100; char s[maxn],t[maxn]; int main(){ while(~scanf("%s\n%s",s,t)){ bool flag = true; int n = strlen(s); int m = strlen(t)...
  • return String.fromCharCode(...str.split(" ").map((char) =&gt; parseInt(char,2))); } binaryAgent("01000001 01110010 01100101 01101110 00100111 01110100 00100000 01100010...
  • String Transformationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a string s consisting of |s| small english letters.In one ...
  • Note that the only difference between String Transformation 1 and String Transformation 2 is in the move Koa does. In this version the letter ???? Koa selects must be strictly greater alphabetically ...
  • 1) A.String Transformation 1 题目链接 Koa the Koala has two strings A and B of the same length n (|A|=|B|=n) consisting of the first 20 lowercase English alphabet letters (ie. from a to t). In one ...
  • C - String Transformation Time Limit: 2 sec / Memory Limit: 1024 MB Score : 300300 points Problem Statement You are given strings SS and TT consisting of lowercase English letters. You can ...
  • String Transformation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output You are given a stringsconsisting o...
  • String Transformationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a string s consisting of |s| small english letters.In one ...
  • String Transformation time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output You are given a string s consisting of |s| small english let...
  • String Transformation Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 553 Accepted Submission(s): 175 Problem Description Bobo has a s...
  • String Transformation time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output You are given a string s consisting of |s| small english letters. In o.....
  • ... String Transformation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output You are
  • From : http://write.blog.csdn.net/postedit?ref=toolbar Given a string, move all even positioned elements to end of string. While moving elements, keep the relative order of all even positione

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,640
精华内容 11,456
关键字:

stringtransformation

友情链接: hostsstiafte.rar