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;

            }

        }

    }

}

巴特西

Educational Codeforces round 78 A、B

最新文章

热门文章