用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

【有道难题资格赛一】解题报告

发表时间:2010-05-31 11:11:34  浏览(1850) 评论(2)


A:另类的异或

【题目叙述】
对于普通的异或,其实是二进制的无进位的加法
这里我们定义一种另类的异或A op B, op是一个仅由^组成的字符串,如果op中包含n个^,那么A op B表示A和B之间进行n+1进制的无进位的加法。
下图展示了3 ^ 5 和 4 ^^ 5的计算过程
  srcoiblog

【输入】
第一行有一个正整数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
6

【算法分析】
直接纯模拟,统计每组数据中包含的"^"的个数N,将每组输入的两个数字转化成N+1进制数,然后每位做加法,加完后模(N+1),最后将结果转化回10进制数。

【我的代码】
var i,j,k,l,m,n,p,q,r,t:longint;
    num1,num2,ans:array[0..100] of longint;
    oup:longint;
    c:char;

begin
  readln(t);
  for i:=1 to t do
  begin
    p:=0;
    while true do
    begin
      read(c);
      if (c in ['0'..'9']) then p:=p*10+ord(c)-48
      else break;
    end;
    k:=1;
    while true do
    begin
      read(c);
      if (c='^') then break;
    end;
    while true do
    begin
      read(c);
      inc(k);
      if (c<>'^') then break;
    end;
    q:=0;
    while not eoln do
    begin
      read(c);
      if (c in ['0'..'9']) then q:=q*10+ord(c)-48;
    end;
    readln;
    m:=0;
    fillchar(num1,sizeof(num1),0);
    fillchar(num2,sizeof(num2),0);
    fillchar(ans,sizeof(ans),0);
    while (p>0) do
    begin
      inc(m);
      num1[m]:=p mod k;
      p:=p div k;
    end;
    m:=0;
    while (q>0) do
    begin
      inc(m);
      num2[m]:=q mod k;
      q:=q div k;
    end;
    for j:=1 to 100 do ans[j]:=(num1[j]+num2[j]) mod k;
    for l:=100 downto 1 do if (ans[l]>0) then break;
    oup:=0;
    for j:=l downto 1 do oup:=oup*k+ans[j];
    writeln(oup);
  end;
end.

【现场总结】
诡异地RE两次,怀疑是有多个空格,于是改变了读入方式,导致读入巨长无比。


B:有道搜索框

【题目叙述】
在有道搜索框中,当输入一个或者多个字符时,搜索框会出现一定数量的提示,如下图所示:
srcoiblog
现在给你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

【算法分析】
用一个字母树(Trie)存储所有给定的单词。然后,每读入一个询问就试着在Trie中查找。如果在没有查找完全改询问前已经出现了空儿子,则输出该单词本身,否则,记录下Trie树中询问的末端位置,并从这个位置开始在Trie中DFS,直到按字典序输出了8个单词或者遍历整个以询问到达的末端位置为根Trie子树完毕。输出格式注意处理。

【我的代码】
var i,j,k,l,m,n,p,q,r,t,many,left:longint;
    trie:array[0..200000,'a'..'z'] of longint;
    have:array[0..200000] of boolean;
    s:string;
    can:boolean;

procedure ins_trie(s:string);
var g:longint;
begin
  p:=0;
  for g:=1 to length(s) do
    if (trie[p,s[g]]>0) then p:=trie[p,s[g]]
    else
    begin
      inc(many);
      trie[p,s[g]]:=many;
      p:=many;
    end;
  have[p]:=true;
end;

procedure dfs(s:string;x:longint);
var c:char;
begin
  if (left=0) then exit;
  if (have[x]) then 
  begin
    if (left<8) then write(' ');
    write(s);dec(left);
  end;
  for c:='a' to 'z' do
    if trie[x,c]>0 then dfs(s+c,trie[x,c]);
end;

begin
  readln(n);
  many:=0;
  fillchar(trie,sizeof(trie),0);
  for i:=1 to n do 
  begin
    readln(s);
    ins_trie(s);
  end;
  readln(q);
  for i:=1 to q do
  begin
    readln(s);
    p:=0;can:=true;
    for j:=1 to length(s) do
      if (trie[p,s[j]]=0) then
      begin
        can:=false;break;
      end else p:=trie[p,s[j]];
    if (not can) then writeln(s) else
    begin
      left:=8;
      dfs(s,p);writeln;
    end;
  end;
end.

【现场总结】
一次AC


C:最大和子序列

【题目叙述】
给一个整数数组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

【算法分析】
这是一道动态规划问题。基于环的动态规划一般比较繁琐。从数据范围分析,对于每组数据,需要O(N)的算法。
我们把环打开,变成1..N的一个数字链。考虑我们选出的两段数,有两种情况:1、两段都不跨头尾;2、有一段跨越头尾。如下图,图中A、B表示我们选出的两段数。
srcoiblog
我们可以用O(N)的时间求出数串的前缀和、后缀和。i位置的前缀和left[i]表示a1+a2+...+ai,后缀和right[i]表示ai+a(i+1)+a(i+2)+...+an。同时,我们处理前缀和最大值、最小值和后缀和最大值、最小值。i位置的前缀和最大值leftmax[i]表示left[1]、left[2]...left[i]里面的最大值,i位置的后缀和最小值rightmin[i]表示right[i]、right[i+1]...right[n]里面的最小值。其他两个的含义显然了。然后,我们处理前缀最大盈利和后缀最大盈利。i位置的盈利定义为left[i]-leftmin[i-1],也就是选择了一段不包含a1的数字的最大和。那么,i位置的前缀最大盈利就是1,2...i的盈利中的最大值。后缀最大盈利的定义也显而易见了。这几个数组每个只要O(N)的时间就能求出,不明白的看程序就可以了。
为什么求这些东西呢?每个数组都是有用的。下面进入程序主体。
回到刚才说到的两种情况。情况1中的A段,可能是a1到某个位置的数字和,也可能不包括a1。如果包括a1,则是一个前缀和,否则是两个前缀和的差,即右端位置的前缀和-(左端位置-1)的前缀和。注意,缀合是面向位置的。假设我们枚举了A、B两段的分界点i,并规定A段的右端点不超过i,B段左端点必须大于i。这样就保证了两段不重叠。那么,我们这里要贪心了。对于A段包括a1,我们显然选择一个i位置的最大前缀leftmax[i];而若不包含a1,我们选择leftdt[i]。这两者中的较大值就是A段。类似的,B段应该是rightmax[i+1]和rightdt[i+1]中的较大值。
情况2麻烦一些。我们枚举B段的右端点和A段处于数列末端一半的左端点的分界点i,要求B右端点为i,末端的A段左端点不能左于i+1。那么,末端的A段比较好做,直接是rightmax[i+1]。而左边的这个就要麻烦一些。分析一下,实际上左边这部分=B的右端点位置的前缀-(B的左端点-1)的前缀+头端半段A的右端点的前缀。在循环i的时候,B的右端点位置的前缀已经确定了,那么,我们就要让-(B的左端点-1)的前缀+头端半段A的右端点的前缀最大。这个东西,我们需要再开一个数组进行预处理。我们定义i位置的最大反盈利为-left[i]+leftmax[i-1]。而i位置的最大反盈利最大值leftdt2[i]为1、2...i这些位置的最大反盈利中的最大值。这个也可以O(N)DP出来。那么,问题迎刃而解。那个比较恶心的部分的值就是left[i]+leftdt2[i-1]啦。
好了,思路就是这样。确实很繁琐,不太好理解。恕我表达能力有限,如果还不明白直接QQ问我吧。

【我的代码】
var i,j,k,l,m,n,p,q,r,s,t,dt:longint;
    a:array[0..50001] of longint;
    left,right,leftmax,rightmax,leftmin,rightmin,leftdt,rightdt:array[0..50001] of longint;
    ans:longint;

function more(x,y:longint):longint;
begin
  if (x>y) then exit(x) else exit(y);
end;

function less(x,y:longint):longint;
begin
  if (x<y) then exit(x) else exit(y);
end;

begin
  read(t);
  for dt:=1 to t do
  begin
    read(n);
    fillchar(left,sizeof(left),0);
    fillchar(right,sizeof(right),0);
    leftmax[0]:=-maxlongint;leftmin[0]:=maxlongint;
    rightmax[n+1]:=-maxlongint;rightmin[n+1]:=maxlongint;
    for i:=1 to n do read(a[i]);
    for i:=1 to n do 
    begin
      left[i]:=left[i-1]+a[i];
      leftmax[i]:=leftmax[i-1];
      if (left[i]>leftmax[i]) then leftmax[i]:=left[i];
      leftmin[i]:=leftmin[i-1];
      if (left[i]<leftmin[i]) then leftmin[i]:=left[i];
    end;
    for i:=n downto 1 do
    begin
      right[i]:=right[i+1]+a[i];
      rightmax[i]:=rightmax[i+1];
      if (right[i]>rightmax[i]) then rightmax[i]:=right[i];
      rightmin[i]:=rightmin[i+1];
      if (right[i]<rightmin[i]) then rightmin[i]:=right[i];
    end;
    ans:=-maxlongint;
    for i:=1 to n-1 do 
      if (leftmax[i]+rightmax[i+1]>ans) then ans:=leftmax[i]+rightmax[i+1];
      
    leftdt[1]:=left[1];
    for i:=2 to n do
    begin
      leftdt[i]:=leftdt[i-1];
      if (left[i]-leftmin[i-1]>leftdt[i]) then leftdt[i]:=left[i]-leftmin[i-1];
    end;
    rightdt[n]:=right[n];
    for i:=n-1 downto 1 do
    begin
      rightdt[i]:=rightdt[i+1];
      if (right[i]-rightmin[i+1]>rightdt[i]) then rightdt[i]:=right[i]-rightmin[i+1];
    end;
    for i:=1 to n-1 do
    begin
      p:=more(left[i],leftdt[i]);
      q:=more(right[i+1],rightdt[i+1]);
      if (p+q>ans) then ans:=p+q;
    end;
    
    leftdt[1]:=-left[1];
    for i:=2 to n do
      leftdt[i]:=more(leftdt[i-1],-left[i]+leftmax[i-1]);
    for i:=2 to n-1 do
      ans:=more(ans,left[i]+leftdt[i-1]+rightmax[i+1]);
    
    writeln(ans);
  end;
end.

【现场总结】
一次AC

【整场比赛总揽】
分数:1000
罚时:03:19:25
排名:122

网友评论:

user1  Guest 于 2010-06-03 23:51:33 说:回复
第三题有难度
user2  Admin 于 2010-06-05 19:00:31 说:回复
回复Guest:暂时不支持留言超链接功能。

Guest 发表评论