先上一张最终的结果:

Screenshot 2019-04-08 at 08.03.06.png

这次资格赛总的来说表现的还不错,可惜第一题没仔细读题处理大数据出了问题。

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
*/

标签: none

添加新评论