jzoj 1568. 【普及模拟】石子游戏

lzusa 发布于 2019-03-19 1 次阅读


 

题目描述

你在桌子上放白和黑两种颜色的石子,第i个石子放在左边第i个位置,一共放了N个石子,当你放第i个石子必须遵循以下规则:

1.当i是奇数时:直接放在左数第i个位置上;

2.当i是偶数时:如果第i个石子和第i-1个石子颜色相同,直接放在第i个位置上;否则把当前最右边的连续的颜色相同的石子全部用相反颜色的石子取代,然后在第i个位置上放下石子i。

例如,假设桌子上现状是:○○●●○○○(○代表白石子,●代表黑石子)

如果第8个石子是白色,因为它和第7个石子颜色相同,就直接放在最右边就可以了,桌面上变成:○○●●○○○○;

如果第8个石子是黑的,因为和第7个颜色不同,就先把右边连续的3个白石子用黑石子代替,然后再放下第8个石子,变成:○○●●●●●●。

写一个程序,给你每个石子的颜色,输出最终桌面上白石子的数量。

 

输入

第一行输入一个整数N(1<=N<=100,000),接下来N行每行一个数C,表示N个石子的颜色,0表示白色,1表示黑色。

输出

输出一个整数表示最终白石子的数量。
首先,这道题数据很大,暴力模拟只有30分,我们把同一个类型的数合并在一起,但是要很注意细节问题
var
  a,b:array[-100..100000] of longint;
  i,j,k,n,m,s,x:longint;
begin
  assign(input,'stone.in'); reset(input);
 assign(output,'stone.out'); rewrite(output);
  readln(n);
  a[0]:=2;
  b[0]:=2;
  j:=1;k:=1;
  readln(m);
  a[1]:=m;
  b[1]:=1;
  for i:=2 to n do
    begin
       readln(m);
      if i mod 2=1 then
       begin
       if m=a[j]
       then begin
             b[k]:=b[k]+1;
            end
       else begin
              j:=j+1;
              a[j]:=m;
              k:=k+1;
              b[k]:=b[k]+1;
            end;
       end
      else begin
             if a[j]<>m
               then begin
                      a[j]:=m;
                      if a[j]=a[j-1]
                        then begin
                               j:=j-1;
                               b[k-1]:=b[k]+b[k-1]+1;
                               b[k]:=0;
                               k:=k-1;
                             end
                      else
                      begin
                      b[k]:=b[k]+1;
                      end;
                    end
               else begin
                      b[k]:=b[k]+1;
                    end;
           end;
    end;

  for i:=1 to k do
    if a[i]=0 then s:=s+b[i];
  writeln(s);

 close(input);
close(output);
end.

 

 

]]>