Qualification Round 2019 - code jam 解题报告
先上一张最终的结果：
这次资格赛总的来说表现的还不错，可惜第一题没仔细读题处理大数据出了问题。
Foregone Solution
- 题目链接
Foregone Solution - 题意
将一个数字分成两个数字相加，使得这两个数字任何一位均不为4。其中有1分该数据不超过1e100，其他数据不超过1e9。 - 分析
将数字逐位处理，如果遇到4拆分成两个部分，如果不是4直接给某一个答案加上这一位即可。 - 代码
（本段代码未特别处理大数据）
#include <bits/stdc++.h>
using namespace std;
void slove(int n){
int temp = 1;
int ans1=0,ans2=;
while (n){
if (n%10==4){
ans1+=2*temp;
ans2+=2*temp;
}
else ans1+=n%10*temp;
n/=10;
temp*=10;
}
cout<<ans1<<' '<<ans2;
return ;
}
int main(){
int t;
cin>>t;
for (int i=1;i<=t;i++){
int n;
cin>>n;
cout<<"Case #"<<i<<": ";
slove(n);
cout<<endl;
}
}
You Can Go Your Own Way
- 题目链接
You Can Go Your Own Way - 题意
在N*N的网格中，每次只能向右或者向下走，当前已经规划出一条路径，请你设计出一个没有任意一段完全相同的路径（没有任意一段完全相同指对于已知路径中任意的A->B，设计的路径也不能有A->B，但是A与B本身均是可以到达的） - 分析
乍一看要设计出很复杂的递归回溯算法什么的，但是分析后发现，只要将读入数据的E与S对调即可。在对角线之外的情况路线完全分离故可行，在对角线之中的情况仅有：交错与途径同一点组成十字两种情况，故该种做法可行。 - 代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
for (int i=1;i<=t;i++){
int nn;
cin>>nn;
string s;
cin>>s;
printf("Case #%d: ",i);
for (auto i:s){
if (i=='S')printf("E");
else printf("S");
}
printf("\n");
}
}
Cryptopangrams
- 题目链接
Cryptopangrams - 题意
本题描述了一种加密方法。首先将26个字母映射到26个不同的素数（规模不超过1e100）上，其中A对于的素数最小，Z对应的素数最大，以此类推。然后将要加密的文本两两相邻的字母所对应的素数相乘，对于长度为k的字符串，可以生成长度为k-1的数字序列。现给你这个数字序列，求还原后的字符串，保证还原后的字符串26个字母至少各出现一次。 - 分析
最开始被两个素数相乘这个条件给蒙骗了，以为需要将大数分解成两个素数，经思考后发现对于序列中相邻的两个数实际上为(x*y)和(y*z)因此只需任意一对数的最大公约数后即可求出该处对应的素数，之后即可递推出所有位置进而处理出对应关系。但是还有一点需要注意：不能直接选取最开始的两个数字，它应付不了此类情况：ABA...这样求出的最大公约数并不是B而是AB。因此需要找到序列中任何一对不相同的数字来求最大公约数。 - 代码
import java.math.BigInteger;
import java.util.Scanner;
public class Solution {
private static BigInteger _0=BigInteger.valueOf(0);
private static BigInteger gcd(BigInteger a, BigInteger b){
if (b.compareTo(_0)==0){
return a;
}
else {
return gcd(b,a.mod(b));
}
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int t;
t=scanner.nextInt();
for (int ii = 1; ii <= t; ii++) {
scanner.nextBigInteger();
int l=scanner.nextInt();
System.out.printf("Case #%d: ",ii);
BigInteger []input=new BigInteger[200];
BigInteger []ans=new BigInteger[200];
for (int i=0;i<l;i++){
input[i]=scanner.nextBigInteger();
}
int pos = 0;
for (int i=0;i<l;i++){
if (input[i].compareTo(input[i+1])!=0){
ans[i+1]=gcd(input[i],input[i+1]);
pos=i+1;
break;
}
}
for (int i=pos-1;i>=0;i--){
ans[i]=input[i].divide(ans[i+1]);
}
for (int i=pos+1;i<=l;i++){
ans[i]=input[i-1].divide(ans[i-1]);
}
BigInteger []hashtable=new BigInteger[30];
for (int i=0;i<=l;i++){
for (int j=0;j<26;j++){
if (hashtable[j]==null){
hashtable[j]=ans[i];
break;
}
else {
final int i1 = hashtable[j].compareTo(ans[i]);
if (i1 ==0){
break;
}
else if (i1 >0){
for (int k=25;k>j;k--){
hashtable[k]=hashtable[k-1];
}
hashtable[j]=ans[i];
break;
}
}
}
if (hashtable[25]!=null)break;
}
for (int i=0;i<=l;i++){
for (int j=0;j<26;j++){
if (hashtable[j].compareTo(ans[i])==0){
System.out.print((char)(j+(int)'A'));
break;
}
}
}
System.out.print("\n");
}
scanner.close();
}
}
Dat Bae
- 题目链接
Dat Bae - 题目大意
本题为交互题。每组数据指定N,B,F三个数字，允许发送长度为N的01串，将返回去除B位，总长度为N-B的01串，求出丢失的是哪些位。其中N不超过1024，B不超过15，F最小为5。 - 分析
表面上看起来5次机会最多处理25种情况，而本题情况显然最大有1024取15种，远远大于25，但实际上这也是本题的障眼法。首先第一次依次输出16个1，16个0相间排列的询问，可以将处理1024长度的字符串分割成处理长度16的字符串。即使15个缺失位全部在同一区间内，长度16的1或0也可以将其分割开。之后输出8个1，8个0相间排列的询问，将原本长度本应为16的区间分成两部分处理，判断前8位缺失多少位，后8位缺失多少位，以此类推。最终通过16，8，4，2，1个连续01相间排列的串刚好共5次即可得到最终缺失的位数。
#include <bits/stdc++.h>
using namespace std;
void generate(int n,int l,char *a){
int t=0,pos=0;
while (pos!=n){
if (pos/l%2) a[pos++]='0';
else a[pos++]='1';
}
a[pos]=0;
}
string s[5];
void slove(string str,int ll,int l,int len,int now){
if (str.length()==0){
for (int i=0;i<len;i++){
cout<<ll+i<<' ';
}
}
else if (len==str.length()){
return ;
}
else if (now==0){
if (str[0]=='0')cout<<ll<<' ';
else cout<<ll+1<<' ';
}
else if (str[str.length()-1]=='1'){
int minn=min(1<<now,len);
slove(s[now-1].substr(l,str.length()),ll,l,minn,now-1);
slove("",ll+(1<<now),l+str.length(),len-minn,now-1);
}
else {
for (int i=0;i<str.length();i++){
if (str[i]=='0'){
slove(s[now-1].substr(l,i),ll,l,1<<now,now-1);
slove(s[now-1].substr(l+i,str.length()-i),ll+(1<<now),l+i,len-(1<<now),now-1);
break;
}
}
}
}
int main(){
int t;
cin>>t;
while (t--){
int n,b,f;
cin>>n>>b>>f;
char a[1100];
for (int k=4;k>=0;--k){
generate(n,1<<k,a);
cout<<a<<endl;
fflush;
cin>>s[k];
}
int pre=0;
int t=0;
int tot=0;
for (int i=1;i<s[4].size();i++){
if (s[4][i]!=s[4][i-1]){
slove(s[3].substr(pre,i-pre),tot,pre,16,3);
pre=i;
tot+=16;
}
}
slove (s[3].substr(pre),tot,pre,n-b-pre+(b-(tot-pre)),3);
cout<<endl;
fflush;
cin>>n;
if (n==-1)break;
}
}
/*
以下为参考测试数据
3
10 2 10
11111111
11111110
11100001
10011001
01010101
1
5 2 10
111
111
110
101
011
1
32 8 10
111111111111000000000000
111100000000111111110000
000011110000111100001111
110011001100110011001100
101010101010101010101010
1
ans:
0 3
0 9
0 1 2 3 28 29 30 31
*/