有道难题资格赛(1).

 

参与人数
4849
提交次数
25797

 

分数   名次

1000  1~239

700   ~265

...

400         ~ 450

 

编号 标题 分数 通过率 通过人数 提交次数
A 另类的异或 150 29% 3405 11947
B 有道搜索框 300 13% 1439 11065
C 最大和子序列 550 10% 274 2785

A:另类的异或

时间限制:
1000ms
内存限制:
131072kB
描述
对于普通的异或,其实是二进制的无进位的加法
这里我们定义一种另类的异或A op B, op是一个仅由^组成的字符串,如果op中包含n个^,那么A op B表示A和B之间进行n+1进制的无进位的加法。
下图展示了3 ^ 5 和 4 ^^ 5的计算过程
输入
第一行有一个正整数T, 表示下面共有T组测试数据。
接下来T行,每行有一组测试数据,是由空格隔开的三个部分组成:
A B C
A和C是两个十进制整数,B是一个字符串,由n个^组成
1 <= T <= 100, 0<=A,B<2^30, 1<=n<=1000
输出
每个测试数据输出一行,包含一个数字,即该数据的结果,用十进制表示。
样例输入
2
3 ^ 5
4 ^^ 5
样例输出
6
代码
#include <stdio.h>
#include 
<string.h>
#include 
<memory.h>

//将数字从十进制转换到制定进制
//input:
//n: 要转换的数字(十进制)
//m: 要转换的进制
//output:
//a,l: 要求进制的数字,和位数,[0]为最低位
void split(int n, int m,int a[],int &l)
{
    l
=0;
    
for(;n;n/=m)
    {
        a[l
++]=n%m;
    }
}

void print(int a[],int l)
{
    
for(int i=0;i<l;i++)
        printf(
"%d ",a[i]);
    printf(
"\n");
}

//将指定进制的数字做xor运算
//input:
//a,n1,b,n2
//m
//output:
//c
int xor(int const a[],int n1, int  const b[],int n2, int m, int c[])
{
    
int k=n1>n2?n1:n2;
    
for(int i=0;i<k;i++)
    {
        c[i]
=(a[i]+b[i])%m;
    }
    
return k;
}

int A[50];
int nA=0;
int nB=0;
int B[50];
int nC=0;
int C[50];

//将数字从指定进制转换到十进制
int merge(int const a[],int n1, int m)
{
    
int r=0;
    
for(int i=0;i<n1;i++)
    {
        r 
=r*m+a[n1-1-i];
    }
    
return r;
}

int main(int argc, char *argv[])
{
    
int T;
    scanf(
"%d",&T);
    
while(T--)
    {
        
int a,b=0,m;
        
char s[1000+1];
        scanf(
"%d %s %d",&a,s,&b);
        m
=strlen(s)+1;
        
//printf("a %d b %d m %d\n",a,b,m);
        memset(A,0,sizeof(A));
        memset(B,
0,sizeof(B));
        memset(C,
0,sizeof(C));
        split(a,m,A,nA);
        split(b,m,B,nB);
        
//print(A,nA);
        
//print(B,nB);
        nC=xor(A,nA,B,nB,m,C);
        
//print(C,nC);
        int r=merge(C,nC,m);
        printf(
"%d\n",r);
    }

    
return 0;
}



B:有道搜索框

时间限制:
1000ms
内存限制:
131072kB
描述
在有道搜索框中,当输入一个或者多个字符时,搜索框会出现一定数量的提示,如下图所示:


现在给你N个单词和一些查询,请输出提示结果,为了简化这个问题,只需要输出以查询词为前缀的并且按字典序排列的最前面的8个单词,如果符合要求的单词一个也没有请只输出当前查询词。
输入
第一行是一个正整数N,表示词表中有N个单词。
接下来有N行,每行都有一个单词,注意词表中的单词可能有重复,请忽略掉重复单词。所有的单词都由小写字母组成。
接下来的一行有一个正整数Q,表示接下来有Q个查询。
接下来Q行,每行有一个单词,表示一个查询词,所有的查询词也都是由小写字母组成,并且所有的单词以及查询的长度都不超过20,且都不为空
其中:N<=10000,Q<=10000
输出
对于每个查询,输出一行,按顺序输出该查询词的提示结果,用空格隔开。
样例输入
10
a
ab
hello
that
those
dict
youdao
world
your
dictionary
6
bob
d
dict
dicti
yo
z
样例输出
bob
dict dictionary
dict dictionary
dictionary
youdao your
z
代码
// test.cpp : Defines the entry point for the console application.
//

#include 
"stdafx.h"

#include 
<stdio.h>
#include 
<string.h>
#include 
<memory.h>
#include 
<assert.h>

struct node
{
    
char end;
    
long child[26];        //idx of its child
    node()
        :end(
0)
    {
        memset(child,
0,sizeof(child));
    }
}nodes[
10000*20];
long n=0;

void insert(char const s[])
{
    
long idx=0;
    
for(int i=0,m=strlen(s);i<m;i++)
    {
        
long *pidx=&nodes[idx].child[s[i]-'a'];
        
if(*pidx==0)
        {
            idx
=*pidx=++n;
        }
        
else
            idx
=*pidx;
        
if(i==m-1)
            nodes[idx].end
=1;
    }
}

char str[20];
int nStr=0;
void print(long idx)
{
    
if(nodes[idx].end)
    {
        str[nStr]
=0;
        printf(
"%s ",str);
    }
    
    
for(int i=0;i<26;i++)
    {
        
long idx2=nodes[idx].child[i];
        
if(idx2)
        {
            str[nStr
++]=i+'a';
            print(idx2);
            nStr
--;
        }
    }
}

void srch(char const s[])
{
    
bool find=true;
    
long idx=0;
    
for(int i=0,m=strlen(s);i<m;i++)
    {
        idx
=nodes[idx].child[s[i]-'a'];
        
if(!idx)
        {
            find 
= false;
            
break;
        }
    }

    
if(!find)
        printf(
"%s\n",s);
    
else
    {
        strcpy(str,s);
        nStr
=strlen(s);
        print(idx);
        printf(
"\n");
    }
}

int main(int argc, char *argv[])
{
    
int N;
    scanf(
"%d",&N);
    
while(N--)
    {
        
char s[20];
        scanf(
"%s",s);
        insert(s);
    }

    
//srch("");

    scanf(
"%d",&N);
    
while(N--)
    {
        
char s[20];
        scanf(
"%s",s);
        srch(s);
    }

    
return 0;
}



C:最大和子序列

时间限制:
1000ms
内存限制:
131072kB
描述
给一个整数数组A={a1,a2,…an}, 将这个数组首尾相接连成一个环状,它的一个子序列是指这个数组连续的一段,比如a2,a3…ak,或者an,a1…ai。请从这个环上选取两个不重叠的非空子序列,使这两个子序列中的所有数字之和最大。
在三个样例中分别选取的子序列是:
样例一: {a1} {a3}
样例二: {a1} {a3}
样例三: {a5,a1} {a3}
输入
输入的第一行包含一个正整数T(1<=T<=40),表示有T组测试数据。
接下来每个测试数据包含两行,第一行是一个正整数n(2<=n<=50000), 第二行是用空格隔开的数组A的n个数,依次为a1,a2,…an (|ai|<=10000)。
输出
每组数据输出一行,包含一个数,即所求的这两个子序列的元素之和。
样例输入
3
3
1 -1 0
4
1 -1 1 -1
5
1 -1 1 -1 1
样例输出
1
2
3
提示

Powered by Jekyll and Theme by solid

本站总访问量