kufaaa

好吧。 我现在还在纠结 是tow 还是two。

4. 双栈排序

(twostack.pas/c/cpp)

【问题描述】

Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。

操作a

如果输入序列不为空，将第一个元素压入栈S1

操作b

如果栈S1不为空，将S1栈顶元素弹出至输出序列

操作c

如果输入序列不为空，将第一个元素压入栈S2

操作d

如果栈S2不为空，将S2栈顶元素弹出至输出序列

如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>

当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。

【输入】

输入文件twostack.in的第一行是一个整数n。

第二行有n个用空格隔开的正整数，构成一个1~n的排列。

【输出】

输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

【输入输出样例1】

twostack.in twostack.out

4

1 3 2 4 a b a a b b a b

【输入输出样例2】

twostack.in twostack.out

4

2 3 4 1 0

【输入输出样例3】

twostack.in twostack.out

3

2 3 1 a c a b b d

【限制】

30%的数据满足： n<=10

50%的数据满足： n<=50

100%的数据满足： n<=1000 

双栈排序题目大意就是用两个栈完成排序，要求输出字典序最小的or 0；

这道题就要运用到栈的知识了，我们应该先考虑什么情况下一定要将两个数放在不同的栈。否则我们可以一直使用第一个栈，这样可以使字典序最小。

当序列中两个数a[i],a[j] （i<j)满足存在一个a[k]使得i<j<k and (a[k]<a[i]<a[j]) 这时候 a[i],a[j]不能放在同一个栈里。 Read More…

【潜伏者 spy】

这道题我能说什么呢。

只要小心注意点就行了，比如 解密的26个字母都要有；要注意是映射。

一样不会做的自己找豆腐。

【Hankson的趣味题 son】

这道题还真是趣味了。

这道题有代码长的，也有代码短的。

最容易想到的是枚举的。 这个就不说了，省得抹杀了趣味。

再来解法就多了。

先说说我的方法吧。

lcm(x,b0)=x*b0/(gcd(x,b0))=b1;

如果我们直接枚举gcd(x,b0），x:=b1/b0*j；再判断gcd(x,a0)是否等于a1；

接下来来考虑枚举的范围。显然只要从b0的约数里去找。因为一个数的约数是“对称”的，所以我们枚举的范围只要定在 j:1>>trunc(sqrt(b0))之间，另一个则为b0 div j。但有一种情况要注意，就是j*j刚刚好等于b0 这时候只能算一个。

var a0,a1,b0,b1,p,ans,i,n,j,q:longint;

function gcd(a,b:longint):longint;
var m,n,c:longint;
begin
 m:=a; n:=b;
 if a<b then begin m:=b; n:=a; end;
 c:=m mod n;
 while c<>0 do
  begin
   m:=n;
   n:=c;
   c:=m mod n;
  end;
 exit(n);
end;
begin
  read(n);
  for i:=1 to n do
   begin
    read(a0,a1,b0,b1);
    ans:=0;
   for j:=1 to trunc(sqrt(b0)) do
    begin
      if b0 mod j=0 then
       begin
        p:=b1 div b0*j;
        if (gcd(p,a0)=a1) and (p*b0=gcd(p,b0)*b1)  then   inc(ans);

        q:=b1 div j;
        if (j*j<>b0) and (gcd(q,a0)=a1) and (q*b0=gcd(q,b0)*b1) then inc(ans);
       end;
     end;
    writeln(ans);
   end;
end.

这个代码比较短，还有一个代码比较长的方法，需要因式分解。

我比较懒，没打。 如果想知道的话可以到谢图图的blog http://xietutu.com/archives/388 

Read More…

【引水入城 flow】 这道题有两问。

 我是一问一问做的。

第一问：能否使最后一行的每个点都到达。

 用广搜吧~ 从第一行的每一个点出发,这个时间复杂度是O（n*m），因为走过的点显然不需要走第二遍。 如果不能到的话，就直接枚举最后一行有几个没被标记过的，输出就好了。

第二问：最少需要几个蓄水站。

这个就神奇了，我们可以把它转化成狗狗大绝杀。或者校门前的树。 我们能够保证第一行的每一个蓄水站在最后一行能到达的沙漠一定是一段连续的区间（因为我们已经确定第一问结果为0）。现在我们只需要知道，对于最上面的每一个蓄水站能到达的沙漠区间。

我用的方法还是广搜，我是先从最后一行到第一行进行广搜的。先从从左到右，显然当前这个点能够到达第一行的某个没有被到过的点，就一定是第一行这个店的区间左边界。右边同理。

剩下的就是 至少用几个区间能覆盖1..m 的问题了 。

我是采用贪心、每次都找左边界满足条件（小于等于上一个右边界+1），且右边界最大的区间，更新右边界。

秀秀代码吧，有点长，但是还算清晰。 Read More…

话说题解这种东西网上一打一打的。我纯粹是打打酱油。

【机器翻译 translate】

水题。 不会做的自己找豆腐。

var  p,m,n,now,i,x,ans:longint;
    f,a:array[0..1005]of longint;

begin
  read(m,n);
  now:=0; p:=0;
  for i:=1 to n do
   begin
    read(x);
    if f[x]<>0 then continue;
    inc(ans);
    if now-p>=m then
     begin
      inc(p);
      f[a[p]]:=0;
     end;
     inc(now);
     a[now]:=x;
     f[x]:=1;
    end;
   write(ans);

end.

&nbsp;

【乌龟棋 tortoise】

这道题 我是用动规做的。 也是一道很简单的题。

因为只有四种卡片，所以直接用f(i,j,k,q)表示卡片1、2、3、4 四种卡片用的张数。

方程为：

F(I,j,k,q):=max(f(i-1,j,k,q),f(i,j-1.k,q),f(I,j,k-1,q),f(I,j,k,q-1))

+a(i+j*2+k*3+q*4);

var f:array[-1..40,-1..40,-1..40,-1..40]of longint;
    a:array[0..350]of longint;
    c:array[1..4]of longint;
    x,y,z,p,u,n,m,i:longint;
function max(a,b,c,d:longint):longint;
begin
 if a>b then max:=a else max:=b;
 if c>max then max:=c;
 if d>max then max:=d;
end;
begin

  read(n,m);
  for i:=1 to n do read(a[i]);
  for i:=1 to m do
   begin
    read(x);
    inc(c[x]);
   end;
  for x:=0 to c[1] do
   for y:=0 to c[2] do
    for z:=0 to c[3] do
     for p:=0 to c[4] do
      begin
       if (x=0)and (y=0) and (z=0) and (p=0) then continue;
       f[x,y,z,p]:=max(f[x-1,y,z,p],f[x,y-1,z,p],f[x,y,z-1,p],f[x,y,z,p-1])+a[x+y*2+z*3+p*4+1];
      end;
   write(f1,c[2],c[3],c[4]]+a[1]);
end.

【关押罪犯 prison】

这道题 有两种做法 Read More…