当前位置: 首页 > 工具软件 > Alchemist > 使用案例 >

A Great Alchemist

蒯宇定
2023-12-01

输入三条等长的s1,s2,s3,字符均为大写字母,且个数是偶数。

用s1和s2中一样的元素个数来构造s3。


分析:将s1,s2,s3转化为ele1[26],ele[26],goal[26],对应这些变量分别存放三个字符串中的A~Z字符个数。

分别有

x0 x1 x2 x3...x25

y0 y1 y2 y3...y25

z0 z1 z2 z3...z25


结果用每个对应x,y构造z,假设上面的结果就是符合要求的结果。于是有:

y25 - x25(范围是确定的,且奇偶性不变,即可选的结果是一个等差数列)

我们需要的结果就是y25-x25 + y24 - x24......y0 - x0 = 0成立。


因此,只需要构造y25-x25的范围,然后拓展至y0-x0的范围,即从后向前叠加范围,只需要考虑判断叠加后的范围,满足最小范围是小于等于0,最大范围大于等于0,然后最大值是偶数。就可以断定这个肯定可以实现,否则不能实现。代码如下。


// edit by colin
// 20141102
// RGF campus recruitment test
#include <iostream>
#include <cstring>
using namespace std;

int ele1[27];
int ele2[27];
int goal[27];

int rangemin[27];
int rangemax[27];

int main()
{
 //   freopen("in.txt","r",stdin);
    string s1,s2,s3;
    cin>>s1;
    cin>>s2;
    cin>>s3;

    unsigned int tmp;
    unsigned int len = s1.length();
    int mark = 0;
    // 存储三列数组
    for(int i = 0; i < len; ++i){
        tmp = s1[i] - 'A';
        ++ele1[tmp];
        tmp = s2[i] - 'A';
        ++ele2[tmp];
        tmp = s3[i] - 'A';
        ++goal[tmp];
    }
    rangemax[26] = 0;
    rangemin[26] = 0;
    for(int i=25;i>=0;--i)
    {
        if(ele1[i]+ele2[i]<goal[i]){
            cout<<"NO"<<endl;
            return 0;
        }
        // 获取x的最大最小值
        int min,max;
        if(goal[i]>=ele2[i])
            min = goal[i] - ele2[i];
        else
            min = 0;
        max = goal[i]>ele1[i]?ele1[i]:goal[i];
        // 最大最小差值,拓展范围
        rangemin[i] = goal[i] - max*2 + rangemin[i+1];
        rangemax[i] = goal[i] - min*2 + rangemax[i+1];
        //cout<<max<<" "<<min<<" "<<goal[i]<<" "<<ele1[i]<<" "<<ele2[i]<<" "<<rangemin[i]<<" "<<rangemax[i]<<endl;
    }
        // 判断最小范围,最大范围,最大值是否为偶数
    if(rangemin[0]<=0 && rangemax[0]>=0 && rangemax[0]%2 == 0)
        mark = 1;
    if(mark)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}


 类似资料:

相关阅读

相关文章

相关问答