ACWing1339.你的旅途由此开始（模拟）

ACWing1339.你的旅途由此开始（模拟）

文章目录

• 前言
• 一、题目
• 二、题解
• • 1.思路
  • 2.完整代码
  • 3.优化

前言

来源：usaco training 1.2

一、题目

题目链接：ACWing1339. 你的旅途由此开始.
有一个众所周知的事实，每个彗星的背后都藏着一个UFO。

这些UFO经常到地球来带走一些它们的忠实支持者。

不幸的是，UFO的空间有限，每次星际之旅都只能带走一组支持者。

为了让所有的支持者团队能够提前知道究竟哪组支持者会被带走，UFO们设计了如下方案：

它们给彗星制定一个名称，通过将该名称和某一组支持团队的名称进行比较，从而判断这一组支持团队是否会被带走。

具体的比较方式如下：

首先，我们将彗星和支持者团队的名称通过以下方式转化为数字：

每个大写字母对应一个整数，A对应1，B对应2，…，Z对应26。
将名称中的每个字母转化为对应数字，再将这些数字相乘，例如，USACO对应的数字相乘为21 * 19 * 1 * 3 * 15 = 17955。
将得到的乘积 mod 47 就可得到最终数字。
我们将彗星和支持者团队的名称都通过上述方式转化为最终数字后，如果两个名称对应的数字相同，那么这组支持者就将被带走。

现在，请你编写一个程序，读取彗星和支持者团队的名称，并根据上述方案判断两个名称是否匹配。

输入格式
第一行，一个由大写字母构成，长度不超过6的字符串，表示彗星的名称。

第二行，一个由大写字母构成，长度不超过6的字符串，表示支持者团队的名称。

输出格式
如果两个名称可以匹配，则输出”GO”，否则输出”STAY”。

输入样例1：
COMETQ
HVNGAT
输出样例1：
GO
输入样例2：
ABSTAR
USACO
输出样例2：
STAY

二、题解

1.思路

模拟题，一开始我想的是把26个字母用数组存起来，对于输入的字符串与这个数组的每位进行比较，如果相同，那么就乘上字母数组的下标%47，每次这个结果自己还得%47。这样多%几次，就不用害怕溢出了。

2.完整代码

#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 15char letter[28] = "0ABCDEFGHIJKLMNOPQRSTUVWXYZ";long int transNum(char a[],int n){long int res = 1;for(int i=0;i<n;i++){for(int j=1;j<=26;j++){if(a[i] == letter[j]){res *= (j%47);res %= 47;break;}}}return res;
}int main(){char a[MAX],b[MAX];long int x,y;scanf("%s",a);scanf("%s",b);x = transNum(a,strlen(a));y = transNum(b,strlen(b));if(x == y){printf("GO");}else{printf("STAY");}return 0;
}

3.优化

可以直接用当前输入的字符-‘A’+1就可以得到当前字符对应的数字。

#include<cstdio>
#include<cstring>
using namespace std;#define MAX 15long int transNum(char num[],int n){long int res = 1;for(int i=0;i<n;i++){res *= ((num[i]-'A'+1)%47);res %= 47;}return res;
}int main(){char a[MAX],b[MAX];scanf("%s",a);scanf("%s",b);if(transNum(a,strlen(a)) == transNum(b,strlen(b))){printf("GO");}else{printf("STAY");}return 0;
}