Educational Codeforces round 78 A、B

链接:https://codeforces.com/contest/1278


A:Shuffle Hashing


题意:对于一个字符串p可以执行一个”hash”操作,首先将p内的元素随机排列(可能保持原样),随后在p的前面和后面分别加两个字符串(可以为空),组成的新字符串称为h。输入字符串p和h,输出h是否可能是p经过hash操作而来。

    例如:输入p = “abacaba”,h = “zyxaabcaabkjh”,输出YES

分析:hash操作分为两步:①随机排列p中的元素②在p的前面和后面分别加两个字符串组成一个新的字符串。那么首先,进行第一步操作之后的p如果记作p’,显然有p中各元素出现的次数与p’中的相等。因此检测另一个字符串是否是p随机排列而来可以使用一个计数数组检测其中各元素出现的次数。其次,②说明p’在h中是连续的一串子字符串,记p长度为plen,h为hlen,则其长度是plen,由此,我们可以遍历h从0位开始一直到hlen-plen位开始的长度为plen的子字符串是否是p随机排列而来。

代码:

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int cnt[30];
int main()
{
    int T;cin >> T;
    while(T--)
    {
        string p,h;cin >> p >> h;
        int plen = p.length(),hlen = h.length();
        int ok = -1;
        for(int i = 0;i <= hlen - plen;++i)
        {
            memset(cnt,0,sizeof(cnt));
            string tmp = h.substr(i,plen);
            for(int j = 0;j < plen;++j)
            {
                ++cnt[tmp[j] - 'a'];
                --cnt[p[j] - 'a'];
            }
            ok = 1;
            for(int i = 0;i < 30;++i)
            {
                if(cnt[i] != 0)
                {
                    ok = 0;
                    break;
                }
            }
            if(ok == 1)
                break;
        }
        if(ok == 1)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

B:A and B


题意:给定两个变量a,b。每次选择两者之间的一个数,执行一个操作:将这个数加上i(i = 当前执行的第i步),求至少多少步可以使a和b相等。

分析:在进行了n次操作之后,对于a和b两个数来说,总体上增加的是dsum = n(n+1)/2。但是如果想要把总体增加的和运用到a和b两个数单个身上来说的话就会变得很复杂,因为你没法知道第几步是给a增加的还是b增加的。所以,我们可以从整体上来看,对于a和b而言,他们的和本来是cursum = a+b,进行了n次操作之后会变成cursum + dsum = a’ + b’(此时a‘ == b’),那么就可以从中得到一个重要信息:cursum+dsum由于这个时候a’ == b’,那么cursum + dsum一定是2的倍数,否则不成立,其次,(cursum+dsum)/2也一定>=max(a,b),因为极端的情况就是一边很小,一直在很小的一边加,最后与右边更大的值相等,倘若(cursum + dsum)/2不满足>=max(a,b),则说明虽然此时加的数已经是2的倍数,但是还不足以分成两半使得a和b此时相等。

代码:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int T;cin >> T;
    while(T--)
    {
        int a,b;cin >> a >> b;
        if(a == b)
        {
            cout << 0 << endl;
            continue;
        }
        int cursum = a + b,n = 1,nsum = 0;
        for(;n <= max(a,b)*2;++n)
        {
            nsum += n;
            if(((cursum + nsum) & 1 ) == 0 && ((cursum + nsum) / 2) >= max(a,b))
            {
                cout << n << endl;
                break;
            }
        }
    }
}



上一篇:LeetCode438找到字符串中所有字母异位词(字符串哈希)


下一篇:数据结构(字符串)—— 循环旋转字符串的判断