CDQZ_Training 2012524 词编码

题目描述地址：http://cdqz.openjudge.cn/noip/1009/

摘要：

一个发送机可以通过一条隧道发送一些以二进制代码组成的单词。，在其尽头的接收机可以使用特殊技术恢复到最初的单词。每个单词最初都由0和1组成。所有的单词最初长上簦都为n(4≤N ≤1000)。当穿过隧道之后单词可能发生以下几种情况之一：

(1)任意(一个)0被1取代

(2)任意(一个)符号被删除

(3)一个符号(0或1)被插入到任何位置

(4)不改变

我们知道最初的单词都具有以下性质：有1的位置号的总和是N+1的倍数，或者是0。

【input】

N和转换后的单词，每个单词占一行。单词数不大于2001．不会有其它任何东西，除了一些空格与空行，

【Output】

你的程序应该打印输出原始序列的词，注意换行。

若有多解，操作4优先，不行则按操作1，2,3优先。同一操作，按操作位置最先的优先。同一操作，按操作位置最先的优先(从左到右数起l，2,3，…N)，还有操作2时，被删数列，先在被删数列添0，不行再添l。

如果没答案输出-1

【Sample input】

0000

011

1011

11011

【Sample Output】

0000

0110

1001

1111

很久以前做这道题的时候就是纯裸的模拟，N^2的复杂度，果断T了两个点

然后这次做…………倒是想到了怎么优化降低复杂度，但问题是当时二了，没看到-1…………果断爆零

其实这个优化很简单的，就是开一个num[i]的数组，表示第i个位置的字符及其后面有多少个1，这样在判断当前字符被删掉或当前字符前面加上一个0或1之后是否符合题意的复杂度就由O(n)降到了O(1)，然后这道题就A掉了…………

这道题需要的就是这个优化，然后就是耐心…………本人弱菜，周五一次，今天又一次，都是调了很久才调通的…………WA了无数

不废话了，上代码

View Code

const
  maxn=1001;
var
  n:longint;
  str:ansistring;
function sum(str:ansistring):longint;
var
  i,s:longint;
begin
  s:=0;
  for i:=1 to length(str) do
    if str[i]='1' then
      inc(s,i);
  exit(s);
end;
procedure main(str:ansistring);
var
  i,s,sum1:longint;
  num:array[0..maxn]of longint;
begin
  s:=sum(str);
  if length(str)=n then
    if s mod (n+1)=0 then
      begin
        writeln(str);
        exit
      end
    else
      if str[s mod (n+1)]='1' then
        begin
          str[s mod (n+1)]:='0';
          writeln(str);
          exit
        end
      else
        begin
          writeln('-1');
          exit
        end;
  sum1:=0;
  num[length(str)+1]:=0;
  for i:=length(str) downto 0 do
    begin
      if str[i]='1' then
        inc(sum1);
      num[i]:=sum1
    end;
  if length(str)=n+1 then
    for i:=1 to length(str) do
      begin
        if ((s-num[i]) mod (n+1)=0) and (str[i]='0') then
          begin
            delete(str,i,1);
            writeln(str);
            exit
          end;
        if ((s-num[i]-i+1) mod (n+1)=0) and (str[i]='1') then
          begin
            delete(str,i,1);
            writeln(str);
            exit
          end;
      end;
  if length(str)=n-1 then
    for i:=1 to length(str)+1 do
      begin
        if (s+num[i]) mod (n+1)=0 then
          begin
            insert('0',str,i);
            writeln(str);
            exit
          end;
        if (s+num[i]+i) mod (n+1)=0 then
          begin
            insert('1',str,i);
            writeln(str);
            exit
          end
      end;
  writeln('-1')
end;
begin
  assign(input,'word.in');reset(input);
  assign(output,'word.out');rewrite(output);
  readln(n);
  while true do
    begin
      readln(str);
      if str='' then
        break
      else
        main(str)
    end;
  close(input);close(output)
end.