【Google Code Jam Qualification Round 2019】 T1.T2.T3._综合

T1.Foregone Solution (17 pt)

题意

给出一个大整数，转换成两个不包含数字4的整数相加。

做法

直接扫描一遍即可，如果当前位是 $4$ ，两个整数当前位分别为 $1 ， 3$ ，否则两个整数当前位分别为 $s t r [i], 0$ 。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1e5+5;
char str[maxn];
int main()
{
    int t;scanf("%d",&t);int cnt=0;while(t--){
    scanf("%s",str);int len=strlen(str);string ans1="",ans2="";for(int i=0;i<len;i++){
    if(str[i]=='4'){
    ans1=ans1+"3";ans2=ans2+"1";}else{
    ans1=ans1+str[i];ans2=ans2+"0";}}int pos=0;while(pos<ans2.size()&&ans2[pos]=='0') pos++;if(pos==ans2.size()) ans2="0";else ans2=ans2.substr(pos);printf("Case #%d: ",++cnt);cout<<ans1<<" "<<ans2<<endl;}return 0;
}

T2.You Can Go Your Own Way (24 pt)

题意

给出一个只包含下和右两个的路径记录，现在让你给出另一种路径记录，使两条路径终点相同并且没有任何一个时刻相交(点可以相交)。

做法

对于给出的每一步，给出相反的方向即可。可以想到这样每次相交都是以一个点的形式，并且每一次都是形成一个矩形，不可能有重合的边。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e5+5;
char str[maxn];
vector<int> tmp1,tmp2;
int main()
{
    int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){
    int len;scanf("%d",&len);scanf("%s",str);len=2*len-2;printf("Case #%d: ",cas);for(int i=0;i<len;i++){
    if(str[i]=='S') str[i]='E';else str[i]='S';}puts(str);}return 0;
}

T3. Cryptopangrams (25 pt)

题意

现在有一种字符串加密方式，给出一个长度为L的字符串和一个数字N，现在找出小于N的不相同的26个素数，排序之后把最小的素数赋值给字符A,次小的素数赋值给B,依次类推。之后对于给定的字符串，从左到右对于每两个相邻的字符把他们的权值乘积记录下来，得到L-1个数字，现在给你这L-1个数字，求出原字符串是什么。

做法

我们可以用前两个给定数字的gcd求出第二个素数是什么，得到第二个素数，我们就可以得到每一个素数是什么，之后进行排序转回相应的字母即可，这里大数据要用高精度，但是我的高精度模板速度有点慢，TLE，这里只贴出小数据的代码。

代码


#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7+5;ll gcd_(ll a, ll b)
{
    return b ==0? a : gcd_(b, a % b);
}
ll a[maxn],ans[maxn],b[maxn];
map<int,int> mp;
int main()
{
    int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){
    mp.clear();int m,n;scanf("%d%d",&m,&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);int pos=-1;for(int i=2;i<=n;i++){
    if(a[i-1]!=a[i]){
    ans[i]=__gcd(a[i-1],a[i]);pos=i;break;}}if(pos==-1) for(int i=1;i<=n+1;i++) ans[i]=sqrt(a[1]);else{
    for(int i=pos-1;i>=1;i--) ans[i]=a[i]/ans[i+1];for(int i=pos+1;i<=n+1;i++) ans[i]=a[i-1]/ans[i-1];}for(int i=1;i<=n+1;i++) b[i]=ans[i];sort(b+1,b+2+n);int cnt=-1;for(int i=1;i<=n+1;i++){
    if(b[i]!=b[i-1]) ++cnt;mp[b[i]]=cnt;}printf("Case #%d: ",cas);for(int i=1;i<=n+1;i++){
    printf("%c",char(mp[ans[i]]+'A'));}printf("\n");}return 0;
}