Fork me on GitHub

编程练习赛63

发表于 | 分类于 
# 题目1 : 命名

描述

有两个公司想要合并，第一个公司的名字是一个字符串S，第二个公司的名字是一个字符串T.

合并后的新公司是这样取名的：

1.先选一个S的子序列A，T的一个子序列B，要求-1 ≤ |A|-|B| ≤ 1

2.如果|A|=|B|，那么可以选择取名为A1B1A2B2..A|A|B|B|或者B1A1B2A2..B|B|A|A|，例如A=abc, B=def，则可以取名为adbecf或者daebfc.

3.如果|A|=|B|+1，那么只能取名为A1B1A2B2..A|B|B|B|A|B|+1

4.如果|B|=|A|+1，那么只能取名为B1A1B2A2..B|A|A|A|B|A|+1

现在第一个公司的老总想知道，是否存在一种取名方式，使得新的名字为S

定义字符串X是字符串Y的子序列，当且仅当X可以由Y删掉若干个位置得到。

输入

输入包含多组数据。第一行包含一个整数N，代表测试数据组数。

对于每组测试数据：

第一行一个小写字母字符串S

第二行一个小写字母字符串T

1 ≤ N ≤ 5, 1 ≤ |S|, |T| ≤ 103

输出

对于每组数据，如果存在一种取名方式使得新的名字为S的话，输出Yes，否则输出No

样例输入

3
hoge
moen
abcdefg
xacxegx
abcdef
ghijkl

样例输出

Yes
Yes
No

思路:

分字符串奇偶模拟然后分s串第一位置,第二位置模拟.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>

using namespace std;
int main(){
    int t;
    string s1,s2;
    cin>>t;
    while(t--){
        cin>>s1>>s2;
        int k=s1.size();
        int p=0;
        if(k%2==1){
          	 int i=0,j=0,cnt=0;
             while(i<s1.size()&&j<s2.size()){
                if(s1[i]==s2[j])
                {
                    i+=2;
                    j++;
                    cnt+=2;
                }else
                j++;
            }
            if(cnt-1==k)
                p=1;
            i=1;j=0;cnt=0;
            while(i<s1.size()&&j<s2.size()){
                if(s1[i]==s2[j]){
                    i+=2;
                    j++;
                    cnt+=2;
                }else{
                    j++;
                }
            }
            if(cnt+1==k)
                p=1;
            }else{
            int i=0,j=0,cnt=0;
            while(i<s1.size()&&j<s2.size()){
                if(s1[i]==s2[j])
                {
                    i+=2;
                    j++;
                    cnt+=2;
                }else
                    j++;
            }
            if(cnt==k)
                p=1;
            i=1;j=0;cnt=0;
            while(i<s1.size()&&j<s2.size()){
                if(s1[i]==s2[j]){
                    i+=2;
                    j++;
                    cnt+=2;
                }else{
                    j++;
                }
             }
               if(cnt==k)
                p=1;
           }
           if(p==1)
              cout<<"Yes"<<endl;
           else
             cout<<"No"<<endl;

 }
}
# 题目2 : 洗牌

描述

你有一副扑克牌，里面一共有2n张牌，从上往下第 i 张牌上的数为ai.

现在定义对一副牌堆洗牌是这样的过程：

1.如果这副牌只有2张牌，交换这两张牌的顺序。

2.否则，假设这副牌有2k张牌，把牌分成上下两部分，每部分的牌的数量都是2k-1，然后分别对这两部分洗一次牌。之后把本来在下面的那部分放到本来在上面那部分的上面。

现在小 C 想知道，对一副牌洗t次后，这副牌会变成什么样。

输入

第一行两个正整数n,t

第二行2n个整数，第i个整数表示ai

2 ≤ n ≤ 10, 1 ≤ t ≤ 109, 1 ≤ ai ≤ 109

输出

输出2n行，第i行一个整数，表示洗了t次牌后从上往下第 i 张牌上的数。

样例输入

2 1
2 4 1 5

样例输出

5
1
4
2

思路：

根据题意易知奇数序列翻转偶数原样输出。关键是递归的如何写，这个要读者自行揣摩。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1028;
ll a[maxn],b[maxn];

void slove(ll l,ll c){
    if(c-l==1)
    {
        ll f;
        f=a[l];
        a[l]=a[c];
        a[c]=f;
        return;
    }
    ll mid=(l+c)/2;
    slove(l,mid);
    slove(mid+1,c);
    int cnt=(c-l+1)/2;
    for(int i=l;i<=mid;i++)
    {
        ll f;
        f=a[i];
        a[i]=a[i+cnt];
        a[i+cnt]=f;
    }
}
int main(){
    ll n,t;
    cin>>n>>t;
    ll c=pow(2,n);
    for(int i=1;i<=c;i++)
        cin>>a[i];
    if(t%2==0){
        for(int i=1;i<=c;i++)
            cout<<a[i]<<endl;
    }
    else{
        slove(1,c);
        for(int i=1;i<=c;i++)
            cout<<a[i]<<endl;
    }

}
# 题目3 : 密码更改

描述

小 C 有一个由数字构成的密码 S，例如：”123” , “3211” ,”111111”，”0123”

定义数字密码的大小为：这个数字密码代表的十进制数字的大小。

现在小 C 想改成一个更强的密码，新密码需要满足以下条件：

1.为了保证强度，每个数字在新密码中必须最多只出现一次。

2.旧密码和新密码的长度一样。

3.新密码和旧密码的距离尽量大。

4.如果有多个距离相同的，则取大小比较小的密码。

定义两个长度相同的数字密码 a , b的距离为min(|a-b|,10N-|a-b|)

其中 N 是数字密码 a,b 的长度。

例如 “012” 和 “987” 的距离为 25。

现在给定S，小 C 想知道满足条件的新密码是啥。

输入

第一行读入一个由数字构成的字符串 S

保证 1 ≤ |S| ≤ 10，其中|S|表示 S 的串长。

输出

输出一个长度和 S 相同的由数字构成的字符串，表示新密码。

样例输入

201

样例输出

701

思路:

爆搜只有10!不会爆栈也不会超时

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=4e6+30;
const int INF=-1;
ll b[maxn],c[30],a[30],cnt=0;
string s;
int k;
void dfs(int n){
    if(n==0)
    {
        ++cnt;
        for(int i=k;i>=1;i--){
            b[cnt]=b[cnt]*10+c[i];
        }
        return;
    }
    for(int j=0;j<=9;j++){
        if(!a[j]){
            c[n]=j;
            a[j]=1;
            dfs(n-1);
            a[j]=0;
        }
    }
}
int main(){
    cin>>s;
    ll m=0;
    k=s.size();
    ll ans=pow(10,k);
    dfs(k);
    for(int i=0;i<s.size();i++){
       m=m*10+(ll)(s[i]-'0');
    }
    //cout<<m<<endl;
    ll Max=INF,xx;
    /*for(int i=1;i<=cnt;i++)
        cout<<b[i]<<" ";
    cout<<endl;*/
    for(int i=1;i<=cnt;i++){
        ll p=min(abs(m-b[i]),ans-abs(m-b[i]));
        //cout<<p<<endl;
        /*if(b[i]==12||b[i]==54){
            cout<<p<<endl;
        }*/
        if(p>Max){
            Max=p;
            xx=b[i];
        }
    }
    int f[20];
    memset(f,0,sizeof(f));
    //cout<<xx<<endl;
    for(int i=1;i<=k;i++){
        f[i]=xx%10;
        xx=xx/10;
    }
    for(int i=k;i>=1;i--)
        cout<<f[i];
    cout<<endl;
    return 0;
}

总结：本次做题我看到自己的进步，也看到自己对于一些算法的设计不知道去考虑爆栈和超时的问题。